改进自组织映射的多无人机协同任务分配方法

孙亚男，吴杰宏，石峻岭，高利军

（沈阳航空航天大学 计算机学院，沈阳 110136）

0 引言

无人机（Unmanned Aerial Vehicle，UAV）具有低成本、高机动性、强隐蔽性等特点，在很多方面得到了应用，例如：勘探［1］、区域搜索与救援［2-3］、货物运输［4］等。由于任务环境的复杂性，单个无人机逐渐不能满足高难度任务的需求，多架无人机协同工作受到了学者的关注［5-7］。多无人机协同能够扩大任务范围，减少任务完成时间，提高任务的完成率。协同任务分配问题作为无人机协同工作的基础，在求解时需要考虑任务规模、无人机的数量以及执行任务的能力等多种因素，是一个非确定性多项式完全问题（Non-deterministic Polynomial Complete problem，NPC）［8］。

对于多无人机协同任务分配问题的研究，首先需要将实际问题进行数学建模，使用合适的数学模型准确表示实际问题。现阶段的研究中，描述该问题常使用的数学模型包括多旅行商问题（Multiple Travelling Salesman Problem，MTSP）、车辆路径问题（Vehicle Routing Problem，VRP）、混合整数线性规划（Mixed Integer Linear Programming，MILP）、协同多任务分配问题。其中应用最广泛的是MTSP，作为旅行商问题（Travelling Salesman Problem，TSP）［9］的一个变体，能弥补其不能解决大规模问题的缺陷，且模型原理简单、可扩展性强，能充分发挥多无人机协同合作的优势。

解决MTSP 主要分为精确法和启发式的方法。最著名的精确算法是分支定界法，首先被提出来求解大规模对称MTSP［10］。精确算法有严格的数学基础，但算法解决问题的能力完全取决于问题的大小，当规模太大时，问题无法在可接受的时间内得到解，甚至无法解决。

为了解决上述计算困难的问题，越来越多的学者将研究的重点转移到启发式算法上来，因为能够容易得到MTSP 的最优解或者次优解。Jiang 等［11］针对MTSP，将单亲遗传算法与蚁群算法相结合，提出了蚁群单亲遗传算法（Ant Colony-Partheno Genetic Algorithm，AC-PGA），在大规模MTSP 求解上具有足够的有效性，且性能优于已有的算法；Zhou 等［12］为了解决具有多个仓库的最小MTSP，提出了单亲遗传算法（Partheno Genetic Algorithm，PGA）与改进的单亲遗传算法（Improved Partheno Genetic Algorithm，IPGA），在TSPLIB 数据集上的实验结果表明，IPGA 在求解MTSP 上具有较高的优越性；胡士娟等［13］针对MTSP，提出了一种模糊C 均值聚类单亲遗传算法，实验结果表明它在求解大规模问题时性能良好，收敛更快；张瑞鹏等［14］针对多无人机协同任务分配问题，提出了考虑航迹长度、任务收益以及完成时间的混合粒子群任务分配算法，提升了算法求解速度，还具有不断跳出局部收敛的能力。上述启发式算法虽然可以取得较好的效果，但在处理多无人机协同任务分配时，存在容易陷入局部最优、自适应能力较差的情况。自组织映射（Self-Organizing Map，SOM）神经网络可以避免陷入局部最小值的情况，并且快速收敛，提升任务分配方案的精度。

SOM 神经网络是一种竞争网络，由Kohonen 教授在20 世纪80 年代提出［15］，而后进行了扩展［16］。近年来，很多学者将SOM 算法应用在多机器人系统中。Zhu 等［17］使用一个启发自组织的图算法，安排一组自主水下航行器（Autonomous Underwater Vehicle，AUV）访问所有指定的目标位置；同时该团队利用SOM 神经网络对水下机器人的任务分配与路径规划问题进行了一系列的研究［18-20］。Zhu 等［21］利用基于SOM神经网络的算法将多机器人系统的任务分配与路径规划结合进行求解，使机器人能够在目的地确定之前就开始移动；但该方法容易导致机器人在多个目标之间迂回，且未考虑机器人自身约束条件。Yi 等［22］提出了一种基于SOM 的研究方法解决三维动态环境下的机器人群的任务分配问题，但没有考虑机器人系统完成任务的整体效率。

