概率采样和目标偏置的变步长RRT*机器人路径规划

doi:10.3778/j.issn.1002-8331.2407-0198

摘要/Abstract

摘要： 针对传统RRT*改进算法路径规划的随机性大、效率低、搜索时间长、路径质量差等问题，提出了一种名为ASP-RRT*的高效路径规划方法。该方法结合任务需求和环境特点，构建了一个包含目标距离、参考路径距离和障碍物复杂度的综合评价函数，并将地图环境分成不同区域，利用该评价函数对每个区域进行评分并计算其采样概率。基于这种概率设计了两种随机采样点，第一种用于引导整体路径探索方向，第二种用于优化局部路径。与此同时，使用目标偏置策略进一步控制第二种采样点的选取，加快向目标点扩展的速度。此外，采用动态步长策略，根据障碍物的复杂度动态调整RRT*的扩展距离。分段使用三次样条插值法对路径进行优化，使其更适合机器人移动。在六种不同环境中对算法进行仿真实验，结果表明，ASP-RRT*在时间效率和路径质量等方面均优于现有的基于采样的路径规划方法，且具有较高的可行性。

关键词: 路径规划, 评价函数, RRT*, ASP-RRT*, 目标偏置, 三次样条插值法

Abstract: To address the issues of high randomness, low efficiency, long search time, and poor path quality in traditional RRT* algorithm for path planning, a new efficient method named ASP-RRT* is proposed. This method combines task requirements and environmental characteristics to construct a comprehensive evaluation function that includes target distance, reference path distance, and obstacle complexity. The map environment is divided into different areas, and this evaluation function is used to score each area and calculate its sampling probability. Based on this probability, two types of random sampling points are designed： the first type is used to guide the overall direction of path exploration, and the second type is used to optimize the local path. At the same time, a target bias strategy is used to further control the selection of the second type of sampling points, accelerating the expansion speed towards the target. Additionally, a dynamic step strategy is adopted to adjust the expansion distance of RRT* dynamically according to the complexity of obstacles. Finally, cubic spline interpolation is applied in segments to optimize the path, making it more suitable for robot movement. Simulation experiments are conducted in six different environments, and the results demonstrate that ASP-RRT* outperforms existing sampling-based path planning methods in terms of time efficiency and path quality, and it exhibits high feasibility.

Key words: path planning, evaluation function, RRT*, ASP-RRT*, target bias, cubic spline interpolation

盛兆康, 宋家乐, 水翔, 宋廷强, 孙媛媛. 概率采样和目标偏置的变步长RRT*机器人路径规划[J]. 计算机工程与应用, 2025, 61(20): 114-122.

SHENG Zhaokang, SONG Jiale, SHUI Xiang, SONG Tingqiang, SUN Yuanyuan. Probabilistic Sampling and Target-Biased Variable Step-Length RRT* for Robot Path Planning[J]. Computer Engineering and Applications, 2025, 61(20): 114-122.

参考文献

