A Decentralized Hybrid Method for Goal Assignment in Multi-Robot Exploration

摘要

Many multi-robot exploration (MRE) methods generate navigation goals so that the robots can observe unknown areas. The assignment of the goals to the robots greatly affects the exploration efficiency. This paper addresses the open-path multi-depot multiple traveling salesmen problem (OP-MmTSP) derived from multi-robot goal assignment (MGA) by presenting a decentralized method: the consensus-based decentralized discrete particle swarm optimization (CD-DPSO) algorithm. CDDPSO is a fully decentralized algorithm that assigns the computational tasks of a population-based metaheuristic algorithm to individual robots and enables them to collaborate. First, a discrete particle swarm optimization (DPSO) algorithm is proposed to resolve the OP-MmTSP. Second, the velocity update formula of DPSO is revised, inspired by the idea of the discrete time consensus algorithm that the particle swarms of all robots converge to the same solution via local communication. Finally, a variable neighborhood descent (VND) method consisting of two local search heuristics designed for min-max OP-MmTSP is adopted to improve the selected particles, which makes the CDDPSO a hybrid method that benefits from global search and local search. We applied two well-known auction-based task allocation algorithms to min-max OP-MmTSP and compared them to CDDPSO via numerical experiments. CDDPSO as a hybrid approach can usually find a better solution.