有关SOM 神经网络的研究大多针对多机器人的任务分配和控制，大多数方法仅考虑了机器人与任务之间的距离约束，并未考虑机器人资源、任务约束等。本文在多无人机协同任务分配时考虑了无人机的航迹长度和执行任务的时间，提出了改进的SOM（Improved Self-Organizing Map，ISOM）算法，保证了无人机之间的负载均衡，减少了任务完成的时间，降低了资源消耗。

1 模型建立

设定任务区域内的任务点分布在地面，UAV 在执行任务时始终保持在同一高度对地面进行观测。本文将UAV 进行抽象化处理，假定无人机均是相同的，具备导航、位置识别等基本功能，重点关注如何降低无人机的能量消耗、提升执行任务的效率。

1.1 无人机模型

本文将多无人机协同执行任务分配问题建模为多旅行商问题，其中旅行商代表UAV，城市代表任务区域内的任务。UAV 集合U={U1，U2，…，UN}，N表示UAV 数量，为了更好地描述UAV，通过四元组表示：Un=(st，post，v，ct)。st表示t时刻Un的状态，如式（1）所示：

其中：post=(xt，yt，zt)表示Un在t时刻的位置；v表示无人机的飞行速度；ct∈[0，1]表示t时刻Un的任务完成率，0 代表Un在基站等待，1 代表Un完成所有任务返回到基站，ct随着无人机执行任务的程度而变化。

1.2 任务模型

任务集合M={m1，m2，…，mK}，K表示区域内的任务数量，通过三元组表示任务：mi={，pos＇，a}，其中表示任务在t时刻的状态：未执行、已完成、执行中；pos＇=(x，y)表示任务点在区域内的位置；a表示完成任务需要的时间。任务的状态通过式（2）表示：

1.3 任务分配模型

Un分配的任务集合用πn表示，定义决策变量πnk，表示Un是否执行任务mk：

在保证模型有效的前提下，为了降低模型求解难度，对提出的模型作出以下合理假设：在任务分配时，所有目标的位置在任务区域内已知；UAV 携带足够的资源并能够完成任务。

本文从航迹长度和完成所有任务的时间两个方面评价多无人机协同任务分配的好坏。航迹长度如式（5）所示：

其中：dn表示在Un执行任务中的航迹长度。完成所有任务的时间与单个UAV 执行任务的时间息息相关，Un执行任务的时间如式（6）所示：

其中：v表示Un的飞行速度；dn与式（5）定义相同；mk(a)表示Un的任务分配集合πn中完成第k个任务需要执行的时间。t时刻Un的任务完成度的计算方法如式（7）所示：

多无人机协同完成任务区域内所有任务的时间如式（8）所示：

为了保证多无人机执行任务的效率，需要考虑其协同约束条件，任务集合M中的任务只能执行一次。决策变量πnk具有以下约束条件：在执行任务过程中，为了减少不必要的能量消耗，一个任务只能由一个UAV 执行。

同一时刻，任意一个UAV 只能执行一个任务：

任务区域内的所有任务均被执行：

2 ISOM协同分配方法

SOM 是一种无监督的神经网络，运用竞争学习策略，依靠神经元之间相互竞争逐步优化网络，且使用邻域函数来维持输入空间的拓扑结构。SOM 一般有2 层：输入层和竞争层。输入层的神经元的数量由输入向量的维度决定，一个神经元对应一个特征，用来接收外界信息，将输入向量向竞争层传递，起观察作用；竞争层对输入向量进行分析比较，寻找规律并进行分类。

ISOM 算法在SOM 的基础上实现，网络结构如图1 所示，神经网络分为3 层：输入层包括K个神经元，分别表示任务区域内K个任务的坐标位置mk(pos＇)；任务分配层包括K×N个神经 元，可以表示为 (π11，π12，…，π1K，π21，π22…，π2K，…，πN1，πN1…，πNK)，其中K个神经元一组，表示Un的任务分配情况。输入层与任务分配层的神经元全连接，连接mk(pos＇) →πnk的权重表示为wnk(wnkx，wnky)，表示任务mk分配给Un。执行任务顺序层根据任务分配层输入(πn1，πn2，…，πnk)，得到Un的执行任务的顺序。

图1 ISOM神经网络结构Fig.1 Neural network structure of ISOM

考虑到多个无人机的负载均衡，希望每个UAV 完成任务的效率相近，根据UAV 的在任务区域内时间，设计了它的负载均衡度，如式（12）所示：

ISOM 算法中选取获胜神经元考虑了与权重之间最相似的任务点以及Un的负载均衡度SLBn：

