EN中文

Journal of Geo-information Science >

2022 , Vol. 24 >Issue 3: 448 - 457

DOI: https://doi.org/10.12082/dqxxkx.2022.210413

Research on Urban Low-altitude Path Planning Method based on Improved RRT* Algorithm

  • LI Yifei ,
  • CHEN Jing , *
Expand
  • State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan 430072, China
*CHEN Jing, E-mail:

Received date: 2021-07-19

  Request revised date: 2021-09-21

  Online published: 2022-05-25

Supported by

National Key Research and Development Program of China(2018YFB0505302)

Copyright

Copyright reserved © 2022
Fold

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

Cite this article

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

1 引言

空中路径规划主要是指在空间中指定起点终点,寻找一条最优（最短）路径从给定起点出发,避开空间中障碍物,到达终点的过程。随着无人机监测、巡查和测绘等低空技术得到广泛应用,如何针对低空长距离复杂三维环境快速规划出最优或可行低空路径成为3DGIS重要的研究内容之一。
常见的路径规划算法有很多,如A*算法,人工势场算法,PRM算法等[1,2,3],但是在三维空间下上述算法均需要对规划空间进行函数建模来完成路径规划,针对复杂的低空环境需要进行大量复杂的计算。快速扩展随机树（Rapidly-Exploring Random Trees/RRT）是由Lavalle等[4]首先提出的一种基于随机采样点的路径规划算法,针对复杂的高维环境,RRT算法不需要对规划空间进行函数表达,可以通过对采样点进行碰撞检测来避开障碍物,从而快速规划出由节点和节点间连线组成地有效飞行路径。后续也有研究学者针对RRT算法的缺点和不足提出了很多改进方法,例如通过迭代计算出最优路径的RRT*算法[5],以起点和终点的连线为基准从起点终点同时扩展随机树的RRT*-connect算 法[6],通过智能采样优化结果路径的RRT*-smart算法[7]等。针对城市地区复杂环境下的无人机路径规划也有很多算法,如鲸鱼优化算法（Whale Optimization Algorithm/WOA）[8],地理围栏算法[9]等。但是目前相关算法一般用于短距离、小范围、模拟障碍物较少,面对大范围、长距离、海量障碍物的情况现有的算法会因为障碍物较多、环境复杂、节点过多导致规划过程计算资源消耗变大,规划速度变慢。
对此,针对上述问题结合已有的研究方法,本文在双向RRT*算法的基础上,提出一种带有R树空间索引的双向启发式RRT*算法,该方法在原本的采样过程中加入启发函数,用概率偏置采样取代原本的随机采样,并且为规划环境内的障碍物建立空间数据索引,从而降低规划过程计算资源消耗,缩短规划时间。

2 研究方法

2.1 双向RRT*算法

RRT算法在路径规划中以其众多优点而得到了广泛的应用,其算法的有效性和完备性得到了诸多学者的论证。针对RRT算法的缺点有多种改进算法,其中2002年由J.Kuffner和M.LaValle提出的双向RRT[10]算法分别从起点和终点同时扩展随机树,可以快速得到规划路径;2011年由Karaman和Frazzoli提出的RRT*算法通过对已有路径的迭代计算,在采样点附近进行父节点重选和节点间重新布线得到规划路径的渐进最优解;同年由Akgun和Stilman等[11]提出的双向RRT*算法综合了双向RRT算法和RRT*算法2种算法的优势,提升RRT*算法的速度。
然而,双向RRT*算法虽然能够得到渐进最优的结果路径,但是面对狭小的障碍物间空隙不容易快速绕出,如图1中蓝色和青色折线所示,随机树进行了很多次采样才从障碍物中间穿过。低空环境中障碍物众多且密集,随着规划距离增长,双向RRT*算法消耗的内存变多,规划时间变长,规划效率变低。
图1 模拟低空环境下双向RRT*算法规划结果

Fig. 1 Simulation results of bidirectional RRT* algorithm planning in low altitude environment altitude environment

2.2 带有R树空间索引的双向启发式RRT*算法

