多无人机协同目标分配与航迹规划

许先静，姜海燕

(福州大学 电气工程与自动化学院，福州 350000)

0 引言

无人机具有体积小、重量轻、成本低等诸多优点，被广泛运用于农业、军事、飞行表演等多个行业。在很多实际场景中，单个无人机无法满足作业需求，需要多无人机的协同作业，而协同目标分配是多无人机协同作业的基础和保障。无人机的目标分配问题是一个约束性多且复杂的优化问题，其解空间随无人机和目标总数的增加呈现指数级增加，求解最优解的时间也呈指数级增加。因此，无人机的目标分配问题是一个多参数、多约束的非线性多项式完全(Non-deterministic polynomial Complete，NPC)问题[1]。在进行目标分配时，需要考虑的因素很多，如无人机数量、任务类别、飞行环境等，同时还需要兼顾航行代价、分配算法以及各种协同约束条件等。

目前针对无人机的协同目标分配主要有集中式和分配式。集中式系统可以统一控制，缺点是扩展性差；而分布式系统的扩展性强，但对通信系统要求较高[2]。目前无人机的协同目标分配的解决方案主要有3种类型，即传统的数学规划法、市场机制法和智能优化算法。传统的数学规划法应用于集中式系统中，具体可分为匈牙利法[3]、分支界定法、隐枚举法、混合整数线性规划法、动态规划法等；市场机制法应用于分布式系统，具体可分为合同网协议[4]、拍卖法等市场机制法[5]；智能优化算法既适用于集中式也适用于分布式，具体包括人工神经网络算法、模拟退火算法[6]、遗传算法[7-9]、差分进化算法、和声搜索算法[10]、蚁群算法、A_算法[11-12]、粒子群优化算法[13-16]等，以及由若干算法组合而成的混合优化算法[1，17]。

无人机的编队切换作为无人机的协同目标分配问题的等效(将N个目标分配给N个无人机)，大部分可以归纳为：给定无人机的起点和终点，赋予一定的目标任务、设定障碍或者航行代价等条件。目前许多的无人机的研究多基于二维平面，而无人机实际是在三维环境中执行各种协同任务的，所以在三维空间中研究无人机的协同目标分配，将会更具有理论研究意义和实际应用价值。对于多无人机队形变换的评价标准比较复杂，因为缩小某一单架无人机的路径长度，必然也会增加其它无人机的飞行路径长度。在单个无人机的最大飞行路径问题上，文献[18]旋翼无人机协同任务指派问题研究与算法改进中，通过将匈牙利算法中代价矩阵各元素值替换为各自值的m次方，有效缩小了单个无人机的最大飞行距离，但m取值不同，其得到的结果也是不同的；文献[19]多旋翼无人机编队队形变换算法研究中，运用粒子群算法实现队形变换时间最小，缩小了单个无人机最大飞行距离，但该研究缺乏飞行距离整体性的考虑。

本文从协同目标分配出发,研究无人机编队切换问题，发现标准的匈牙利算法在多无人机编队切换应用中，存在部分无人机分配的飞行路径过长的问题，同时由于无人飞行的能量消耗大于无人机悬停时能量消耗。从而导致个别无人机的电量下降迅速，因此相较于其他无人机会提前降落，而且会导致其他无人机在编队切换过程中等待时间过长，影响整体编队飞行的时长和编队切换时长。因此缩小单个无人机的最大飞行路径，既可以缩短编队切换的时间，还可以平衡无人机的耗能，延长整体的编队时长。利用匈牙利算法本身的特性，求解总的飞行距离最短，将目标函数改为求解在满足约束条件下，单个无人机的最大飞行距离最小，对匈牙利算法进行改进。改进的匈牙利算法可以使得在总的飞行距离尽量小的前提下，尽可能缩减单个无人机的飞行距离，从而有效地降低单个无人机的最大能耗，减少无人机在编队切换时悬停等待的时间和编队切换的时间，有效延长整体编队飞行的时间。适用于每架无人机到达各自目标空域点后需要悬停，等待所有无人机就位后再开始执行任务，比如多无人机定点拍照、监控或测量、协同打击等时间协同性强的应用场景。而且算法简单，没有过多的参数设置，无需占用太多的计算资源，适合无人机嵌入式系统的实时计算。

