有障碍区域的多无人机多目标点路径规划*

2019-09-16肖春晖邹媛媛李少远

空间控制技术与应用 2019年4期

肖春晖，邹媛媛，李少远

0 引言

无人机具有敏捷、地面保障要求低、安全风险系数小等特性，且运行成本较低，近年来已广泛地应用于民用及军事等多个领域，如电力巡检、农业灌溉、物流配送、遥感[1-4]及情报搜集、侦查监视、通信中继、对地打击等[5-8]. 在无人机的运动控制过程中，路径规划是重要的一部分.一般而言,无人机路径规划的目标是在到达目标点的同时尽可能最小化燃料消耗、时间消耗等因素. 在二维环境中的无人机路径规划类似于一般地面机器人路径规划[9]. 常规无人机路径规划的现有解决方案主要有Dijkstra算法[10]、基于启发式的搜索算法A*和D*和各种其他元启发式算法[11]、基于采样的路径搜索方式，包括快速扩展随机树算法(RRT)[12]和随机路标图算法(PRM)[13]. 对于有障碍物的情况，文献[14]通过模拟人类躲避障碍的思想，制定了五项飞行规则，提出了基于广度优先和RRT结合的算法，文献[15]提出了切向量矢量场引导和李雅普诺夫矢量场引导的无人机路径规划算法，文献[16]则设计了基于神经网络和反步法的状态反馈算法.

对于有多个目标点需要访问的无人机路径规划,可以将其转化为旅行商问题(traveling salesman problem, TSP)或车辆路径问题(vehicle routing problem, VRP). 文献[17]针对无人机运输任务提出了两个多旅途VRP，分别使用了混合整数线性规划算法和模拟退火算法，以解决时间窗约束及时间窗和预算约束问题，并通过数值仿真与效果分析进行了算法验证. 文献[18]针对具有曲率约束的无人机的TSP，提出了一种基于自组织映射网络(self organizing map, SOM)的非监督式学习算法，解决了邻域约束的多个体Dubins旅行商问题，并能够在传统的计算资源上以秒为单位快速地提供解决方案，使得该方法适合于在线规划. 上述工作均未考虑障碍区域，但实际中存在的飞行障碍往往导致现有方案规划的路径不可行.

本文考虑解决有障碍区域限制的多无人机遍历多目标点的路径规划问题，难点主要体现在两方面：一方面是如何求解每个无人机的访问顺序和各点的航向角，得到适用于无人机的路径；另一方面是如何处理路径与障碍区域的约束. 本文的结构如下：首先建立了无人机模型，确定无人机路径所用曲线；其次确定了优化问题. 针对该优化问题，使用改进的遗传算法求得所需要的无人机数量及各无人机对应的路径，并判断所获得路径是否存在障碍区域约束，若存在则使用Dubins-RRT算法进行调优以得到满足约束的路径. 最后，通过仿真算法案例证明了本文方法的有效性.

1 无人机模型

选取小型固定翼多无人机(unmanned aerial vehicle，UAV)作为本文的研究对象，为保证规划的路径平滑可飞，便于UAV后续的运动控制，使用Dubins模型来描述固定翼UAV简化的动力学特性，满足了无人机的曲率约束[19].

1.1 Dubins模型

Dubins模型的公式如下所示：

(1)

式中，(xA,yA)为UAV在二维平面直角坐标系下的横纵坐标，θA为UAV的转向角，vA和rA分别为UAV的飞行速度和最小转弯半径，uA为控制转向的输入.(xA,yA,θA)∈R3表示Dubins运动体的状态，可以称之为Dubins状态(Dubins Configuration). 通过Dubins模型可以看出，当uA>0时，Dubins运动体相对于当前运动方向左转弯，而uA<0时，Dubins运动体相对于当前运动方向向右转弯，当uA=0时，Dubins运动体保持当前运动方向直行. 同时，rA限制了Dubins运动体转弯的最小半径，当|uA|=1时，表示Dubins运动体以最小转弯半径向左或者向右转.

