基于改進(jìn)蛙跳算法的多無(wú)人機(jī)協(xié)同任務(wù)分配研究*

張耀中，趙雪芳，豐文成

（西北工業(yè)大學(xué)電子信息學(xué)院，西安 710072）

0 引言

隨著無(wú)人機(jī)（unmanned aerial vehicle，UAV）的廣泛使用，多架UAV 協(xié)同作戰(zhàn)應(yīng)用已經(jīng)成為當(dāng)前的研究熱點(diǎn)之一。合理有效的任務(wù)分配是發(fā)揮多UAV 協(xié)同優(yōu)勢(shì)的關(guān)鍵技術(shù)，多UAV 協(xié)同任務(wù)分配涉及戰(zhàn)場(chǎng)態(tài)勢(shì)、UAV 自身性能和任務(wù)特性等諸多要素，是多種約束條件下的大規(guī)模協(xié)調(diào)控制問(wèn)題。

國(guó)內(nèi)外學(xué)者針對(duì)任務(wù)分配問(wèn)題進(jìn)行了大量研究，通常將該問(wèn)題轉(zhuǎn)化為一些經(jīng)典模型，如多旅行商問(wèn)題（MTSP）模型［1］、車(chē)輛路徑問(wèn)題（VRP）模型［2］、混合整數(shù)線性規(guī)劃（MILP）模型［3］等，同時(shí)也提出了許多有效的算法來(lái)求解任務(wù)分配問(wèn)題。文獻(xiàn)［4］通過(guò)重新隨機(jī)方式對(duì)陷入“停止”和局部最優(yōu)的粒子進(jìn)行重置，將粒子群算法（PSO）與貪心算法相結(jié)合來(lái)求解任務(wù)分配問(wèn)題。文獻(xiàn)［5］將細(xì)菌覓食算法與粒子群算法相結(jié)合，提出了混合細(xì)菌覓食算法，并對(duì)動(dòng)態(tài)重分配策略進(jìn)行改進(jìn)，增加了對(duì)突發(fā)事件的處理能力。文獻(xiàn)［7］針對(duì)異構(gòu)無(wú)人機(jī)在攻擊與評(píng)估時(shí)的任務(wù)分配問(wèn)題，提出了將引力搜索算法與遺傳算法相結(jié)合的混合算法。

目前，國(guó)內(nèi)外針對(duì)任務(wù)的預(yù)分配及動(dòng)態(tài)分配問(wèn)題已經(jīng)取得了不少成果，但通常針對(duì)的UAV 類(lèi)型、任務(wù)類(lèi)型較為單一，特別是針對(duì)任務(wù)場(chǎng)景中出現(xiàn)的突發(fā)型任務(wù)，算法的求解收斂速度往往較慢。本文針對(duì)上述問(wèn)題，建立了協(xié)同任務(wù)分配的數(shù)學(xué)模型，提出了一種基于Levy 飛行的改進(jìn)隨機(jī)蛙跳算法用來(lái)生成初始任務(wù)方案，通過(guò)引入市場(chǎng)拍賣(mài)機(jī)制解決了針對(duì)突發(fā)任務(wù)環(huán)境下的動(dòng)態(tài)任務(wù)分配問(wèn)題，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性。

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

1.1.1 任務(wù)方案總價(jià)值收益

由于任務(wù)的重要程度不同，完成任務(wù)所獲得的收益也不相同，用Vj表示任務(wù)tj的價(jià)值。對(duì)于偵察任務(wù)，用PD 表示無(wú)人機(jī)的探測(cè)能力，PDij即為無(wú)人機(jī)ui執(zhí)行任務(wù)uj時(shí)的探測(cè)概率。偵察任務(wù)收益VDij計(jì)算如下：

圖1 任務(wù)分配問(wèn)題示意圖Fig.1 Schematic diagram of the task allocation problem

對(duì)于打擊任務(wù)，用PK 表示無(wú)人機(jī)的毀傷能力，PKij為無(wú)人機(jī)執(zhí)行任務(wù)tj時(shí)的毀傷概率。打擊任務(wù)收益VKij計(jì)算如下：