1 无人机编队切换问题描述和算法改进

1.1 队形切换的数学模型及匈牙利算法

无人机的编队切换问题，主要指的是在已知起点和目标位置的情况下进行位置移动，形成新的队形，主要影响编队切换效率的因素是每个无人机目标位置的选取。标准的匈牙利算法和其他算法大多数都只考虑无人机总飞行路径最短，并在此基础上去选取每个无人机的目标位置。然而考虑无人机总飞行路径最短时，就会存在部分无人机分配的飞行路径过长的问题，导致个别无人机电量迅速下降，提前降落且造成其他无人机等待时间过长，影响整体编队的飞行时长。因此以单个无人机最大的飞行距离最小为优化目标，并满足多约束条件，保证总移动距离尽可能小的情况下，可以延长整体编队的飞行时长。

为了简化问题的研究，假设每个无人机都是匀速飞行，忽略转弯以及外界环境的影响并不考虑碰撞。记无人机编队中各无人机的编号为i(i=1,2,3,...,n)，目标位置编号为j(j=1,2,3,...,n)；无人机的初始位置坐标(Xa,Ya,Za),无人机目标的坐标(Xs,Ys,Zs)。可以计算出第i架无人机飞往第j个目标的路径长度：

(1)

匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法[20-21]。匈牙利算法在多无人机编队切换应用中是将对于目标位置的分配抽象成指派问题。即：

1)有n个飞机飞往n个目标。

2)每个飞机只能飞往一个目标，每个目标只能有一个飞机飞往。

3)已知每个飞机飞往目标的能耗值。

4)求如何分配使得总飞行距离最短。

将上述问题转换成数学模型可以得到：

(1)无人机/目标机对定义一个二值函数Xij，

(2)则总飞行距离最短的性能指标函数为：

(i=1,2,3,...,n;j=1,2,3,...,n)

(2)

(3)需要满足的约束条件有：

(3)

(4)

Xij=0,1

(5)

满足上述约束条件去求性能指标函数最优解，库恩(W.W.Kuhn)于1955年提出了指派问题的一种解法，他引用了匈牙利数学家康尼格(D.konig)一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。这解法称为匈牙利算法。将其运用到多无人机编队切换应用中，其求解的过程是：

1)先将每个飞机飞往每个目标的飞行距离求出并赋值为代价矩阵H(n×n)。行代表飞机编号，列代表目标编号。

(i=1,2,3，...，n;j=1,2,3，...，n)

(6)

2)把代价矩阵进行行归约和列归约，即每行减去该行的最小值，再把每列减去该列的最小值。

3)进行试指派，用尽可能少的直线去覆盖矩阵中所有的0，如果所用的直线为n条则停止，得到最优匹配结果A，如果少于n，则继续下一步。

4)在第三步中得到的代价函数中找寻最小的元素X，然后将直线未覆盖的元素都减去该元素，并在直线相交处加上该元素。再更新代价矩阵后重复第三步。

图1为算法流程图：

图1 标准匈牙利算法流程图

图2是一个4个飞机飞往4个目标的指派问题中匈牙利算法的过程。左1为代价矩阵，中间的图是完成求解过程第二步和第三步后的矩阵，由于图中只有3条直线，而n等于4，故执行第4步，减去最小元素2，并在直线交点处加上2，更新矩阵，得到右1图。然后再从该矩阵中利用匈牙利算法找出最优匹配。

图2 匈牙利求解过程

1.2 改进的匈牙利算法设计

标准的匈牙利算法只解决了在满足约束条件的情况下性能指标函数Z的最优解，得到的分配结果A：

A=[S1J,S2J,S3J,...,S18J]，(j=1,2,3,...,n)

(7)

