基于改进RRT*算法的城市低空路径规划方法研究

doi:10.12082/dqxxkx.2022.210413

摘要/Abstract

摘要：

随着无人机监测、巡查和测绘等低空技术得到广泛应用,低空长距离空中路径规划成为低空航空器应用面临的一个挑战。而传统快速扩展随机树（Rapidly-Exploring Random Trees/RRT）及其改进算法在大范围长距离低空三维空间下面临计算效率慢的问题,对此,本文提出一种带有R树空间索引的双向启发式RRT*算法,该算法在双向RRT*算法基础上为随机采样过程设置了启发函数,使得在面对狭小城市障碍物之间空隙时,能够避免局部最小值情况的出现。在此基础上为城市障碍物建立R树空间索引,减少了海量障碍物情况下碰撞检测的时间,提高了低空长距离空中路径规划效率。此外,为了得到更加符合无人机运动规律的路径,提高算法的实用性,在采样过程中设置转弯阈值控制转弯角度,并且对规划结果路径使用3次B-spline函数进行路径平滑。最后在武汉市三维城市场景中,利用武汉市建筑物数据进行了实验,实验证明相比已有算法,本文提出的带有R树空间索引的双向启发式RRT*算法相比较RRT算法和双向RRT*算法在500 m、 2000 m、 10 000 m不同距离下规划时间均降低了90%以上;采样次数相比RRT算法在不同距离下分别降低了51.6%、75%、86.7%,相比双向RRT*算法在不同距离下分别降低了20%、24.7%、57.3%;转弯次数相比RRT算法在不同距离下分别降低了77.3%、73.5%、78.3%,相比双向RRT*算法在不同距离下分别降低了37.5%、30.8%、16.8%;同时带有R树空间索引的双向启发式RRT*算法得到的结果路径长度相比其他2种算法也有缩短。该算法应用于低空长距离空中路径规划能够有效提高计算效率,降低规划时间,减少采样次数,缩短结果路径,减少转弯次数,丰富无人机的应用场景。

关键词: 三维RRT, RRT*, 双向RRT, 双向RRT*, R树索引, 空中路径规划, 碰撞检测, B-spline曲线, 三维城市

Abstract:

With the wide application of Unmanned Aerial Vehicle (UAV) monitoring, inspection, mapping, and other low-altitude technologies, low-altitude and long-distance aerial path planning has become a great challenge for low-altitude aircraft applications. However, the traditional Rapidly Exploring Random Trees (RRT) and its improved algorithm face the problem of slow computational efficiency in a large-range, long-distance, low-elevation three-dimensional space. Therefore, a bidirectional heuristic RRT* algorithm with R-tree spatial index is proposed in this paper. Based on the bidirectional RRT* algorithm, the heuristic function is set for random sampling process to avoid the occurrence of local minimum when facing the gap between small urban obstacles. On this basis, R tree spatial index is established for urban obstacles, which reduces the time of collision detection in the case of massive obstacles and improves the efficiency of low altitude and long distance air path planning. In addition, in order to obtain a path more in line with the motion law of unmanned aerial vehicle and improve the practicability of the algorithm, a turning threshold is set in the sampling process to control the turning angle to prevent it from being too large, and the planning result path is smoothed by using the cubic B-spline function. Finally, in the three-dimensional city scene of Wuhan, the experiment is carried out using the 3D building data of Wuhan. The experiment results show that, compared with RRT algorithm and bidirectional RRT* algorithm, the planning time of the two-way heuristic RRT* algorithm with R-tree spatial index is reduced by more than 90% at different distances, i.e., 500 m, 2000 m, and 10 000 m. Compared to RRT algorithm, the sampling time is reduced by 51.6%, 75%, and 86.7%, respectively, at different distances; and compared to bidirectional RRT* algorithm, the sampling time is reduced by 20%, 24.7%, and 57.3%, respectively, at different distances. Compared to RRT algorithm, the turning time is reduced by 77.3%, 73.5%, and 78.3%, respectively, at different distances; and compared to bidirectional RRT * algorithm, it is reduced by 37.5%, 30.8%, and 16.8%, respectively, at different distances. The result path length of the bidirectional heuristic RRT * algorithm with R-tree spatial index is also shorter than that of the other two algorithms. Our algorithm applied to low-altitude long-distance air path planning can effectively improve the calculation efficiency and reduce the planning time, reduce sampling times, shorten the result path, reduce the swerve times, and enrich the application scenarios of unmanned aerial vehicle.

Key words: three-dimensional RRT, RRT*, bidirectional RRT, bidirectional RRT*, R-tree index, air path planning, collision detection, B-spline curve, three-dimensional city

