常松 賈子彥

摘 要：傳統(tǒng)合同網(wǎng)算法在任務(wù)分配過(guò)程中存在任務(wù)分配不合理，不能有效利用資源的問(wèn)題;其在進(jìn)行任務(wù)分配時(shí)，不能按照任務(wù)需求進(jìn)行任務(wù)分配，任務(wù)分配效率低下。針對(duì)以上問(wèn)題，文中提出一種基于改進(jìn)合同網(wǎng)算法的多無(wú)人機(jī)任務(wù)分配方法。該方法通過(guò)優(yōu)化每架無(wú)人機(jī)的負(fù)載平衡，并結(jié)合時(shí)間和協(xié)作要求，解決任務(wù)分配不合理的問(wèn)題，提高任務(wù)的分配和執(zhí)行效率。

關(guān)鍵詞：任務(wù)分配;無(wú)人機(jī);合同網(wǎng)算法;負(fù)載平衡;資源消耗;飛行距離

中圖分類(lèi)號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-1302（2020）05-00-03

0 引 言

隨著無(wú)人機(jī)技術(shù)的發(fā)展，無(wú)人機(jī)的應(yīng)用領(lǐng)域在逐漸增加，無(wú)人機(jī)可以執(zhí)行的任務(wù)種類(lèi)也變得多樣化。但是單機(jī)無(wú)人機(jī)的任務(wù)執(zhí)行能力畢竟有限，所以對(duì)多架無(wú)人機(jī)執(zhí)行任務(wù)的研究也越來(lái)越多[1]。多無(wú)人機(jī)協(xié)作技術(shù)的發(fā)展是為了有效執(zhí)行任務(wù)，而合理的進(jìn)行任務(wù)分配則為無(wú)人機(jī)快速、高效完成任務(wù)打下了基礎(chǔ)，所以對(duì)多無(wú)人機(jī)的任務(wù)分配算法的研究是十分有意義的。

任務(wù)分配的目的是使無(wú)人機(jī)執(zhí)行任務(wù)時(shí)消耗的資源少、飛行距離短、花費(fèi)的時(shí)間短。而隨著無(wú)人機(jī)應(yīng)用領(lǐng)域的增多，任務(wù)規(guī)模、種類(lèi)、復(fù)雜度也增加了任務(wù)分配算法的難度。目前已有的任務(wù)分配方法主要有合同網(wǎng)算法、蟻群算法、粒子群算法等[2-4]。合同網(wǎng)算法在進(jìn)行規(guī)模大、數(shù)量多、復(fù)雜度較高的任務(wù)分配時(shí)，相比于其他算法有一定的優(yōu)勢(shì)。

本文針對(duì)傳統(tǒng)合同網(wǎng)算法分配效率低，分配不合理等問(wèn)題對(duì)算法進(jìn)行了改進(jìn)，增加了任務(wù)分配條件，提高任務(wù)分配和無(wú)人機(jī)執(zhí)行效率[5]。

1 合同網(wǎng)算法

合同網(wǎng)算法源自人們?cè)谏虅?wù)過(guò)程中用于管理商品和服務(wù)的合同機(jī)制[6]。該算法是模仿經(jīng)濟(jì)行為的“管理者-工作者”的機(jī)制進(jìn)行任務(wù)協(xié)商，實(shí)現(xiàn)任務(wù)分配。在合同網(wǎng)算法中，所有主體分為三個(gè)角色：招標(biāo)者、投標(biāo)者和中標(biāo)者。

在多無(wú)人機(jī)任務(wù)分配的合同網(wǎng)算法中，招標(biāo)者即任務(wù)管理者，負(fù)責(zé)任務(wù)信息的收集、發(fā)布和管理[7]。投標(biāo)者是無(wú)人機(jī)，其根據(jù)自身的信息和資源對(duì)任務(wù)進(jìn)行評(píng)估，參與投標(biāo)，向招標(biāo)者發(fā)送任務(wù)請(qǐng)求。中標(biāo)者是獲得任務(wù)的無(wú)人機(jī)，負(fù)責(zé)完成任務(wù)。任務(wù)分配過(guò)程如圖1所示。