無(wú)人機(jī)集群執(zhí)行偵察打擊任務(wù)的總價(jià)值收益VT為所有無(wú)人機(jī)任務(wù)收益之和，即：

1.1.2 任務(wù)方案總損耗成本

用PS 表示無(wú)人機(jī)的生存概率；PSij即為無(wú)人機(jī)ui執(zhí)行任務(wù)tj時(shí)的生存概率；Vu表示無(wú)人機(jī)的價(jià)值。假設(shè)無(wú)人機(jī)ui共需執(zhí)行q 項(xiàng)任務(wù)tj（j=j1，j2，…，jq），則此無(wú)人機(jī)ui執(zhí)行任務(wù)的損耗成本如下：

1.1.3 任務(wù)方案總航程代價(jià)

計(jì)算無(wú)人機(jī)航程時(shí)，為了便于分析問(wèn)題，不考慮實(shí)際轉(zhuǎn)彎角度限制，無(wú)人機(jī)從一個(gè)任務(wù)點(diǎn)到下一個(gè)任務(wù)點(diǎn)的任務(wù)路徑為直線。無(wú)人機(jī)ui共需執(zhí)行q項(xiàng)任務(wù)tj（j=j1，j2，…，jq），則此無(wú)人機(jī)ui執(zhí)行任務(wù)的航程代價(jià)如下：

1.1.4 任務(wù)方案評(píng)估模型

對(duì)任務(wù)方案進(jìn)行評(píng)估時(shí)，需要考慮任務(wù)價(jià)值收益、無(wú)人機(jī)損耗成本和無(wú)人機(jī)的航程代價(jià)等因素。引入權(quán)重系數(shù)，將多個(gè)因素進(jìn)行歸一化處理，則多無(wú)人機(jī)協(xié)同任務(wù)分配的目標(biāo)可以表述為總收益最大，如下式所示：

其中，ω1、ω2、ω3為價(jià)值收益、損耗代價(jià)、航程代價(jià)的權(quán)重系數(shù)；Vmax為所有任務(wù)價(jià)值的最大值；Vumax為所有無(wú)人機(jī)價(jià)值中的最大值；dismax為所有任務(wù)點(diǎn)構(gòu)成的最小凸多邊形周長(zhǎng)。

1.2 約束條件

1.2.1 無(wú)人機(jī)載荷資源約束

無(wú)人機(jī)為任務(wù)提供的任務(wù)載荷資源之和不得超過(guò)其所攜帶的總?cè)蝿?wù)載荷資源，假設(shè)無(wú)人機(jī)ui的任務(wù)集合為T(mén)A，則有：

1.2.2 任務(wù)需求約束

為了提高任務(wù)執(zhí)行效率，設(shè)定每個(gè)任務(wù)最多由一架無(wú)人機(jī)執(zhí)行。同時(shí)，在任務(wù)分配過(guò)程中要求每個(gè)任務(wù)都必須被執(zhí)行。用xij表示任務(wù)決策變量，則有：

xij=0 表示無(wú)人機(jī)ui不執(zhí)行任務(wù)tj；xij=1 表示無(wú)人機(jī)ui執(zhí)行任務(wù)tj。任務(wù)需求約束可以表示為：

1.2.3 無(wú)人機(jī)航程約束

設(shè)定每架無(wú)人機(jī)的任務(wù)航程不得大于其自身的可用航程Di：

2 改進(jìn)隨機(jī)蛙跳算法

2.1 隨機(jī)蛙跳算法原理

隨機(jī)蛙跳算法（shuffled frog leaping algorithm，SFLA）是由Eusuff 和Lansey 在2003 年提出的一種亞啟發(fā)式協(xié)同搜索算法［7］。具有易于實(shí)現(xiàn)、尋優(yōu)能力強(qiáng)的優(yōu)勢(shì)。

