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:
- Start with a seed at the origin of a lattice
- A second particle is added at a random location far from the origin. The particle randomly walks until it visits a location adjactent to the seed.
- Particles are continuously added in this manner to the lattice, randomly walking until joined to the cluster
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:
- When agent x requires recharge, begin transmitting alert tone
- Alert tone is propogated throughout the swarm, agents begin random walking
- When an assisting agent detects a frequency freqIn >= freqPlatform, stop and begin transmitting freqIn + 1
- Agent x begins performing gradient search on lowest frequency detected >= freqPlatform.
- When platform detects that an agent has boarded it, disable beacon
- When assisting agents detect that freqIn has been disabled, disable output and resume primary task
The simulation software used was the Aseba Framework, with the audio simulation capabilities ported from the Swis2D plugin for Webots.