1.1 任務(wù)建模

任務(wù)分配的主要參與對(duì)象是無(wú)人機(jī)和任務(wù)。令V={V1， V2， …， Vm}代表執(zhí)行任務(wù)的無(wú)人機(jī)集合，T ={T1，T2， …， Tn}代表需要完成的任務(wù)集合。

1.2 任務(wù)描述

假設(shè)有n個(gè)任務(wù)需要執(zhí)行，但每個(gè)任務(wù)的緊急程度不一樣，這就需要對(duì)任務(wù)限制任務(wù)完成的時(shí)間。每個(gè)任務(wù)的工作量也不一樣，為了能夠在規(guī)定時(shí)間內(nèi)完成，工作量大的任務(wù)要求無(wú)人機(jī)協(xié)作完成。

（1）任務(wù)時(shí)間。無(wú)人機(jī)的資源消耗與時(shí)間成正比，每架無(wú)人機(jī)都需要保證自身的資源足夠完成分配到的所有任務(wù)并安全返航。設(shè)：ti， j為完成某個(gè)任務(wù)的時(shí)間;ts1i， j是無(wú)人機(jī)到達(dá)目標(biāo)點(diǎn)的飛行時(shí)間;ts2i， j是無(wú)人機(jī)執(zhí)行任務(wù)時(shí)間;Di是無(wú)人機(jī)到第i任務(wù)點(diǎn)的飛行距離;Vj是無(wú)人機(jī)j的飛行速度;Qi是第i個(gè)任務(wù)的任務(wù)量;pj是無(wú)人機(jī)j執(zhí)行任務(wù)的速率;

i=1， 2， …， n是任務(wù)編號(hào)，j=1， 2， …， m是無(wú)人機(jī)編號(hào)（給某個(gè)無(wú)人機(jī)）。

（2）任務(wù)協(xié)作。每個(gè)任務(wù)都有自己的工作量Qi，如果工作量較大，無(wú)人機(jī)單獨(dú)完成會(huì)影響無(wú)人機(jī)的整體資源消耗，從而使得任務(wù)分配不合理。以所有任務(wù)的平均值為條件，如果Qi≥，則需要無(wú)人機(jī)協(xié)作完成任務(wù)。是總的平均任務(wù)量。

1.3 目標(biāo)函數(shù)

無(wú)人機(jī)在收到任務(wù)信息后，在任務(wù)范圍內(nèi)均勻分布，每架無(wú)人機(jī)在自己的航線(xiàn)上搜索附近的任務(wù)，以無(wú)人機(jī)到任務(wù)的飛行距離為條件，優(yōu)先選擇距離近的任務(wù)，有：

式中：（xi， yi）為目的任務(wù)的坐標(biāo);（xj， yj）無(wú)人機(jī)當(dāng)前坐標(biāo)點(diǎn)。

2 改進(jìn)合同網(wǎng)算法

利用上述方法雖然可以實(shí)現(xiàn)任務(wù)的分配，但是存在任務(wù)分配不合理，分配效率低的情況。為了解決傳統(tǒng)合同網(wǎng)算法可能存在的問(wèn)題，進(jìn)行了以下改進(jìn)：

無(wú)人機(jī)在以距離為限制選擇任務(wù)時(shí)，也要考慮到任務(wù)時(shí)間的順序。當(dāng)任務(wù)量大于預(yù)設(shè)的平均任務(wù)量時(shí)，選擇將這個(gè)任務(wù)交付于兩架無(wú)人機(jī)協(xié)作完成，減少無(wú)人機(jī)投標(biāo)的次數(shù)，提高分配效率。

無(wú)人機(jī)的負(fù)載可以和無(wú)人機(jī)的資源消耗、飛行距離、任務(wù)時(shí)間等條件結(jié)合起來(lái)，根據(jù)負(fù)載結(jié)果來(lái)判斷任務(wù)分配結(jié)果是否合理。

設(shè)無(wú)人機(jī)i的負(fù)載量為Fi，所有無(wú)人機(jī)的平均負(fù)載能力為：

