Improved Ant Colony Algorithm for Multi-Agent Path Planning in Dynamic Environment

摘要

In order to overcome the shortcomings of original Ant Colony algorithm, such as slow convergence speed and easily falling into the local optimum during solving path planning among multi-agents in dynamic environment, an improved ant colony algorithm is proposed by 1) adjusting the transition probability, 2) adapting the pheromone strength Q value adaptively and introduce the pheromone reduction factor to speed up the algorithm's iterative speed, 3) using the explosive algorithm of the fireworks algorithm to expand the search area to avoid trapping for the deadlock problem. In addition, the collision prediction and path transition evaluation function between Agents are given so as to avoid collisions between multi-agents. The experiment of simulation verified its validity of algorithm in terms of time and iterations.