李逸斐, 陈静. 基于改进RRT*算法的城市低空路径规划方法研究[J]. 地球信息科学学报, 2022, 24(3): 448-457.DOI:10.12082/dqxxkx.2022.210413

LI Yifei, CHEN Jing. Research on Urban Low-altitude Path Planning Method based on Improved RRT* Algorithm[J]. Journal of Geo-information Science, 2022, 24(3): 448-457.DOI:10.12082/dqxxkx.2022.210413

图/表 17

图1

图2

图3

表1

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

表2

参考文献 22

[1]	赵晓, 王铮, 黄程侃, 等. 基于改进A*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6):903-910. doi: 10.13973/j.cnki.robot.170591
	[ Zhao X A, Wang Z, Huang C K, et al. Mobile robot path planning based on an improved A* algorithm[J]. Robot, 2018, 40(6):903-910. ] DOI: 10.13973/j.cnki.robot.170591
[2]	唐志荣, 冀杰, 吴明阳, 等. 基于改进人工势场法的车辆路径规划与跟踪[J]. 西南大学学报(自然科学版), 2018, 40(6):174-182.
	[ Tang Z R, Ji J, Wu M Y, et al. Vehicle path planning and tracking based on improved artificial potential field method[J]. Journal of Southwest University (Natural Science), 2018, 40(6):174-182. ] DOI: 10.13718/j.cnki.xdzk.2018.06.025
[3]	谭建豪, 肖友伦, 刘力铭, 等. 改进PRM算法的无人机航迹规划[J]. 传感器与微系统, 2020, 39(1):38-41.
	[ Tan J H, Xiao Y L, Liu L M, et al. Improved PRM algorithm for uav flight path planning[J]. Sensors and Microsystems, 2020, 39(1):38-41. ] DOI: 10.13873/J.1000-9787(2020)01-0038-04
[4]	Lavalle S M, Rapidly-exploring random trees: A new tool for path planning[D]. Ames: Iowa State University, 1998.
[5]	Karaman S, Frazzoli E. Incremental sampling-based algorithms for optimal motion planning[J]. Robotics: Science and Systems, 2011, 6:267-274. DOI: 10.15607/RSS.2010.VI.034
[6]	Klemm S, Oberländer J, Hermann A, et al. RRT -Connect: Faster, asymptotically optimal motion planning[C]// 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO). IEEE, 2015:1670-1677. DOI: 10.1109/ROBIO.2015.7419012
[7]	Islam F, Nasir J, Malik U, et al. RRT -Smart: Rapid convergence implementation of RRT towards optimal solution[C]// 2012 IEEE International Conference on Mechatronics and Automation. IEEE, 2012:1651-1656. DOI: 10.1109/ICMA.2012.6284384
[8]	Wu J F, Wang H L, Li N, et al. Path planning for solar-powered UAV in urban environment[J]. Neurocomputing, 2018, 275:2055-2065. DOI: 10.1016/j.neucom.2017.10.037 doi: 10.1016/j.neucom.2017.10.037
[9]	Maiouak M, Taleb T. Dynamic maps for automated driving and UAV geofencing[C]//IEEE Wireless Communications. IEEE:54-59. DOI: 10.1109/MWC.2019.1800544
[10]	Kuffner J J, LaValle S M. RRT-connect: An efficient approach to single-query path planning[C]// Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065). IEEE, 2000:995-1001. DOI: 10.1109/ROBOT.2000.844730
[11]	Akgun B, Stilman M. Sampling heuristics for optimal motion planning in high dimensions[C]// 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2011:2640-2645. DOI: 10.1109/IROS.2011.6095077
[12]	Urmson C, Simmons R. Approaches for heuristically biasing RRT growth[C]// Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003)(Cat. No.03CH37453). IEEE, 2003:1178-1183. DOI: 10.1109/IROS.2003.1248805
[13]	Gammell J D, Srinivasa S S, Barfoot T D. Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]// 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2014:2997-3004. DOI: 10.1109/IROS.2014.6942976
[14]	司徒华杰, 雷海波, 庄春刚. 动态环境下基于人工势场引导的RRT路径规划算法[J]. 计算机应用研究, 2021, 38(3):714-717,724.
	[ Situ H J, Lei H B, Zhuang C G. Artificial potential field based RRT algorithm for path planning in dynamic environment[J]. Application Research of Computers, 2021, 38(3):714-717,724. ] DOI: 10.19734/jissn.1001-3695.2020.02.0044
