无人机蜂群静态航线规划方法研究

张帆 胡航

（中国人民解放军66133部队 北京市 100144）

无人机蜂群在进入特定环境时，根据总体任务进行了全局任务分配，每个无人机在确定自己需要承担的任务后需进行全局的飞行航线规划。在航线规划时每个无人机需考虑的要素包括：所有的任务点、任务区域、进入点和退出点。

1 RRT算法研究

1.1 RRT算法原理简介

假设任务空间为C，Cfree表示可行区域，Cobs表示障碍区域，Cfree和Cobs同为C的子集，且满足C=Cfree∪Cobs和Cfree∩Cobs=φ。初始位置qinit∈Cfree和目标位置qgoal∈Cfree，现需要为规划出从初始位置到目标位置的可行路径。

使用 RRT 算法进行路径规划分为任务空间内的随机树生长和可行路径的反向搜索两个阶段。其中随机树的生长，即如何构造随机树是 RRT 算法的主要内容。RRT 算法通过逐步迭代的增量方式进行随机树的构造，首先在任务区域内选定起始节点qinit作为树的根节点，通过从根节点不断扩展出叶节点的方式构建随机树。首先以概率Pg选择目标位置qgoal作为随机目标点qrand，或者以概率1-Pg在任务空间内随机选择一个随机目标点qrand；从随机树当前所有的叶节点之中，选择出一个离qrand最近的，称之为临近节点qnear；然后从qnear向qrand的方向延伸一个步长的距离ε，得到一个新的节点qnew。在延伸过程中，判断是否与已知的威胁区域有冲突，若无冲突接受该新节点qnew，并将其添加为随机树的节点；若qnew与威胁区域有冲突，说明该次扩展出的新节点不符合安全要求，则舍弃该新节点，并重新进行随机目标点qrand的选取。通过这样不断的延伸扩展，当随机树中的叶节点与目标位置足够近的时候，则认为随机数的构造工作完成，此时以距离目标位置最近的叶节点为起始，依次向上搜索父节点，则可以获得一条从起始位置到目标位置的可行路径。二维空间内的RRT算法节点扩展过程如图1。

1.2 RRT算法的改进

RRT*的原理是在RRT算法的基础上，生成随机点qrand，找到树上最临近节点qnearest，根据设置好的步长Segment，会预先生成一个qnew，在以qnew为中心，以radius为半径的圆内，找到所有点半径小于radius的节点qnear，遍历所有的qnear，计算每个qnear作为qnew父节点时的代价，将每条路径的代价与原路径代价相比较。如果比原路径代价小且能够通过碰撞检测，则将正在遍历的qnear作为新的父节点。

如前所述，由于无人机的平台性能是受限的，因此在基于RRT算法进行航线规划时，应当考虑无人机上一节点与下一个需要扩展的节点的夹角。根据前面的讨论，新产生的节点应当满足如图2所示的约束。

另一方面，直接应用RRT算法存在的缺点是算法向各个方向扩展的概率是相同的。这将会导致生成大量的冗余节点，极大的降低了算法的计算效率。在航线规划时扩展树中的节点均是随机生成扩展而来，因此随机节点xrand的选取合适与否将直接影响最终生成航线的质量。为了得到质量更高的xrand节点，可以采用多重随机采样策略，即从规划空间中产生一组随机采样点，然后对这一组点中选择最优的xrand进行拓展。为了在一个采样集合中得到最优的xrand，需要根据相应的评价函数对节点集进行评价。由航线规划的目的可知，优化的航线应是连接起始点与终点，满足各种约束且能够保证无人机不冗余飞行的航线。因此，RRT算法扩展的与目标方向相反的航点大概率将会生成低效的飞行航线。

无人机在空中飞行时，决定飞机状态评价的参数包括两个参数，即当前飞行位置，飞行方向。因此在对采样点的评价函数确定为：

如图3所示，其中d表示采样点到终点的欧氏距离，a表示起始点到目标点与采样点到目标点的夹角，w1、w2分别是距离和角度的权重系数。

由于距离与方向量纲不统一，还需对该评价函数中的d和a进行归一化处理，即计算k 个采样点的距离和角度值，然后求出其平均值d和a，即：

