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, analyze, and optimize a flocking algorithm for e-pucks on the Webots simulator. The algorithm should provide the robots with the ability to 1) avoid obstacles within the arena while retaining the collective formation, and 2) maintain collective formation while two different flocks of robots cross each other moving in opposite directions. The analysis should evaluate the performance and scalability of the algorithm for increasing dimensions of the e-pucks swarm. The second part of this project consist in optimizing the behavior of the robots. For this purpose, an appropriate fitness function has been designed along with an optimization method. There are a number of parameters that shape the navigation behavior and need to be considered by the optimization methods. We are interested in seeing the resulting behavior of the optimized controllers using Particle Swarm Optimization. Evaluation of the project was based on the final performance of the navigation with and without optimization, the 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 implemented controllers uses the Reynolds flocking rules. It works by having a supervisor that knows the position of all the robots in a world and computes a direction vector for each robot. Flocking is achieved as each robot follows its direction vector. The direction is computed in a way that the robots want to come together, while also avoiding collisions. This direction vector is the sum of multiple sub-vectors that ensure flock behavior: Cohesion (moving towards the center of mass of the flock), Dispersion (moving away from other robots), Consistency (moving at the same speed as the flock), and Migration (moving towards an arbitrary point).

An recursive neural network to control the motion control

We utilized unsupervised learning to determine the weights of the proximity sensors of the e-puck. We constructed a recursive neural network comprising of two neurons, each responsible for controlling the speed of a wheel, employing sigmoidal output functions. The inputs consist of the eight proximity sensors (one for each wheel), along with a recursive connection from the neuron's previous output, lateral inhibitions, and two bias factors.

Particle Swarm Optimization

Particle swarm optimization (PSO) is a metaheuristic technique that can be utilized to search for candidate solutions in a large combinatorial space. Additionally, it can be adapted to be noise-resistant. PSO has been employed to optimize the Braitenberg parameters for the Reynolds controller, as well as for the Kikker controller. We have implemented PSO in a noise-resistant manner to achieve a more accurate approximation of the fitness function. Moreover, we have implemented it in a distributed manner to reduce 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