Multistage Particle Swarm Optimization for Heterogeneous Multipoint Dynamic Aggregation

摘要

Multipoint dynamic aggregation (MPDA) is a multirobot task allocation problem, which requires the collaborative scheduling of multiple robots to complete time-varying tasks distributed on a map. Most existing studies consider the scenarios with homogeneous robots and tasks. To model the application scenarios where different types of robots are required, we propose a heterogeneous MPDA problem, which incorporates different types of robots and tasks with dependency. Correspondingly, a novel metaheuristic algorithm called multistage particle swarm optimization is designed and consists of two parts: 1) a multistage strategy and 2) a specially designed particle swarm optimization (PSO) algorithm. The multistage strategy imposes temporary constraints to force cooperation between robots, which can reduce and smoothen the search space. The proposed PSO contains a mixed updating mechanism consisting of a continuous velocity updating rule and a discrete position updating rule, which is effective for updating the permutation-based solutions of MPDA. The experiments on a newly designed benchmark test set show that the proposed algorithm is more effective and efficient than the state-of-the-art methods.