Adaptive extended RRT* path planning algorithm based on node-to-obstacle distance

doi:10.11772/j.issn.1001-9081.2024030400

Abstract

Abstract:

Rapidly-exploring Random Tree star （RRT^*） is widely used in the robot path planning field owing to its asymptotic optimality and probabilistic completeness. However， RRT^* and its improved algorithms still suffer from several limitations such as poor initial path quality， slow path convergence， and low search efficiency. In response to these challenges， an adaptive extended RRT^* algorithm based on node-to-obstacle distance， namely AE-RRT^*， was proposed. To improve the search efficiency， a dynamic goal-biased sampling strategy and a dynamic step size strategy based on the node-to-obstacle distance were adopted. Furthermore， to improve the path quality， a more accurate parent node choice method MA-ChooseParent was proposed， which broadened the set of potential parent nodes. In addition， to speed up path convergence， an adaptive Gaussian sampling method and a global Gaussian sampling method AG-Gaussian Sample based on the node-to-obstacle distance were adopted. Through simulation in Matlab， AE-RRT^* was compared with RRT^*， Quick-RRT^*， Bi-RRT^*， Informed-RRT^*， and Smart-RRT^*. Experimental results demonstrate that compared to RRT^*， AE-RRT^* achieves reductions of 63.78%， 6.55%， and 71.93%， respectively， in the time taken to find the initial path， the length of the initial path， and the time to converge to a global sub-optimal path in 2D environments. In 3D environments， AE-RRT^* achieves reductions of 59.44%， 18.26%， and 79.58%， respectively， in the three indicators.

Key words: Rapidly-exploring Random Tree (RRT), dynamic goal-biased sampling, dynamic step size strategy, adaptive Gaussian sampling, path planning

摘要：

快速扩展随机树星（RRT^*）因具有渐近最优性和概率完备性，在机器人路径规划领域有广泛的应用。然而，RRT^*及其改进算法仍存在初始路径质量差、路径收敛慢和探索效率低等缺陷。针对这些问题，提出一种基于节点到障碍物距离的自适应扩展RRT^*算法——AE-RRT^*。为提高探索效率，采用基于节点到障碍物距离的动态目标偏置采样策略和动态步长策略，从而在更短的时间内获得初始路径。为提高路径的质量，提出一种更精确的选择父节点的方法MA-ChooseParent，从而扩大选择父节点的集合。此外，为加快路径收敛，在路径收敛阶段采用基于节点到障碍物距离的自适应高斯采样方法和全局高斯采样方法AG-Gaussian Sample。通过Matlab中的仿真实验将AE-RRT^*与RRT^*、Quick-RRT^*、Bi-RRT^*、Informed-RRT^*和Smart-RRT^*进行对比。实验结果表明，与RRT^*相比，AE-RRT^*在二维环境中找到初始路径的时间、初始路径的长度和收敛至全局次优路径的时间分别减少了63.78%、6.55%和71.93%；在三维环境中的3个指标分别减少了59.44%、18.26%和79.58%。

关键词: 快速扩展随机树, 动态目标偏置采样, 动态步长策略, 自适应高斯采样, 路径规划

CLC Number:

TP242.6

Caiqi WANG, Xining CUI, Yi XIONG, Shiqian WU. Adaptive extended RRT^* path planning algorithm based on node-to-obstacle distance[J]. Journal of Computer Applications, 2025, 45(3): 920-927.

王蔡琪, 崔西宁, 熊毅, 伍世虔. 基于节点到障碍物距离的自适应扩展RRT^*路径规划算法[J]. 《计算机应用》唯一官方网站, 2025, 45(3): 920-927.

Figures/Tables 17

Tab. 1 Definitions of symbols

符号	含义
$x s t a r t$	起点
$x g o a l$	目标区域中心点
$X g o a l$	目标区域
$x r a n d$	随机采样点
$x n e a r$	随机采样点 $x r a n d$ 附近的节点
$R n e a r$	寻找附近点 $x n e a r$ 的范围
$N m a x i t e r a t i o n$	最大迭代次数
$s t e p$	随机树的扩展步长
$G$	随机树
$V$	随机树节点的集合
$E$	连接随机树节点的边的集合
$x n e a r e s t$	随机树中距离随机采样点 $x r a n d$ 最近的节点
$x n e w$	在 $x r a n d$ 与 $x n e a r e s t$ 方向上新扩展出的节点
$x p a r e n t$	新节点 $x n e w$ 的父节点

Tab. 1 Definitions of symbols

