旋翼无人机协同任务指派问题研究与算法改进

沈 奥，周树道，王 敏，彭舒龄,3，刘展华

(1.国防科技大学 气象海洋学院，南京 211100；2.中国人民解放军 94303部队，山东 潍坊 2610003.中国人民解放军 61206部队，北京 100043)

0 引言

旋翼无人机具有结构简单、操作灵活、起降要求低、可悬停等特点，在拍照录像、气象监测、物资投递等领域具有难以替代的作用。而多架旋翼无人机可以通过协同配合、编队飞行等方式完成单架无人机难以完成的任务。在多架旋翼无人机协同执行任务时，无人机会根据需要飞至不同目的地执行任务。这种情况下一般采用多架相同的无人机，每一架无人机都有相同的属性和功能[1-3]。根据无人机实际应用情况，可以大致分为两种情况：

情况1，每架无人机分别分配一个目标点，到达目标空域点即可降落，比如利用无人机进行物资运送；

情况2，每架无人机到达各自目标空域点后需要悬停，等待所有无人机就位后再开始执行任务，比如多无人机定点拍照、监控或测量。

在这类问题中，计算复杂度随无人机数量上升，呈指数上涨，属于多项式问题(Polynomial Problem，P问题)，所以无人机自主快速智能地根据任务性质和目标点位置进行匹配，可以免除人工调度，增加无人机协同工作的自动化程度，对提升无人机集群飞行的性能有重要意义[4-5]。由于在此类应用实际中，空间内无人机密度相对稀疏，无人机避碰相对容易实现。同时，各无人机目标空域点相距较远，且高度往往不同，使用时碰撞的几率较小。所以在本文中暂不将无人机避碰作为研究的重点。

本文主要是针对旋翼无人机，设计了适用于无人机嵌入式系统的轻量级算法，完成不同情况下多无人机的目标空域点匹配。第一部分介绍了旋翼无人机目标空域点匹配的数学模型；第二部分针对第一种情况采用匈牙利算法进行求解；第三部分针对第二种情况，在匈牙利算法的结构上，针对实际问题进行了改进，确定了改进后的参数，并设计了遗传算法进行对比；第四部分为结论。

1 旋翼无人机多目标空域点匹配问题数学模型

多无人机与多目标点的匹配可以看作图论中二分图的匹配问题[6-7]，可以简述为：

有n架无人机A1,A2,……，An；n个目标点B1,B2,……，Bn，将无人机设置为矩阵的行，目标点设置为矩阵的列，则可得到匹配矩阵为X=(xij)，其中，xij表示匹配情况，取值为1表示无人机Ai与目标点Bj匹配，取值0表示无人机Ai与目标点Bj不匹配。同时，一架无人机必须且仅能与一个目标点匹配，优化函数可以通过实际情况进行设置。因此，问题可以看作n2个变量2n个约束条件的最优规划问题：

minimizez=f(X)

(1)

服从于：

其中:

xij=0 or 1,i,j=1,2,…,n

根据实际需要，设置合适的目标函数f(X)，在服从约束条件的情况下，优化匹配矩阵X，即可获得问题的优化解。

2 针对情况1的匈牙利算法使用

2.1 匈牙利算法

对于二分图的最佳匹配问题，如果采用遍历的方法，将所有匹配情况进行比较和选取，则在问题规模较大时，会发生组合爆炸的情况。而此问题中限制条件特殊且具有明显的数学特征，难以采用遗传算法和模拟退火算法等随机算法，且随机算法在求解此问题中，丢失了问题的数学本质，具有较大盲目性。

而匈牙利算法是基于Hall定理中充分性证明的思想，通过不断寻找增广路径的方法大幅度降低时间复杂度，是解决二分图匹配问题的主要算法[8-9]。算法步骤如下。

将优化目标定义为：

(2)

通过利用代价矩阵的相关定理，对矩阵进行等价变换，算法可按图1步骤执行。

图1 匈牙利算法流程图

通过图1中步骤计算，可得到xij的具体取值，即得到匹配矩阵X，将匹配矩阵中取值为1元素的行号对应的无人机与列号对应的目标点进行匹配，即为该问题的最优匹配结果。

2.2 匈牙利算法使用

