Darwinian swarm exploration under communication constraints: Initial deployment and fault-tolerance assessment

• An autonomous and fault-tolerant initial deployment strategy is presented.
• The initial deployment is carried out based on a hierarchical division.
• A fault-tolerant search to prevent communication network splits is proposed.
• Fault-tolerance is achieved by maintaining a kk-connected MANET.
• Both strategies are evaluated in groups of 18 physical robots.

In most real multi-robot applications, such as search-and-rescue, cooperative robots have to move to complete their tasks while maintaining communication among themselves without the aid of a communication infrastructure. However, initially deploying and ensuring a mobile ad-hoc network in real and complex environments is an arduous task since the strength of the connection between two nodes (i.e., robots) can change rapidly in time or even disappear. An extension of the Particle Swarm Optimization to multi-robot applications has been previously proposed and denoted as Robotic Darwinian PSO (RDPSO). This paper contributes with a further extension of the RDPSO, thus integrating two research aspects: (i) an autonomous, realistic and fault-tolerant initial deployment strategy denoted as Extended Spiral of Theodorus (EST); and (ii) a fault-tolerant distributed search to prevent communication network splits. The exploring agents, denoted as scouts, are autonomously deployed using supporting agents, denoted as rangers. Experimental results with 15 physical scouts and 3 physical rangers show that the algorithm converges to the optimal solution faster and more accurately using the EST approach over the random deployment strategy. Also, a more fault-tolerant strategy clearly influences the time needed to converge to the final solution, but is less susceptible to robot failures.