马小陆, 梅宏. 基于JPS策略的ACS移动机器人全局路径规划[J]. 机器人, 2020, 42(4): 494-502.DOI: 10.13973/j.cnki.robot.190463.
MA Xiaolu, MEI Hong. The Global Path Planning of Ant Colony System Mobile Robot Based onJump Point Search Strategy. ROBOT, 2020, 42(4): 494-502. DOI: 10.13973/j.cnki.robot.190463.
Abstract: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.
[1] 黄辰,费继友,刘洋,等.基于动态反馈A* 蚁群算法的平滑路径规划方法[J].农业机械学报,2017,48(4):34-40. Huang C, Fei J Y, Liu Y, et al. Smooth path planning method based on dynamic feedback A* ant colony algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2017, 48(4):34-40. [2] 史恩秀,陈敏敏,李俊,等.基于蚁群算法的移动机器人全局路径规划方法研究[J].农业机械学报,2014,45(6):53-57. Shi E X, Chen M M, Li J, et al. Research on method of global path-planning for mobile robot based on ant-colony algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2014, 45(6):53-57. [3] 刘二辉,姚锡凡,蓝宏宇,等.基于改进遗传算法的自动导引小车动态路径规划及其实现[J].计算机集成制造系统,2018,24(6):1455-1467. Liu E H, Yao X F, Lan H Y, et al. AGV dynamic path planning based on improved genetic algorithm and its implementation[J]. Computer Integrated Manufacturing Systems, 2018, 24(6):1455-1467. [4] Lee J,Kim D W. An effective initialization method for genetic algorithm-based robot path planning using a directed acyclic graph[J]. Information Sciences, 2016, 332:1-18. [5] Petrović M, Vuković N, Mitić M, et al. Integration of process planning and scheduling using chaotic particle swarm optimization algorithm[J]. Expert Systems with Applications, 2016, 64:569-588. [6] Dorigo M, Maniezzo V, Colorni A. Ant system:Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 1996, 26(1):29-41. [7] Dorigo M, Gambardella L M. Ant colony system:A cooperative learning approach to the traveling salesman problem[J]. IEEE Transitions on Evolutionary Computation, 1997, 1(1):53-66. [8] 朱艳,游晓明,刘升,等.基于改进蚁群算法的机器人路径规划问题研究[J].计算机工程与应用,2018,54(19):135-140. Zhu Y, You X M, Liu S, et al. Research on path planning of mobile robot based on improved ant colony system algorithm[J]. Computer Engineering and Applications, 2018, 54(19):135-140. [9] 李娟,游晓明,刘升,等.动态混沌蚁群系统及其在机器人路径规划中的应用[J].计算机应用,2018,38(1):126-131. Li J, You X M, Liu S, et al. Dynamic chaotic ant colony system and its application in robot path planning[J]. Journal of Computer Applications, 2018, 38(1):126-131. [10] 王志中.基于改进蚁群算法的移动机器人路径规划研究[J].机械设计与制造,2018,323(1):248-250. Wang Z Z. Path planning for mobile robot based on improved ant colony algorithm[J]. Machinery Design & Manufacture, 2018, 323(1):248-250. [11] 刘建华,杨建国,刘华平,等.基于势场蚁群算法的移动机器人全局路径规划方法[J].农业机械学报,2015,46(9):18-27. Liu J H, Yang J G, Liu H P, et al. Robot global path planning based on ant colony optimization with artificial potential field[J]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(9):18-27. [12] 张原艺,章政,王泉.基于改进多步长蚁群算法的机器人路径规划[J].计算机工程与设计,2018,39(12):237-242,274. Zhang Y Y, Zhang Z, Wang Q. Robot path planning based on improved multi-step ant colony algorithm[J]. Computer Engineering and Design, 2018, 39(12):237-242, 274. [13] 赵晓,王铮,黄程侃,等.基于改进A* 算法的移动机器人路径规划[J].机器人,2018,40(6):137-144. Zhao X, Wang Z, Huang C K, et al. Mobile robot path planning based on an improved A* algorithm[J]. Robot, 2018, 40(6):137-144. [14] 夏小云,周育人.蚁群优化算法的理论研究进展[J].智能系统学报,2016,11(1):27-36. Xia X Y, Zhou Y R. Advances in theoretical research of ant colony optimization[J]. CAAI Transactions on Intelligent Systems, 2016, 11(1):27-36. [15] 邱磊.利用跳点搜索算法加速A* 寻路[J].兰州理工大学学报,2015,41(3):102-107. Qiu L. Speed-up of A* pathfinding with jump point search algorithm[J]. Journal of Lanzhou University of Technology, 2015, 41(3):102-107.