[1] DING J, ZHOU Y X, HUANG X, et al. An improved RRT* algorithm for robot path planning based on path expansion heuristic sampling[J]. Journal of Computational Science, 2023, 67: 101937.
[2] 姜佩贺, 王敬, 桑忠启, 等. 改进A*与DWA的室内服务机器人路径规划研究[J]. 计算机工程与应用, 2024, 60(15): 327-335.
JIANG P H, WANG J, SANG Z Q, et al. Research on indoor service robot path planning based on improved A* and DWA[J]. Computer Engineering and Applications, 2024, 60(15): 327-335.
[3] 孙帅帅, 冯春晓, 张良. 基于离散采样的多模态四足机器人路径规划[J]. 吉林大学学报(工学版), 2024, 54(4): 1120-1128.
SUN S S, FENG C X, ZHANG L. Trajectory path planning for multimodal quadruped robots based on discrete sampling[J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(4): 1120-1128.
[4] 宋宇航, 陈宇帆, 魏延岭, 等. 基于强化学习环境设计策略的电动汽车充电路径规划[J]. 电力系统自动化, 2024, 48(11): 184-196.
SONG Y H, CHEN Y F, WEI Y L, et al. Charging path planning for electric vehicles based on reinforcement learning environment design strategy[J]. Automation of Electric Power Systems, 2024, 48(11): 184-196.
[5] GU Q Y, ZHEN R, LIU J L, et al. An improved RRT algorithm based on prior AIS information and DP compression for ship path planning[J]. Ocean Engineering, 2023, 279: 114595.
[6] 刘建宇, 范平清. 基于改进的RRT~*-connect算法机械臂路径规划[J]. 计算机工程与应用, 2021, 57(6): 274-278.
LIU J Y, FAN P Q. Robot path planning of manipulator based on improved RRT*-connect algorithm[J]. Computer Enginee-ring and Applications, 2021, 57(6): 274-278.
[7] 靳午煊, 马向华, 赵金良. 改进Informed-RRT*的移动机器人路径规划算法研究[J]. 计算机工程与应用, 2023, 59(19): 75-81.
JIN W X, MA X H, ZHAO J L. Research on path planning algorithm of mobile robot based on improved informed-RRT*[J]. Computer Engineering and Applications, 2023, 59(19): 75-81.
[8] SUWOYO H, ADRIANSYAH A, ANDIKA J, et al. An integrated RRT*SmarT-A* algorithm for solving the global path planning problem in a static environment[J]. IIUM Engineering Journal, 2023, 24(1): 269-284.
[9] LIU Y, ZHOU Z D, SANG H, et al. Efficient exploration of mobile robot based on DL-RRT and AP-BO[J]. IEEE Transactions on Instrumentation and Measurement, 2024, 73: 1-9.
[10] WANG Y, KONG Y Q, DING Z Y, et al. NRTIRL based NN-RRT* path planner in human-robot interaction environment[C]//Proceeding of the 14th International Conference on Social Robotics. Cham: Springer Nature Switzerland, 2022: 496-508.
[11] LIU H Y, ZHANG X B, WEN J, et al. Goal-biased bidirectional RRT based on curve-smoothing[J]. IFAC-PapersOnLine, 2019, 52(24): 255-260.
[12] 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 Enginee-ring, 2022, 17(2): 200-208.
[13] 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.
[14] 刘奥博, 袁杰. 目标偏置双向RRT*算法的机器人路径规划[J]. 计算机工程与应用, 2022, 58(6): 234-240.
LIU A B, YUAN J. Robot path planning based on goal biased bidirectional RRT* algorithm[J]. Computer Engineering and Applications, 2022, 58(6): 234-240.
[15] SUN Z R, WANG J K, MENG M Q H. Multi-tree guided efficient robot motion planning[J]. Procedia Computer Science, 2022, 209: 31-39.
[16] 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.
[17] CHEN Y, HE Z, LI S L, Horizon-based lazy optimal RRT for fast, efficient replanning in dynamic environment[J]. Autonomous Robots, 2019, 43(8): 2271-2292.
[18] LI Y, CUI R X, LI Z J, et al. Neural network approximation based near-optimal motion planning with kinodynamic constraints using RRT[J]. IEEE Transactions on Industrial Electronics, 2018, 65(11): 8718-8729.
[19] SALZMAN O, HALPERIN D. Asymptotically near-optimal RRT for fast, high-quality, motion planning[C]//Proceedings of the IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2014: 4680-4685.
[20] 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.
[21] 刘佳顺, 刘检华, 张之敬, 等. 基于任意时间RRT算法的三维自动布线技术[J]. 机械工程学报, 2016, 52(13): 156-165.
LIU J S, LIU J H, ZHANG Z J, et al. Anytime RRT based cable automatic routing under three-dimensional environment[J]. Journal of Mechanical Engineering, 2016, 52(13): 156-165.
[22] ESMAIEL H, ZHAO G L, QASEM Z A, et al. Double-Layer RRT* objective bias anytime motion planning algorithm[J]. Robotics, 2024, 13(3): 41.
[23] 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 .
[24] QI J, YANG H, SUN H X. MOD-RRT*: a sampling-based algorithm for robot path planning in dynamic environment[J]. IEEE Transactions on Industrial Electronics, 2020, 68(8): 7244-7251.
[25] 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 9th International Conference on Mechatronics and Robotics Engineering, 2023: 207-213.
[26] FAN J M, CHEN X, LIANG X. UAV trajectory planning based on bi-directional APF-RRT* algorithm with goal-biased[J]. Expert Systems with Applications, 2023, 213: 119137.
[27] 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 IEEE International Conference on Unmanned Systems, 2023: 1165-1170.