1.2 Dubins路径

Dubins路径表示从起始Dubins状态到目标Dubins状态的符合Dubins动力学模型的最短路径.文献[19]证明，当给定任意起始Dubins状态和目标Dubins状态时，存在六种类型的最短路径，根据运动模式的不同称它们为: RSR, LSL, RSL, LSR, RLR, LRL. 其中，R、L、S分别代表右转、左转、直行. 图1分别给出了在这两个Dubins状态下的RSR路径和RLR路径示例，其中SP表示起始Dubins状态，TP表示目标Dubins状态. 在寻找两个Dubins状态之间的Dubins路径时，需要计算这六种Dubins路径各自的长度(部分情况下可能存在某些种类路径不存在)，其中长度最短的路径就是这两个Dubins状态下的Dubins路径.

图1 Dubins路径Fig.1 Dubins path

2 问题形成

2.1 问题描述

指挥中心拥有K个UAV，UAV需要到达N个目标点并装载一定量的任务物品以完成任务. 安排合理科学的UAV遍历路径，使得一定数量的UAV从指挥中心出发，在总飞行成本最低的目标下，完成任务后再返回到指挥中心.

UAV在飞行的过程中，可能遇到影响其飞行的障碍物或禁飞区域(两者统称为障碍区域)，所规划的路径应该避开这些障碍区域.

为构建问题的数学模型，做出一定的假设：只有一个指挥中心，且所有的UAV均以指挥中心为起点，执行完各自的任务后返回指挥中心；每一个任务点对于UAV执行该点任务时所需要的装备、物资是已知且不变的，且小于UAV的额定载重量指挥中心和任务点的位置已知；障碍区域提前已知且静态的.

2.2 数学模型

为了更方便地描述模型，首先给出使用到的符号的定义.

N：任务点集合；

K：UAV集合，下标用表示；

O：指挥中心，下标用表示；

C：UAV单位距离所耗费的飞行成本；

dij：从任务点i到j的Dubins距离；

qi：执行任务点处任务所需的装备物资量；

Q：UAV的额定装备物资载重量；

D：UAV飞行距离上限；

Obs：障碍区域集合，每个障碍区域用圆来表示；

Φik：当xijk=1时，UAVk在任务点i的航向角.

针对该问题，给定目标函数为：

(2)

s.t.

(3)

(4)

(5)

(6)

(7)

(8)

path(X,Y,Φ)Obs

(9)

其中，式(2)为目标函数；式(3)保证了每次任务都以指挥中心为起点和终点；式(4)保证每个任务都被执行且仅执行一次；式(5)表示额定载重量约束；式(6)表示所有使用的UAV数量少于指挥中心所拥有的数量；式(7)表示任务点的总数为N；式(8)表示UAV最大距离约束；式(9)表示障碍区域约束，即形成的所有路径都不经过障碍区域.

3 问题求解

在节2.2中形成的NP-hard的优化问题中，由于约束条件复杂繁多，问题规模较大，同时决策变量具有离散性，且Dubins路径具有组合性，使得传统的优化算法不便于求解该问题. 遗传算法具有强大的并行搜索能力，自学习性、自组织性和自适应性强，并且不易陷入局部最优. 本节首先使用遗传算法求解优化问题得到路径，对得到的路径进行障碍区域检测，若不满足障碍约束，则通过Dubins-RRT算法进行调优以满足约束.

3.1 改进的遗传算法

遗传算法主要包括染色体编码、初始化、适应性函数设置、选择、进化等步骤. 在交叉步骤中，通常是对染色体中的元素随机交叉，本文在交叉过程中通过设计新的交叉算子以改进遗传算法，在保留了父代优秀染色体的同时加快了收敛速度. 改进的遗传算法各个步骤如下.

1)编码

