改進自組織映射的多無人機協(xié)同任務分配方法

孫亞男，吳杰宏，石峻嶺，高利軍

（沈陽航空航天大學 計算機學院，沈陽 110136）

0 引言

無人機（Unmanned Aerial Vehicle，UAV）具有低成本、高機動性、強隱蔽性等特點，在很多方面得到了應用，例如：勘探［1］、區(qū)域搜索與救援［2-3］、貨物運輸［4］等。由于任務環(huán)境的復雜性，單個無人機逐漸不能滿足高難度任務的需求，多架無人機協(xié)同工作受到了學者的關注［5-7］。多無人機協(xié)同能夠擴大任務范圍，減少任務完成時間，提高任務的完成率。協(xié)同任務分配問題作為無人機協(xié)同工作的基礎，在求解時需要考慮任務規(guī)模、無人機的數(shù)量以及執(zhí)行任務的能力等多種因素，是一個非確定性多項式完全問題（Non-deterministic Polynomial Complete problem，NPC）［8］。

對于多無人機協(xié)同任務分配問題的研究，首先需要將實際問題進行數(shù)學建模，使用合適的數(shù)學模型準確表示實際問題。現(xiàn)階段的研究中，描述該問題常使用的數(shù)學模型包括多旅行商問題（Multiple Travelling Salesman Problem，MTSP）、車輛路徑問題（Vehicle Routing Problem，VRP）、混合整數(shù)線性規(guī)劃（Mixed Integer Linear Programming，MILP）、協(xié)同多任務分配問題。其中應用最廣泛的是MTSP，作為旅行商問題（Travelling Salesman Problem，TSP）［9］的一個變體，能彌補其不能解決大規(guī)模問題的缺陷，且模型原理簡單、可擴展性強，能充分發(fā)揮多無人機協(xié)同合作的優(yōu)勢。

解決MTSP 主要分為精確法和啟發(fā)式的方法。最著名的精確算法是分支定界法，首先被提出來求解大規(guī)模對稱MTSP［10］。精確算法有嚴格的數(shù)學基礎，但算法解決問題的能力完全取決于問題的大小，當規(guī)模太大時，問題無法在可接受的時間內(nèi)得到解，甚至無法解決。

為了解決上述計算困難的問題，越來越多的學者將研究的重點轉移到啟發(fā)式算法上來，因為能夠容易得到MTSP 的最優(yōu)解或者次優(yōu)解。Jiang 等［11］針對MTSP，將單親遺傳算法與蟻群算法相結合，提出了蟻群單親遺傳算法（Ant Colony-Partheno Genetic Algorithm，AC-PGA），在大規(guī)模MTSP 求解上具有足夠的有效性，且性能優(yōu)于已有的算法；Zhou 等［12］為了解決具有多個倉庫的最小MTSP，提出了單親遺傳算法（Partheno Genetic Algorithm，PGA）與改進的單親遺傳算法（Improved Partheno Genetic Algorithm，IPGA），在TSPLIB 數(shù)據(jù)集上的實驗結果表明，IPGA 在求解MTSP 上具有較高的優(yōu)越性；胡士娟等［13］針對MTSP，提出了一種模糊C 均值聚類單親遺傳算法，實驗結果表明它在求解大規(guī)模問題時性能良好，收斂更快；張瑞鵬等［14］針對多無人機協(xié)同任務分配問題，提出了考慮航跡長度、任務收益以及完成時間的混合粒子群任務分配算法，提升了算法求解速度，還具有不斷跳出局部收斂的能力。上述啟發(fā)式算法雖然可以取得較好的效果，但在處理多無人機協(xié)同任務分配時，存在容易陷入局部最優(yōu)、自適應能力較差的情況。自組織映射（Self-Organizing Map，SOM）神經(jīng)網(wǎng)絡可以避免陷入局部最小值的情況，并且快速收斂，提升任務分配方案的精度。

