改进Informed RRT*算法移动机器人路径规划

doi:10.3778/j.issn.1002-8331.2405-0216

摘要/Abstract

摘要： Informed RRT*算法对初始解不敏感，规划出的路径太接近障碍物，导致路径不平滑。提出一种改进的Informed RRT*路径规划算法，该算法改进了约束采样空间和引导策略。在采样初期，将采样区域限制在一个圆形区域，加快初始解收敛，在算法规划的过程中引入人工势场中引力场和斥力场的思想，使机器人与障碍物保持安全距离，并向目标位置行进。对Informed RRT*算法和基于目标偏置的Informed RRT*算法（Goal-bias-Informed RRT*）以及改进后的Informed RRT*算法进行比较实验，实验结果验证了改进后Informed RRT*算法的有效性和优越性及稳定性。该算法较Informed RRT*算法和Goal-bias-Informed RRT*效率更高、更容易得到初始解、更安全、更平滑、更稳定。

关键词: 移动机器人, 路径规划, 随机采样, Informed RRT*算法, 目标偏置, 约束采样空间

Abstract: The Informed RRT* algorithm is insensitive to the initial solution, and the planned path is too close to the obstacles, which leads to the unsmooth path. This paper presents an improved Informed RRT* path planning algorithm, which improves the constrained sampling space and guidance strategy. Firstly, in the initial sampling stage, the sampling area is limited to a circular area to speed up the convergence of the initial solution. Secondly, the idea of gravitational field and repulsive field in artificial potential field is introduced in the algorithm planning process, so that the robot can keep a safe distance from obstacles and move towards the target position. Compared with the Informed RRT* algorithm and the Informed RRT*algorithm based on target offset (Goal-bias-Informed RRT*), the experimental results verify the effectiveness, superiority and stability of the improved Informed RRT* algorithm. Compared with the Informed RRT* algorithm and Goal-bias-Informed RRT*, this algorithm is more efficient, easier to get the initial solution, safer, smoother and more stable.

Key words: mobile robot, path planning, random sampling, Informed RRT* algorithm, target offset, constrained sampling space

鲁宇明, 周羽逵, 郭鑫, 池吕庭, 戴骏. 改进Informed RRT*算法移动机器人路径规划[J]. 计算机工程与应用, 2025, 61(8): 283-293.

LU Yuming, ZHOU Yukui, GUO Xin, CHI Lyuting, DAI Jun. Mobile Robot Path Planning Based on Improved Informed RRT* Algorithm[J]. Computer Engineering and Applications, 2025, 61(8): 283-293.

参考文献

