Research on Robot Path Planning Based on Improved RRT-Connect Algorithm

doi:10.3778/j.issn.1673-9418.2404005

Abstract

Abstract: The proposed improved RRT-Connect algorithm (TRRT-Connect) addresses the issues of path elongation, excessive turns, and inadequate pass ability encountered in the standard RRT-Connect algorithm for path planning. Firstly, an improved RRT algorithm is employed to search and add a middle root node, facilitating the simultaneous expansion of four random trees to expedite algorithm convergence. Additionally, a target-biased strategy is employed for random point selection, and an attractive field is superimposed on node generation, along with integration of a greedy search strategy. Furthermore, a novel dynamic step size adjustment method is introduced, which dynamically selects appropriate step sizes by identifying the number of obstacles within the scanning region. Then, a bidirectional pruning optimization method is applied to the generated initial paths to accelerate pruning efficiency and remove redundant nodes along the paths. Finally, path smoothing is conducted at path turning points and the number of paths􀆳 turns is reduced. Simulation comparative experiments are conducted in three different environmental maps. The results indicate that the TRRT-Connect algorithm shows significant improvements compared with the standard RRT-Connect algorithm in terms of path length, number of iterations, and number of nodes. The paths generated are smoother without path turns, and there is better pass ability in densely populated obstacle areas. Experimental results confirm the effectiveness of this algorithm. Moreover, the application of the TRRT-Connect algorithm in field instance simulations reduces the transportation path length of mobile robots by 15.4% compared with traditional fixed paths, with smoother paths, further confirming the practicality of the algorithm.

Key words: RRT-Connect algorithm, dynamic step size adjustment, bidirectional pruning optimization, path planning

摘要： 针对标准RRT-Connect算法在路径规划中存在的路径冗长、转折较多和区域通过性欠缺问题，提出了一种新的改进RRT-Connect算法（TRRT-Connect）。采用改进RRT算法搜索并添加一个中间根节点，实现同时扩展四棵随机树，加快算法收敛速度。在随机点的选取上使用目标偏置策略，在新节点的生成上叠加引力场，同时融合贪婪搜索策略。结合新的动态步长调节方法，通过识别扫描区域内障碍物的个数动态选择合适的步长。对生成的初始路径使用双向剪枝优化方法，加快剪枝效率，剔除路径上的冗余节点。对路径转折处进行光滑处理，减少路径转折。在三种不同环境地图中进行仿真对比实验，结果表明，TRRT-Connect算法与标准RRT-Connect算法相比较，在路径长度、迭代次数和节点数上有较大改善，在密集障碍物区域的通过性较好，路径更加光滑且无转折，证明了该算法的有效性。同时将TRRT-Connect算法应用于现场实例仿真中，使得移动机器人的运输路径长度相较于传统固定路径降低了15.4%，且路径光滑，进一步验证了该算法的实用性。

关键词: RRT-Connect算法, 动态步长调节, 双向剪枝优化, 路径规划

CHEN Zhilan, TANG Haoyang. Research on Robot Path Planning Based on Improved RRT-Connect Algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(2): 396-405.

陈志澜, 唐昊阳. 改进RRT-Connect算法的机器人路径规划研究[J]. 计算机科学与探索, 2025, 19(2): 396-405.

References