注：S1J代表编号为1的无人机飞往编号为j位置。

其中A集合中最大值即单个飞机飞行的最大飞行距离。

Smax=max(A)

(8)

考虑到时间的协同性，当无人机到达既定位置时需要等待其他无人机到达后统一开始执行任务，则完成任务的总时间T为：

T=Smax/v

(9)

而无人机无论是处于悬停还是飞行都需要损耗能量，则整个过程的能量损耗为：

(10)

注：k1代表无人机飞行能耗，k2代表无人机悬停能耗。

显然无人机的总的耗能、所有无人机飞行的总距离、单个无人机最大的飞行距离存在关联关系。而且由于无人机的飞行耗能要大于悬停耗能，因此减小单个无人机的最大飞行距离，不仅可以减小编队切换的时间，还可以减小总的能耗及减小单个无人机的最大能耗，延长无人机整体编队的时间。

针对标准的匈牙利算法，需要解决的问题就变成在满足约束条件下，如何减小Smax的值，并保证性能指标Z的值尽量小(无人机飞行的总飞行距离尽量短)。此时优化的性能指标变为:

f=min[max(A)]

(11)

由上述分析可知，标准匈牙利算法在多无人机编队切换应用中只考虑了总飞行距离最短，而没有考虑在任务分配后单个飞机飞行的最大飞行距离。因此造成个别无人机的电量下降迅速相较于其他无人机提前降落且会造成其他无人机等待时间过长，影响整体编队飞行的时长。所以在算法的改进过程中将单个飞机飞行的最大飞行距离考虑在内就可以解决这个问题。

改进算法的核心在于如何缩减单机最大飞行距离，本文通过标准的匈牙利算随后将代价矩阵中比该值大的元素都赋值一个更大的元素M。在矩阵更新后，再通过标准的匈牙利算法进行求解。重复上述步骤，直至分配结果中出现元素M，接着返回上一次的分配结果，即可得出最优解。该算法可以保证在总的飞行距离尽可能小的情况下，缩小单个飞机飞行的最大飞行距离。算法具体求解的伪代码如下：

begin

输入：无人机的初始位置坐标(Xs,Ys,Zs),无人机目标的坐标(Xa,Ya,Zs)，

初始化：无人机数量n，矩阵H为n×n的零矩阵，最大元素M=0，矩阵A为1×n的零矩阵

For i=1 to n:

For j=1 to n:

Hij←Sij//将得到的距离值赋值到代价矩阵中

End for

End for

M←10×max(H)//M赋值为矩阵元素最大值的10倍

While Ture：

A←proceduce(Hungarian method)//进行标准匈牙利算法，并将结果赋值给A

If (max(A)=M)： //判断单个无人机飞行最大距离是否等于M

Break //等于则返回上一次结果，结束循环

End if

For i->1 to n:

For j->1 to n:

If (Hij≥max(A)),

Hij←M//将大于单个无人机最大飞行距离的值都赋值为M，更新代价矩阵

End if

End for

End for

a=A

End while

输出：最优分配结果a

End

注：M必须大于1倍max(H)，这样才能保证第一次循环不会报错，若小于等于1倍的maxH，第一次循环的分配结果的maxA有可能等于M导致循环报错。

1.3 算法说明

设代价矩阵H为：

(i=1,2,3,...,n;j=1,2,3,...,n)

(12)

由匈牙利算法计算结果为：

A=[S1J,S2J,S3J,...,S18J]，(j=1,2,3,...,n)

(13)

由标准的匈牙利算法可知，最大元素Smax=max(A)出现在最优解的结果中时，是因为在步骤1进行行归约、列归约和步骤3更新代价矩阵时该元素Sij被赋值为0。

即在步骤2进行试指派的代价矩阵中：Sij←0将大于等于Sij的元素都赋值为M记此时代价矩阵为H′，再进行匈牙利算法计算。

