改进RRT*-Smart算法的移动机器人全局路径规划研究

doi:10.3778/j.issn.1002-8331.2409-0254

摘要/Abstract

摘要： 针对RRT*算法在移动机器人路径规划时搜索效率低、迭代次数多以及搜索路径不平滑等问题，提出一种改进RRT*-Smart的移动机器人全局路径规划算法。基于传统RRT*-Smart算法引入A*算法代价函数和启发式思想，引导随机采样点集中分布于潜在最优路径附近，减少无效搜索；采用椭圆采样空间策略精确控制采样范围，提高搜索效率；利用Cantmull-Rom样条插值曲线对初始路径进行平滑处理，得到更为安全平滑的最终路径。基于Python和ROS仿真平台开展实验验证，改进RRT*-Smart算法在搜索效率、行走时间以及路径平滑度方面均有显著提升。

关键词: 路径规划, 改进RRT*-Smart, 启发式思想, 椭圆采样空间, Cantmull-Rom样条插值, ROS仿真平台

Abstract: An improved RRT*-Smart global path planning algorithm for mobile robots is proposed to address the issues of low search efficiency, excessive iteration times, and uneven search paths encountered in the traditional RRT* algorithm. Based upon the traditional RRT*-Smart algorithm, the A* algorithm’s cost function and heuristic thinking are introduced to steer random sampling points towards the vicinity of potential optimal paths, thereby minimizing ineffective searches. By adopting an elliptical sampling space strategy, the sampling range is precisely managed to enhance search efficiency. Additionally, a Cantmull-Rom spline interpolation curve is utilized to smoothen the initial path, resulting in a safer and smoother final path. Experiments conducted using Python and the ROS simulation platform confirm that the improved RRT*-Smart algorithm exhibits notable enhancements in search efficiency, travel time, and path smoothness.

Key words: path planning, improved RRT*-Smart, heuristic ideas, elliptic sampling space, Cantmull-Rom spline interpolation, ROS simulation platforms

赖荣燊, 窦磊, 巫志勇, 孙帅. 改进RRT*-Smart算法的移动机器人全局路径规划研究[J]. 计算机工程与应用, 2025, 61(13): 378-388.

LAI Rongshen, DOU Lei, WU Zhiyong, SUN Shuai. Research on Global Path Planning for Mobile Robots with Improved RRT*-Smart Algorithm[J]. Computer Engineering and Applications, 2025, 61(13): 378-388.

参考文献