符号	含义
$x s t a r t$	起点
$x g o a l$	目标区域中心点
$X g o a l$	目标区域
$x r a n d$	随机采样点
$x n e a r$	随机采样点 $x r a n d$ 附近的节点
$R n e a r$	寻找附近点 $x n e a r$ 的范围
$N m a x i t e r a t i o n$	最大迭代次数
$s t e p$	随机树的扩展步长
$G$	随机树
$V$	随机树节点的集合
$E$	连接随机树节点的边的集合
$x n e a r e s t$	随机树中距离随机采样点 $x r a n d$ 最近的节点
$x n e w$	在 $x r a n d$ 与 $x n e a r e s t$ 方向上新扩展出的节点
$x p a r e n t$	新节点 $x n e w$ 的父节点

Fig. 1 Flow of AE-RRT*

Fig. 2 Sigmoid function and translated Sigmoid function

Fig. 3 Dynamic extended step size

Fig. 4 Process of parent node choice

Fig. 5 Process of adaptive Gaussian sampling

Fig. 6 Maps for simulations

Fig. 7 Convergence curves of RRT* using different step sizes

Tab. 2 Simulation results of different algorithms for finding initial paths on three maps

地图分类	算法	找到初始路径的时间/s	初始路径的长度
单通道地图	RRT^*	0.285	687.98
	Q-RRT^*	0.328	635.59
	Bi-RRT^*	0.039	694.60
	D-RRT^*	0.028	747.38
	DQ-RRT^*	0.073	657.59
	AE-RRT^*	0.068	634.34
多通道地图	RRT^*	0.473	579.25
	Q-RRT^*	0.510	559.40
	Bi-RRT^*	0.029	594.49
	D-RRT^*	0.170	606.65
	DQ-RRT^*	0.193	555.23
	AE-RRT^*	0.166	547.18
散乱地图	RRT^*	0.274	514.79
	Q-RRT^*	0.302	508.81
	Bi-RRT^*	0.145	526.12
	D-RRT^*	0.135	507.73
	DQ-RRT^*	0.138	496.93
	AE-RRT^*	0.134	482.29

Fig. 8 Simulation results of single channel map

Fig. 9 Simulation results of multi-channel map

Fig. 10 Simulation results of scattered map

Fig. 11 Simulation effects of adaptive Gaussian sampling

Fig. 12 Path convergence curves in 2D environments

Tab. 3 Average time path to converge to global sub-optimal path

算法	单通道地图	多通道地图	散乱地图
RRT^*	16.32	18.91	10.86
Informed-RRT^*	12.01	7.33	5.09
Smart-RRT^*	5.16	10.42	6.48
AE-RRT^*	4.53	4.77	3.39

Fig. 13 Simulation results in 3D environment

Tab. 4 Simulation results in a 3D environment

算法	找到初始路径的时间/s	初始路径的长度	收敛至全局次优路径的时间/s
RRT^*	0.249	639.34	45.21
Informed-RRT^*	0.257	643.37	16.56
Smart-RRT^*	0.261	631.03	11.73
AE-RRT^*	0.101	522.61	9.23

References 31

1	HA Q P， YEN L， BALAGUER C. Robotic autonomous systems for earthmoving in military applications ［J］. Automation in Construction， 2019， 107： No.102934.
2	SUN Z， YANG H， MA Y， et al. BIT-DMR： a humanoid dual-arm mobile robot for complex rescue operations ［J］. IEEE Robotics and Automation Letters， 2022， 7（2）： 802-809.
3	AFRIN M， JIN J， RAHMAN A， et al. Resource allocation and service provisioning in multi-agent cloud robotics： a comprehensive survey ［J］. IEEE Communications Surveys and Tutorials， 2021， 23（2）： 842-870.
4	IBNE HOSSAIN N U， SAKIB N， GOVINDAN K. Assessing the performance of unmanned aerial vehicle for logistics and transportation leveraging the Bayesian network approach ［J］. Expert Systems with Applications， 2022， 209： 118301-118318.
5	张康，陈建平. 复杂环境下基于采样空间自调整的航迹规划算法［J］. 计算机应用， 2021， 41（4）： 1207-1213.
	ZHANG K， CHEN J P. Path planning algorithm in complex environment using self-adjusting sampling space ［J］. Journal of Computer Applications， 2021， 41（4）： 1207-1213.