式中，m為無(wú)人機(jī)的個(gè)數(shù)，則無(wú)人機(jī)的負(fù)載率為：

通過(guò)人為設(shè)置固定值E，若負(fù)載率小于E，則表示無(wú)人機(jī)可以繼續(xù)對(duì)任務(wù)進(jìn)行投標(biāo);若負(fù)載率大于E，則無(wú)人機(jī)不可以繼續(xù)對(duì)任務(wù)進(jìn)行投標(biāo)，并放棄最后選擇的任務(wù)。

為了使任務(wù)負(fù)載的均衡性更好，通過(guò)方差計(jì)算無(wú)人機(jī)每次任務(wù)中標(biāo)后的負(fù)載變化。

式中，ρj代表無(wú)人機(jī)的負(fù)載均衡性，ρj越小，則任務(wù)分配越合理。

為了滿(mǎn)足時(shí)間上的安排，結(jié)合遺傳算法對(duì)無(wú)人機(jī)的任務(wù)時(shí)間進(jìn)程進(jìn)行了安排。在獲得任務(wù)的時(shí)間信息后，每個(gè)遺傳因子都是一個(gè)時(shí)間點(diǎn)。通過(guò)不停的迭代和遺傳變異的方式使得彼此之間不會(huì)出現(xiàn)重合的時(shí)間點(diǎn)，從而使得任務(wù)時(shí)間安排合理、有效。

3 仿真實(shí)驗(yàn)

基于以上思路，采用Matlab平臺(tái)開(kāi)展仿真實(shí)驗(yàn)。無(wú)人機(jī)的飛行高度一致，飛行起點(diǎn)均勻分布，以x y∈[0，1000]的二維區(qū)間為飛行環(huán)境。總共20個(gè)任務(wù)隨機(jī)分布在同一區(qū)域中。任務(wù)信息中包含時(shí)間和協(xié)作的要求。時(shí)間和任務(wù)量的關(guān)系圖如圖2所示。為了使無(wú)人機(jī)在接收任務(wù)后，合理安排任務(wù)的執(zhí)行順序，給每個(gè)任務(wù)設(shè)置任務(wù)完成時(shí)刻，時(shí)刻為0或者負(fù)數(shù)的任務(wù)表示無(wú)需在規(guī)定時(shí)刻完成任務(wù)，這樣的任務(wù)可以留在最后執(zhí)行。此圖為實(shí)驗(yàn)的仿真條件之一。

根據(jù)實(shí)驗(yàn)數(shù)據(jù)中的任務(wù)量得到需要協(xié)作的任務(wù)信息見(jiàn)

無(wú)人機(jī)根據(jù)傳統(tǒng)合同網(wǎng)算法進(jìn)行任務(wù)分配的結(jié)果如圖3所示。

改進(jìn)后的任務(wù)分配圖如圖4所示。通過(guò)圖3和圖4的對(duì)比可以看出：傳統(tǒng)合同網(wǎng)算法中每架無(wú)人機(jī)分配到的任務(wù)數(shù)量為1，4，3，7，8，6，而改進(jìn)后的每架無(wú)人機(jī)分配的任務(wù)數(shù)量為4，4，3，7，5，6。從分配結(jié)果上看改進(jìn)后合同網(wǎng)算法分配的結(jié)果更平均。若無(wú)人機(jī)在完成任務(wù)后回航或者接收到了新的任務(wù)信息需要執(zhí)行，那么傳統(tǒng)合同網(wǎng)中的一些無(wú)人機(jī)由于之前分配的任務(wù)較多，消耗了過(guò)多的資源，這樣就不能在繼續(xù)接收新的任務(wù)。而改進(jìn)后得到的任務(wù)分配結(jié)果中，每架無(wú)人機(jī)消耗的資源相對(duì)較少，可以繼續(xù)執(zhí)行新的任務(wù)，所以改進(jìn)后的合同網(wǎng)算法比傳統(tǒng)合同網(wǎng)算法任務(wù)分配更合理。無(wú)人機(jī)以相同的飛行速度去執(zhí)行任務(wù)，從分配結(jié)果的時(shí)間上看，改進(jìn)后的合同網(wǎng)算法對(duì)傳統(tǒng)合同網(wǎng)算法花費(fèi)更少的時(shí)間。由此可以看出，在本文的任務(wù)分配算法中，改進(jìn)合同網(wǎng)算法比傳統(tǒng)合同網(wǎng)算法更有優(yōu)勢(shì)。