[1] KARTHIK K, NITIN S, CHINMAY D, et al. A survey of path planning algorithms for mobile robots[J]. Vehicles, 2021, 3(3): 448-468.
[2] LI X, TONG Y. Path planning of a mobile robot based on the improved RRT algorithm[J]. Applied Sciences, 2023, 14(1): 25.
[3] 宋晓茹, 任怡悦, 高嵩, 等. 移动机器人路径规划综述[J].计算机测量与控制, 2019, 27(4): 1-5.
SONG X R, REN Y Y, GAO S, et al. Survey on technology of mobile robot path planning[J]. Computer Measurement & Control, 2019, 27(4): 1-5.
[4] 韦玉海, 张辉, 刘理, 等. 基于AMRRT-Connect算法的移动机器人路径规划[J]. 武汉大学学报(工学版), 2022, 55(5): 531-538.
WEI Y H, ZHANG H, LIU L, et al. Path planning of mobile robot based on AMRRT-Connect algorithm[J]. Engineering Journal of Wuhan University, 2022, 55(5): 531-538.
[5] 王怀震, 高明, 王建华, 等. 基于改进RRT*-Connect算法的机械臂多场景运动规划[J]. 农业机械学报, 2022, 53(4): 432-440.
WANG H Z, GAO M, WANG J H, et al. Multi-scene fast motion planning of manipulator based on improved RRT*- Connect algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2022, 53(4): 432-440.
[6] LAVALLE S M，KUFFNER J J. Randomized kino dynamic planning[C]//Proceedings of the 1999 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2001: 378-400.
[7] 崔永杰, 王寅初, 何智, 等. 基于改进RRT算法的猕猴桃采摘机器人全局路径规划[J]. 农业机械学报, 2022, 53(6): 151-158.
CUI Y J, WANG Y C, HE Z, et al. Global path planning of kiwifruit harvesting robot based on improved RRT algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2022, 53(6): 151-158.
[8] KUFFNER J J, LAVALLE S M. RRT-connect: an efficient approach to single-query path planning[C]//Proceedings of the 2000 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2000: 995-1001.
[9] 赵超力, 马行, 张春涛, 等. 基于引力场引导的RRT-Connect路径规划算法[J]. 电子测量技术, 2021, 44(22): 44-49.
ZHAO C L, MA X, ZHANG C T, et al. RRT-Connect path planning algorithm based on gravitational field guidance[J]. Electronic Measurement Technology, 2021, 44(22): 44-49.
[10] 王坤, 黄勃, 曾国辉, 等. 基于改进RRT-Connect的快速路径规划算法[J]. 武汉大学学报(理学版), 2019, 65(3): 283-289.
WANG K, HUANG B, ZENG G H, et al. Faster path planning based on improved RRT-Connect algorithm[J]. Journal of Wuhan University (Natural Science Edition), 2019, 65(3): 283-289.
[11] 黄壹凡, 胡立坤, 薛文超. 基于改进RRT-Connect算法的移动机器人路径规划[J]. 计算机工程, 2021, 47(8): 22-28.
HUANG Y F, HU L K, XUE W C. Mobile robot path planning based on improved RRT-Connect algorithm[J]. Computer Engineering, 2021, 47(8): 22-28.
[12] 杜传胜, 高焕兵, 侯宇翔, 等. 同根双向扩展的贪心RRT路径规划算法[J]. 计算机工程与应用, 2023, 59(21): 312-318.
DU C S, GAO H B, HOU Y X, et al. Greedy RRT path planning algorithm with same root bidirectional extension[J]. Computer Engineering and Applications, 2023, 59(21): 312-318.
[13] 王冠强, 张驰洲, 陈明松, 等. 融合RRT-Connect和DWA算法的室内移动机器人单目标点导航任务研究[J]. 中南大学学报(自然科学版), 2023, 54(11): 4326-4337.
WANG G Q, ZHANG C Z, CHEN M S, et al. Research on single-target point navigation task of indoor mobile robot integrating RRT-Connect and DWA algorithms[J]. Journal of Central South University (Science and Technology), 2023, 54(11): 4326-4337.
[14] CHEN J, ZHAO Y, XU X. Improved RRT-Connect based path planning algorithm for mobile robots[J]. IEEE Access, 2021, 9: 145988-145999.
[15] 施力, 徐立云. 基于RRT-connect算法的充装单元六轴机器人避障路径规划[J]. 现代制造技术与装备, 2023, 59(4): 43-47.
SHI L, XU L Y. Obstacle avoidance path planning of charging unit six-axis robot based on RRT-Connect algorithm[J]. Modern Manufacturing Technology and Equipment, 2023, 59(4): 43-47.
[16] 张丹萌, 甄子洋, 陈棪. 基于改进RRT-Connect的协同航迹规划[J]. 电光与控制, 2021, 28(9): 25-29.
ZHANG D M, ZHEN Z Y, CHEN Y. Collaborative path planning based on improved RRT-Connect algorithm[J]. Electronics Optics & Control, 2021, 28(9): 25-29.
[17] ZHANG L, SHI X, YI Y, et al. Mobile robot path planning algorithm based on RRT_Connect[J]. Electronics, 2023, 12(11): 2456.
[18] WANG L, YANG X, CHEN Z, et al. Application of the improved rapidly exploring random tree algorithm to an insect-like mobile robot in a narrow environment[J]. Biomimetics, 2023, 8(4): 374.
[19] 胡晓阳, 赵杰, 武炎明. 基于改进RRT-Connect算法的路径规划研究[J]. 沈阳理工大学学报, 2023, 42(4): 26-30.
HU X Y, ZHAO J, WU Y M. Research on path planning based on improved RRT-Connect algorithm[J]. Journal of Shenyang Ligong University, 2023, 42(4): 26-30.
[20] CHEN Y, FU Y, ZHANG B, et al. Path planning of the fruit tree pruning manipulator based on improved RRT-Connect algorithm[J]. International Journal of Agricultural and Biological Engineering, 2022, 15(2): 177-188.
[21] KANG J G, LIM D W, CHOI Y S, et al. Improved RRT-connect algorithm based on triangular inequality for robot path planning[J]. Sensors, 2021, 21(2): 333.
[22] LI Y, MA S. Navigation of apple tree pruning robot based on improved RRT-Connect algorithm[J]. Agriculture, 2023, 13(8): 1495.
[23] KARAMAN S, WALTER M R, PEREZ A, et al. Anytime motion planning using the RRT[C]//Proceedings of the 2011 ieee International Conference on Robotics and Automation. Piscataway: IEEE, 2011: 1478-1483.