其中：式（16）表示任务mk与输出神经元πnk的连接权重之间的距离；式（15）在距离的基础上添加了负载均衡的因素，获胜神经元为最小的Dkn，这样在任务分配的过程中既考虑了相近的任务点，又考虑了多无人机的负载均衡。在传统的SOM 算法中，学习速率决定学习时间，如果设定过大，权重的更新幅度太大，导致学习中的效果不稳定；相反如果过小会使权重更新幅度较小，导致不容易收敛。在学习中通过动态地调整学习率能解决上述问题，使用参数α表示学习率，设定最大值αmax=0.5，最小值αmin=0.01，设计非线性函数更新α，如式（17）所示：

其中：iter表示当前的迭代次数；max(iter)表示训练过程中最大的迭代次数。

通过邻域半径确定优胜邻域的更新范围，参数σ表示邻域半径，设定初始值σmax=5，最小值σmax=0.1，通过非线性函数设计邻域半径的衰减函数如式（18）所示：

邻域函数决定了输入任务位置对优胜者和邻近神经元的影响，对获胜者的影响是最大的，这种影响随着神经元与优胜者之间的距离增大而减小，定义如式（19）：

其中：di＇表示神经元i与获胜神经元之间的距离，如果距离大于邻域半径，则其值为0。根据学习率α、邻域半径σ和邻域函数f(di＇，α)对神经元的权重进行更新：

ISOM 算法解决任务分配问题的具体步骤如下：

首先对ISOM 算法的参数初始化：对任务集合M中每个任务的位置坐标mk(pos＇)作标准化处理，具体如下所示：

其中：xmin、ymin、xmax、ymax分别表示任务点的位置在x轴和y轴的最小值与最大值。将神经网络的权重系数初始化为均值为0、方差为0.01 的服从高斯分布的随机数，初始化决策变量πnk和负载均衡度SLBn；然后不断更新学习率、邻域半径、权重等参数。当神经网络中权重保持不变时，认为ISOM 算法达到了收敛状态，得到多无人机协同任务分配结果。具体如算法1 所示。

算法1 ISOM 算法。

3 实验与结果分析

3.1 实验条件

本文首先对ISOM 算法进行验证，并与结合遗传算法的粒子群优化算法（Particle Swarm Optimization Combined with Genetic Algorithm，GA-PSO）［23］、Gurobi 算 法［24］、ORTools 算法［25］分别进行了对比；其次在TSPLIB［26］数据集中验证ISOM算法对大任务量的处理能力，并与杂草优化（Invasive Weed Optimization，IWO）算法［27］、IPGA［12］、AC-PGA［11］进行对比。本文通过多无人机完成任务的时间和执行任务的航行距离来评估算法的质量，其中完成任务时间以用时最长的无人机完成任务时间为准。

实验中设定无人机的速度v=50 m/s，任务的观测时间a=5 s。在1 800 m×1 200 m 的任务区域设置了10 个任务点T1～T10，表1 为各任务在任务区域内的位置信息。S表示多无人机的基站，坐标为(0，0)。

表1 任务点的位置信息Tab.1 Location information of task points

3.2 ISOM算法测试与验证

本文在3.1 节设置的任务场景对ISOM 算法进行测试与评估，图2 为ISOM 算法得到的任务分配方案。其中U1的执行顺序 为 (S，T5，T6，T9，T3，T8，S)，U2的执行 顺序为(S，T7，T1，T2，S)，U3的执行顺序为(S，T4，T10，S)。

图2 ISOM算法的任务分配方案Fig.2 Task assignment scheme of ISOM algorithm

表2 为ISOM 算法执行任务的数据，其中U2、U3完成各自分配任务的时间分别为85.99 s 和77.68 s，即使用ISOM 算法多无人机完成任务的时间为85.99 s。多无人机之间完成任务时间的极差（即无人机完成任务的最长时间与最短时间的差值）为8.31 s，整体上完成任务的时间相近。

表2 ISOM算法的执行任务结果Tab.2 Execution results of ISOM algorithm

在ISOM 算法训练过程中，通过负载均衡度SLBn来实现多无人机之间的负载均衡，图3 为ISOM 算法在训练过程中单个UAV 完成任务的时间变化。纵轴表示UAV 完成分配任务的时间，包括飞行时间和在任务点悬停的时间。从图中可以看出在60 个回合左右算法到达收敛状态，且每个UAV 完成任务的时间相近，实现了多无人机间的负载均衡。