面对RRT*算法的缺陷,研究学者们提出了许多解决办法,包括：① 为随机采样过程添加偏置函数[12]。② 为已有的结果路径添加偏置函数[13]。 ③ 与其它规划算法的结合[14]。其中第①种方法对比后2种方法较为灵活,针对不同的规划环境可以选择不同的偏置函数。
对此,本文在第一种方法的基础上,针对原有的RRT及其改进算法无法从障碍物间快速绕出,且随着规划距离增加,规划时间增长,计算资源消耗增大,规划效率降低等问题。本文提出一种带有R树空间索引的双向启发式RRT*算法,该算法在采样过程中选择使用启发函数进行偏置采样,在此基础上为障碍物建立R树空间索引,从而加快规划时间,提升规划效率,最后,对规划结果路径进行平滑处理,增强算法的实用性。方法总体流程如图2所示。
图2 低空长距离空中路径规划方法总体流程

Fig. 2 General flow of low altitude long distance air path planning method

2.2.1 城市环境中障碍物数据组织方法
为了组织带有R树空间索引的障碍物数据,首先根据障碍物数据计算底面包围盒和MBR（Minimum Bounding Rectangle,最小外包矩形表示面要素坐标范围）存储起来,然后为障碍物建立R树空间索引,为后续节点的碰撞检测做准备。
（1）城市环境中障碍物数据存储
低空环境下障碍物种类多,形状复杂,而在三维城市环境中,主要障碍物有建筑物、人行路、电线电缆等。本文对于建筑物采用二维底图和高度信息进行三维建模,如图3（a）和（b）所示,分别计算每个棱柱的包围盒组合形成障碍物,计算结果如图3（c）所示。对于人行路和电线电缆,根据其特征数据进行建模和包围盒计算,其过程和建筑物一致。
图3 障碍物包围盒计算过程

Fig. 3 Obstacle enveloping box calculation process

在进行大范围低空路径规划时,无需进行非常精确的空间计算,为了提高计算效率,本文根据带有高度信息的建筑物底面图形文件分别计算底面包围盒和MBR,作为建筑物的三维模型信息,并且以表1的形式进行储存,其中角点坐标为横轴墨卡托投影坐标系下的坐标,建筑物高度单位为m。针对图3所示的复杂建筑物储存为2个不同的障碍物分别储存。人行路、电线电缆的三维模型信息储存过程和储存结构与建筑物一致。
表1 障碍物信息存储结构

Tab. 1 Obstacle information storage structure

字段说明 类型
障碍物ID int
底面包围盒左上角点坐标 float
底面包围盒右上角点坐标 float
底面包围盒右下角点坐标 float
底面包围盒左下角点坐标 float
底面MBR最小横纵坐标 float
底面MBR最大横纵坐标 float
障碍物高度H int
（2） 障碍物对象R树空间索引
R树在三维GIS中数据储存,数据管理等方面应用广泛,同时R树空间索引能够方便地建立障碍物索引,实现快速高维空间搜索[15,16,17]。
大范围长距离空中路径规划计算资源消耗大,规划时间长,其主要原因为环境中障碍物多,无法将障碍物信息全部读入内存进行空间计算,如果不进行优化,节点进行碰撞检测时,需要和所有障碍物进行检测,导致计算时间过长。
因此,为了提高低空长距离空中路径规划速度,需要加快节点碰撞检测的计算效率。由此,如何在大量障碍物信息中快速检索需要计算的障碍物信息,进行快速计算,是需要解决的关键问题之一。
为此,对障碍物的底面建立二维R树空间索引,进行碰撞点检测时,如2.2所述,需要带有高度信息的障碍物底面数据,只需要搜索采样点周围2 m×2 m的“窗口“内障碍物底面包围盒的索引,根据索引将建筑物底面数据读入内存,进行碰撞检测。R树示意图如图4所示,其中R树中叶节点存储的范围为建筑物底面MBR范围,即红色矩形范围,索引障碍物过程如图5所示。
图4 障碍物建立R树索引

Fig. 4 Obstacle building R-tree

图5 R树索引检索障碍物

Fig. 5 R-tree index retrieves obstacles

