基于多级视野自适应蚁群算法的移动机器人路径规划

Mobile Robot Path Planning Based on Multi-level Field of View Adaptive Ant Colony Algorithm

摘要:

针对传统蚁群算法(Ant colony optimization，ACO)在应用于移动机器人路径规划时存在优化能力差，易于死锁，搜索效率低等问题，提出一种多级视野自适应蚁群(Multilevel field of view adaptive ant colony optimization，MLFVAACO)算法。首先在ACO的基础上依次扩展2级视野使得规划出的路径更加平滑；其次设计了自适应全局初始信息素更新策略，既避免了蚂蚁在算法初期出现盲目搜索现象又加强了蚂蚁选择可选区域的指导作用；然后对算法迭代过程中的死锁蚂蚁进行优化，以提高蚁群的利用率和增加搜索解的多样性；最后对蚂蚁的状态转移规则进行改进来避免蚂蚁陷入局部最优解。通过仿真选取MLFVAACO算法的最优参数，在2种不同复杂程度的格栅地图中分别与传统ACO算法、改进ACO算法和图搜索算法进行对比，验证MLFVAACO算法的可行性和有效性。仿真结果表明，在简单与复杂环境中，MLFVAACO算法相较于传统ACO算法最优路径分别缩短12.74%和4.38%，路径转折点分别减少50%和63.16%，蚂蚁利用率分别提升99.99%和99.95%，搜索效率分别提高60.14%和62.17%；相较于改进ACO算法和图搜索算法，MLFVAACO算法能够规划出路径平滑度更好的最短路径，同时搜索解的质量也更好。这充分验证了MLFVAACO算法在应用于移动机器人路径规划时具有出色的综合性能。

关键词:移动机器人;全局路径规划;蚁群算法;多级视野;死锁

Abstract:

Aiming at the problems of poor optimization ability, easy deadlock, and low search efficiency of the traditional ant colony optimization (ACO) when applied to mobile robot path planning, a multilevel field of view adaptive ant colony optimization (MLFVAACO) algorithm was proposed. Firstly, on the basis of ACO, the two levels field of view was expanded sequentially to make the planned path smooth. Secondly, an adaptive global initial pheromone update strategy was designed, which not only avoided the blind search phenomenon of ants in the early stage of the algorithm but also strengthened the guiding role of ants in selecting optional areas. Then the deadlock ants in the algorithm iteration process were optimized to improve the utilization of the ant colony and increase the diversity of search solutions. Finally, the state transition rule of ants was improved to prevent ants from falling into the local optimal solution. The optimal parameters of the MLFVAACO algorithm were selected through simulation analysis, and the feasibility and effectiveness of the MLFVAACO algorithm were verified by comparing it with the traditional ACO algorithm, the improved ACO algorithms, and the graph search algorithms, respectively, in two kinds of grid maps with different levels of complexity. The simulation results showed that in simple and complex environments, compared with the traditional ACO algorithm, the optimal path of the MLFVAACO algorithm was shortened by 12.74% and 4.38%, respectively, the turning points of the path were reduced by 50% and 63.16%, respectively, the ant utilization rate was increased by 99.99% and 99.95%, respectively, and the search efficiency was increased by 60.14% and 62.17%, respectively. Compared with the improved ACO algorithms and the graph search algorithms, MLFVAACO algorithm can plan the shortest path with better path smoothness, while the quality of the search solutions was also better. This fully validated the excellent performance of MLFVAACO algorithm when applied to mobile robot path planning.

Key words:mobile robot;global path planning;ant colony algorithm;multi-level field of view;deadlock