若分配结果中max(A′)=M时，说明在步骤1进行行归约、列归约和步骤3更新代价矩阵时某个为M的元素被赋值为0。此时在满足指派问题的约束条件下，必须将代价矩阵H′中等于M的元素添加到最优解中。

又因为已知元素等于M的值在原代价矩阵H中的值都是大于Sij的；所以上一次的分配结果A即为满足指派问题约束条件下的最优解。

2 实验结果与分析

2.1 实验背景

本次仿真模拟18架无人机的编队切换，每架无人机到达各自目标空域点后需要悬停，等待所有无人机就位后再开始执行任务，比如多无人机定点拍照、监控或测量、协同打击等。本文提出的方法是在已知无人机自身的位置和周围环境信息下的目标分配与航迹规划方法。无人机的初始位置坐标由自身携带的定位系统确定，目标位置坐标由无人机控制系统给定。

假定无人机初始位置坐标：

A_x=[100,140,180,220,260,300,100,140,180,140,260,260,260,140,140,140,180,220]

A_y=[400,400,400,400,400,400,100,100,100,350,300,250,200,150,200,300,250,250]

A_z=[500,500,500,500,500,500,200,200,200,450,400,350,300,250,300,400,350,350]

将上述对应初始位置的无人机进行编号为1-18。

无人机目标点位置坐标：

B_x=[100,140,180,220,260,300,100,140,180,100,260,260,260,220,120,160,200,240]

B_y=[400,400,400,400,400,400,100,100,100,350,350,150,100,100,150,190,260,315]

B_z=[500,500,500,500,500,500,200,200,200,450,450,250,200,200,250,290,360,415]

将上述对应目标点位置编号为任务1～18。

编队飞行实验从队形F到队形Z，如图3～4所示。

图3 编队F 图4 编队Z

为了验证算法的性能，针对上述问题设计了粒子群算法并且分别用标准的匈牙利算法、m次方的匈牙利算法[18]、和本文中改进的匈牙利算法进行目标位置的分配，无人机编队切换航线由各算法的目标分配结果确定，以二维空间的下匈牙利算法为例，其坐标值为上述坐标中去除z轴坐标，将初始位置坐标和目标点坐标赋予匈牙利算法，得到目标分配结果。算法输出结果如下：任务1～18依次分配的无人机编号为：

[1,2,3,4,5,6,7,8,9,10,11,13,12,15,16,18,17,14]。根据算法分配结果的飞行路线如图5所示，图中圆表示无人机的初始位置，*号表示无人机的目标位置。对应的飞行距离为：

[0,0,0,0,0,0,0,0,0,40,50,150,50,20,22,101,22,150]

图5 无人机编队切换示例

2.2 粒子群算法

粒子群算法的思想是模拟鸟群捕食的行为演化而来，捕食的鸟群都是通过各自的搜索与群体的合作最终发现食物所在的位置。通过一种无质量的粒子来模拟鸟群中的鸟，每个粒子含有两种属性，速度和位置，速度表示移动的快慢，位置表示移动的方向。算法中将无人机当作粒子，首先，每个无人机在空间中搜索当前个体极值，每个个体极值通过比较，以此找到当前最优的个体极值作为当前全局最优解，根据当前全局最优，粒子来调整自己的速度和位置，往最优化方向靠近来求得最优解。

而本次任务要求分配方案要满足无人机飞行路径相近，因此，在粒子搜索最优解(即路径和最小)的过程中加入第一优先级：满足相近条件。在相近的条件下，再来找到路径和最小。PSO算法流程图，如图6所示。

图6 PSO算法流程图

2.3 实验结果

将无人机的初始位置和目标位置分别赋予给匈牙利算法、m次方的匈牙利算法、粒子群算法和本文中改进的匈牙利算法，通过各算法给出的目标分配结果指定无人机的航线并计算无人机的飞行距离。文献[18]中比较了当m分别等于2、3、4情况下算法的匹配结果，当m越大时，其结果变化趋势与之前相同，综合考虑优化参数和实际中对路线的要求，最终将m的值设定为2。本次实验中引入该算法，并且分别比较当m等于2和3两种情况下的匹配结果。如表1所示为上述各算法的目标分配结果，可见各算法的匹配结果不见相同。