SOM 神經(jīng)網(wǎng)絡是一種競爭網(wǎng)絡，由Kohonen 教授在20 世紀80 年代提出［15］，而后進行了擴展［16］。近年來，很多學者將SOM 算法應用在多機器人系統(tǒng)中。Zhu 等［17］使用一個啟發(fā)自組織的圖算法，安排一組自主水下航行器（Autonomous Underwater Vehicle，AUV）訪問所有指定的目標位置；同時該團隊利用SOM 神經(jīng)網(wǎng)絡對水下機器人的任務分配與路徑規(guī)劃問題進行了一系列的研究［18-20］。Zhu 等［21］利用基于SOM神經(jīng)網(wǎng)絡的算法將多機器人系統(tǒng)的任務分配與路徑規(guī)劃結合進行求解，使機器人能夠在目的地確定之前就開始移動；但該方法容易導致機器人在多個目標之間迂回，且未考慮機器人自身約束條件。Yi 等［22］提出了一種基于SOM 的研究方法解決三維動態(tài)環(huán)境下的機器人群的任務分配問題，但沒有考慮機器人系統(tǒng)完成任務的整體效率。

有關SOM 神經(jīng)網(wǎng)絡的研究大多針對多機器人的任務分配和控制，大多數(shù)方法僅考慮了機器人與任務之間的距離約束，并未考慮機器人資源、任務約束等。本文在多無人機協(xié)同任務分配時考慮了無人機的航跡長度和執(zhí)行任務的時間，提出了改進的SOM（Improved Self-Organizing Map，ISOM）算法，保證了無人機之間的負載均衡，減少了任務完成的時間，降低了資源消耗。

1 模型建立

設定任務區(qū)域內(nèi)的任務點分布在地面，UAV 在執(zhí)行任務時始終保持在同一高度對地面進行觀測。本文將UAV 進行抽象化處理，假定無人機均是相同的，具備導航、位置識別等基本功能，重點關注如何降低無人機的能量消耗、提升執(zhí)行任務的效率。

1.1 無人機模型

本文將多無人機協(xié)同執(zhí)行任務分配問題建模為多旅行商問題，其中旅行商代表UAV，城市代表任務區(qū)域內(nèi)的任務。UAV 集合U={U1，U2，…，UN}，N表示UAV 數(shù)量，為了更好地描述UAV，通過四元組表示：Un=(st，post，v，ct)。st表示t時刻Un的狀態(tài)，如式（1）所示：

其中：post=(xt，yt，zt)表示Un在t時刻的位置；v表示無人機的飛行速度；ct∈[0，1]表示t時刻Un的任務完成率，0 代表Un在基站等待，1 代表Un完成所有任務返回到基站，ct隨著無人機執(zhí)行任務的程度而變化。

1.2 任務模型

任務集合M={m1，m2，…，mK}，K表示區(qū)域內(nèi)的任務數(shù)量，通過三元組表示任務：mi={，pos＇，a}，其中表示任務在t時刻的狀態(tài)：未執(zhí)行、已完成、執(zhí)行中；pos＇=(x，y)表示任務點在區(qū)域內(nèi)的位置；a表示完成任務需要的時間。任務的狀態(tài)通過式（2）表示：

1.3 任務分配模型

Un分配的任務集合用πn表示，定義決策變量πnk，表示Un是否執(zhí)行任務mk：

在保證模型有效的前提下，為了降低模型求解難度，對提出的模型作出以下合理假設：在任務分配時，所有目標的位置在任務區(qū)域內(nèi)已知；UAV 攜帶足夠的資源并能夠完成任務。

本文從航跡長度和完成所有任務的時間兩個方面評價多無人機協(xié)同任務分配的好壞。航跡長度如式（5）所示：

其中：dn表示在Un執(zhí)行任務中的航跡長度。完成所有任務的時間與單個UAV 執(zhí)行任務的時間息息相關，Un執(zhí)行任務的時間如式（6）所示：

其中：v表示Un的飛行速度；dn與式（5）定義相同；mk(a)表示Un的任務分配集合πn中完成第k個任務需要執(zhí)行的時間。t時刻Un的任務完成度的計算方法如式（7）所示：

多無人機協(xié)同完成任務區(qū)域內(nèi)所有任務的時間如式（8）所示：

