基于改進合同網算法的多無人機任務分配

常松 賈子彥

摘 要：傳統合同網算法在任務分配過程中存在任務分配不合理，不能有效利用資源的問題;其在進行任務分配時，不能按照任務需求進行任務分配，任務分配效率低下。針對以上問題，文中提出一種基于改進合同網算法的多無人機任務分配方法。該方法通過優化每架無人機的負載平衡，并結合時間和協作要求，解決任務分配不合理的問題，提高任務的分配和執行效率。

關鍵詞：任務分配;無人機;合同網算法;負載平衡;資源消耗;飛行距離

中圖分類號：TP393文獻標識碼：A文章編號：2095-1302（2020）05-00-03

0 引 言

隨著無人機技術的發展，無人機的應用領域在逐漸增加，無人機可以執行的任務種類也變得多樣化。但是單機無人機的任務執行能力畢竟有限，所以對多架無人機執行任務的研究也越來越多[1]。多無人機協作技術的發展是為了有效執行任務，而合理的進行任務分配則為無人機快速、高效完成任務打下了基礎，所以對多無人機的任務分配算法的研究是十分有意義的。

任務分配的目的是使無人機執行任務時消耗的資源少、飛行距離短、花費的時間短。而隨著無人機應用領域的增多，任務規模、種類、復雜度也增加了任務分配算法的難度。目前已有的任務分配方法主要有合同網算法、蟻群算法、粒子群算法等[2-4]。合同網算法在進行規模大、數量多、復雜度較高的任務分配時，相比于其他算法有一定的優勢。

本文針對傳統合同網算法分配效率低，分配不合理等問題對算法進行了改進，增加了任務分配條件，提高任務分配和無人機執行效率[5]。

1 合同網算法

合同網算法源自人們在商務過程中用于管理商品和服務的合同機制[6]。該算法是模仿經濟行為的“管理者-工作者”的機制進行任務協商，實現任務分配。在合同網算法中，所有主體分為三個角色：招標者、投標者和中標者。

在多無人機任務分配的合同網算法中，招標者即任務管理者，負責任務信息的收集、發布和管理[7]。投標者是無人機，其根據自身的信息和資源對任務進行評估，參與投標，向招標者發送任務請求。中標者是獲得任務的無人機，負責完成任務。任務分配過程如圖1所示。

1.1 任務建模

任務分配的主要參與對象是無人機和任務。令V={V1， V2， …， Vm}代表執行任務的無人機集合，T ={T1，T2， …， Tn}代表需要完成的任務集合。

1.2 任務描述

假設有n個任務需要執行，但每個任務的緊急程度不一樣，這就需要對任務限制任務完成的時間。每個任務的工作量也不一樣，為了能夠在規定時間內完成，工作量大的任務要求無人機協作完成。

（1）任務時間。無人機的資源消耗與時間成正比，每架無人機都需要保證自身的資源足夠完成分配到的所有任務并安全返航。設：ti， j為完成某個任務的時間;ts1i， j是無人機到達目標點的飛行時間;ts2i， j是無人機執行任務時間;Di是無人機到第i任務點的飛行距離;Vj是無人機j的飛行速度;Qi是第i個任務的任務量;pj是無人機j執行任務的速率;

i=1， 2， …， n是任務編號，j=1， 2， …， m是無人機編號（給某個無人機）。

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

1.3 目標函數

無人機在收到任務信息后，在任務范圍內均勻分布，每架無人機在自己的航線上搜索附近的任務，以無人機到任務的飛行距離為條件，優先選擇距離近的任務，有：

式中：（xi， yi）為目的任務的坐標;（xj， yj）無人機當前坐標點。

2 改進合同網算法

利用上述方法雖然可以實現任務的分配，但是存在任務分配不合理，分配效率低的情況。為了解決傳統合同網算法可能存在的問題，進行了以下改進：

無人機在以距離為限制選擇任務時，也要考慮到任務時間的順序。當任務量大于預設的平均任務量時，選擇將這個任務交付于兩架無人機協作完成，減少無人機投標的次數，提高分配效率。

無人機的負載可以和無人機的資源消耗、飛行距離、任務時間等條件結合起來，根據負載結果來判斷任務分配結果是否合理。

設無人機i的負載量為Fi，所有無人機的平均負載能力為：

式中，m為無人機的個數，則無人機的負載率為：

通過人為設置固定值E，若負載率小于E，則表示無人機可以繼續對任務進行投標;若負載率大于E，則無人機不可以繼續對任務進行投標，并放棄最后選擇的任務。

為了使任務負載的均衡性更好，通過方差計算無人機每次任務中標后的負載變化。

式中，ρj代表無人機的負載均衡性，ρj越小，則任務分配越合理。

為了滿足時間上的安排，結合遺傳算法對無人機的任務時間進程進行了安排。在獲得任務的時間信息后，每個遺傳因子都是一個時間點。通過不停的迭代和遺傳變異的方式使得彼此之間不會出現重合的時間點，從而使得任務時間安排合理、有效。

3 仿真實驗

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

根據實驗數據中的任務量得到需要協作的任務信息見

無人機根據傳統合同網算法進行任務分配的結果如圖3所示。

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

4 結 語

本文通過對合同網算法進行改進，在合同中的任務信息添加時間和協作的條件，將任務以整體的形式廣播發送給無人機。無人機以時間、協作和飛行距離等作為約束條件實現任務的投標過程。而任務管理者通過收集對比無人機的投標，選擇最優的分配方式，從而實現多無人機協作完成任務的分配方法，有效提高整體任務執行效率[8]。在已知環境下獲得任務目標，采用全局與局部相結合的方法，綜合考慮資源代價和任務執行能力，建立多機協作任務分配模型。

這一模型對其他自主機器設備也可以進行實際應用，但這一方案僅僅局限于靜態環境中，能否適應于未知環境還需要進行更多的實驗，而且在進行任務分配時考慮是否結合動態實際任務完成情況作為任務分配目標條件也是是今后的研究點之一。

參考文獻

[1]郜晨.多無人機自主任務規劃方法研究[D].南京：南京航空航天大學，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]李士波.基于粒子群算法的多無人機任務分配[J]. 軟件導刊，2018，17（7）：197-199.

[4]王靈霞，張遠平，吳佩莉.蟻群算法求解分布式系統任務分配問題[J]. 計算機工程與設計，2008（6）：168-170.

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

[6]錢艷平，夏潔，劉天宇.基于合同網的無人機協同目標分配方法

[J].系統仿真學報，2011，23（8）：1672-1676.

[7]李新亮，翟江濤，戴躍偉. 動態環境下基于改進合同網的多Agent任務分配算法[J]. 科學技術與工程，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]陳轉，劉平，王超.無人機在偵查與監視領域的研究與展望[J].物聯網技術，2019，9（10）：82-83.

[10]趙露露.有人/無人機協同互操作性研究[J].物聯網技術，2015，5（5）：59-61.