基于节点到障碍物距离的自适应扩展RRT*路径规划算法

doi:10.11772/j.issn.1001-9081.2024030400

《计算机应用》唯一官方网站 ›› 2025, Vol. 45 ›› Issue (3): 920-927.DOI: 10.11772/j.issn.1001-9081.2024030400

基于节点到障碍物距离的自适应扩展RRT^*路径规划算法

王蔡琪, 崔西宁, 熊毅, 伍世虔()

武汉科技大学信息科学与工程学院，武汉 430081

收稿日期:2024-04-08 修回日期:2024-06-29 接受日期:2024-07-03 发布日期:2024-08-01 出版日期:2025-03-10
通讯作者: 伍世虔
作者简介:王蔡琪（2000—），男，湖北荆门人，硕士研究生，主要研究方向：智能机器人
崔西宁（1996—），男，山东聊城人，博士研究生，主要研究方向：智能机器人
熊毅（2000—），男，湖北荆州人，硕士研究生，主要研究方向：智能机器人
基金资助:
湖北省技术创新专项(ZDCX2019000025)

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

Caiqi WANG, Xining CUI, Yi XIONG, Shiqian WU()

School of Information Science and Engineering，Wuhan University of Science and Technology，Wuhan Hubei 430081，China

Received:2024-04-08 Revised:2024-06-29 Accepted:2024-07-03 Online:2024-08-01 Published:2025-03-10
Contact: Shiqian WU
About author:WANG Caiqi， born in 2000， M. S. candidate. His research interests include intelligent robot.
CUI Xining， born in 1996， Ph. D. candidate. His research interests include intelligent robot.
XIONG Yi， born in 2000， M. S. candidate. His research interests include intelligent robot.
Supported by:
Hubei Key Technical Innovation Project(ZDCX2019000025)

摘要/Abstract

摘要：

快速扩展随机树星（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%。

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

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

中图分类号:

TP242.6

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

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.

图/表 17

表1 符号的定义

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$ 的父节点

表1 符号的定义

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$ 的父节点

图1 AE-RRT*的流程

Fig. 1 Flow of AE-RRT*

图2 Sigmoid函数和平移后的Sigmoid函数

Fig. 2 Sigmoid function and translated Sigmoid function

图3 动态扩展步长

Fig. 3 Dynamic extended step size

图4 父节点选择过程

Fig. 4 Process of parent node choice

图5 自适应高斯采样过程

Fig. 5 Process of adaptive Gaussian sampling

图6 仿真实验地图

Fig. 6 Maps for simulations

图7 RRT*使用不同步长在不同地图上的收敛曲线

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

表2 不同算法在3种地图上寻找初始路径的仿真实验结果

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

图8 单通道地图的仿真实验结果

Fig. 8 Simulation results of single channel map

图9 多通道地图的仿真实验结果

Fig. 9 Simulation results of multi-channel map

图10 散乱地图的仿真实验结果

Fig. 10 Simulation results of scattered map

图11 自适应高斯采样的仿真实验效果

Fig. 11 Simulation effects of adaptive Gaussian sampling

图12 二维环境下的路径收敛曲线

Fig. 12 Path convergence curves in 2D environments

表3 收敛至全局次优路径的平均时间 (s)

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

图13 三维仿真实验结果

Fig. 13 Simulation results in 3D environment

表4 三维环境中的仿真实验结果

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

参考文献 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]	冉义, 李永胜, 蒋烨. 基于S型生长曲线的蝗虫优化算法求解机器人路径规划问题[J]. 《计算机应用》唯一官方网站, 2025, 45(1): 178-185.
[2]	田润泽, 周宇龙, 朱洪, 薛岗. 基于局部信息的服务迁移路径选择算法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2168-2174.
[3]	马天, 席润韬, 吕佳豪, 曾奕杰, 杨嘉怡, 张杰慧. 基于深度强化学习的移动机器人三维路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2055-2064.
[4]	李建强, 何舟. 面向多行程取送货车辆路径问题的混合NSGA-Ⅱ[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1187-1194.
[5]	黄海新, 于广威, 程寿山, 李春明. 基于改进灰狼优化的桥梁检测爬壁机器人全覆盖路径规划[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 966-971.
[6]	宋紫阳, 李军怀, 王怀军, 苏鑫, 于蕾. 基于路径模仿和SAC强化学习的机械臂路径规划算法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 439-444.
[7]	邓辅秦, 官桧锋, 谭朝恩, 付兰慧, 王宏民, 林天麟, 张建民. 基于请求与应答通信机制和局部注意力机制的多机器人强化学习路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 432-438.
[8]	邓辅秦, 谭朝恩, 黎俊炜, 钟家铭, 付兰慧, 张建民, 王宏民, 李楠楠, 姜炳春, 林天麟. 面向大型仓储环境的基于冲突搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3854-3860.
[9]	孙鉴, 马宝全, 吴隹伟, 杨晓焕, 武涛, 陈攀. 地震场景下无人机群路径规划与任务分配均衡联合优化[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3232-3239.
[10]	李永迪, 李彩虹, 张耀玉, 张国胜. 基于改进SAC算法的移动机器人路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 654-660.
[11]	王龙宝, 栾茵琪, 徐亮, 曾昕, 张帅, 徐淑芳. 基于动态簇粒子群优化的无人机集群路径规划方法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3816-3823.
[12]	黄霖, 符强, 童楠. 基于自适应调整哈里斯鹰优化算法求解机器人路径规划问题[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3840-3847.
[13]	刘晨, 陈洋, 符浩. 基于值函数迭代的持续监测无人机路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3290-3296.
[14]	范厚明, 牟爽, 岳丽君. 考虑冲突和拥堵的自动导引车调度与路径规划协同优化[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2281-2291.
[15]	陈昇, 周隽, 胡小兵, 马霁. 基于混合模拟退火算法的机场进场程序优化[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 606-615.

基于节点到障碍物距离的自适应扩展RRT^*路径规划算法

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 17

参考文献 31

相关文章 15

编辑推荐

Metrics

基于节点到障碍物距离的自适应扩展RRT*路径规划算法

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 17

参考文献 31

相关文章 15

编辑推荐

Metrics

基于节点到障碍物距离的自适应扩展RRT^*路径规划算法

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