為了保證多無人機執(zhí)行任務的效率，需要考慮其協(xié)同約束條件，任務集合M中的任務只能執(zhí)行一次。決策變量πnk具有以下約束條件：在執(zhí)行任務過程中，為了減少不必要的能量消耗，一個任務只能由一個UAV 執(zhí)行。

同一時刻，任意一個UAV 只能執(zhí)行一個任務：

任務區(qū)域內(nèi)的所有任務均被執(zhí)行：

2 ISOM協(xié)同分配方法

SOM 是一種無監(jiān)督的神經(jīng)網(wǎng)絡，運用競爭學習策略，依靠神經(jīng)元之間相互競爭逐步優(yōu)化網(wǎng)絡，且使用鄰域函數(shù)來維持輸入空間的拓撲結構。SOM 一般有2 層：輸入層和競爭層。輸入層的神經(jīng)元的數(shù)量由輸入向量的維度決定，一個神經(jīng)元對應一個特征，用來接收外界信息，將輸入向量向競爭層傳遞，起觀察作用；競爭層對輸入向量進行分析比較，尋找規(guī)律并進行分類。

ISOM 算法在SOM 的基礎上實現(xiàn)，網(wǎng)絡結構如圖1 所示，神經(jīng)網(wǎng)絡分為3 層：輸入層包括K個神經(jīng)元，分別表示任務區(qū)域內(nèi)K個任務的坐標位置mk(pos＇)；任務分配層包括K×N個神經(jīng) 元，可以表示為 (π11，π12，…，π1K，π21，π22…，π2K，…，πN1，πN1…，πNK)，其中K個神經(jīng)元一組，表示Un的任務分配情況。輸入層與任務分配層的神經(jīng)元全連接，連接mk(pos＇) →πnk的權重表示為wnk(wnkx，wnky)，表示任務mk分配給Un。執(zhí)行任務順序層根據(jù)任務分配層輸入(πn1，πn2，…，πnk)，得到Un的執(zhí)行任務的順序。

圖1 ISOM神經(jīng)網(wǎng)絡結構Fig.1 Neural network structure of ISOM

考慮到多個無人機的負載均衡，希望每個UAV 完成任務的效率相近，根據(jù)UAV 的在任務區(qū)域內(nèi)時間，設計了它的負載均衡度，如式（12）所示：

ISOM 算法中選取獲勝神經(jīng)元考慮了與權重之間最相似的任務點以及Un的負載均衡度SLBn：

其中：式（16）表示任務mk與輸出神經(jīng)元πnk的連接權重之間的距離；式（15）在距離的基礎上添加了負載均衡的因素，獲勝神經(jīng)元為最小的Dkn，這樣在任務分配的過程中既考慮了相近的任務點，又考慮了多無人機的負載均衡。在傳統(tǒng)的SOM 算法中，學習速率決定學習時間，如果設定過大，權重的更新幅度太大，導致學習中的效果不穩(wěn)定；相反如果過小會使權重更新幅度較小，導致不容易收斂。在學習中通過動態(tài)地調(diào)整學習率能解決上述問題，使用參數(shù)α表示學習率，設定最大值αmax=0.5，最小值αmin=0.01，設計非線性函數(shù)更新α，如式（17）所示：

其中：iter表示當前的迭代次數(shù)；max(iter)表示訓練過程中最大的迭代次數(shù)。

通過鄰域半徑確定優(yōu)勝鄰域的更新范圍，參數(shù)σ表示鄰域半徑，設定初始值σmax=5，最小值σmax=0.1，通過非線性函數(shù)設計鄰域半徑的衰減函數(shù)如式（18）所示：

鄰域函數(shù)決定了輸入任務位置對優(yōu)勝者和鄰近神經(jīng)元的影響，對獲勝者的影響是最大的，這種影響隨著神經(jīng)元與優(yōu)勝者之間的距離增大而減小，定義如式（19）：

其中：di＇表示神經(jīng)元i與獲勝神經(jīng)元之間的距離，如果距離大于鄰域半徑，則其值為0。根據(jù)學習率α、鄰域半徑σ和鄰域函數(shù)f(di＇，α)對神經(jīng)元的權重進行更新：