在情况1中，由于无人机到达空域点后即可降落，不需要等待其他无人机，所以可以将距离设置为问题中的代价值，即可求解令无人机群飞行总距离最短的匹配方式。通过卫星定位获取可获取每一架无人机的当前坐标和空域点的坐标值，计算各无人机对应各空域点的距离，并将其作为代价矩阵C1中的元素,即：

C1=(c1,ij)

(3)

其中:c1,ij=distance(Ai,Bj)

对矩阵C1进行2～6步骤运算，即可得到匹配矩阵X1，将匹配矩阵中值为“1”的元素所在行列号进行匹配，即为最佳匹配结果。

图2以13架随机初始位置的无人机对应13个空域点为例，展示了匹配的几组结果，图中“*”代表无人机所在位置，“o”代表目标点位置，连线表示无人机和目标点的匹配结果。匹配结果中，无人机群总体移动距离之和最小，而从图2中可以看出，使用匈牙利算法进行目标匹配，无人机径直飞向目标点时，飞行线路不会存在交叉的情况，即可不必考虑无人机避碰的问题，在安全性和节能性上都有较好的效果。

图2 情况1中的匹配结果

3 针对情况2的匈牙利算法的改进和对比

3.1 在情况2中存在的问题

对于情况2中时应用背景，当旋翼无人机到达自己空域点后，需要悬停飞行，等待其他无人机到达各自空域点，在等待的过程中，悬停飞行同样会产生能量的消耗[10]。可以计算整个过程的总消耗为：

(4)

可以化简为：

(5)

式中，a1,a2分别为飞行和悬停时，单位时间内的能量消耗，v为旋翼无人机飞行速度，di为无人机Ai距离匹配到目标点的距离，dmax为无人机到目标点的距离的最大值。

与此同时，响应速度快是无人机的优势，长时间悬停等待会影响旋翼无人机群整体执行任务的效率[11]，所以整个过程所用的时间应当考虑在内，计算整个过程完成的时间为：

T=dmax/v

(6)

可以看出，影响旋翼无人机群总能量消耗和完成时间取决于无人机需要移动的总距离(平均每架无人机需要移动的距离)和各无人机到各自空域点距离中的最大值，所以，要对无人机空域点进行优化匹配，应当同时优化减小每架无人机移动的平均距离和无人机需移动距离的最大值。此外，无人机飞行的路线应尽量减少交叉，减少相互间的避让过程。

而匈牙利算法主要是针对单一变量进行优化，当存在多个独立变量时，需要按照变量影响程度加权计算出代价矩阵。但在此问题中，优化目标为无人机平均移动距离和无人机的最大移动距离是一对相互耦合的变量，只有当一种匹配完成后，才能进行二次匹配，得到这种匹配下的最大移动距离[12]。

针对于此，许多二次分配问题线性化方法已被提出，如：Kaufman和Broeckx线性化模型[13]，Lawler线性化模型[14]等，此外Peter Hahn还提出一种基于匈牙利算法的对偶上升求解方法[15]，但这些方法需要大量的矩阵运算，占用大量计算资源和时间，不适用于无人机嵌入式系统实时计算[16]。

3.2 算法改进

使用标准的匈牙利算法，得到结果可以使平均移动距离最小，但却无法优化无人机中的最大移动距离，经过多次实例计算发现，当两架以上无人机全部位于空域点一侧时，如图3所示，由于线段AB与线段CD的和小于线段AD与BC的和，所以无人机B与目标A匹配，无人机D与目标C匹配，但实际中，A与D匹配，B与C匹配更符合应用要求，在平均距离相差不大的情况下，均衡无人机的最大移动距离，同时，避免了前方无人机到达目标后阻挡了后方无人机路线的情况。同样的情况还存在于无人机F、H与目标点G、H。

图3 匹配结果分析

针对这一问题，为了避免较大距离的移动，在不增加额外矩阵计算的情况下，可以将代价矩阵中的元素由距离的一次函数改为距离的m次函数，增大远距离匹配的代价，具体改进如下：

C2=(c2,ij)

(7)

其中:c2,ij=[distance(Ai,Bj)]m,m∈Z+,m≥2

对矩阵C1进行2～6步骤运算，即可得到匹配矩阵X2，匹配矩阵中所有值为“1”的元素所在行号无人机与所在列号目标进行匹配，可视为此情况下的优化匹配。

