A Map-Coverage Algorithm Basing on Particle Swarm Optimization

Abstract

With the development of multi-robots technology, with multi-robots, large scale swarms are often applied to improve the efficiency and robustness of coverage process. The traditional methods basing on negotiation and task allocation often meet their bottleneck in this scenario of large scale swarm task for the dramatic increase of communication and computation. In this paper we propose a novel algorithm basing on the Particle Swarm Optimization (PSO) model. In this algorithm, a virtual pheromone based communication mechanism is adopted to decrease the communication cost and optimize the cooperation between nodes. For the nodes, there are two phases, exploration and exploitation, with different indicators in the PSO model. By switching between these two phases, the swarm completes the task of map coverage. A series of experiments on simulator is carried out and proves the convergence and excellent scalability of our algorithm. By optimizing some parameter in the PSO model with the simulator, the efficiency of map-coverage is further improved.