基于双向搜索策略的改进蚁群路径规划算法

Improved Ant Colony Path Planning Algorithm Based on Bidirectional Search Strategy

针对在多障碍物地形中将传统蚁群算法运用在移动机器人路径规划问题上出现收敛速度慢,容易陷入局部最优,易于陷入死锁等一系列问题,提出了一种改进蚁群算法。在传统蚁群算法的基础上,根据蚂蚁周围可行栅格距离目标点的远近,自适应地调整启发函数,加快算法收敛速度;针对传统蚁群所用的回退和死亡策略,提出了一种最优路径保留策略,提高了算法性能;使用两组不同种类的蚂蚁分别从起始点和目标点进行双向搜索的方法来构建最优路径,进一步提升了算法的搜索效率。实验表明该方法与传统的蚁群算法相比减少了搜索时间,降低了迭代次数,明显提高了算法的寻优效率。

An improved ant colony algorithm is proposed to overcome a series of problems, such us slow convergence speed and easy to fall into local optimal or deadlock phenomenon, which occur on the condition that the traditional ant colony algorithm is applied into mobile robot path planning in multi-obstacle terrain. On the basis of the traditional ant colony algorithm, the heuristic function is adjusted adaptively to accelerate the convergence speed according to the distance between the feasible grid and target point around the ant;An optimal path reservation strategy is proposed to improve the performance of the algorithm in terms of the rollback and death strategies used by the traditional ant colony algorithm;An bidirectional search method applied with two different kinds of ants from the starting point and the target point respectively is advanced to build the optimal path and increase the search efficiency. Experiments demonstrate that compared with the traditional ant colony algorithm, improved method reduces the search time and the number of iterations, thus significantly improving the efficiency of the algorithm.