Optimized flocking algorithm for e-pucks GithubPaper

Project about flocking algorithms using small robots. Multidisciplinary team with a computer engineer and a mechanical engineer.
C, Webots

The goal of the project is to implement, test, analyse, and optimize a flocking algorithm for e-pucks on the Webots simulator. The algorithm should provide the robots with the ability 1) to avoid obstacles within the arena while retaining the collective formation, and 2) to maintain collective formation while two different flocks of robots cross each other moving in opposite directions. The analysis should evaluate the performance and the scalability of the algorithm for increasing dimensions of the e- pucks swarm. The second part of this project would be on optimizing the behavior of the robots. For this purpose an appropriate fitness function should be designed along using an optimization method. There are a number of parameters which shape the navigation behavior that need to be considered by the optimization methods. We are interested to see the resulting behavior of the optimized controllers using Particle Swarm Optimization. Evaluation of the projects would be based on the final performance of the navigation with and without optimization, effectiveness of the designed fitness function, and the discussion that the students make on the comparison of the two steps.


The Project

Flocking behaviour

One of the controller implemented uses the Reynolds flocking rules. It works by having an entity that knows the position of all the robots in a world and compute, for each robot, a direction vector. Flocking is achieved by each robot following its direction vector. The direction is computed such that the robots want to get together. At the same time, they should also not collide. This direction vector is the sum of multiples sub vectors that ensure the flock behaviour: Cohesion: move toward the centre of mass of the flock; Dispersion: move away from other robots; Consistency: move at the same speed as the flock; Migration: move toward an arbitrary point.

Advanced model for the motion control

We have used unsupervised learning in order to learn the weights of the proximity sensors of the e-puck. We developed a recurrent neural network of two neurons, one for each wheel speed, with sigmoidal output functions. The inputs are the eight proximity sensors (one for each wheel), as well as a recurrent recursive connection from the previous output of the neuron, lateral inhibitions and the two bias.

Particle Swarm Optimization

Particle swarm optimization (PSO) is meta-heuristic technique which can be used to search candidate solutions in large combinatorial space and can also be adapted to be noise-resistant. It has been used to optimize the Braitenberg parameters for the Reynolds controller as well as those for the Kikker controller. We have implemented PSO in a noise-resistant manner, in order to have better approximation of the fitness function, but also in a distributed way to decrease the training time.


Miscellaneous

Type Course project
Degree M.Sc. EPFL, 1st semester
Course Distributed intelligent systems
Duration ~50 hours
Supervisor Dr. Inaki Navarro Oiza
Co-developer Damien Doy, Martin d'Hoffschmidt