[1] 毛文平, 李帅永, 谢现乐, 等. 基于自适应机制改进蚁群算法的移动机器人全局路径规划[J]. 控制与决策, 2023, 38(9): 2520-2528.
MAO W P, LI S Y, XIE X L, et al. Global path planning of mobile robot based on adaptive mechanism improved ant colony algorithm[J]. Control and Decision, 2023, 38(9): 2520-2528.
[2] 何丽, 宁子豪, 袁亮, 等. 社会交互空间下基于Social_DWA算法的服务机器人动态路径规划[J/OL]. 西安交通大学学报: 1-10 (2024-01-23) [2024-09-16]. http://kns.cnki.net/kcms/detail/61.1069.T.20240122.1359.004.html.
HE L, NING Z H, YUAN L, et al. Dynamic path planning of service robot based on Social_DWA in social interaction space[J]. Journal of Xi’an Jiaotong University: 1-10 (2024-01-23) [2024-06-16]. http://kns.cnki.net/kcms/detail/61.1069.T.20240122.1359.004.html.
[3] 魏武, 韩进, 李艳杰, 等. 基于双树Quick-RRT算法的移动机器人路径规划[J]. 华南理工大学学报(自然科学版), 2021, 49(7): 51-58.
WEI W, HAN J, LI Y J, et al. Path planning of mobile robots based on dual-tree quick-RRT algorithm[J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(7): 51-58.
[4] 崔炜, 朱发证. 机器人导航的路径规划算法研究综述[J]. 计算机工程与应用, 2023, 59(19): 10-20.
CUI W, ZHU F Z. Review of path planning algorithms for robot navigation[J]. Computer Engineering and Applications, 2023, 59(19): 10-20.
[5] SIHITE E, MOTTIS B, GHANEM P, et al. Efficient path planning and tracking for multi-modal legged-aerial locom- otion using integrated probabilistic road maps (PRM) and reference governors (RG)[C]//Proceedings of the 2022 IEEE 61st Conference on Decision and Control. Piscataway: IEEE, 2022: 764-770.
[6] CHEN G L, SHENG W H, LI Y Q, et al. Humanoid robot portrait drawing based on deep learning techniques and efficient path planning[J]. Arabian Journal for Science and Engineering, 2022, 47(8): 9459-9470.
[7] TAHERI E, FERDOWSI M H, DANESH M. Fuzzy greedy RRT path planning algorithm in a complex configuration space[J]. International Journal of Control, Automation and Systems, 2018, 16(6): 3026-3035.
[8] MOHAMMED H, ROMDHANE L, JARADAT M A. RRT*N: an efficient approach to path planning in 3D for Static and Dynamic Environments[J]. Advanced Robotics, 2021, 35(3/4): 168-180.
[9] CHOON K T, WAI K W, THU S M. Vision based indoor surveillance patrol robot using extended dijkstra algorithm in path planning[J]. Journal of Engineering Technology and Applied Physics, 2021, 3(2): 21-28.
[10] FRANSEN K, VAN EEKELEN J. Efficient path planning for automated guided vehicles using A* (Astar) algorithm incorporating turning costs in search heuristic[J]. International Journal of Production Research, 2023, 61(3): 707-725.
[11] LAI R S, WU Z Y, LIU X G, et al. Fusion algorithm of the improved A* algorithm and segmented Bézier curves for the path planning of mobile robots[J]. Sustainability, 2023, 15(3): 2483.
[12] 龙厚云, 李光, 谭薪兴, 等. 融合A*的改进RRT机械臂路径规划[J]. 计算机工程与应用, 2024, 60(4): 366-374.
LONG H Y, LI G, TAN X X, et al. Path planning of robotic arm based on improved RRT algorithm combined with A* [J]. Computer Engineering and Applications, 2024, 60(4): 366-374.
[13] KARAMAN S, FRAZZOLI E. Incremental sampling-based algorithms for a class of pursuit-evasion games[M]. Berlin, Heidelberg: Springer, 2011: 71-87.
[14] 许万, 杨晔, 余磊涛, 等. 一种基于改进RRT*的全局路径规划算法[J]. 控制与决策, 2022, 37(4): 829-838.
XU W, YANG Y, YU L T, et al. A global path planning algorithm based on improved RRT*[J]. Control and Decision, 2022, 37(4): 829-838.
[15] KUFFNER J J, LAVALLE S M. RRT-connect: an efficient approach to single-query path planning[C]//Proceedings of the IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2002: 995-1001.
[16] 王海芳, 张瑶, 朱亚锟, 等. 基于改进双向RRT*的移动机器人路径规划算法[J]. 东北大学学报(自然科学版), 2021, 42(8): 1065-1070.
WANG H F, ZHANG Y, ZHU Y K, et al. Mobile robot path planning based on improved bidirectional RRT*[J]. Journal of Northeastern University (Natural Science), 2021, 42(8): 1065-1070.
[17] 罗征志, 韩怡可, 张鑫, 等. 改进RRT-Connect与DWA算法的巡检机器人路径规划研究[J]. 计算机工程与应用, 2024, 60(15): 344-354.
LUO Z Z, HAN Y K, ZHANG X, et al. Research on path planning of inspection robot with improved RRT-connect and DWA algorithm[J]. Computer Engineering and Applications, 2024, 60(15): 344-354.
[18] GAMMELL J D, SRINIVASA S S, BARFOOT T D. Informed RRT*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]//Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway: IEEE, 2014: 2997-3004.
[19] NASIR J, ISLAM F, MALIK U, et al. RRT*-SMART: a rapid convergence implementation of RRT[J]. International Journal of Advanced Robotic Systems, 2013, 10(7): 299.
[20] LI Q H, WANG J H, LI H M, et al. HQD-RRT*: a high-quality path planner for mobile robot in dynamic environment[J]. The Journal of China Universities of Posts and Telecommunications, 2022, 29(3): 69-80.
[21] ZHANG Z C, WU H B, ZHOU H, et al. Recovery path planning for autonomous underwater vehicles using constrained Bi-RRT*-smart algorithms[C]//Proceedings of the OCEANS 2023-Limerick. Piscataway: IEEE, 2023: 1-6.
[22] 董璐, 熊爱玲. 基于改进RRT*-Smart的复杂动态环境下的无人艇路径规划[J]. 智能科学与技术学报, 2022, 4(2): 264-276.
DONG L, XIONG A L. Path planning for unmanned surface vehicle in complex dynamic environment based on improved RRT*-Smart[J]. Chinese Journal of Intelligent Science and Technology, 2022, 4(2): 264-276.
[23] 张瑞, 周丽, 刘正洋. 融合RRT*与DWA算法的移动机器人动态路径规划[J]. 系统仿真学报, 2024, 36(4): 957-968.
ZHANG R, ZHOU L, LIU Z Y. Dynamic path planning for mobile robot based on RRT* and dynamic window approach[J]. Journal of System Simulation, 2024, 36(4): 957-968.
[24] 赖荣燊, 窦磊, 巫志勇, 等. 融合改进A*算法和动态窗口法的移动机器人路径规划[J]. 系统仿真学报, 2024, 36(8): 1884-1894.
LAI R S, DOU L, WU Z Y, et al. Fusion of improved A* and dynamic window approach for mobile robot path planning[J]. Journal of System Simulation, 2024, 36(8): 1884-1894.
[25] YUKSEL C, SCHAEFER S, KEYSER J. On the parameteri-zation of catmull-Rom curves[C]//Proceedings of the 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling. New York: ACM, 2009: 47-53.