基于RRT算法的某型无人机航路在线规划设计

路 引，郭昱津，王道波

(1.南京航空航天大学 中小型无人机先进技术工业和信息化部重点实验室， 南京 210016；2.中电集团第二十八研究所，南京 210007；3.南京航空航天大学 自动化学院，南京 210016)

【装备理论与装备技术】

基于RRT算法的某型无人机航路在线规划设计

路 引1,3，郭昱津2，王道波3

(1.南京航空航天大学 中小型无人机先进技术工业和信息化部重点实验室， 南京 210016；2.中电集团第二十八研究所，南京 210007；3.南京航空航天大学 自动化学院，南京 210016)

针对高原地区复杂地形地貌，提出了无人机需具备在线航路规划能力；分析了快速随机搜索树(RRT)算法的基本原理，并对RRT算法的收敛性和参数选择进行了探讨，设计了基于RRT算法的在线航路规划方法；对所设计的方法进行仿真验证。仿真结果表明：该航路在线规划方法达到了预期目的，能够很好的规避突发障碍。

无人机；航路规划；快速随机搜索树

高原地区地形地貌复杂，群山连绵，无人机按照预设的航线飞行，可能会遇到山等障碍物，对无人机飞行造成很大的威胁。无人机在复杂的应用环境中执行飞行任务，外界环境突发变化，无人机很难预先获得飞行过程中的全部环境信息，突发威胁仅当无人机抵达其附近一定区域后才能发现，在无人机的飞行过程中，改变无人机的飞行任务，这都需要无人机具备在线的航路规划能力，在满足飞行条件限制的前提下避开当前的危险。考虑实时性、可行性等需求，所研制的某型无人机采用快速随机搜索树(RRT)算法作为无人机的复杂航路在线规划方法[1-4]。

1 RRT算法

快速随机搜索树(RRT)算法是一种随机性、实时性好、速度快的算法，该算法能够在威胁、障碍物复杂的情况下快速找到一条路径。RTT搜索能力强，其独特优点是经过扩展后，可以直接应用到动力学规划。此算法采用一种能逐步迅速缩短随机状态与期望状态点之间距离的特殊增量方式进行构造[5]，考虑高原地区复杂的地形地貌条件，采用RRT算法进行航路规划能快速找到一条规避突发威胁的航路。

如图1所示，无人机按照预设航路从A点飞向G点，在飞行过程中，遇到突发威胁，需要在线规划航路，改变飞行路径，保证飞行安全。

图1 无人机飞行中遇威胁示意图

2 RRT算法的基本原理

假设无人机飞行区域为R，Rfree为无障碍区域，Robs为障碍区域，Rfree是Robs的补集，两个同为R的子集，且Rfree∪Robs=R。Rinit为起点，Rgoal为终点，且满足Rinit和Rgoal都为Rfree的子集。在飞行区域R中寻找一条从Rinit到Rgoal的可行路径。

RRT 算法是通过逐步迭代的增量方式构建随机树的。图2为RRT算法的节点扩展过程。首先RRT算法中树的根节点是在任务区域内选定的起始节点Rinit，所生成的随机树是通过从根节点连续扩展出叶节点方式构建的。以概率rg选择目标位置Rgoal为随机目标Rran，临近节点Rnear是在随机树的叶节点里离Rran最近的节点。从Rnear向Rran的方向延伸一个步长的距离ε，得到一个新的节点Rnew。在延伸过程中，判断是否与威胁区域有冲突，若Rnew与威胁区域有冲突，则舍弃该扩展的新节点，并重新选取随机目标点Rran，若Rnew与威胁区域无冲突，则接受该扩展的新节点Rnew，并将其新节点Rnew添加为随机树的节点。依此通过这样连续的扩展，直至随机树中的叶节点与目标点Rgoal足够近的时候，认为随机树的构建工作完成，从构建的随机树中，寻找从起始点Rinit到最终目标点Rgoal的路径，可以获得一条从起始位置到目标位置的可行路径[6]。

图2 RRT算法的节点扩展

3 RRT 算法收敛性分析

