Obstacle avoidance path planning based on improved RRT algorithm

doi:10.3785/j.issn.1006-754X.2024.03.141

Chinese Journal of Engineering Design

2023, Vol. 30

Issue (6): 707-716 DOI: 10.3785/j.issn.1006-754X.2024.03.141

Robotic and Mechanism Design

Obstacle avoidance path planning based on improved RRT algorithm

Yao FENG¹(

),Zhifeng ZHOU¹(

),Yichun SHEN²,Liduan WANG³

^1.School of Mechanical and Automotive Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
^2.Shanghai Institute of Satellite Engineering, Shanghai 200240, China
^3.ComNav Technology Ltd. , Shanghai 201801, China

Download:

HTML

PDF(3761KB)
Export: BibTeX | EndNote (RIS)

Abstract

Aiming at the problems of rapidly-exploring random tree (RRT) algorithm in obstacle avoidance path planning, such as weak adaptability to maps, poor sampling quality, many invalid nodes, long planning time and poor path quality, an improved RRT algorithm was proposed. Firstly, on the basis of the traditional RRT algorithm, the map complexity evaluation strategy was used to calculate the appropriate step size and bias probability, so as to realize the self-adaptation to different maps. Then, through the dynamic update strategy of sampling area, the random tree was sampled in the effective area to ensure the positive growth. After the sampling area was determined, the sampling point optimization strategy was adopted to improve the effectiveness of sampling points and make the random tree grow near the target points. Finally, the node reconnection strategy was used to optimize the planned initial obstacle avoidance path, and an obstacle avoidance path with fewer bending times was obtained. The feasibility of the improved RRT algorithm was verified in Python and MATLAB environments. The results showed that the improved RRT algorithm could quickly plan a collision-free high-quality path for maps with different complexity and when applied to robotic arms. The research results can provide reference for improving efficiency of robot obstacle avoidance path planning.

Key words： path planning rapidly-exploring random tree algorithm dynamic update of sampling area sampling point optimization node reconnection

Received: 30 March 2023 Published: 02 January 2024

CLC:

TH 113.2

Corresponding Authors: Zhifeng ZHOU E-mail: fyao1998@163.com;zhousjtu@126.com

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Yao FENG
	Zhifeng ZHOU
	Yichun SHEN
	Liduan WANG

Cite this article:

Yao FENG,Zhifeng ZHOU,Yichun SHEN,Liduan WANG. Obstacle avoidance path planning based on improved RRT algorithm. Chinese Journal of Engineering Design, 2023, 30(6): 707-716.

URL:

https://www.zjujournals.com/gcsjxb/10.3785/j.issn.1006-754X.2024.03.141 OR https://www.zjujournals.com/gcsjxb/Y2023/V30/I6/707

基于改进RRT算法的避障路径规划

针对快速搜索随机树（rapidly-exploring random tree, RRT）算法在避障路径规划中存在的对地图适应性弱、采样质量差、无效节点多、规划时间长及路径质量差等问题，提出了一种改进RRT算法。首先，在传统RRT算法的基础上，基于地图复杂程度评估策略计算得到合适的步长及偏置概率，以实现对不同地图的自适应。然后，通过采样区域动态更新策略，使随机树在有效区域内进行采样，以确保随机树的正向生长；在确定采样区域后，利用采样点优化策略来提高采样点的有效性，使得随机树朝目标点附近生长。最后，采用节点重连策略对规划的初始避障路径进行优化，以获得一条弯折次数较少的避障路径。在Python及MATLAB环境中对改进RRT算法的可行性进行验证。结果表明，在面向复杂程度不同的地图和应用于机械臂时，改进RRT算法均能快速规划出一条无碰撞的高质量路径。研究结果可为提高机器人避障路径的规划效率提供参考。

关键词： 路径规划, 快速搜索随机树算法, 采样区域动态更新, 采样点优化, 节点重连

Fig.1 Principle of RRT algorithm

算法	偏置概率	耗时/s	路径长度/cm
传统RRT	无	124.658	28.932
改进RRT	$1 - ? C 1$	规划失败
	$1 - ? C 1 2$	25.604	33.839
	$1 - ? C 1 3$	10.687	26.154
	$1 - ? C 1 4$	40.401	27.407

Table 1 Comparison of path planning results of RRT algorithm with different bias probabilities

Fig.2 Schematic diagram of dynamic update of sampling area

Fig.3 Schematic diagram of sampling point optimization process

Fig.4 Schematic diagram of node reconnection