[15]	刘艳, 马劲松, 张永玉. 三维GIS中R树空间索引研究[J]. 测绘科学, 2010, 35(1):167-168.
	[ Liu Y, Ma J S, Zhang Y Y. Studies on R-tree spatial index for 3D GIS[J]. Science of Surveying and Mapping, 2010, 35(1):167-168. ] DOI: 10.16251/j.cnki.1009-2307.2010.01.056
[16]	龚俊, 朱庆, 张叶廷, 等. 顾及多细节层次的三维R树索引扩展方法[J]. 测绘学报, 2011, 40(2):249-255.
	[ Gong J, Zhu Q, Zhang Y T, et al. An efficient 3D R-tree extension method concerned with levels of detail[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(2):249-255. ] DOI: CNKI:SUN:CHXB.0.2011-02-022
[17]	于安斌, 梅文胜. 一种R树与格网结合的海量地铁隧道点云管理方法[J]. 武汉大学学报·信息科学版, 2019, 44(10):1553-1559.
	[ Yu A B, Mei W S. An efficient management method for massive point cloud data of metro tunnel based on R-tree and grid[J]. Geomatics and Information Science of Wuhan University, 2019, 44(10):1553-1559. ] DOI: 10.13203/j.whugis20170419
[18]	Wu X J, Xu L, Zhen R, et al. Biased sampling potentially guided intelligent bidirectional RRT algorithm for UAV path planning in 3D environment[J]. Mathematical Problems in Engineering, 2019, 2019:1-12. DOI: 10.1155/2019/5157403
[19]	Yu M, Luo J J, Wang M M, et al. Spline-RRT: Coordinated motion planning of dual-arm space robot[J]. IFAC-PapersOnLine, 2020, 53(2):9820-9825. DOI: 10.1016/j.ifacol.2020.12.2685 doi: 10.1016/j.ifacol.2020.12.2685
[20]	Wen N F, Zhang R B, Liu G Q, et al. Online planning low-cost paths for unmanned surface vehicles based on the artificial vector field and environmental heuristics[J]. International Journal of Advanced Robotic Systems, 2020, 17(6):172988142096907. DOI: 10.1177/1729881420969076
[21]	刘奥博, 袁杰. 目标偏置双向RRT*算法的机器人路径规划[J/OL]. 计算机工程与应用:1-8[2021-09-07].
	[ Liu A B, Yuan J. Robot path planning with target bias bidirectional RRT* algorithm[J/OL]. Computer Engineering and Applications: 1-8[2021-09-07].]
[22]	王嘉琦. 基于改进RRT^*算法的无人机避障路径规划[D]. 南昌:南昌航空大学, 2019.
	[ Wang J Q. Obstacle avoidance path planning for UAV based on improved RRT^* algorithm[D]. Nanchang: Nanchang Hangkong University, 2019.]

字段说明	类型
障碍物ID	int
底面包围盒左上角点坐标	float
底面包围盒右上角点坐标	float
底面包围盒右下角点坐标	float
底面包围盒左下角点坐标	float
底面MBR最小横纵坐标	float
底面MBR最大横纵坐标	float
障碍物高度H	int

算法1 带有R树空间索引的双向启发式RRT： (T_a,T_b) ← bid-RRT-h (N_init, N_goal)
	T_a ← InitializeTree (N_init); E_a ← Ø; T_b ← InitializeTree (N_goal); E_b ← Ø;
	for i=0 to i=n do
	N_rand ← Sample-h (q, V) ;
	(X_new, E_a) ← Extend (T_a, N_rand) ;
	Obs ← Index(X_new);
	if (CollisionFree(X_new, E_a, Obs) = true) then
	(P_near, U) ← Near(T_a, X_new,r);
	P_min ← Exparent(P_near, X_new);
	T_a ← Rewire(T_a, P_near, P_min, X_new);
	if (Angle(P_near) = true) then
	Delete(X_new);
	if (Connect(T_a, T_b) = true) then
	return(T_a, T_b);
	Swap(T_a,T_b);
	return failure

距离/km	RRT算法				双向RRT*算法				带有R树空间索引的双向启发式RRT*算法
距离/km	规划时间/s	采样次数/次	路径长度/m	转弯次数/次	规划时间/s	采样次数/次	路径长度/m	转弯次数/次	规划时间/s	采样次数/次	路径长度/m	转弯次数/次
500	258.3	124	554.96	22	593.4	75	532.86	8	1.24	60	520.37	5
2000	1957.8	341	2681.24	34	6827.7	113	2219.74	13	5.16	85	2081.63	9
10 000	8456.2	1386	14 309.21	46	38 546.5	297	10 522.79	12	13.48	184	10 472.51	10