6	YANG L， QI J， SONG D， et al. Survey of robot 3D path planning algorithms ［J］. Journal of Control Science and Engineering， 2016， 2016： No.7426913.
7	WAHAB M N AB， NEFTI-MEZIANI S， ATYABI A. A comparative review on mobile robot path planning： classical or meta-heuristic methods？［J］. Annual Reviews in Control， 2020， 50： 233-252.
8	LaVALLE S， KUFFNER J J. Rapidly-exploring random trees： progress and prospects ［M］// DONALD B， LYNCH K， RUS D. Algorithmic and computational robotics： new directions 2000 WAFR. Sarasota， FL： A K Peters/CRC Press， 2001： 303-307.
9	HART P， NILSSON N J， RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths ［J］. IEEE Transactions on Systems Science and Cybernetics， 1968， 4（2）： 100-107.
10	DIJKSTRA E W. A note on two problems in connexion with graphs［M］// APT K R， HOARE T. Edsger Wybe Dijkstra： his life， work， and legacy. New York： ACM， 2022： 287-290.
11	DANIEL K， NASH A， KOENIG S， et al. Theta^*： any-angle path planning on grids ［J］. Journal of Artificial Intelligence Research， 2010， 39： 533-579.
12	陈若男，文聪聪，彭玲，等. 改进A^*算法在机器人室内路径规划中的应用［J］. 计算机应用， 2019， 39（4）： 1006-1011.
	CHEN R N， WEN C C， PENG L， et al. Application of improved A^* algorithm in indoor path planning for mobile robot ［J］. Journal of Computer Applications， 2019， 39（4）： 1006-1011.
13	DORIGO M， GAMBARDELLA L. Ant colony system： a cooperative learning approach to the traveling salesman problem［J］. IEEE Transactions on Evolutionary Computation， 1997， 1（1）： 53-66.
14	TU J， YANG S X. Genetic algorithm based path planning for a mobile robot ［C］// Proceedings of the 2003 IEEE International Conference on Robotics and Automation — Volume 1. Piscataway： IEEE， 2003： 1221-1226.
15	ROBERGE V， TARBOUCHI M， LABONTE G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning ［J］. IEEE Transactions on Industrial Informatics， 2013， 9（1）： 132-141.
16	李二超，齐款款. B样条曲线融合蚁群算法的机器人路径规划［J］. 计算机应用， 2021， 41（12）： 3558-3564.
	LI E C， QI K K. Robot path planning based on B-spline curve and ant colony algorithm ［J］. Journal of Computer Applications， 2021， 41（12）： 3558-3564.
17	邓辅秦，黄焕钊，谭朝恩，等. 结合遗传算法和滚动调度的多机器人任务分配算法［J］. 计算机应用， 2023， 43（12）： 3833-3839.
	DENG F Q， HUANG H Z， TAN C E， et al. Multi-robot task allocation algorithm combining genetic algorithm and rolling scheduling ［J］. Journal of Computer Applications， 2023， 43（12）： 3833-3839.
18	ZHOU C， HUANG B， FRÄNTI P. A review of motion planning algorithms for intelligent robots ［J］. Journal of Intelligent Manufacturing， 2022， 33（2）： 387-424.
19	LaVALLE S M. Rapidly-exploring random trees： a new tool for path planning ［EB/OL］. ［2023-12-12］. .
20	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.
21	BOHLIN R， KAVRAKI L E. Path planning using lazy PRM ［C］// Proceedings of the 2000 IEEE International Conference on Robotics and Automation — Volume 1. Piscataway： IEEE， 2000： 521-528.
22	KARAMAN S， FRAZZOLI E. Sampling-based algorithms for optimal motion planning ［J］. The International Journal of Robotics Research， 2011， 30（7）： 846-894.
23	WEBB D J， VAN DEN BERG J. Kinodynamic RRT*： asymptotically optimal motion planning for robots with linear dynamics ［C］// Proceedings of the 2013 IEEE International Conference on Robotics and Automation. Piscataway： IEEE， 2013： 5054-5061.
24	WANG X， WEI J， ZHOU X， et al. AEB-RRT^： an adaptive extension bidirectional RRT^ algorithm ［J］. Autonomous Robots， 2022， 46（6）： 685-704.
25	GAMMELL J D， SRINIVASA S S， BARFOOT 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.
26	GAMMELL J D， BARFOOT D， SRINIVASA S S. Informed sampling for asymptotically optimal path planning ［J］. IEEE Transactions on Robotics， 2018， 34（4）： 966-984.
27	ISLAM F， NASIR J， MALIK U， et al. RRT^*-Smart： rapid convergence implementation of RRT^∗ towards optimal solution［C］// Proceedings of the 2012 IEEE International Conference on Mechatronics and Automation. Piscataway： IEEE， 2012： 1651-1656.
28	JEONG I B， LEE S J， KIM J H. Quick-RRT^： triangular inequality-based implementation of RRT^ with improved initial solution and convergence rate ［J］. Expert Systems with Applications， 2019， 123： 82-90.
29	CHABRIER A. Vehicle Routing Problem with elementary shortest path based column generation ［J］. Computers and Operations Research， 2006， 33（10）： 2972-2990.
30	LINGELBACH F. Path planning using probabilistic cell decomposition ［C］// Proceedings of the 2004 IEEE International Conference on Robotics and Automation — Volume 1. Piscataway： IEEE， 2004： 467-472.
31	JORDAN M， PEREZ A. Optimal bidirectional rapidly-exploring random trees： MIT-CSAIL-TR-2013-021［R/OL］. ［2024-01-23］..