SFLA 是一種模仿青蛙尋找食物行為的隨機(jī)啟發(fā)式優(yōu)化算法。該算法基于種群的概念生成一個(gè)虛擬的青蛙種群，并分成m 個(gè)族群，其中，每個(gè)青蛙代表一組可能的解決方案。青蛙之間的信息交換分為兩種，即族群內(nèi)的局部信息交流和種群內(nèi)的全局信息交流［11］。前者通過(guò)應(yīng)用蛙跳規(guī)則在搜索空間中移動(dòng)到一個(gè)更好的新位置來(lái)進(jìn)化出適應(yīng)度更優(yōu)的青蛙個(gè)體。蛙跳規(guī)則如下式所示：

SFLA 全局性的信息交換和內(nèi)部信息交流機(jī)制的結(jié)合，使得算法具有避免過(guò)早陷入局部極值的能力，從而指引算法搜索向最優(yōu)方向進(jìn)行［7］。SFLA 算法的程序流程如圖2 所示。

圖2 SFLA（算法）流程圖Fig.2 Flowchart of SFLA（algorithm）

2.2 改進(jìn)的隨機(jī)蛙跳算法

針對(duì)多無(wú)人機(jī)協(xié)同任務(wù)分配問(wèn)題，主要考慮兩個(gè)方面的因素：1）無(wú)人機(jī)的任務(wù)集；2）無(wú)人機(jī)的路徑集。無(wú)人機(jī)的任務(wù)集確定了無(wú)人機(jī)執(zhí)行的任務(wù)，無(wú)人機(jī)的路徑集確定了無(wú)人機(jī)執(zhí)行任務(wù)的順序。為便于問(wèn)題分析和求解，本文采用一維實(shí)數(shù)向量編碼方式表示任務(wù)分配的一個(gè)解，具體如下：

任務(wù)分配解向量si為包含M 個(gè)元素的行向量，M 為任務(wù)個(gè)數(shù)。則向量中每個(gè)元素xi為：

xi采用包含有一位小數(shù)的正實(shí)數(shù)。xi的整數(shù)部分表示將任務(wù)j 分配給對(duì)應(yīng)編號(hào)的無(wú)人機(jī)，整數(shù)部分相同的元素對(duì)應(yīng)的任務(wù)構(gòu)成無(wú)人機(jī)的任務(wù)集；小數(shù)部分按照從小到大的順序進(jìn)行排列，對(duì)應(yīng)無(wú)人機(jī)執(zhí)行任務(wù)的順序。

針對(duì)傳統(tǒng)SFLA 算法在解空間較大時(shí)求解效率較低的缺點(diǎn)，本文結(jié)合任務(wù)分配問(wèn)題的特點(diǎn)對(duì)基本隨機(jī)蛙跳算法進(jìn)行了相應(yīng)改進(jìn)，有效提高了算法的搜索效率。

由于更新后的青蛙位置受到最優(yōu)蛙位置的限制，算法初期的全局搜索性能較差，因此，在更新青蛙位置時(shí)引入動(dòng)態(tài)跳躍步長(zhǎng)C（n）使青蛙能夠向更多位置進(jìn)行搜索，C（n）為迭代次數(shù)n 的函數(shù)，如圖3所示。

圖3 蛙跳規(guī)則示意Fig.3 Schematic diagram of the frog leaping rules

跳躍步長(zhǎng)影響到算法的搜索能力，如果步長(zhǎng)太小，會(huì)使算法的全局搜索能力較差，容易陷入局部最優(yōu)解。如果步長(zhǎng)過(guò)大，則局部搜索能力的改進(jìn)較小，且容易引起算法的早熟現(xiàn)象。因此，本文引入自適應(yīng)調(diào)節(jié)方法對(duì)跳躍步長(zhǎng)進(jìn)行調(diào)整，以提高算法前期的搜索能力，調(diào)節(jié)公式如下：

式中，Cmax為最大跳躍步長(zhǎng)；Cmin為最小跳躍步長(zhǎng)；nmax為最大迭代次數(shù)；n 為當(dāng)前迭代次數(shù)。

針對(duì)算法可能陷入局部最優(yōu)的問(wèn)題，引入Levy飛行機(jī)制。Levy 飛行可以描述為一個(gè)運(yùn)動(dòng)的實(shí)體能夠偶爾邁出異常大的步子，從而改變一個(gè)體系的行為。Levy 飛行被廣泛用于最優(yōu)化問(wèn)題和進(jìn)行最優(yōu)化搜索，能有效防止搜索陷入局部最優(yōu)［7-8］。引入Levy飛行后的位置更新公式如下：