在遗传算法中，一条染色体就是一个解.由于xijk,yki,Φik均存在不少的约束条件，设定一个合适的染色体编码直接处理掉这些约束尤为重要. 使用[S,φ]来表示一个解，它们都是N+K+1维的向量，其中S表示UAV对于V的访问顺序，φ表示UAV在S所对应点处的航向角.S由K+1个0(首尾一定是0)和1到N的排列组成，其中0表示指挥中心，自然数表示任务点，两个0之间的元素代表了一条UAV访问路径的顺序. 例如，S=[0,4,1,0,2,5,0,3,0]，[0,4,1,0]代表UAV1从指挥中心->任务点4->任务点1->指挥中心的路径，[0,2,5,0]以及[0,3,0]表示UAV2和UAV3的路径. 如果S中包含两个连续的0即[0,0]，则表示该UAV未被使用.

2)初始化

种群数量popsize、迭代次数maxiter都与N、K有关系，通常情况下两种参数设置在50～200之间，此外，还有交叉概率、变异概率也需要根据实际调试结果进行修正.

3)适应度函数

4)选择

选择操作以一定概率从旧群体中选择个体到新群体. 选择个体的概率与适合度值相关. 个体适应度越大，被选中的概率越大.

5)交叉与变异

交叉时将[S,φ]绑定，同时进行交换. 为了保留父代的优秀子路径，设计新的交叉算子，具体步骤如下：

Step1:分别在两个父染色体上随机选取一段子路径.如图2所示.

图2 随机选择子路径Fig.2 Randomly select subpath

Step2：前置父代中被选择的子路径，如图3所示.

图3 前置子路径Fig.3 Put subpath in front

Step3：将父染色体1中子路径A保留，然后将父染色体2中子路径A没有的自然数以及最后一位0按照父染色体2的顺序添加到子路径A的后面，同样方法得到子染色体2. 如图4所示.

图4 初步得到子染色体Fig.4 Preliminary chromosome

Step4：对于子染色体1，空缺的0(对应的航向角随机生成)随机插入任何一个位置，并计算插入每个位置时对应的适应度函数，选择最优的染色体作为最终得到的子染色体1，同样的方法得到子染色体2.

变异算子则只改变航向角的值，随机选择几个航向角进行变异，若得到更优的染色体则进行替换.

为了衡量UAV数量、任务点数量、种群数量等参数对算法的影响，对本节介绍的改进的遗传算法进行简要的时间复杂度分析. 在编码过程中提到染色体中S、φ都是N+K+1维，为了简便，记n=N+K+1.求适应度阶段的时间复杂度为O(popsize×n)，选择阶段为O(popsize×logpopsize),交叉阶段为O(popsize2),变异阶段为O(popsize).故对整个改进遗传算法来说，其时间复杂度为:

O(maxiter)×

[O(popsize×n)+O(popsize×logpopsize)+

O(popsize2)+O(popsize)]=

O[maxiter×popsize×(popsize+n)]

因此，可以看出，迭代次数、种群数量、任务点数量、UAV数量都是影响改进遗传算法的因素，其中，由于种群数量是二次项，所以为影响整个算法时间复杂度的最重要因素.

3.2 障碍区域检测方法

为了方便描述，将由两个Dubins状态得到的Dubins路径称为“基本Dubins路径”，由多个“基本Dubins路径”连接得到的称为“复合Dubins路径”. 显然，每个UAV的路径都是复合Dubins路径. 所以，要对UAV的路径进行障碍区域检测，只需要对每个基本Dubins路径进行检测，而每个基本Dubins路径都是有线段和弧组成的，所以只需要对每条线段和弧进行检测.

对线段来说，首先判断线段所在的直线是否与障碍区域有交点，如果有交点则进一步判断交点是否在线段上；对于弧来说，首先补全弧所在的圆，判断该圆是否与障碍区域相交，若相交则进一步判断交点是否在弧上. 图5给出了具体实例，黄色代表障碍区域，红色实线代表线段和弧，红色虚线代表辅助的直线和圆，黑色实心点表示辅助线与障碍区域的交点，蓝色实心点表示线段和弧与障碍区域的交点.

