Mechanism and Convergence Analysis of a Multi-Robot Swarm Approach Based on Natural Selection
Couceiro, M. Couceiro
; Rocha, R. P.
; Ferreira, N. M.
Journal of Intelligent and Robotic Systems Vol. 75, Nº 1, pp. 1 - 31, June, 2014.
ISSN (print): 0921-0296
ISSN (online): 0921-0296
Journal Impact Factor: 1,178 (in 2014)
Digital Object Identifier: 10.1007/s10846-014-0030-0
The Darwinian Particle Swarm Optimization (DPSO) is an evolutionary algorithm that extends the Particle Swarm Optimization (PSO) using natural selection, or survival-of-the-fittest, to enhance the ability to escape from local optima. An extension of the DPSO to multi-robot applications has been recently proposed and denoted as Robotic Darwinian PSO (RDPSO), benefiting from the dynamical partitioning of the whole population of robots. Therefore, the RDPSO decreases the amount of required information exchange among robots, and is scalable to large populations of robots. This paper presents a stability analysis of the RDPSO to better understand the relationship between the algorithm parameters and the robot’s convergence. Moreover, the analysis of the RDPSO is further extended for real robot constraints (e.g., robot dynamics, obstacles and communication constraints) and experimental assessment with physical robots. The optimal parameters are evaluated in groups of physical robots and a larger population of simulated mobile robots for different target distributions within larger scenarios. Experimental results show that robots are able to converge regardless of the RDPSO parameters within the defined attraction domain. However, a more conservative parametrization presents a significant influence on the convergence time. To further evaluate the herein proposed approach, the RDPSO is further compared with four state-of-the-art swarm robotic alternatives under simulation. It is observed that the RDPSO algorithm provably converges to the optimal solution faster and more accurately than the other approaches.
Keywords swarm robotics · natural selection · convergence analysis · robot constraints · parameterization · source localization
Mathematics Subject Classification (2000) 39A30 · 70E60 · 65L20