Fig.5 Comparison of path planning effect of four RRT algorithms in 2D map 1

Fig.6 Comparison of path planning effect of four RRT algorithms in 2D map 2

Fig.7 Comparison of path planning effect of four RRT algorithms in 2D map 3

Table 2 Comparison of path planning data of four RRT algorithms in 2D map 1

Table 3 Comparison of path planning data of four RRT algorithms in 2D map 2

Table 4 Comparison of path planning data of four RRT algorithms in 2D map 3

Fig.8 Comparison of path planning effect of four RRT algorithms in 3D map

Table 5 Comparison of path planning data of four RRT algorithms in 3D map

Fig. 9 Obstacle avoidance path planning result of robotic arm based on improved RRT algorithm

Table 6 Comparison of obstacle avoidance path planning data of robotic arm based on four RRT algorithms


[1]	FAN X J， GUO Y J， LIU H， et al. Improved artificial potential field method applied for AUV path planning［J］. Mathematical Problems in Engineering， 2020， 2020： 6523158.

[2]	DOLGOV D， THRUN S， MONTEMERLO M， et al. Path planning for autonomous vehicles in unknown semi-structured environments［J］. The International Journal of Robotics Research， 2010， 29（5）： 485-501.

[3]	杨明亮，李宁.改进A算法的移动机器人路径规划［J］. 机械科学与技术，2022，41（5）：795-800. YANG M L， LI N. Study on mobile robot path planning based on improved A algorithm［J］. Mechanical Science and Technology for Aerospace Engineering， 2022， 41（5）： 795-800.

[4]	王殿君.基于改进A算法的室内移动机器人路径规划［J］.清华大学学报（自然科学版），2012，52（8）：1085-1089. WANG D J. Indoor mobile-robot path planning based on an improved A algorithm ［J］. Journal of Tsinghua University （Science & Technology）， 2012， 52（8）： 1085-1089.

[5]	LaVALLE S M， KUFFNER J J. Randomized kinodynamic planning［J］. The International Journal of Robotics Research， 2001， 20（5）： 378-400.

[6]	陈志梅，李敏，邵雪卷，等.基于改进RRT算法的桥式起重机避障路径规划［J］.系统仿真学报，2021，33（8）：1832-1838. CHEN Z M， LI M， SHAO X J， et al. Obstacle avoidance path planning of bridge crane based on improved RRT algorithm［J］. Journal of System Simulation， 2021， 33（8）： 1832-1838.

[7]	HSU D， LATOMBE J C， KURNIAWATI H. On the probabilistic foundations of probabilistic roadmap planning［J］. The International Journal of Robotics Research， 2006， 25（7）： 83-97.

[8]	刘亚秋，赵汉琛，刘勋，等.一种基于改进的快速扩展随机树的工业机器人路径避障规划算法［J］.信息与控制，2021，50（2）：235-246. LIU Y Q， ZHAO H C， LIU X， et al. An improved RRT based obstacle avoidance path planning algorithm for industrial robot［J］. Information and Control， 2021， 50（2）： 235-246.

[9]	阮晓钢，周静，张晶晶，等.基于子目标搜索的机器人目标导向RRT路径规划算法［J］.控制与决策，2020，35（10）：2543-2548. RUAN X G， ZHOU J， ZHANG J J， et al. Robot goal guide RRT path planning based on sub-target search［J］. Control and Decision， 2020， 35（10）： 2543-2548.

[10]	余敏，罗建军，王明明，等.一种改进RRT结合四次样条的协调路径规划方法［J］.力学学报，2020，52（4）：1024-1034. YU M， LUO J J， WANG M M， et al. Coordinated path planning by integrating improved RRT and quartic spline［J］. Chinese Journal of Theoretical and Applied Mechanics， 2020， 52（4）： 1024-1034.

[11]	YUAN C R， ZHANG W Q， LIU G F， et al. A heuristic rapidly-exploring random trees method for manipulator motion planning［J］. IEEE Access， 2020， 8： 900-910.

[12]	徐娜，陈雄，孔庆生，等.非完整约束下的机器人运动规划算法［J］.机器人，2011，33（6）：666-672. doi：10.3724/SP.J.1218.2011.00666 XU N， CHEN X， KONG Q S， et al. Motion planning for robot with nonholonomic constraints［J］. Robot， 2011， 33（6）： 666-672. doi: 10.3724/SP.J.1218.2011.00666