图5 对线段和弧的障碍区域检测Fig.5 Detection for line and arc

结合对线段和弧进行障碍检测的方法，就可以对基本Dubins路径进行障碍区域检测. 图6给出了针对两类基本Dubins路径检测的实例，一类是针对弧-直线-弧(Circle-Straight-Circle, CLC，包含LSL,LSR,RSL,RSR)种类曲线的障碍区域检测方法，另一类是针对弧-弧-弧(Circle-Circle-Circle, CCC，包含LRL,RLR)种类曲线的障碍区域检测方法.

图6 对基本Dubins路径的障碍区域检测Fig.6 Detection for basic Dubins path

3.3 路径调优

对得到的UAV路径中的每一段基本Dubins路径进行障碍区域检测，然后对经过障碍区域的基本Dubins路径进行重新规划，以得到安全路径.

RRT算法是一种速度较快的路径规划算法，能快速扩展以充分地搜索可行(无障碍)空间，并构建一个从初始点向目标点探寻可行路径的树T(V;E)，其中V代表节点，E代表边. RRT算法中用于探索空间的并非一定是二维顶点，也可以是Dubins状态，边也可以是Dubins曲线，该树用T(Vd;Ed)来表示，在扩展过程中Vd和Ed不断增加. 为此，本文针对Dubins路径改进RRT算法，称其为“Dubins-RRT”算法. 算法流程如下：

1)初始化树，T(Vd;Ed),dinit作为树的根节点，设定选择目标Dubins状态dgoal作为随机目标点的概率pg;

2)是否到达目标dgoal，否则专向步骤3)，是则表明树已构造完成，转向步骤7);

3)生成随机数p∈[0,1],若p≤pg则转向步骤4)，否则转向步骤5);

4)选择目标dgoal作为drand，从Vd的所有节点中，找出离drand最近的节点，称为dnear；

5)生成一个随机节点作为drand，从Vd的所有节点中，找出离drand最近的节点，称为dnear；

6)判断从dnear到drand的路径lnr是否与障碍区域冲突，若不冲突则将drand，lnr分别作为节点和边添加到随机树中，完成一次树的扩展，转向步骤2)，若冲突则转向步骤3)；

7)从构造完成的随机树中，确定一条从dinit到dgoal的路径.

图7展示了给定两个Dubins状态以及障碍区域(黑色实心圆)，使用Dubins-RRT的扩展过程，(a)中随机树只新增了两个节点和两条边，(b)中随机树已有近50个节点和边，(c)中随机树有近200个节点和边，(d)是算法结束时随机树的结果，红色线条表示满足障碍约束的路径.

图7 Dubins-RRT扩展过程Fig.7 Dubins-RRT extension process

4 案例仿真

本章节通过一个具体仿真案例验证算法的有效性. 给定指挥中心和25个任务点，表1给出了其相应的坐标位置，其中Ti表示第个任务点，表2给出了任务的相关参数和改进遗传算法的相关参数.

表1 指挥中心与任务点的坐标Tab.1 Coordinate of center and target points

表2 相关参数设定Tab.2 Related parameters

仿真结果如图8～9所示，红绿蓝三条线分别代表了三个UAV的路径，黑色圆表示多个障碍区域. 图8展示了使用改进遗传算法的结果，可以看出有部分路径(T2->T14，T3->T1，T9->T24)违反了障碍区域约束，经过局部调优后得到的结果如图9所示.

将本文方案结果与其他两种方案进行比较，两种方案分别采用未改进的遗传算法(GA)和蚁群算法(ant colony optimization, ACO)求解优化问题后进行调优. 三种方案的结果如表3所示. 可以看出，本文方案与GA+Dubins-RRT方案相比，收敛速度提升了77%，避障后飞行成本减少了11.3%；与ACO+Dubins-RRT方案相比，收敛速度提升了122%，避障后飞行成本减少了8.9%. 综上所述，本文提出的方案在收敛速度提升较大的同时减少了飞行成本.