式中，α 為步長(zhǎng)控制量，通常取1；L（β）為L(zhǎng)evy 分布的搜索路徑。

在算法進(jìn)行位置更新時(shí)，使用的信息較少，只利用到了族群中最優(yōu)蛙的位置信息?？紤]到實(shí)際中個(gè)體的運(yùn)動(dòng)常常會(huì)受到整個(gè)族群的影響，在更新位置時(shí)引入族群認(rèn)知因子Pe，本文中Pe用子族群中處于中間位置的青蛙表示。通過(guò)添加族群認(rèn)知因子，對(duì)族群的信息利用更加充分，擴(kuò)充了種群多樣性。

綜合上述可得最終青蛙位置更新策略如下：

式中，ω1、ω2、ω3為L(zhǎng)evy 飛行系數(shù)、進(jìn)化系數(shù)、族群認(rèn)知系數(shù)。

2.3 基于拍賣(mài)機(jī)制的動(dòng)態(tài)任務(wù)協(xié)調(diào)

一維向量的整數(shù)編碼可以清晰地表示任務(wù)分配的方案，但由于任務(wù)分配問(wèn)題的復(fù)雜性，在算法執(zhí)行過(guò)程中容易出現(xiàn)非法解，例如任務(wù)類(lèi)型不滿(mǎn)足約束或任務(wù)未被執(zhí)行等。若在適應(yīng)度計(jì)算時(shí)將非法解剔除，則會(huì)大大降低算法的執(zhí)行效率。針對(duì)非法解提出沖突消解策略，將其變?yōu)榭尚薪?，提高算法效率。非法解主要由以下原因?qū)е拢?/p>

1）無(wú)人機(jī)類(lèi)型不滿(mǎn)足任務(wù)類(lèi)型約束；

2）任務(wù)集中偵察（或打擊）任務(wù)個(gè)數(shù)需求超過(guò)無(wú)人機(jī)可執(zhí)行偵察（或打擊）任務(wù)數(shù)。

在進(jìn)行可行性校驗(yàn)的過(guò)程中，首先將不滿(mǎn)足約束的任務(wù)解除分配，標(biāo)記為未分配狀態(tài)，然后將未分配的任務(wù)以拍賣(mài)的方式分配給其他能夠完成任務(wù)的無(wú)人機(jī)。具體操作流程如下所示：

Step 1 根據(jù)任務(wù)約束條件對(duì)每架無(wú)人機(jī)任務(wù)集中的任務(wù)進(jìn)行檢查，若任務(wù)類(lèi)型與無(wú)人機(jī)類(lèi)型不符或是任務(wù)總數(shù)超過(guò)無(wú)人機(jī)可執(zhí)行任務(wù)數(shù)，則根據(jù)任務(wù)分配約束條件，選擇不符合約束的任務(wù)標(biāo)記為未分配，并從任務(wù)集中刪除；

Step 2 由不符合約束的無(wú)人機(jī)作為拍賣(mài)者，選擇無(wú)法執(zhí)行的任務(wù)進(jìn)行拍賣(mài)；

Step 3 根據(jù)收益最大化原則，在不改變?cè)腥蝿?wù)順序的前提下，所有競(jìng)拍無(wú)人機(jī)選擇收益最大方案作為競(jìng)拍方案對(duì)被拍賣(mài)任務(wù)出價(jià)；

Step 4 拍賣(mài)者選擇出價(jià)最高的無(wú)人機(jī)作為任務(wù)獲得者，獲得任務(wù)的無(wú)人機(jī)根據(jù)競(jìng)拍方案重構(gòu)任務(wù)集和路徑集；

Step 5 將被拍出的任務(wù)標(biāo)記為已分配，若仍有任務(wù)未分配，則轉(zhuǎn)至Step 2；否則，結(jié)束該流程。

3 仿真驗(yàn)證