图1：RRT搜索原理图示

图2：基于无人机的机动性能确定航线规划的约束

图3：节点评价函数构造示意图

图4：贝塞尔曲线

求出均值后，再对每一个采样点对应的距离和角度进行归一化处理，因此评价函数变为：

另一种改进方法为基于最近邻可达点的改进RRT方法，即NAPRRT。由于基本RRT算法过程中包含了大量的浮点运算，影响了算法效率，针对此问题，希望在扩展子节点时优先扩展当前节点附近的、无碰的节点，而不需要处理随机点角度相关的复杂运算，故提出该种改进方法。

2 贝塞尔曲线路径的平滑处理

贝塞尔对于路径平滑非常有效，它有一个最重要的特点就是在不更改整条路径形状的前提下重新构建局部路线。研究中运用贝塞尔曲完成RRT*算法执行后的后续工作，创建一条更加平滑的路径。

贝塞尔曲线可以定义为下式：

在此重点考虑n-3的情况，即三次贝塞尔多项式Bp(t)。随着伯恩斯坦多项式的扩展，得到贝塞尔曲线的参数方程：

上式中，四个点P1、P2、P3和P4确定了一个三次贝塞尔曲线，其中，P1和P4为曲线的端点，P2和P3为曲线的控制点，曲线的属性如下：

（1）Bp(0)=P1且Bp(1)=P4；

根据贝塞尔曲线的属性（1），将路径段Gp构建为P1=qinit与P4=qgoal，也就是说，随机数在扩展的过程中，每一个扩展的端点qinit可以定为P1，每一个扩展的目标点qgoal可以定为P4，那么随机树就能够按照三次贝塞尔曲线进行扩展了。扩展过程如图4所示。

3 融合RRT*和贝塞尔曲线的无人机蜂群航线规划方法

图5：参照无人机调整航线示意图

情况设想中，有多个无人机编队共同执行任务，各编队执行的任务各不相同。编队中各架飞机执行任务情况相同，无人机之间保持通信，同时到达任务点执行任务。因此，无人机蜂群在完成任务过程中是作为一个集群在飞行，需要保证群队飞行的效果。每架无人机在规划航线时都必须考虑编队飞行，而不仅仅考虑自身航线最优。

为了达到此目的，可在编队中选出一架参照无人机，参照无人机独立运用RRT*和贝塞尔曲线规划出最优航线，同时将最优航线发布给编队中其他无人机，其他无人机据此进行自身航线规划。参照无人机的选择标准有：起始状态下位于编队中的位置（前方或中间）、飞行能力较强、油料较多。具体方法如下：

（1）运用RRT*算法和贝塞尔曲线规划出参照无人机执行任务的最优路线；

（2）参照无人机向编队中其他无人机发布最优航线，其他无人机以一定安全距离伴随飞行；

（3）参照无人机适当调整自己的航线，需要考虑其他无人机的可飞性，适当增加参照无人机与障碍物间的距离，保证其他无人机伴随飞行时的安全等，使整个编队到达下一个任务点的时间最短或尽可能避障、远离威胁,如图5所示。

（4）其他无人机规划伴随飞行航线应以无人机间安全距离和避障等为约束，编队规模较小时，其他无人机根据参照无人机方位飞行，使整个尽可能避免冲突、远离威胁；编队规模较大，则编队中部分无人机与参照无人机的距离远，无法很好地进行通信和伴随飞行，这时需要将编队进行分层，如果参照无人机在编队前部，则中部无人机伴随参照无人机飞行，后部无人机以中部无人机为参照伴随飞行。

接着，假设每个无人机编队中的无人机为等距横向排列，设置编队中无人机之间的间隔为λ米，机群中先到达执行任务点的无人机在汇合过程任务范围内徘徊，汇合过程路径由贝塞尔曲线产生；

最后，将规划好的航路段分配给所属的无人机编队，并将无人机编队的每个航路段连接起来，无人机编队等间距λ生成五条航线，同时将第3个步骤中生成的汇合过程路径与编队航线连接起来，即为规划的完整航线。