RRT 算法具有很强的路径规划能力，下面从理论上对RRT能够从起始位置扩展到目标位置的概率完备性进行分析[7]。令Dk(R*)是一个随机变量，表示位置R*与RRT随机树T上的最近节点之间的距离，dk表示随机变量的取值，k表示RRT的节点数，ε是RRT算法的扩展步长。

定理1Rfree为n维非凸有界开集，起始位置R0和目标位置R*位于Rfree的同一个连通区内，随着RRT节点足够增大，则RRT获得从R0到R*路径的概率为1，即

证明：R0与R*位于Rfree内的同一连通区内，那么在Rfree内存在一个节点序列R0,R1,…Rm，以及相应的超球体B(R1),B(R2),…B(Rm)，使得R0∈B1(R1)和R*∈Bm(Rm)，并且同时满足：

Bi(Ri)∩Bi+1(Ri+1)≠∅，i=1,2,…,m-1

令Ci=Bi∩Bi+1，对B(Ri)的构造，可以使得Ci为开集，测度μ(Ci)>0。

4 RRT参数研究

与其他的路径规划方法相比，RRT算法的一个显著优点是该算法需要设置的参数较少，主要包括随机点Rran和扩展步长ε等。简单的结构有利于RRT算法的应用推广，但目前关于算法参数的选取缺少严格的理论依据，在实际应用中一般根据经验试凑获得，不能保证算法参数的最优性。此处主要探讨参数扩展步长ε对RRT算法的影响。

在Rran与随机树所有节点计算距离之后，得到与之最近的节点Rnear，然后沿着Rnear与Rran的方向，从Rnear开始延伸一个步长的距离ε。较大的步长有利于减少路径所需要的节点数，但也增加了节点扩展过程中遇到威胁区域的概率，被迫重新进行随机节点的选择，反而降低了优化效率；较小的步长能够增大从Rnear到Rnew扩展的成功率，但需要很多的步数才能到达目标位置。在简单威胁环境下，可使用较大的步长ε，以加快规划的速度，且所得路径较短；在复杂威胁环境下，过大的步长会限制RRT算法的扩展能力，导致规划成功率降低，且所得路径的长度较大，不符合最优性要求，此时可以采用较小的步长。综合来看，RRT 算法中的参数ε选取至关重要，直接影响着规划问题的求解优劣和成功率，并且对任务环境有一定的依赖性，可以根据实际环境情况，进行此参数的选择。

5 RRT算法的在线实时规划

无人机按照预设的航线飞行，一边飞行，一边探测附近区域是否有突发威胁信息，一旦探测到新威胁，立即更新威胁信息表。如果突发威胁与预设航路有交点，则启动航路在线规划，将航路前面一定距离的节点作为新起始点，利用RRT算法在线重新规划新航路[8]。无人机按照重新规划的新航路飞行到指定航点，为了减少计算量，需确定合适的规划空间。无人机在正常飞行过程中，遇到突发威胁时，航路在线规划流程如图3所示。

图3 RRT算法在线规划流程

利用RRT算法进行无人机在线航路规划算法如下：

1) 无人机按照预设航线飞行；

2) 若无人机到达目标点，则算法终止，飞行结束；否则，进入第3步；

3) 无人机沿预设航路飞行，同时探测附近是否有威胁信息；

4) 若无人机探测到有突发威胁信息，进入第5步；否则，转第2步；

5) 利用RRT算法在线重新规划航路，更新飞行航路；

6) 转第2步。

6 RRT算法的仿真验证

选取无人机任务区域为100 km×100 km的矩形地形区域，随机生成100个障碍威胁，起始位置的坐标为(0,0)，目标位置坐标为(100,100)。设置RRT算法的参数为rg=0.5，步长ε=5。首先进行离线情况下的航路预规划，所得RRT随机树和飞行路径如图4所示。离线航路长度为182.06 km，程序运行时间为4.186 1 s。

当无人机飞行至图5中的A点位置，任务环境中出现突发威胁区域，如图5所示，由该图可知，新出现的突发威胁与无人机的待飞航路由重合，因此无人机此时不能再按照原有路径飞行，必须进行航路重规划。此时进行数字地图更新，并以无人机当前位置为起点，重新调用RRT算法进行航路重规划，所得结果如图6所示。

