SN-BI-RRT*：基于动态梯度和人工势场的双向探索随机树算法

doi:10.3778/j.issn.1002-8331.2506-0280

摘要/Abstract

摘要： 针对RRT*（rapidly-exploring random tree star）算法在复杂障碍物场景下存在收敛效率低、搜索方向随机性强，导致生成路径效果不佳的问题，提出一种基于动态梯度采样和人工势场的双向快速探索随机树算法（SN-BI-RRT*）。采用分步式动态梯度采样策略优化采样过程，更有效地探索配置空间。在拓展方面引入一种改进的人工势场法，提高算法的收敛速度。对生成的新节点采用改进的重连父节点策略进行优化，减少路径总成本。为了提高路径的平滑度，采用路径剪枝、线性插值和B样条平滑的融合路径平滑策略进行后处理。通过仿真实验，将SN-BI-RRT*算法与其他几种基于采样的路径规划算法在不同障碍物环境和狭窄环境下进行了比较，结果表明该算法在不同环境下均有良好的性能，在机器人路径规划中可以有效解决机器人在复杂室内环境中的高效路径规划问题。

关键词: 路径规划, 动态梯度采样策略, 人工势场法, 节点优化

Abstract: Aiming at the problems of low convergence efficiency and randomness of search direction of RRT*(rapidly-exploring random tree star) algorithm in complex obstacle scenarios, which lead to poor path generation, this paper proposes a bidirectional fast exploratory random tree algorithm (SN-BI-RRT*) based on dynamic gradient sampling and artificial potential field. A stepwise dynamic gradient sampling strategy is used to optimize the sampling process and explore the configuration space more effectively. An improved artificial potential field method is introduced in the expansion to improve the convergence speed of the algorithm. In addition, the generated new nodes are optimized with an improved reconnection parent node strategy to reduce the total cost of the path. In order to improve the smoothness of the paths, a fusion path smoothing strategy of path pruning, linear interpolation and B-spline smoothing is used for post-processing. Through simulation experiments, the SN-BI-RRT* algorithm is compared with several other sampling-based path planning algorithms in different obstacle environments and narrow environments, and the results show that the algorithm has good performance in different environments, and it can be an effective solution to the problem of efficient path planning for robots in complex indoor environments in robot path planning.

Key words: path planning, dynamic gradient sampling strategy, artificial potential field method, node optimization

黄友锐, 朱忠涛, 韩涛. SN-BI-RRT*：基于动态梯度和人工势场的双向探索随机树算法[J]. 计算机工程与应用, 2025, 61(24): 116-133.

HUANG Yourui, ZHU Zhongtao, HAN Tao. SN-BI-RRT*: Bidirectional Exploratory Random Tree Algorithm Based on Dynamic Gradient and Artificial Potential Field[J]. Computer Engineering and Applications, 2025, 61(24): 116-133.

参考文献