4 結(jié) 語(yǔ)

本文通過(guò)對(duì)合同網(wǎng)算法進(jìn)行改進(jìn)，在合同中的任務(wù)信息添加時(shí)間和協(xié)作的條件，將任務(wù)以整體的形式廣播發(fā)送給無(wú)人機(jī)。無(wú)人機(jī)以時(shí)間、協(xié)作和飛行距離等作為約束條件實(shí)現(xiàn)任務(wù)的投標(biāo)過(guò)程。而任務(wù)管理者通過(guò)收集對(duì)比無(wú)人機(jī)的投標(biāo)，選擇最優(yōu)的分配方式，從而實(shí)現(xiàn)多無(wú)人機(jī)協(xié)作完成任務(wù)的分配方法，有效提高整體任務(wù)執(zhí)行效率[8]。在已知環(huán)境下獲得任務(wù)目標(biāo)，采用全局與局部相結(jié)合的方法，綜合考慮資源代價(jià)和任務(wù)執(zhí)行能力，建立多機(jī)協(xié)作任務(wù)分配模型。

這一模型對(duì)其他自主機(jī)器設(shè)備也可以進(jìn)行實(shí)際應(yīng)用，但這一方案僅僅局限于靜態(tài)環(huán)境中，能否適應(yīng)于未知環(huán)境還需要進(jìn)行更多的實(shí)驗(yàn)，而且在進(jìn)行任務(wù)分配時(shí)考慮是否結(jié)合動(dòng)態(tài)實(shí)際任務(wù)完成情況作為任務(wù)分配目標(biāo)條件也是是今后的研究點(diǎn)之一。

參考文獻(xiàn)

[1]郜晨.多無(wú)人機(jī)自主任務(wù)規(guī)劃方法研究[D].南京：南京航空航天大學(xué)，2016.

[2] SMITH R G. The contract net protocol：high-level communication and control in a distributed problem solver [J]. IEEE transactions on computers，1980，C-29（12）：1104-1113.

[3]李士波.基于粒子群算法的多無(wú)人機(jī)任務(wù)分配[J]. 軟件導(dǎo)刊，2018，17（7）：197-199.

[4]王靈霞，張遠(yuǎn)平，吳佩莉.蟻群算法求解分布式系統(tǒng)任務(wù)分配問(wèn)題[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2008（6）：168-170.

[5]王欽釗，程金勇，李小龍.多無(wú)人機(jī)協(xié)同任務(wù)規(guī)劃方法[J].火力與指揮控制，2018，43（3）：86-89.

[6]錢(qián)艷平，夏潔，劉天宇.基于合同網(wǎng)的無(wú)人機(jī)協(xié)同目標(biāo)分配方法

[J].系統(tǒng)仿真學(xué)報(bào)，2011，23（8）：1672-1676.

[7]李新亮，翟江濤，戴躍偉. 動(dòng)態(tài)環(huán)境下基于改進(jìn)合同網(wǎng)的多Agent任務(wù)分配算法[J]. 科學(xué)技術(shù)與工程，2013（27）：104-109.

[8] LI Y W，LI B A. Research of multiple UAVs task allocation based on improved contract net [J]. Advanced materials research，2013，823：439-444.

[9]陳轉(zhuǎn)，劉平，王超.無(wú)人機(jī)在偵查與監(jiān)視領(lǐng)域的研究與展望[J].物聯(lián)網(wǎng)技術(shù)，2019，9（10）：82-83.

[10]趙露露.有人/無(wú)人機(jī)協(xié)同互操作性研究[J].物聯(lián)網(wǎng)技術(shù)，2015，5（5）：59-61.