[1] 朱大奇, 颜明重. 移动机器人路径规划技术综述[J]. 控制与决策, 2010, 25(7): 961-967.
ZHU D Q, YAN M Z. Overview of mobile robot path planning technology[J]. Control and Decision, 2010, 25(7): 961-967.
[2] 王旭, 朱其新, 朱永红. 面向二维移动机器人的路径规划算法综述[J]. 计算机工程与应用, 2023, 59(20): 51-66.
WANG X, ZHU Q X, ZHU Y H. Review of path planning algorithms for mobile robots[J]. Computer Engineering and Applications, 2023, 59(20): 51-66.
[3] SUN Y, FANG M, SU Y. AGV path planning based on improved Dijkstra algorithm[J]. Journal of Physics: Conference Series, 2021, 1746(1): 12-52.
[4] SHANG E K, DAI B, NIE Y M, et al. An improved A-Star based path planning algorithm for autonomous land vehicles[J]. International Journal of Advanced Robotic Systems, 2020, 17(5): 1-13.
[5] 邱硕涵, 谭章禄, 蔡晓梅. 基于D_Star算法的巡检机器人路径规划优化研究[J]. 中国矿业大学学报, 2021, 50(5): 1011-1018.
QIU S H, TAN Z L, CAI X M. Research on path planning optimization of patrol robot based on D_Star algorithm[J]. Journal of China University of Mining and Technology, 2021, 50(5): 1011-1018.
[6] 江明, 王飞, 葛愿, 等. 基于改进蚁群算法的移动机器人路径规划研究[J]. 仪器仪表学报, 2019, 40(2): 113-121.
JIANG M, WANG F, GE Y, et al. Research on path planning of mobile robot based on improved ant colony algorithm[J]. Journal of Instrumentation, 2019, 40(2): 113-121
[7] 马小陆, 梅宏. 基于改进势场蚁群算法的移动机器人全局路径规划[J]. 机械工程学报, 2021, 57(1): 19-27.
MA X L, MEI H. Mobile robot global path planning based on improved potential field ant colony algorithm[J]. Journal of Mechanical Engineering, 2021, 57(1): 19-27.
[8] 刘洋, 马建伟, 臧绍飞, 等. 基于融合Bezier优化遗传算法的路径规划[J]. 控制工程, 2021, 28(2): 284-292.
LIU Y, MA J W, ZANG S F, et al. Path planning based on fusion Bezier optimized genetic algorithm[J]. Control Engineering, 2021, 28(2): 284-292.
[9] LAVALLE S M. Rapidly-exploring random trees: a new tool for path planning[R]. Iowa: Iowa State University, 1998.
[10] 宁宇铭, 李团结, 姚聪, 等. 基于快速扩展随机树——贪婪边界搜索的多机器人协同空间探索方法[J]. 机器人, 2022, 44(6): 708-719.
NING Y M, LI T J, YAO C, et al. Multi robot collaborative space exploration method based on fast expanding random tree greedy boundary search[J]. Robot, 2022, 44(6): 708-719.
[11] 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 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2014: 2997-3004.
[12] WANG X Z. The comparison of three algorithms in shortest path issue[J]. Journal of Physics: Conference Series, 2018, 1087(2): 1-7.
[13] KARAMAN S, FRAZZOLI E. Sampling-based algorithms for optimal motion planning[J]. arXiv:1105.1186, 2011.
[14] MASHAYEKHI R, IDRIS M Y I, ANISI M H, et al. Informed RRT*-connect: an asymptotically optimal single-query path planning method[J]. IEEE Access, 2020, 8: 19842-19852.
[15] KLEMM S, OBERL?NDER J, HERMANN A, et al. RRT?-connect: faster, asymptotically optimal motion planning[C]//Proceedings of the IEEE International Conference on Robotics and Biomimetics, 2015: 1670-1677.
[16] WANG X, MA X, LI X, et al. Target-biased informed trees: sampling-based method for optimal motion planning in complex environments[J]. Journal of Computational Design and Engineering, 2022, 9(2): 755-771.
[17] 涂睿, 王文格, 卢成阳. 移动机器人实时采样路径重规划[J]. 计算机工程与应用, 2021, 57(20): 157-163.
TU R, WANG W G, LU C Y. Real-time sampling path replanning of mobile robot[J]. Computer Engineering and Applications, 2021, 57(20): 157-163.
[18] 段书用, 王启帆, 韩旭, 等. 具有确保安全距离的A* 路径优化方法[J]. 机械工程学报, 2020, 56(18): 205-215.
DUAN S Y, WANG Q F, HAN X, et al. A * path optimization method with safe distance[J]. Journal of Mechanical Engineering, 2020, 56 (18): 205-215.
[19] 刘翰培, 王东署, 汪宇轩, 等. 移动机器人路径规划的模糊人工势场法研究[J]. 控制工程, 2022, 29(1): 33-38.
LIU H P, WANG D S, WANG Y X, et al. Research of path planning for mobile robots based on fuzzy artificial potential field method[J]. Control Engineering of China, 2022, 29(1): 33-38.
[20] MIN C K, JAE B S. Informed-RRT* with improved converging rate by adopting wrapping procedure[J]. Intelligent Service Robotics, 2018, 11(1): 53-60.
[21] 李二超, 王玉华. 改进人工势场法的移动机器人避障轨迹研究[J]. 计算机工程与应用, 2022, 58(6): 296-304.
LI E C, WANG Y H. Research on obstacle avoidance trajectory of mobile robot based on improved artificial potential field[J]. Computer Engineering and Applications, 2022, 58(6): 296-304.