為了驗(yàn)證改進(jìn)隨機(jī)蛙跳算法求解任務(wù)分配問(wèn)題的有效性，設(shè)置仿真實(shí)驗(yàn)對(duì)算法進(jìn)行驗(yàn)證，設(shè)ω1=0.3、ω2=0.4、ω3=0.3，SFLA 算法參數(shù)為：最大迭代次數(shù)nmax為300，族群數(shù)為10，每個(gè)族群青蛙數(shù)為10，最大跳躍步長(zhǎng)Cmax為1.25，最小跳躍步長(zhǎng)Cmin為1，Levy 飛行系數(shù)ω1為0.3，進(jìn)化系數(shù)為0.5，族群認(rèn)知系數(shù)為0.2。

3.1 任務(wù)預(yù)分配仿真算例

由6 架異構(gòu)無(wú)人機(jī)在10 km×10 km 的戰(zhàn)場(chǎng)環(huán)境中協(xié)同執(zhí)行任務(wù)，場(chǎng)景內(nèi)共14 個(gè)任務(wù)目標(biāo)，每個(gè)目標(biāo)對(duì)應(yīng)一個(gè)偵察或打擊任務(wù)，初始時(shí)刻無(wú)人機(jī)與目標(biāo)位置關(guān)系如圖4 和表1～下頁(yè)表5 所示。

表1 任務(wù)場(chǎng)景中的初始任務(wù)信息Table 1 Initial task information for the mission scenarios

表2 任務(wù)場(chǎng)景中的無(wú)人機(jī)信息Table 2 UAV information for the mission scenarios

表3 無(wú)人機(jī)執(zhí)行任務(wù)時(shí)的生存概率Table 3 Survival probability of UAV during the execution of the mission

表4 無(wú)人機(jī)對(duì)任務(wù)的偵察能力信息表Table 4 Information sheet of UAV reconnaissance capabilities for mission

表5 無(wú)人機(jī)對(duì)任務(wù)的殺傷能力信息表Table 5 UAV kill capability information sheet for mission

圖4 任務(wù)場(chǎng)景初始態(tài)勢(shì)圖Fig.4 Initial situation map of the mission scenarios

每架無(wú)人機(jī)在執(zhí)行相應(yīng)任務(wù)時(shí)的生存概率如表3 所示。

3.2 任務(wù)預(yù)分配仿真結(jié)果

算法迭代結(jié)束得到的任務(wù)預(yù)分配方案如表6所示。

表6 任務(wù)預(yù)分配仿真結(jié)果Table 6 The simulation results of pre-allocation of mission

每架無(wú)人機(jī)的具體任務(wù)分配方案如圖5 所示。

圖5 任務(wù)預(yù)分配結(jié)果示意圖Fig.5 Schematic diagram of pre-allocation mission results

由仿真結(jié)果可知，通過(guò)編碼設(shè)計(jì)和可行性校驗(yàn)，可以將無(wú)人機(jī)類(lèi)型和任務(wù)類(lèi)型進(jìn)行有效匹配，所有分配結(jié)果均滿(mǎn)足任務(wù)類(lèi)型約束及優(yōu)化指標(biāo)約束。如：無(wú)人機(jī)u5執(zhí)行任務(wù)t8時(shí)由于損耗成本較高、任務(wù)收益較低，故u5雖然距離t8較近，但未被分配執(zhí)行任務(wù)t8。最終的任務(wù)分配結(jié)果能夠滿(mǎn)足各項(xiàng)任務(wù)約束，實(shí)現(xiàn)了任務(wù)的協(xié)同合理分配。

為了驗(yàn)證改進(jìn)后SFLA 算法的收斂性能，針對(duì)上述任務(wù)場(chǎng)景與基本隨機(jī)蛙跳算法、混合粒子群-遺傳算法［8］、改進(jìn)遺傳算法［10］在典型算法參數(shù)條件下進(jìn)行了對(duì)比。算法迭代過(guò)程中的總收益曲線如圖6 所示。

圖6 算法收益曲線變化圖Fig.6 Gain variation curve of the algorithm

