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

doi:10.13973/j.cnki.robot.190463

摘要
图/表
参考文献
相关文章 (15)

全文: PDF (618 KB) HTML ( ) 输出: BibTeX \| EndNote (RIS)
引用本文:
马小陆, 梅宏. 基于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.

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

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	马小陆
	梅宏

关键词 ：移动机器人, 路径规划, 最优路径, 蚁群系统算法, 跳点搜索算法

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.

Key words： mobile robot path planning optimal path ant colony system (ACS) algorithm jump point search (JPS) algorithm

收稿日期: 2019-08-30 录用日期: 2020-02-17

TP242.6

基金资助:国家自然科学基金（51574004）；安徽高校自然科学研究项目（KJ2019A0065）

通讯作者: 马小陆,77578249@qq.com E-mail: 77578249@qq.com

作者简介: 马小陆(1979-),男,博士后,副教授.研究领域:嵌入式系统,V2X,服务机器人路径规划等.
梅宏(1995-),男,硕士生.研究领域:移动机器人路径规划.

链接本文:

https://robot.sia.cn/CN/10.13973/j.cnki.robot.190463 或 https://robot.sia.cn/CN/Y2020/V42/I4/494

[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.