基于改进A<sup>*</sup>算法的移动机器人路径规划

doi:10.13973/j.cnki.robot.170591

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

全文: PDF (986 KB) HTML ( ) 输出: BibTeX \| EndNote (RIS)
引用本文:
赵晓, 王铮, 黄程侃, 赵燕伟. 基于改进A^算法的移动机器人路径规划[J]. 机器人, 2018, 40(6): 903-910.DOI: 10.13973/j.cnki.robot.170591. ZHAO Xiao, WANG Zheng, HUANG Chengkan, ZHAO Yanwei. Mobile Robot Path Planning Based on an Improved A^ Algorithm. ROBOT, 2018, 40(6): 903-910. DOI: 10.13973/j.cnki.robot.170591.

摘要为了解决较大场景下A^*寻路算法存在的内存开销大、计算时间长等问题，本文在A^*算法的基础上，结合跳点搜索算法，提出一种改进的A^*算法．该算法通过筛选跳点进行扩展，直到生成最终路径，扩展过程中使用跳点代替A^*算法中大量可能被添加到OpenList和ClosedList的不必要节点，从而减少计算量．为了验证改进A^*算法的有效性，分别在不同尺寸的2维栅格地图中进行仿真，仿真结果表明，相比A^*算法，改进A^*算法在寻路过程中扩展更少的节点，寻路速度更快，且加速效果随环境地图的增大更加明显．最后将改进A^*算法应用于移动机器人Turtlebot2进行对比实验．实验结果表明，在生成相同路径的基础上，改进A^*算法的寻路速度较A^*算法提高了约200%，能够满足移动机器人路径规划的要求．

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	赵晓
	王铮
	黄程侃
	赵燕伟

关键词 ：移动机器人, 路径规划, A^*算法, 跳点搜索

Abstract：Aiming at the problems of A^* algorithm in the large scene, such as large memory overhead and long computation time, an improved A^* algorithm is proposed based on A^* algorithm and jump point search algorithm. The algorithm expands by selecting jump points until the final path is generated. During the expansion process, a lot of unnecessary nodes in A^* algorithm which are added to OpenList and ClosedList can be replaced by jump points to reduce computation. In order to prove the validity of the improved A^* algorithm, the simulation is carried out in 2D grid map of different sizes. The simulation result shows that the improved A^* algorithm expands fewer nodes in the pathfinding process, and the pathfinding speed is faster. The acceleration effect becomes more apparent with the increase of environment map. Finally, the improved A^* algorithm is implemented on the mobile robot Turtlebot2 to conduct comparative experiments. The experimental result shows that the improved A^* algorithm can speed up by about 200% compared with the A^* algorithm when generating the same path, and it can meet the requirements of path planning for mobile robots.

Key words： mobile robot path planning A^* algorithm jump point search

收稿日期: 2017-10-27 录用日期: 2018-03-23

TP242.6

基金资助:国家自然科学基金（61572438）；浙江省公益技术应用研究计划（2017C31072）

通讯作者: 赵燕伟,zyw@zjut.edu.cn E-mail: zyw@zjut.edu.cn

作者简介: 赵晓(1993-),男,硕士生.研究领域:移动机器人路径规划,视觉SLAM
王铮(1986-),男,博士.研究领域:智能系统与智能自动化技术
黄程侃(1994-),男,硕士生.研究领域:移动机器人路径规划.

链接本文:

https://robot.sia.cn/CN/10.13973/j.cnki.robot.170591 或 https://robot.sia.cn/CN/Y2018/V40/I6/903

[1] 曲道奎,杜振军,徐殿国,等.移动机器人路径规划方法研究[J].机器人,2008,30(2):97-101,106.Qu D K, Du Z J, Xu D G, et al. Research on path planning for a mobile robot[J]. Robot, 2008, 30(2):97-101,106.
[2] 王殿君.基于改进A^* 算法的室内移动机器人路径规划[J].清华大学学报:自然科学版,2012,52(8):1085-1089.Wang D J. Indoor mobile-robot path planning based on an improved A^* algorithm[J]. Journal of Tsinghua University:Science and Technology, 2012, 52(08):1085-1089.
[3] Jeddisaravi K, Alitappeh R J, Pimenta L C A, et al. Multi-objective approach for robot motion planning in search tasks[J]. Applied Intelligence, 2016, 45(2):305-321.
[4] 刘一松,魏宁,孙亚民.基于栅格法的虚拟人快速路径规划[J].计算机工程与设计,2008(5):1229-1230,1267.Liu Y S, Wei N, Sun Y M. Path planning algorithm based on grid method for virtual human[J]. Computer Engineering and Design, 2008(5):1229-1230,1267.
[5] Bakdi A, Hentout A, Boutami H, et al. Optimal path planning and execution for mobile robots using genetic algorithm and adaptive fuzzy-logic control[J]. Robotics and Autonomous Systems, 2017, 89(1):95-109.
[6] 刘建华,杨建国,刘华平,等.基于势场蚁群算法的移动机器人全局路径规划方法[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 of Agricultural Machinery, 2015, 46(9):18-27.
[7] 朱大奇,颜明重.移动机器人路径规划技术综述[J].控制与决策,2010,25(7):961-967.Zhu D Q, Yan M Z. Survey on technology of mobile robot path planning[J]. Control and Decision, 2010, 25(7):961-967.
[8] Dijkstra E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1):269-271.
[9] Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2):100-107.
[10] Stentz A. Optimal and efficient path planning for partially-known environments[C]//IEEE International Conference on Robotics and Automation. Piscataway, USA:IEEE, 2002:3310-3317.
[11] Koenig S, Likhachev M. Fast replanning for navigation in unknown terrain[J]. IEEE Transactions on Robotics, 2005, 21(3):354-363.
[12] 辛煜,梁华为,杜明博,等.一种可搜索无限个邻域的改进A^* 算法[J].机器人,2014,36(5):627-633.Xin Y, Liang H W, Du M B, et al. An improved A^* algorithm for searching infinite neighbourhoods[J]. Robot, 2014, 36(5):627-633.
[13] Korf R E. Depth-first iterative-deepening:An optimal admissible tree search[J]. Artificial Intelligence, 1985, 27(1):97-109.
[14] Botea A, Müller M, Schaeffer J. Near optimal hierarchical path-finding[J]. Journal of Game Development, 2004, 1:7-28.
[15] Goldberg A V, Harrelson C. Computing the shortest path:A^* search meets graph theory[C]//Annual ACM-SIAM Symposium on Discrete Algorithms. New York, USA:ACM, 2005:156-165.
[16] Sturtevant N R, Felner A, Barrer M, et al. Memory-based heuristics for explicit state spaces[C]//International Joint Conference on Artificial Intelligence. USA:International Joint Conferences on Artificial Intelligence, 2009:609-614.
[17] Harabor D, Grastien A. The JPS pathfinding system[C]//5th Annual Symposium on Combinatorial Search. Menlo Park, USA:AAAI, 2012:207-208
[18] Korf R E. Real-time heuristic search[J]. Artificial Intelligence, 1990, 42(2/3):189-211.
[19] Harabor D, Grastien A. Online graph pruning for pathfinding on grid maps[C]//25th AAAI Conference on Artificial Intelligence. Menlo Park, USA:AAAI, 2011:1114-1119.