[1] 毕竟, 刘俊. 结合DC-A*与FE-DWA的巡检机器人路径规划方法[J/OL]. 计算机工程与应用, 2025: 1-16 (2025-04-28)[2025-06-10]. https://kns.cnki.net/kcms/detail/11.2127.TP.20250428. 1440.016.html.
BI J, LIU J. A path planning method for inspection robots combining DC-A* and FE-DWA[J/OL]. Computer Engineering and Applications, 2025: 1-16(2025-04-28)[2025-06-10]. https://kns.cnki.net/kcms/detail/11.2127.TP.20250428.1440.016.html.
[2] 陈林, 缪志强, 王祥科, 等. 自主飞行器技术及其在低空经济中的应用综述[J]. 机器人, 2025, 47(3): 470-496.
CHEN L, MIAO Z Q, WANG X K, et al. Overview on autonomous aircraft technology and its application to low-altitude economy[J]. Robot, 2025, 47(3): 470-496.
[3] LI Q H, WANG J H, LI H M, et al. Fast-RRT*: an improved motion planner for mobile robot in two-dimensional space[J]. IEEJ Transactions on Electrical and Electronic Engineering, 2022, 17(2): 200-208.
[4] MENG Z J. Optimization path planning algorithm based on deep reinforcement learning[C]//Proceedings of the 2024 Asia-Pacific Conference on Software Engineering, Social Network Analysis and Intelligent Computing. Piscataway: IEEE, 2024: 872-876.
[5] 顾谦, 安琪, 张妙恬, 等. 基于改进RRT算法的机器人路径规划研究[J]. 组合机床与自动化加工技术, 2025(3): 204-208.
GU Q, AN Q, ZHANG M T, et al. Research on robot path planning based on improved RRT algorithm[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2025(3): 204-208.
[6] NOREEN I, KHAN A, HABIB Z. Optimal path planning using RRT* based approaches: a survey and future directions[J]. International Journal of Advanced Computer Science and Applications, 2016, 7(11): 071114.
[7] ZHANG Y W, WANG R R, SONG C L, et al. An improved dynamic step size RRT algorithm in complex environments[C]//Proceedings of the 2021 33rd Chinese Control and Decision Conference. Piscataway: IEEE, 2021: 3835-3840.
[8] 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.
[9] 赖荣燊, 窦磊, 巫志勇, 等. 改进RRT*-Smart算法的移动机器人全局路径规划研究[J]. 计算机工程与应用, 2025, 61(13): 378-388.
LAI R S, DOU L, WU Z Y, et al. Research on global path planning for mobile robots with improved RRT*-smart algorithm[J]. Computer Engineering and Applications, 2025, 61(13): 378-388.
[10] SUMMERS T. Distributionally robust sampling-based motion planning under uncertainty[C]//Proceedings of the 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway: IEEE, 2019: 6518-6523.
[11] YU S N, CHEN J K, LIU G Y, et al. SOF-RRT*: an improved path planning algorithm using spatial offset sampling[J]. Engineering Applications of Artificial Intelligence, 2023, 126: 106875.
[12] WU Z P, MENG Z J, ZHAO W L, et al. Fast-RRT: a RRT-based optimal path finding method[J]. Applied Sciences, 2021, 11(24): 11777.
[13] DONG X X, WANG Y J, FANG C, et al. FHQ-RRT*: an improved path planning algorithm for mobile robots to acquire high-quality paths faster[J]. Sensors, 2025, 25(7): 2189.
[14] 孙鹏飞, 么娆, 邹宸玮, 等. 基于改进RRT*算法的机械臂路径规划[J]. 智能计算机与应用, 2025, 15(4): 171-176.
SUN P F, YAO R, ZOU C W, et al. Path planning of manipulator based on improved RRT* algorithm[J]. Intelligent Computer and Applications, 2025, 15(4): 171-176.
[15] GUAN T, HAN Y, KONG M C, et al. An improved artificial potential field with RRT star algorithm for autonomous vehicle path planning[J]. Scientific Reports, 2025, 15: 16982.
[16] LEI S J, LI T Y, GAO X C, et al. Research on improved RRT path planning algorithm based on multi-strategy fusion[J]. Scientific Reports, 2025, 15: 13312.
[17] 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.
[18] JI H C, XIE H B, WANG C, et al. E-RRT*: path planning for hyper-redundant manipulators[J]. IEEE Robotics and Automation Letters, 2023, 8(12): 8128-8135.
[19] QI J Y, YUAN Q N, WANG C, et al. Path planning and collision avoidance based on the RRT*FN framework for a robotic manipulator in various scenarios[J]. Complex & Intelligent Systems, 2023, 9(6): 7475-7494.
[20] LI Y J, WEI W, GAO Y, et al. PQ-RRT*: an improved path planning algorithm for mobile robots[J]. Expert Systems with Applications, 2020, 152: 113425.
[21] CONG J P, HU J B, WANG Y Y, et al. FF-RRT*: a sampling-improved path planning algorithm for mobile robots against concave cavity obstacle[J]. Complex & Intelligent Systems, 2023, 9(6): 7249-7267.
[22] LIANG Y M, ZHAO H Y. CCPF-RRT*: an improved path planning algorithm with consideration of congestion[J]. Expert Systems with Applications, 2023, 228: 120403.
[23] GUO Y C, LIU X X, LIU X H, et al. FC-RRT*: an improved path planning algorithm for UAV in 3D complex environment[J]. ISPRS International Journal of Geo-Information, 2022, 11(2): 112.
[24] VINCE A. A framework for the greedy algorithm[J]. Discrete Applied Mathematics, 2002, 121(1/2/3): 247-260.
[25] 王智慧, 代永强, 刘欢. 基于自适应飞蛾扑火优化算法的三维路径规划[J]. 计算机应用研究, 2023, 40(1): 63-69.
WANG Z H, DAI Y Q, LIU H. 3D path planning based on adaptive moth-fiame optimization algorithm[J]. Application Research of Computers, 2023, 40(1): 63-69.
[26] 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): 1729881420962263.
[27] MA B S, WEI C, HUANG Q, et al. APF-RRT*: an efficient sampling-based path planning method with the guidance of artificial potential field[C]//Proceedings of the 2023 9th International Conference on Mechatronics and Robotics Engineering. Piscataway: IEEE, 2023: 207-213.
[28] DAI J, ZHANG Y, DENG H. Novel potential guided bidirectional RRT* with direct connection strategy for path planning of redundant robot manipulators in joint space[J]. IEEE Transactions on Industrial Electronics, 2024, 71(3): 2737-2747.
[29] CONG K D, HU Y H, XU L, et al. Safe model predictive tracking with an improved APF-RRT* path planning for UGVs[C]//Proceedings of the 2023 IEEE International Conference on Unmanned Systems. Piscataway: IEEE, 2023: 1165-1170.
[30] ELBANHAWI M, SIMIC M, JAZAR R N. Continuous path smoothing for car-like robots using B-spline curves[J]. Journal of Intelligent & Robotic Systems, 2015, 80(1): 23-56.
[31] HUANG Y J, LI H, DAI Y, et al. A 3D path planning algorithm for UAVs based on an improved artificial potential field and bidirectional RRT[J]. Drones, 2024, 8(12): 760.
[32] YUAN L H, ZHAO J C, LI W H, et al. Improved informed-RRT* based path planning and trajectory optimization for mobile robots[J]. International Journal of Precision Engineering and Manufacturing, 2023, 24(3): 435-446.
[33] CHAO N, LIU Y K, XIA H, et al. Grid-based RRT for minimum dose walking path-planning in complex radioactive environments[J]. Annals of Nuclear Energy, 2018, 115: 73-82.