Collective Navigation

In order to make the bacterial search algorithm useful in areas larger than the limitations of the e-puck's audio sensory capabilities, we proposed that a collective navigation strategy could be implemented that utilised other mobile agents as beacons throughout the environment. By creating a traversable structure in the environment that is rooted at the charging platform, a robot could traverse it and begin the recharging process when required. The process of Diffusion Limited Aggregation was identified as a suitable way of configuring the agents for this task in a decentralised way.

A computer simulated DLA structure
(Image courtesy paulbourke.net/fractals/dla)

Diffusion Limited Aggregation

Diffusion Limited Aggregation is a naturally occuring process that results in a randomly grown rooted tree structure (snow flakes are an example). The process can be simulated by the following algorithm:

A DLA-based collective navigation strategy

A collective navigation strategy was developed that built upon the bacterial search developed for the single robot. The strategy can be briefly described as:

With some additional logic to determine causality of the alert and release states of the swarm, the result is a completely self-managed and distributed recharging strategy. The following video demonstrates the navigation strategy implemented in a swarm of 60 virtual e-puck robots in a square environment.

The simulation software used was the Aseba Framework, with the audio simulation capabilities ported from the Swis2D plugin for Webots.