2.2.2 节点碰撞检测方法
面对低空长距离规划环境下海量障碍物,对每一个需要碰撞检测的节点进行以下2个步骤：
（1）判断节点在底面的投影点是否在障碍物底面包围盒范围内,如果不在包围盒范围内则节点不和该障碍物发生碰撞,如果在包围盒范围内进行第二步。
（2）判断节点高度是否在障碍物高度区间内,如果不在障碍物高度范围内则节点不和该障碍物发生碰撞,如果在障碍物高度范围内则发生碰撞,重新采样。
碰撞检测过程示意图如图6所示。其中判断投影点是否在障碍物底面包围盒范围内的过程如图7所示,首先将需要进行检测的障碍物数据读入内存,根据底面包围盒顶点坐标计算障碍物底面4条直线的方程f（x,y）= 0。每条相对直线为一组,将节点投影点坐标分别代入2条直线的方程,将代入结果相乘,乘积为负则代表采样点在这一组直线异侧,反之在这一组直线同侧。如果节点代入计算后,同时在2组直线的异侧,则判断节点在障碍物区域内。如果节点在障碍物区域内且节点高度在建筑物地面高度和顶面高度区间内,则发生碰撞,否则不发生碰撞。
图6 采样点碰撞检测过程

Fig. 6 Collision detection process of sampling points

图7 判断投影点是否在包围盒范围内

Fig. 7 Determine whether the projection point is within the bounding box

节点碰撞检测方法用公式表示如式（1）所示。
R x = 1 f m x p , y p * f n x p , y p < 0 ⋂ f d x p , y p * f e x p , y p < 0 ⋂ z p ∈ h 0 f m x p , y p * f n x p , y p > 0 ⋃ f d x p , y p * f e x p , y p > 0 ⋃ z p ∉ h
式中：R(x)表示节点和障碍物的碰撞关系,R(x)=1表示发生碰撞R(x)=0则表示不发生碰撞;fm,fn,fe,fd代表4条直线;xp,yp表示节点经纬度坐标;h表示障碍物高度区间,zp表示采样点高度。

2.3 带有R树空间索引的双向启发式RRT*算法

随机树算法在面对复杂环境时如果障碍物之间只有狭小的空隙,由于其扩展的“随机性”,无法快速准确地绕出。面对双向RRT*算法的局限性,本文利用启发函数进行偏置采样,从而实现快速从障碍物中间穿过,降低规划时间,提高规划效率。带有R树空间索引的双向启发式RRT*算法在规划前设置一个采样阈值,规划过程中在采样前生成一个取值范围在（0,1）的伪随机数,当随机数大于采样阈值时进行偏置采样,小于采样阈值时进行随机采样,即概率偏置采样。其中,通过启发函数进行偏置采样的过程如下：
（1）初始化当前节点坐标为P(x0, y0, z0),通过3.2节中建立的R树索引找到距离P点最近的障碍物Obstacle,得到障碍物底面包围盒4个角点坐标C1(x1, y1),C2 (x2, y2),C3 (x3, y3),C4(x4, y4)。
（2）计算P点在底面投影点D(x0, y0)到4个角点的欧氏距离d1,d2,d3,d4,通过比较得出距离点D点最近的角点C(x, y)。
（3）得到距离最近的角点后,将P点高度赋予最近角点C,得到新的采样点坐标P1(x, y, z0),将其带入传统RRT*算法中延伸随机树和碰撞检测得到新的节点,并将新节点作为当前节点继续进行采样。
（4）每次触发启发函数时重复上述步骤。
如图8所示,启发式采样可以很好地避开障碍物,且选择包围盒角点也避免了和障碍物发生碰撞。当采样次数大于等于3时,根据得到新节点、当前节点、当前节点父节点计算路径在当前节点处的角度,当角度小于一个阈值时将新节点舍弃重新采样,当角度大于该阈值时将新节点加入随机树并重新采样。
图8 双向启发式RRT*算法示意图

Fig. 8 Schematic diagram of heuristic RRT * algorithm

