An Improved Ant Colony Optimization Algorithm for Multi-robot Path Planning under Complex Tasks
Shilong Yuan, Zhou He, Pengyang He, Wei Tang · 2024
In this work, we study path planning for multi-robot systems under complex tasks, which are given by global high-level specifications represented as Boolean formulas. This paper proposes a path planning method based on an improved ant colony optimization algorithm to compute the trajectory of each robot, ensuring that the total trajectories of the team fulfill the Boolean specifications while minimizing the total motion cost. The algorithm introduces a neighborhood search mechanism to enhance the neighborhood search capability. In addition, it incorporates an elite strategy to improve the qualities of the offspring populations and algorithm convergence speed. Simulation results show that compared with the Boolean specification-based multi-robot system path planning method using simulated annealing, the improved algorithm reduces the convergence time and minimizes the cost of the team. The solution time is shorter and the solution quality is higher, demonstrating the effectiveness of the proposed algorithm in solving the path planning problem for complex multi-robot tasks.