由图7可知，无人机按照各算法的匹配结果飞至指点目标位置的飞行距离中，匈牙利算法的单个无人机的飞行距离最长为212.13 m，其次是粒子群算法为156.84 m，m次方的匈牙利算法和本文提出的改进的匈牙利算法均为141.42 m。单个无人机的飞行距离影响着无人机的编队切换时长和悬停等待能耗，同时也可以降低各无人的能耗差，延长无人机的整体编队飞行时长，m次方的匈牙利算法和本文提出的改进的匈牙利算法在这方面均表现良好。

图7 根据各算法匹配结果无人机飞至指定目标的距离

无人机的编队切换时间取决于最大飞行距离，并且无

表1 各算法的任务匹配结果

人机的能耗取决于悬停等待时间和飞行的距离。由表2可知，粒子群算法相比于匈牙利算法，其最大飞行距离虽然缩短了，但粒子群算法不仅有着大量的参数设置，并且其结果不如其他的改进算法，计算结果和效率明显欠缺。相对于其他算法，改进的匈牙利算法得到的最大飞行距离最小，且总距离只比匈牙利算法多了11 m；m次方匈牙利算法的匈牙利算法的最大距离虽然和改进的匈牙利算法一致，但其总的飞行距离比较大，影响无人机编队切换的总体能耗。改进的匈牙利算法不仅缩减了无人机的等待和编队切换时间，还降低了无人机悬停等待能耗和各无人机之间的能耗差，同时其总的飞行距离和平均距离较小，无人机的飞行能耗也较小，降低了整体编队的耗能，延长了整体编队飞行时间。

表2 算法结果对比

经过实验对比，本文提出的算法在面对每架无人机到达各自目标空域点后需要悬停，等待所有无人机就位后再开始执行任务这类场景下的目标分配表现良好。不仅可以缩短无人机的编队切换时间，还可以降低无人机的总体能耗和各无人机的能耗差，延长无人机的整体编队飞行时间。并且该算法简单，无需占用太多的计算资源，相比于计算智能领域的各种算法如粒子群算法、蚁群算法等，没有过多的参数设置并且其分配结果不会因为参数的改变而变化，适用于无人机嵌入式系统实时计算。能够适应时间协同性强的目标分配系统；如无人机编队表演时能延长整体编队飞行时长，缩短编队切换时间；对敌方目标进行协同打击时能缩短无人机的集结时间，快速完成打击任务等。

3 结束语

标准匈牙利算法在无人机编队切换中存在问题，即单个无人机飞行距离过长，造成其他无人机悬停等待过长，影响编队切换的时长又以及因为各个无人机能耗差别导致个别无人机的电量下降迅速而提前降落，影响整体编队飞行时间。单个无人机的飞行距离可通过粒子群等智能优化算法有效缩短飞行距离，但存在参数的选取等问题，在一部分系统中不能很好的得到最优解，且只考虑了单个无人机的飞行距离，未将总的飞行距离考虑在内。通过仿真实例，利用匈牙利算法特性，将目标函数改为求解满足约束条件下单个无人机的最大飞行距离最小。经过改进的匈牙利算法对无人机编队切换有着很好的表现，虽然标准的匈牙利算法可以得到飞行总距离最小的最优解，但使用改进的匈牙利可以在总距离变化不大的情况下，最大化的减小单个无人机的飞行距离。可以有效的降低单个无人机的最大能耗，减少无人机在编队切换时悬停等待和编队切换的时间，有效延长整个编队飞行的时间。本文提出的方法相较于匈牙利算法、粒子群算法及m次方的匈牙利算法更适用于无人机飞行时的编队切换，能够缩短无人编队切换的时间，提升整体飞行的时长；同时适用于具有时间协同性的目标分配系统及性能指标为最小化单个个体指标的协同目标分配系统，算法简单具有良好的适用性。