带有R树空间索引的双向启发式RRT* 算法伪码如下：
算法1 带有R树空间索引的双向启发式RRT*：
(Ta,Tb) ← bid-RRT*-h (Ninit, Ngoal)
Ta ← InitializeTree (Ninit); Ea ← Ø;
Tb ← InitializeTree (Ngoal); Eb ← Ø;
for i=0 to i=n do
Nrand ← Sample-h (q, V) ;
(Xnew, Ea) ← Extend (Ta, Nrand) ;
Obs ← Index(Xnew);
if (CollisionFree(Xnew, Ea, Obs) = true) then
(Pnear, U) ← Near(Ta, Xnew,r);
Pmin ← Exparent(Pnear, Xnew);
Ta ← Rewire(Ta, Pnear, Pmin, Xnew);
if (Angle(Pnear) = true) then
Delete(Xnew);
if (Connect(Ta, Tb) = true) then
return(Ta, Tb);
Swap(Ta,Tb);
return failure
其中,Ninit,Ngoal分别表示起点终点;i表示采样次数;Ta,Tb分别表示从起点和终点开始扩展的随机树;Ea,Eb表示随机树节点间的连线;Xnew表示加入随机树的新节点,q表示判断是否进行偏置采样生成的随机数;Obs表示根据R树空间索引检索出的障碍物集合。其中和双向RRT*算法的主要区别在第3步和第5步,第3步为采样添加了启发函数,第5步通过索引找到需要进行碰撞检测的建筑物。带有R树空间索引的双向启发式RRT*算法流程图如图9所示。
图9 带有R树空间索引的双向启发式RRT*算法流程

Fig. 9 Flow chart of bidirectional heuristic RRT* algorithm with R tree spatial index

2.4 规划结果路径平滑

根据带有R树空间索引的双向启发式RRT*算法得到的结果路径虽然相比较RRT算法和双向RRT*算法更加简短,但是仍然不符合无人机运动规律,需要对结果路径进行平滑,增强算法的实 用性。
B-spline曲线在路径规划方面应用广泛[18,19]。B-spline曲线可以将路径中的节点作为控制点生成连续平滑的曲线。K次B-spline函数公式如式(2)所示。
C ( u ) = ∑ i = 0 n B i , k u P i , ( i = 1,2 , … , n )
式中：Pi为曲线的控制点,Bi,k(u)为K次B-spline基函数,u=[u0, u1, …, un+k+1]为节点向量。最常用的三次B-spline曲线的基函数Bi,3(u)如式(3)所示。由于平滑后的路径和原路径在转点有一些差别,为了防止平滑后的路径和障碍物发生碰撞,因此只选择转点附近一小段路径进行平滑。路径平滑结果如图10所示。
b 0 = 1 6 ( - u 3 + 3 u 2 - 3 u + 1 ) b 1 = 1 6 ( 3 u 3 - 6 u 2 + 4 ) b 2 = 1 6 - 3 u 3 + 3 u 2 + 3 u + 1 b 3 = 1 6 u 3
图10 路径平滑结果

Fig. 10 Path smoothing results

3 实验与分析