经过改进，由于指数函数的单调性，每一架无人机匹配各自目标点的代价值大小排序仍与无人机与目标点距离远近的排序一致。但此时与距离较大的目标进行匹配的代价值将会明显增大，限制了匹配中对较远距离目标点的匹配，在匈牙利算法的框架中，在不增加变量的情况下，通过无人机-目标点匹配的特点均衡优化了平均移动距离和最大移动距离两个参数。同时，优化后的匹配结果不具有随机性，对同一矩阵多次的匹配结果相同，可以在分布式系统中使用[17]。

3.3 遗传算法对此问题的求解

为了更好的验证算法性能，针对此问题设计了遗传算法进行求解：

1)产生r条父辈染色体，染色体为1×n维矩阵，每个基因取值范围为[1,n]，其中n为无人机数量，父辈中染色体为随机生成的n的排列，第i个基因取值为N1代表无人机i与目标N1匹配；

2)由于匹配模型限制较多，采用只变异不交叉的方式，从父辈染色体中随机选择两个基因变异，为了保证目标的逐一匹配，变异方式为此两段基因进行交换；

3)将父辈中r条染色体与产生的条子代染色体进行评价，淘汰评价低的r条，保留评价高的r条染色体；

4)将保留的染色体作为父辈重复迭代。

5)经过迭代，选择最终染色体中评价最高的作为匹配结果。

在此例中，将r设置为100，迭代次数设置为1 000，对问题进行解算。

3.4 实例对比

以13架随机位置的无人机对应13个已知空域点进行计算，表1和图4展示了m不同取值时匹配结果的对比，并与遗传算法结果进行比较。可以看出，匈牙利算法在解决此问题时，计算时间相差不大，将代价矩阵由距离的函数改为m次函数会使平均移动距离增大，但差别几乎可以忽略，而最大移动距离会得到很大的改善，减小无人机群整体的等待时间。而遗传算法由于在选择上具有随机性，计算效果和效率明显欠缺，并且每次计算结果会不同，不利于无人机自主分布式计算。

表1 算法参数对比(无人机在空域点四周)

图4 算法性能对比柱形图(无人机在空域点四周)

改变无人机群与空域点的相对位置，使无人机群位于空域点的不同方向，表2、图5展示了无人机群位于空域点一侧时的匹配结果对比。可以看出，当无人机群位于目标点一侧时，当m值变大时，结果变化趋势与之前相似，而遗传算法的效果有了很大提升，但计算时间仍然远远超过匈牙利算法。经过多次实验，改变无人机和目标点的相对位置，也会得到类似的结果。

表2 算法参数对比(无人机在空域点一侧)

图5 算法性能对比柱形图(无人机在空域点一侧)

此外，图6～9和图10～13展示了几组m不同取值下，无人机与目标点的匹配结果图。通过多次试验可以看出，当m=1时，由于匹配结果为总距离最短的最优匹配，不存在路线的交叉，各无人机与其匹配的目标点之间路线相离度较大；而m=2时，匹配结果会为了减小最大移动距离而做出一定修改，有时会发生路线交叉的情况；m=3或4时，由于代价矩阵元素变化较大，匹配时会发生过度避免较远目标的情况，导致匹配结果中交叉较多，实际应用中，不仅提升很小，并且会带来飞行安全隐患。所以，将算法中m的值设置为2，可以兼顾优化参数和实际中对路线的要求。

图6 当m=1时匹配结果(无人机在空域点四周)

图7 当m=2时匹配结果(无人机在空域点四周)

图8 当m=3时匹配结果(无人机在空域点四周)

图9 当m=4时匹配结果(无人机在空域点四周)

图10 当m=1时匹配结果(无人机在空域点一侧)

图12 当m=3时匹配结果(无人机在空域点一侧)

图13 当m=4时匹配结果(无人机在空域点一侧)

4 结束语

通过实例可以发现，匈牙利算法对于解决无人机群的空域点匹配有很好的效果。对于到达空域点即可降落的情况，使用标准匈牙利算法可以得到最优解；而对于到达空域点后需要等待的情况，可以修改匈牙利算法中的代价矩阵，将其中元素改为各自值的平方，可以在平均移动距离和计算时间变化不大的情况下，将无人机中最大移动距离减小，通过与遗传算法的比较和多次结果的对比，验证了算法在此问题中的优越性。