基于JPS策略的ACS移动机器人全局路径规划

针对蚁群系统（ACS）算法收敛速度慢、易陷入局部最优、路径转折点数量过多等问题，提出了一种基于跳点搜索（JPS）策略的ACS全局路径规划算法．该算法在迭代前加入一只特殊蚂蚁，利用方向因子引导该蚂蚁始终朝着目标方向前进，并查询是否存在最简路径；在蚂蚁查询下一个节点时，利用JPS算法思想舍去大部分不需要计算的节点．最后，为验证该方法的有效性，使用不同规格的栅格地图进行了仿真实验，仿真结果表明，改进的ACS算法相比于ACS算法，收敛速度加快、收敛时间缩短，且路径更优．最后将算法应用到实际的基于机器人操作系统（ROS）的移动机器人导航实验中，实验结果表明，改进的ACS算法能够有效地解决移动机器人全局路径规划问题，且能明显提升机器人全局路径规划的效率．

The Global Path Planning of Ant Colony System Mobile Robot Based onJump Point Search Strategy

For the problems of ant colony system (ACS) algorithm such as slow convergence speed, falling into local optimum easily and too many turning points, an ACS global path planning algorithm based on jump point search (JPS) strategy is proposed. The algorithm adds a special ant before iteration, uses the direction factor to guide the ant towards the target direction, and queries whether there is the simplest path. When ants query the next node, JPS algorithm is used to eliminate most of the nodes that don't need to be calculated. Finally, simulation experiments are carried out with different grid maps in order to verify the effectiveness of the proposed method. The simulation results show that compared with ACS algorithm, the improved ACS algorithm has faster convergence speed and shorter convergence time, and its path is better. Finally, the algorithm is applied to the actual navigation experiment of mobile robot based on robot operating system (ROS). The experimental results show that the improved ACS algorithm can effectively solve the global path planning problem of mobile robot and significantly improve the efficiency of global path planning of robot.