航路重规划的运行时间为1.781 5 s，耗时较少，能够满足无人机航路重规划的实时性要求。新的航路长度为118.38 km。

图4 无人机离线航路预规划路径

图5 无人机飞行中突发威胁

图6 无人机航路重规划路径

7 结束语

无人机的航路规划是无人机飞行控制的重要组成部分，根据某型无人机的飞行控制研制需求，为了适应复杂地形地貌高原地区的飞行要求，分析了快速随机搜索树(RRT)算法的基本原理，并对RRT算法的收敛性和参数选择进行了探讨，设计了基于快速随机搜索树(RRT)算法作为无人机的航路在线规划方法，仿真结果表明该航路在线规划方法达到了预期目的，能够很好的规避突发障碍。

[1] 杨力.无人机航路规划技术研究[D].南京航空航天大学硕士论文,2009.

[2] MARTIN S R,WRIGHT S E,SHEPPARD J W.Offline and Online Evolutionary Bi-Directional RRT Algorithms for Efficient Re-Planning in Dynamic Environments[C]//Proceedings of the 3rd Annual IEEE Conference on Automation Science and Engineering,Scottsdale,2007:1131-1136.

[3] JAMES J,STEVEN M.An Efficient Approach to Single-Query Path Planning[C]//Proceedings of the 2000 IEEE International Conference on Robotics and Automation,2000,995-1002.

[4] 彭辉，王林，沈林成.区域目标搜索中基于改进 RRT 的 UAV 实时航迹规划[J].国防科技大学学报,2009,31(5):86-91.

[5] 李猛.基于智能优化与RRT算法的无人机任务规划方法研究[D].南京：南京航空航天大学,2012.

[6] LAVALLE S M.Planning Algorithms[M].Cambridge：Cambridge University Press,2006:229-243.

[7] LAVALLE S M,KUFFNER J J.DONALD B R,et al.Rapidly-Exploring Random Trees[J].Progress and Prospects.Algorithmic and Computational Robotics:New Directions,Wellesley,2001:293-308.

[8] PENG H,SU F,BU Y L,et al.Cooperative Area Search for Multiple UAVs Based RRT and Decentralized Receding Horizon Optimization[C]//Proceedings of the 7th Asian Control Conference,Hong Kong,2009:298-303.

[9] 李子杰，刘湘伟.基于进化算法的多无人机协同航路规划[J].火力与指挥控制，2015(2):85-89.

[10]沈培志，张邦钰，聂奇刚，等.基于蚁群算法的无人机航路规划辅助决策研究[J].四川兵工学报，2015(8):145-148.

(责任编辑周江川)

Design on Route Online Planning for a Certain UAV Based on RRT Algorithm

LU Yin1,3, GUO Yu-jin2, WANG Dao-bo3

(1.Key Laboratory of Unmanned Aerial Vehicle Technology, Nanjing University of Aeronautics and Astronautics, Ministry of Industry and Information Technology, Nanjing 210016, China; 2.The 28thResearch Institute of China Electronics Technology Group Corporation, Nanjing 210007, China; 3.College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)

Route online planning function of the UAV was putted forward in view of the complex plateau topography. Rapidly-exploring Random Tree(RRT) algorithm was analyzed and the convergence of RRT algorithm and parameter selection were discussed. RRT algorithm, as the method of route online planning, was designed. The method was applied to the route online planning simulation. And the simulation results show that the design of the method has reached the expected purpose and can avoid unexpected obstacles very well.

UAV; route planning; rapidly-exploring random tree

2016-07-25；

高空长航时无人直升机保性能飞行控制与旋翼转速优化策略研究(61374188)

路引(1988—)，男，博士，主要从事无人机飞行力学与飞行控制研究。

10.11809/scbgxb2016.12.004

路引，郭昱津，王道波.基于RRT算法的某型无人机航路在线规划设计[J].兵器装备工程学报，2016(12):18-21.

format:LU Yin, GUO Yu-jin, WANG Dao-bo.Design on Route Online Planning for a Certain UAV Based on RRT Algorithm[J].Journal of Ordnance Equipment Engineering,2016(12):18-21.

V279+.2

A

2096-2304(2016)12-0018-04

修回日期：2016-08-25