Mechanism and Convergence Analysis of a Multi-Robot Swarm Approach Based on Natural Selection

M. S. Couceiro, F. M. Martins, R. P. Rocha and N. M. F. Ferreira

Journal of Intelligent and Robotic Systems, 76(2), pp 353-381, Springer, Nov. 2014. DOI: 10.1007/s10846-014-0030-0

Abstract

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.

Full text

You may ask Rui P. Rocha for an electronic copy of this publication’s full text by e-mail:
.

Please select for your message’s subject ‘Requesting Rui Rocha’s electronic copy’ and include on the message’s body your full name, title and affiliation, why do you need to access the publication and the BibTeX information below.

BibTeX

@ARTICLE(Couceiro_et_al_14c,

AUTHOR = "M. S. Couceiro and F. M. Martins and R. P. Rocha and N. M. F. Ferreira",

TITLE = "Mechanism and Convergence Analysis of a Multi-Robot Swarm Approach Based on Natural Selection",

JOURNAL = "Journal of Intelligent and Robotic Systems",

VOLUME = "76",

NUMBER = "2",

YEAR = "2014",

MONTH = "Nov.",

PAGES = "353-381"

)

(top of the page)

Last update: 06/11/2014