图3 ISOM算法的收敛分析Fig.3 Convergence analysis of ISOM algorithm

3.3 ISOM算法与其他算法对比

3.3.1 复杂多任务场景的对比

图4（a）是GA-PSO 解决3.1 节中问题的任务分配方案，其 中U1的执行 顺序为(S，T3，T9，T4，S)，U2的执行 顺序为(S，T6，T7，T2，T1，T10，S)，U3的执行顺序为(S，T5，T8，S)，任务区域内的所有任务均被执行。

图4 对比算法的任务分配方案Fig.4 Task assignment schemes of comparison algorithms

图4（b）是Gurobi 算法解决3.1 节中问题的任务分配方案，其中U1的执行顺序为(S，T9，T2，T7，T6，S)，U2的执行顺序为(S，T4，T10，T3，T5，T8，S)，U3的执行顺序为(S，T1，S)，任务区域内的所有任务均被执行。

图4（c）是ORTools 解决3.1 节中问题的任务分配方案，其 中U1的执行 顺序为(S，T2，T1，T8，S)，U2的执行 顺序为(S，T5，T7，T6，S)，U3的执行顺序为(S，T3，T9，T10，T4，S)，任务区域内的所有任务均被执行。

表3 为对比算法执行任务的具体数据，GA-PSO 得到的任务分配方案虽然整体航迹长度与其他算法相比较短，但单个无人机完成任务时间差距比较大，没有发挥多无人机协同的优势，导致总任务的完成时间比较长。Gurobi 算法得到的任务分配方案中，单个无人机完成任务时间与GA-PSO 相比，多无人机的负载均衡效果提升了，但整体上完成任务的时间仍比ISOM 算法长。ORTools 算法得到的任务分配方案较GA-PSO 和Gurobi 算法得到的任务方案有一定提升，但整体上完成任务的时间仍比ISOM 算法长。

表3 对比算法的任务执行数据Tab.3 Task execution data of comparison algorithms

表4 为上述4 个对比算法得到任务分配方案后，在无人机的速度v=50 m/s，任务点的观测时间a=5 s 时，任务区域内所有任务均被执行的时间。使用极差表示多无人机之间的负载均衡。由表4 可知，ISOM 算法的极差最小，多无人机之间完成任务的时间相近，能很好地实现多无人机之间的负载均衡；在完成区域内所有任务的时间上，ISOM 算法较GAPSO 减少了15.5%，较Gurobi 时间减少了12.7%，较ORTools时间减少了7.3%，说明ISOM 算法提高了多无人机完成任务的效率。

表4 不同算法完成任务的时间 单位：sTab.4 Task complementation time of different algorithms unit：s

3.3.2 大任务量环境的验证

在实际应用中，由于环境的复杂性，一个任务区域内往往存在大量的任务。为了验证ISOM 算法在处理大任务数量时的任务分配能力，采用国际通用算例库TSPLIB 进行实验，并与IWO 算法、AC-PGA、IPGA 进行对比。分别设置任务数量K=100，150，200，对 应TSPLIB 的实例 为KroA100、KroA150、KroA200，实验结果见表5。

表5 不同算法的任务分配方案的航迹长度 单位：mTab.5 Track lengths of task assignment schemes of different algorithms unit：m

由表5 可知，无人机数量N=2，3，4，5，8 时，ISOM 算法在各实例下均获得了最短的航迹长度（加粗数据）。如N=2：当任务数量为100 时，与IWO 算法、IPGA、AC-PGA 相比，ISOM算法的航迹长度分别减少了44.96%、23.61%、17.05%；当任务数量为150 时，ISOM 算法的航迹长度分别减少了59.03%、39.59%、18.02%；任务数量为200 时，ISOM 算法的航迹长度分别减少了53.44%、43.15%、10.59%。这说明随着任务数量逐渐增加，ISOM 算法提升的效果逐渐明显，在大任务数量的场景下，能够较少消耗无人机的能量。

4 结语

本文针对多无人机协同任务分配问题，从无人机之间负载均衡和算法的稳定性出发，提出了ISOM 算法，为解决该问题提供了一种新的思路，通过与已有算法的对比，显示了本文算法的有效性和鲁棒性，特别是当任务数量较大时，在缩短轨迹长度和减少能量消耗方面有很大优势。下一步的研究工作将专注于异构无人机的协同任务分配方法上。