ISOM 算法解決任務分配問題的具體步驟如下：

首先對ISOM 算法的參數(shù)初始化：對任務集合M中每個任務的位置坐標mk(pos＇)作標準化處理，具體如下所示：

其中：xmin、ymin、xmax、ymax分別表示任務點的位置在x軸和y軸的最小值與最大值。將神經(jīng)網(wǎng)絡的權重系數(shù)初始化為均值為0、方差為0.01 的服從高斯分布的隨機數(shù)，初始化決策變量πnk和負載均衡度SLBn；然后不斷更新學習率、鄰域半徑、權重等參數(shù)。當神經(jīng)網(wǎng)絡中權重保持不變時，認為ISOM 算法達到了收斂狀態(tài)，得到多無人機協(xié)同任務分配結果。具體如算法1 所示。

算法1 ISOM 算法。

3 實驗與結果分析

3.1 實驗條件

本文首先對ISOM 算法進行驗證，并與結合遺傳算法的粒子群優(yōu)化算法（Particle Swarm Optimization Combined with Genetic Algorithm，GA-PSO）［23］、Gurobi 算 法［24］、ORTools 算法［25］分別進行了對比；其次在TSPLIB［26］數(shù)據(jù)集中驗證ISOM算法對大任務量的處理能力，并與雜草優(yōu)化（Invasive Weed Optimization，IWO）算法［27］、IPGA［12］、AC-PGA［11］進行對比。本文通過多無人機完成任務的時間和執(zhí)行任務的航行距離來評估算法的質量，其中完成任務時間以用時最長的無人機完成任務時間為準。

實驗中設定無人機的速度v=50 m/s，任務的觀測時間a=5 s。在1 800 m×1 200 m 的任務區(qū)域設置了10 個任務點T1～T10，表1 為各任務在任務區(qū)域內(nèi)的位置信息。S表示多無人機的基站，坐標為(0，0)。

表1 任務點的位置信息Tab.1 Location information of task points

3.2 ISOM算法測試與驗證

本文在3.1 節(jié)設置的任務場景對ISOM 算法進行測試與評估，圖2 為ISOM 算法得到的任務分配方案。其中U1的執(zhí)行順序 為 (S，T5，T6，T9，T3，T8，S)，U2的執(zhí)行 順序為(S，T7，T1，T2，S)，U3的執(zhí)行順序為(S，T4，T10，S)。

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

表2 為ISOM 算法執(zhí)行任務的數(shù)據(jù)，其中U2、U3完成各自分配任務的時間分別為85.99 s 和77.68 s，即使用ISOM 算法多無人機完成任務的時間為85.99 s。多無人機之間完成任務時間的極差（即無人機完成任務的最長時間與最短時間的差值）為8.31 s，整體上完成任務的時間相近。

表2 ISOM算法的執(zhí)行任務結果Tab.2 Execution results of ISOM algorithm

在ISOM 算法訓練過程中，通過負載均衡度SLBn來實現(xiàn)多無人機之間的負載均衡，圖3 為ISOM 算法在訓練過程中單個UAV 完成任務的時間變化?？v軸表示UAV 完成分配任務的時間，包括飛行時間和在任務點懸停的時間。從圖中可以看出在60 個回合左右算法到達收斂狀態(tài)，且每個UAV 完成任務的時間相近，實現(xiàn)了多無人機間的負載均衡。

圖3 ISOM算法的收斂分析Fig.3 Convergence analysis of ISOM algorithm

3.3 ISOM算法與其他算法對比

3.3.1 復雜多任務場景的對比

圖4（a）是GA-PSO 解決3.1 節(jié)中問題的任務分配方案，其 中U1的執(zhí)行 順序為(S，T3，T9，T4，S)，U2的執(zhí)行 順序為(S，T6，T7，T2，T1，T10，S)，U3的執(zhí)行順序為(S，T5，T8，S)，任務區(qū)域內(nèi)的所有任務均被執(zhí)行。