本文的实验环境中硬件为：Inter(R) Xeon(R) CPU E3-1240 v6 @3.70GHz,软件采用：Windows 10,Cesium 1.75以及 Python 3.9.2。Cesium是一个基于JavaScript编写的跨平台展示三维地球和地图的可视化平台。为了验证本文所提出算法的有效性,本实验在三维空间下对RRT;双向RRT*;带有R树空间索引的双向启发式RRT*这3种算法在大范围长距离空间下进行了对比试验。首先在Open Street Map（OSM/ https://www.openstreetmap.org）中下载shp格式的武汉市建筑物矢量数据,经过数据清洗后收集到武汉市165 378栋建筑物的位置和高度数据,其中最高的建筑物204 m,最低的建筑物3 m,建筑物高度平均数为13.756 m,中位数为9 m。分别计算建筑物底面包围盒和MBR,将包围盒角点、MBR、高度数据按3.2数据组织部分描述的结构储存。
小型无人机一般飞行距离为2~5 km,因此10 km即为长距离的无人机飞行。对此,本文实验选择了相同起点,距离起点分别为500,2000,10 000 m的终点进行实验,步长分别为10,40,200 m,启发函数阈值为0.5,最大迭代次数均为20 000次,路径规划高度范围为10 ~50 m,且设定了10 m的高度令无人机进行起飞降落。其中,启发函数阈值选择参考了相关文献[20,21,22],当阈值小于0.5时,随着阈值的增加,规划时间减少,规划效率提升;阈值等于0.5时,规划结果达到最优;当阈值大于0.5时,随着阈值增加,规划时间增加,规划效率降低。建筑物在Cesium 1.75中建模后效果如图11所示,其中建筑物依据不同高度绘制为5种不同颜色,如图11中图例所示,不同算法在不同长度距离下规划结果如图12—图14所示。底图为Bing Map Aerial,蓝色星表示规划起点,红色三角表示不同距离的规划终点,黄色折线即为平滑后的规划结果。不同算法在距离不同情况下的规划时间和路径长度和采样点个数如表2所示。
图11 武汉市三维建筑物场景

Fig. 11 3D building scene map of wuhan city Part of building data in Wuhan

图12 直线距离500 m三种算法规划结果

Fig. 12 Planning results of three algorithms for linear distance 500 m

图13 直线距离2000 m三种算法规划结果

Fig. 13 Planning results of three algorithms for linear distance 2000 m

图14 直线距离10 000 m三种算法规划结果

Fig. 14 Planning results of three algorithms for linear distance 10000 m

表2 三种算法在不同距离下的规划时间、采样次数、路径长度和转弯次数

Tab. 2 Planning time,iteration times, Number of path nodes and Turning times of three algorithms under different distances

距离/km RRT算法 双向RRT*算法 带有R树空间索引的双向
启发式RRT*算法
规划
时间/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
通过分析不同算法在不同距离下的规划结果可知,带有R树空间索引的双向启发式RRT*算法相比较RRT算法和双向RRT*算法在不同距离下规划时间均降低了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*算法得到的结果路径长度相比其他两种算法也有缩短。综上所述,带有R树空间索引的双向启发式RRT*算法能够有效提高规划效率,适合低空长距离的空中路径规划。

4 结论

本文提出了一种带有R树空间索引的双向启发式RRT*算法,针对传统算法面对低空长距离海量障碍物的规划场景规划速度慢,计算效率低的情况,进行了以下几点改进：
（1）为障碍物建立二维空间R树索引。低空长距离中存在着大量障碍物,为障碍物建立R树索引可以减少随机树节点每次碰撞检测的时间,提高路径规划的计算效率。
（2）为采样过程添加启发函数。通过添加启发函数增加采样过程的“目的性”,使得随机树可以快速从障碍物之间狭小的缝隙中穿过,减少随机树扩展的“盲目性”,减少采样次数,提高规划速度。
（3）控制转弯角度、平滑规划结果路径。每个新的节点加入随机树前计算随机树转弯角度,小于提前设定好的角度阈值时将节点加入随机树,否则舍弃节点。得到规划结果路径后利用3次B-spline函数对结果路径中转点附近的路径进行平滑处理,得到平滑的规划结果路径。通过添加角度阈值和平滑结果路径增强算法的实用性。
最后利用武汉市三维城市数据对本文方法进行了验证,实验证明：相比RRT算法和双向RRT*算法,在起点终点直线距离10 000 m的远距离规划场景下,带有R树索引的双向启发式RRT*算法的规划时间均降低了90%以上,采样次数分别降低了86.7%和57.3%,转弯次数分别降低了78.3%和16.8%,结果路径长度也有所缩短。
本文提出的带有R树空间索引的双向RRT*算法虽然通过添加转弯角度阈值和B-spline曲线增强了算法的实用性,但是依然存在中间节点高度较大,节点间高差较大等问题导致实际飞行效果不佳,后续还需不断完善算法以增加实用性。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
赵晓, 王铮, 黄程侃, 等. 基于改进A*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6):903-910.

DOI

[ 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

[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

[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.]

Options
Outlines

/

〈 〉