[1]	Yi RAN, Yongsheng LI, Ye JIANG. Addressing robot path planning issues using S-shaped growth curve integrated grasshopper optimization algorithm [J]. Journal of Computer Applications, 2025, 45(1): 178-185.
[2]	Runze TIAN, Yulong ZHOU, Hong ZHU, Gang XUE. Local information based path selection algorithm for service migration [J]. Journal of Computer Applications, 2024, 44(7): 2168-2174.
[3]	Tian MA, Runtao XI, Jiahao LYU, Yijie ZENG, Jiayi YANG, Jiehui ZHANG. Mobile robot 3D space path planning method based on deep reinforcement learning [J]. Journal of Computer Applications, 2024, 44(7): 2055-2064.
[4]	Jianqiang LI, Zhou HE. Hybrid NSGA-Ⅱ for vehicle routing problem with multi-trip pickup and delivery [J]. Journal of Computer Applications, 2024, 44(4): 1187-1194.
[5]	Haixin HUANG, Guangwei YU, Shoushan CHENG, Chunming LI. Full coverage path planning of bridge inspection wall-climbing robot based on improved grey wolf optimization [J]. Journal of Computer Applications, 2024, 44(3): 966-971.
[6]	Ziyang SONG, Junhuai LI, Huaijun WANG, Xin SU, Lei YU. Path planning algorithm of manipulator based on path imitation and SAC reinforcement learning [J]. Journal of Computer Applications, 2024, 44(2): 439-444.
[7]	Jian SUN, Baoquan MA, Zhuiwei WU, Xiaohuan YANG, Tao WU, Pan CHEN. Joint optimization of UAV swarm path planning and task allocation balance in earthquake scenarios [J]. Journal of Computer Applications, 2024, 44(10): 3232-3239.
[8]	Yongdi LI, Caihong LI, Yaoyu ZHANG, Guosheng ZHANG. Mobile robot path planning based on improved SAC algorithm [J]. Journal of Computer Applications, 2023, 43(2): 654-660.
[9]	Lin HUANG, Qiang FU, Nan TONG. Solving robot path planning problem by adaptively adjusted Harris hawk optimization algorithm [J]. Journal of Computer Applications, 2023, 43(12): 3840-3847.
[10]	Chen LIU, Yang CHEN, Hao FU. UAV path planning for persistent monitoring based on value function iteration [J]. Journal of Computer Applications, 2023, 43(10): 3290-3296.
[11]	Houming FAN, Shuang MU, Lijun YUE. Collaborative optimization of automated guided vehicle scheduling and path planning considering conflict and congestion [J]. Journal of Computer Applications, 2022, 42(7): 2281-2291.
[12]	Sheng CHEN, Jun ZHOU, Xiaobing HU, Ji MA. Optimization of airport arrival procedures based on hybrid simulated annealing algorithm [J]. Journal of Computer Applications, 2022, 42(2): 606-615.
[13]	LI Kairong, LIU Shuang, HU Qianqian, TANG Yiyuan. Improved ant colony optimization algorithm for path planning based on turning angle constraint [J]. Journal of Computer Applications, 2021, 41(9): 2560-2568.
[14]	TANG Andi, HAN Tong, XU Dengwu, XIE Lei. Path planning method of unmanned aerial vehicle based on chaos sparrow search algorithm [J]. Journal of Computer Applications, 2021, 41(7): 2128-2136.
[15]	ZHANG Kang, CHEN Jianping. Path planning algorithm in complex environment using self-adjusting sampling space [J]. Journal of Computer Applications, 2021, 41(4): 1207-1213.