圖4 對比算法的任務分配方案Fig.4 Task assignment schemes of comparison algorithms

圖4（b）是Gurobi 算法解決3.1 節(jié)中問題的任務分配方案，其中U1的執(zhí)行順序為(S，T9，T2，T7，T6，S)，U2的執(zhí)行順序為(S，T4，T10，T3，T5，T8，S)，U3的執(zhí)行順序為(S，T1，S)，任務區(qū)域內(nèi)的所有任務均被執(zhí)行。

圖4（c）是ORTools 解決3.1 節(jié)中問題的任務分配方案，其 中U1的執(zhí)行 順序為(S，T2，T1，T8，S)，U2的執(zhí)行 順序為(S，T5，T7，T6，S)，U3的執(zhí)行順序為(S，T3，T9，T10，T4，S)，任務區(qū)域內(nèi)的所有任務均被執(zhí)行。

表3 為對比算法執(zhí)行任務的具體數(shù)據(jù)，GA-PSO 得到的任務分配方案雖然整體航跡長度與其他算法相比較短，但單個無人機完成任務時間差距比較大，沒有發(fā)揮多無人機協(xié)同的優(yōu)勢，導致總任務的完成時間比較長。Gurobi 算法得到的任務分配方案中，單個無人機完成任務時間與GA-PSO 相比，多無人機的負載均衡效果提升了，但整體上完成任務的時間仍比ISOM 算法長。ORTools 算法得到的任務分配方案較GA-PSO 和Gurobi 算法得到的任務方案有一定提升，但整體上完成任務的時間仍比ISOM 算法長。

表3 對比算法的任務執(zhí)行數(shù)據(jù)Tab.3 Task execution data of comparison algorithms

表4 為上述4 個對比算法得到任務分配方案后，在無人機的速度v=50 m/s，任務點的觀測時間a=5 s 時，任務區(qū)域內(nèi)所有任務均被執(zhí)行的時間。使用極差表示多無人機之間的負載均衡。由表4 可知，ISOM 算法的極差最小，多無人機之間完成任務的時間相近，能很好地實現(xiàn)多無人機之間的負載均衡；在完成區(qū)域內(nèi)所有任務的時間上，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 大任務量環(huán)境的驗證

在實際應用中，由于環(huán)境的復雜性，一個任務區(qū)域內(nèi)往往存在大量的任務。為了驗證ISOM 算法在處理大任務數(shù)量時的任務分配能力，采用國際通用算例庫TSPLIB 進行實驗，并與IWO 算法、AC-PGA、IPGA 進行對比。分別設置任務數(shù)量K=100，150，200，對 應TSPLIB 的實例 為KroA100、KroA150、KroA200，實驗結果見表5。

表5 不同算法的任務分配方案的航跡長度 單位：mTab.5 Track lengths of task assignment schemes of different algorithms unit：m

由表5 可知，無人機數(shù)量N=2，3，4，5，8 時，ISOM 算法在各實例下均獲得了最短的航跡長度（加粗數(shù)據(jù)）。如N=2：當任務數(shù)量為100 時，與IWO 算法、IPGA、AC-PGA 相比，ISOM算法的航跡長度分別減少了44.96%、23.61%、17.05%；當任務數(shù)量為150 時，ISOM 算法的航跡長度分別減少了59.03%、39.59%、18.02%；任務數(shù)量為200 時，ISOM 算法的航跡長度分別減少了53.44%、43.15%、10.59%。這說明隨著任務數(shù)量逐漸增加，ISOM 算法提升的效果逐漸明顯，在大任務數(shù)量的場景下，能夠較少消耗無人機的能量。

4 結語

本文針對多無人機協(xié)同任務分配問題，從無人機之間負載均衡和算法的穩(wěn)定性出發(fā)，提出了ISOM 算法，為解決該問題提供了一種新的思路，通過與已有算法的對比，顯示了本文算法的有效性和魯棒性，特別是當任務數(shù)量較大時，在縮短軌跡長度和減少能量消耗方面有很大優(yōu)勢。下一步的研究工作將專注于異構無人機的協(xié)同任務分配方法上。