[13]	杜明博，梅涛，陈佳佳，等.复杂环境下基于RRT的智能车辆运动规划算法［J］.机器人，2015，37（4）：443-450. DU M B， MEI T， CHEN J J， et al. RRT-based motion planning algorithm for intelligent vehicle in complex environments［J］. Robot， 2015， 37（4）： 443-450.

[14]	KARAMAN S， FRAZZOLI E. Sampling-based algorithms for optimal motion planning［J］. The International Journal of Robotics Research， 2011， 30（7）： 846-894.

[15]	LUO S Y， LIU S R， ZHANG B T， et al. Path planning algorithm based on Gb informed RRT* with heuristic bias［C］//2017 36th Chinese Control Conference （CCC）， Dalian， Jul. 26-28， 2017.

[16]	张玉伟，左云波，吴国新，等.基于改进Informed-RRT算法的路径规划研究［J］.组合机床与自动化加工技术，2020（7）：21-25. ZHANG Y W， ZUO Y B， WU G X， et al. Research on path planning based on improved Informed-RRT algorithm［J］. Modular Machine Tool & Automatic Manufacturing Technique， 2020（7）： 21-25.

[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， San Francisco， Apr. 24-28， 2000.

[18]	韩康，程卫东.基于改进RRT-Connect算法的机械臂路径规划［J］.计算机应用与软件，2022，39（3）：260-265. doi：10.3969/j.issn.1000-386x.2022.03.042 HAN K， CHENG W D. Path planning of robot arm based on improved RRT algorithm［J］. Computer Applications and Software， 2022， 39（3）： 260-265. doi: 10.3969/j.issn.1000-386x.2022.03.042

[19]	张丹萌，甄子洋，陈棪.基于改进RRT-Connect的协同航迹规划［J］.电光与控制，2021，28（9）：25-29. doi：10.3969/j.issn.1671-637X.2021.09.006 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. doi: 10.3969/j.issn.1671-637X.2021.09.006

[20]	王坤，黄勃，曾国辉，等.基于改进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.

[21]	黄壹凡，胡立坤，薛文超.基于改进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.

[1]	TANG Dong-lin, LONG Zai-yong, TANG Yan-jin, PAN Feng, YOU Chuan-kun. Complete coverage path planning of oil tank detection wall climbing robot[J]. Chinese Journal of Engineering Design, 2020, 27(2): 162-171.

[2]	ZHOU Jie-hua, DAI Ji-yang, ZHOU Ji-qiang, ZHANG Xiao-yong. Research on path planning and trajectory tracking control of mowing robot for large airport lawn[J]. Chinese Journal of Engineering Design, 2019, 26(2): 146-152.

[3]	TANG Dong-lin, YUAN Bo, HU Lin, LI Mao-yang, WEI Zi-bing. Complete coverage path planning method for oil tank inspection wall climbing robot[J]. Chinese Journal of Engineering Design, 2018, 25(3): 253-261.

[4]	LIANG Cheng-ji, SHEN Shan-shan, HU Wen-hui. AGV path planning considering alternative paths based on time window of road section[J]. Chinese Journal of Engineering Design, 2018, 25(2): 200-208.

[5]	ZHU Long-biao, WANG Hui, WANG Jing-liang, SHAO Xiao-jiang, ZHU Zhi-hui. Research on path planning of parking system based on dynamic time window[J]. Chinese Journal of Engineering Design, 2017, 24(4): 440-448.

[6]	LI Bao-kun, HAN Ying-ge, GUO Yong-cun, CAO Yi, WANG Cheng-jun. Singularity-free position path planning of the Gough-Stewart parallel mechanism[J]. Chinese Journal of Engineering Design, 2016, 23(6): 544-552.

[7]	WANG Hui, ZHU Long-biao, WANG Jing-liang, CHEN Hong-yan, SHAO Xiao-jiang, ZHU Zhi-hui. Research on path planing of parking system based on Dijkstra-Ant colony hybrid algorithm[J]. Chinese Journal of Engineering Design, 2016, 23(5): 489-496.

[8]	WANG Hui, ZHU Long-biao, ZHU Tian-cheng, CHEN Hong-yan, SHAO Xiao-jiang, ZHU Zhi-hui. Research on path planning of parking system based on PSO-genetic hybrid algorithm[J]. Chinese Journal of Engineering Design, 2016, 23(2): 195-200.

[9]	XIAO Hao, SONG Xiao-Lin, CAO Hao-Tian. Local path planning for autonomous vehicle collision avoidance based on dangerous repellant fields[J]. Chinese Journal of Engineering Design, 2012, 19(5): 379-384.

Viewed

Full text

Abstract

Cited

Shared

Discussed