由圖6 可知，算法迭代過(guò)程中總收益最優(yōu)值不斷上升，改進(jìn)SFLA 算法迭代25 次時(shí)達(dá)到收斂。算法運(yùn)行前期由于跳躍步長(zhǎng)較大，故尋優(yōu)速度較快，后期跳躍步長(zhǎng)較小，容易陷入局部最優(yōu)，在Levy 飛行和種群認(rèn)識(shí)因子的影響下，能快速收斂到全局最優(yōu)解，表明了改進(jìn)算法在求解任務(wù)分配問(wèn)題方面具有可行性，收斂速度較快。由對(duì)比曲線可以看出，3種算法都能尋找到最優(yōu)解。改進(jìn)的隨機(jī)蛙跳算法在收斂速度和尋優(yōu)能力方面優(yōu)于對(duì)比算法。

3.3 動(dòng)態(tài)任務(wù)分配仿真算例

針對(duì)戰(zhàn)場(chǎng)態(tài)勢(shì)變化導(dǎo)致出現(xiàn)突發(fā)新目標(biāo)時(shí)的動(dòng)態(tài)任務(wù)過(guò)程進(jìn)行仿真分析。

針對(duì)上述表6 的任務(wù)預(yù)分配結(jié)果，在任務(wù)執(zhí)行過(guò)程中新增2 個(gè)任務(wù)目標(biāo)需要進(jìn)行動(dòng)態(tài)任務(wù)分配，有關(guān)信息如表7～表10 所示。

表7 新增任務(wù)信息Table 7 Newly increased mission information

表8 無(wú)人機(jī)執(zhí)行任務(wù)時(shí)的生存概率Table 8 Survival probability of UAV during the execution of the mission

表9 無(wú)人機(jī)對(duì)目標(biāo)的偵察能力信息Table 9 Reconnaissance capability of UAV to targets

表10 無(wú)人機(jī)對(duì)目標(biāo)的殺傷能力信息Table 10 Killing ability of UAV to targets

在任務(wù)預(yù)分配的基礎(chǔ)上，當(dāng)任務(wù)場(chǎng)景中出現(xiàn)新目標(biāo)時(shí)，改進(jìn)的SFLA 算法采用市場(chǎng)拍賣(mài)機(jī)制將新任務(wù)進(jìn)行動(dòng)態(tài)分配。動(dòng)態(tài)任務(wù)分配結(jié)果如圖7 所示。

圖7 新目標(biāo)出現(xiàn)后任務(wù)分配結(jié)果圖Fig.7 Mission allocation results after new targets appearing

相應(yīng)的任務(wù)分配方案如表11 所示。

表11 發(fā)現(xiàn)新目標(biāo)后任務(wù)分配結(jié)果Table 11 Mission allocation results after finding the new targets

由上述仿真結(jié)果可以看出，本文提出的基于市場(chǎng)拍賣(mài)機(jī)制的隨機(jī)蛙跳算法，能較好地解決多無(wú)人機(jī)動(dòng)態(tài)任務(wù)分配問(wèn)題，能夠快速實(shí)現(xiàn)突發(fā)新目標(biāo)時(shí)的動(dòng)態(tài)任務(wù)分配過(guò)程，有效調(diào)整了各個(gè)無(wú)人機(jī)所分配的任務(wù)。

4 結(jié)論

本文以多無(wú)人機(jī)協(xié)同偵察打擊任務(wù)為背景，研究了任務(wù)預(yù)分配和突發(fā)新目標(biāo)情況下的動(dòng)態(tài)任務(wù)分配問(wèn)題。以多無(wú)人機(jī)協(xié)同收益最大化為目標(biāo)函數(shù)建立了多約束任務(wù)分配模型，提出了改進(jìn)型隨機(jī)蛙跳算法用于問(wèn)題模型的求解。通過(guò)仿真實(shí)驗(yàn)可以看出，改進(jìn)后的SFLA 算法不僅能夠給出合理的分配方案，而且能夠滿(mǎn)足動(dòng)態(tài)戰(zhàn)場(chǎng)環(huán)境的要求，有效實(shí)現(xiàn)多無(wú)人機(jī)之間的協(xié)同動(dòng)態(tài)任務(wù)分配過(guò)程。