基于任務與巡航方向相關性分析的無人機任務分配

摘要：在有限能耗下提高任務執行效率是無人機系統中一個關鍵問題，然而現有的無人機任務分配方法忽視任務與無人機巡航方向的相關性對能耗和時延的影響。為此，提出一種基于任務與巡航方向相關性分析的無人機任務分配方法，該方法包括任務篩選和基于共識的沖突解決兩個階段。在第一階段，該方法首先利用任務與無人機巡航方向的夾角為單個無人機篩選出無折返任務，然后提出兼顧能耗和時間緊迫性的任務篩選算法從無折返任務中篩選出交互前候選任務。在第二階段，該方法在多個無人機交互候選任務列表后，根據任務在這多個無人機巡航方向上的能耗效用參數和時延評估值來解決它們之間的任務沖突。經實驗驗證，提出的方法能夠獲得更低的任務平均能耗和平均時延。

關鍵詞：無人機任務分配；相關性分析；巡航方向；能耗

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695（2022）10-016-2989-07

doi：10.19734/j.issn.1001-3695.2022.03.0125

UAV task allocation based on relevance analysis between tasks and cruise directions

He Xingyua，b，Fu Chonga，Yang Guisonga，Zhao Zihaob，Li Ziyuanb

（a.School of Optic-Electrical amp; Computer Engineering，b.College of Communication amp; Art Design，University of Shanghai for Science amp; Technology，Shanghai 200093，China）

Abstract：To achieve high efficiency with limitation of energy consumption is a key problem in the system of UAV.In existing UAV task allocation methods，the relevance between tasks and UAV cruise directions is neglected，which may further influence the energy consumption and delay of task accomplishment.In view of this，this paper proposed a UAV task allocation method based on the relevance analysis between tasks and cruise directions.This method included two phases：task screening phase and conflict resolution phase based on consensus.In the first phase，this method selected out tasks without turning back for a UAV according to angles between the cruise direction of the UAV and directions of these tasks，then designed an algorithm to further select candidate tasks before interaction from the tasks without turning back according to their energy consumption utility parameters and time urgency parameters.In the second phase，this method solved tasks conflicts between UAV after exchanging of their candidate tasks according to energy consumption utility parameters and time delay parameters of these tasks in different cruise directions of these UAV.Simulation results verify that the proposed method can achieve lower average task energy consumption and average task delay.

Key words：UAV task allocation；relevance analysis；cruise direction；energy consumption

0引言

隨著智能制造、無線通信、人工智能等相關技術的快速發展，無人自主系統也日趨成熟。其中，無人機具有機動性和靈活性等優勢，且不受交通狀況和周圍環境的影響，阿里巴巴和亞馬遜在其配送服務中引入了無人機配送模式［1］。雖然無人機在任務配送中擁有上述優點，但由于其能量有限，不能長時間持續提供服務，對配送系統的任務分配產生較大局限性。所以，在有限能耗下提高任務執行效率是無人機系統中的一個重要問題，而任務分配方法是解決該問題的關鍵。現有的無人機任務分配方法主要包括集中式任務分配和分布式任務分配方法。

在集中式任務分配方法中，現有研究為優化無人機能耗主要根據任務屬性進行分組聚類［2～4］、利用啟發式算法優化任務完成順序［5～7］以及根據任務的時空屬性進行任務分配［8～10］。集中式任務分配算法簡單，具有獲取全局最優解的潛力，但是依然存在缺點。當任務的離散程度較大時，聚類結果誤差較大，很難通過聚類的方法生成一組相似度較高的任務分配序列實現能耗的協同優化；而利用啟發式算法優化任務的完成順序的研究，與傳統的旅行商問題相似，在優化能耗時容易陷入局部最優；在考慮任務時空屬性的任務分配研究中，需要綜合考慮任務時間和空間多種因素對能耗的影響，求解空間過大。

在分布式任務分配方法中，現有研究為優化無人機能耗，主要采用基于博弈論的分布式任務分配方法［11～ 13］、基于拍賣的分布式任務分配方法［14～16］以及基于共識的分布式任務分配方法［17，18］。分布式任務分配系統無須像集中式任務分配系統一樣需要一個全局的中央服務器，系統內的每架無人機都可以根據獲取的信息獨立決策，在任務分配過程中這種獨立決策會引發多無人機間的沖突問題，可根據博弈、拍賣、共識等策略進行交互解決沖突問題，同時分布式系統還具有較高的并發性、可擴展性、去中心以及適應動態環境的優點。

經分析本文發現，上述兩類方法在為無人機分配任務時，為了提升系統性能，考慮了能耗、路徑長短和完成時間等多種影響因素，而未直接分析任務方向與無人機巡航方向的相關性。在進一步研究中，本文利用現有算法進行實驗時還發現，當把任務完成截止時間的約束條件放寬松時，任務和無人機巡航方向相關性程度越高的任務越容易被優先執行。通過上述發現，本文獲得兩方面的啟發：a）任務與無人機巡航方向的相關性對系統性能有非常重要的影響，尤其可以減少無人機因任務方向不一致帶來的折返開銷，故本文可以嘗試在任務分配時對該因素進行直接分析和考量；b）在任務分配時直接考慮任務與無人機巡航方向的相關性會導致一些不具有方向相關性但完成截止時間約束比較嚴格的任務無法及時執行。

為此，根據第一點啟發，本文將提出一種基于任務與巡航方向相關性分析的無人機任務分配方法，通過利用任務與巡航方向相關性來優化系統能耗；另一方面，本文將通過合理設置多個無人機巡航方向的配合，從而避免第二點啟發中的問題，使得完成截止時間緊迫的任務總能找到一個和自己任務方向相關性高的無人機，但這又會帶來不同巡航方向無人機之間的任務沖突問題，為此，本文的任務分配方法將采用基于共識的分布式框架。現有基于共識的分布式任務分配方法主要包括任務篩選和基于共識的沖突解決兩個階段［19］。在第一階段主要通過優化能耗、時延來篩選任務，例如根據無人機與任務發布位置間的距離篩選任務［20］，以及根據任務的等待時間篩選任務［21］，篩選任務時并未考慮無人機巡航方向對能耗和時延的影響，在應對本文提出的無人機往返巡航的場景中存在較大局限；在第二階段主要通過能耗最小的共識解決任務沖突［20］，以及任務成本的評估指標最小的共識解決任務沖突［21］，在解決任務沖突時并未考慮無人機巡航方向對能耗、時延、任務成本等評估指標的影響，在應對本文提出的無人機往返巡航的場景中存在較大局限。具體地，在本文任務分配方法的任務篩選階段，首先根據任務方向與無人機巡航方向的夾角為單個無人機篩選出無折返任務，然后定義任務能耗效用參數和時間緊迫性參數，并根據兩者的綜合評估值，提出一種任務篩選算法為單個無人機從無折返任務中篩選出交互前候選任務列表；在本文任務分配方法的共識沖突解決階段，提出一種沖突解決算法，在多個無人機交互候選任務列表后，根據任務在不同無人機巡航方向上的能耗效用參數和時延性能參數評估值來解決多個無人機之間的任務沖突。

1系統模型

本文構建了一個基于任務與巡航方向相關性的分布式無人機任務分配模型，如圖1所示。在該模型中，無人機集合表示為W={w1，w2，…，wm}，多架無人機在一對固定充電站之間往返飛行并執行任務（這對充電站分別被稱為這些無人機的巡航起點站和終點站，無人機經過起點站和終點站都需要停留進行任務獲取和能量補充），任意一個無人機wj都可用六元組（Owj（x，y），Qwj（x，y），Ewj，Vwj，Hwj，Twj）表示，Owj（x，y）為無人機wj巡航起點站的坐標，Qwj（x，y）為無人機wj巡航終點站的坐標，Ewj表示無人機wj的最大能量儲備，Vwj表示無人機wj的飛行速度，Hwj表示無人機wj的飛行高度（為避免無人機發生碰撞，為每架無人機設置不同的飛行高度），Twj表示無人機wj巡航起飛的時間，同一充電站相同巡航方向上無人機起飛時間間隔為ΔT，且固定一對充電站點的兩架無人機將同時相向巡航（巡航起點站Owj（x，y）和終點站Qwj（x，y）之間的連線方向表示無人機wj的巡航方向）。根據文獻［22］無人機能耗與飛行時間的關系，可以通過任意一架無人機wj的最大能量儲備Ewj，計算出無人機wj每輪巡航的最大飛行時間twj，計算公式為

twj=Ewjf（Vwj）（1）

其中：Ewj為無人機wj的最大能量儲備；f（Vwj）表示無人機wj以速度Vwj勻速飛行的功率。每對充電站之間相同巡航方向上的無人機巡航起飛間隔ΔT滿足如下約束：

ΔT≤1m′×twj（2）

其中：m′表示每對充電站之間單個巡航方向的無人機數。

任意一個任務ai都可用三元組（Oai（x，y），Qai（x，y），Tai）表示，Oai（x，y）表示任務ai取貨點的坐標，Qai（x，y）表示任務ai配送點的坐標，Tai表示任務ai要求的最晚配送時間，取貨點Oai（x，y）和配送點Qai（x，y）之間的連線可定義為任務ai的方向。

每個充電站不僅具有充電能力，而且可以接收其任務覆蓋范圍內（任務覆蓋范圍半徑為無人機巡航起點站和終點站之間的距離，無人機的通信半徑是任務覆蓋范圍半徑的兩倍）的配送任務，彼此在通信范圍內的充電站之間可以進行任務交互，無人機在每經過一個充電站后將能量儲備恢復到最大，并獲取充電站接收的任務集（每當無人機結束一輪巡航，當前所在充電站變換為巡航起點站，對應的另一充電站變換為巡航終點站），以及通過本文提出的分布式任務分配方法生成每輪巡航（從巡航起點站到終點站）可執行的無沖突任務列表。該任務分配方法包括任務篩選階段和基于共識的沖突解決階段兩個階段。該方法在具有相同起飛時間的多個無人機之間執行。

在任務篩選階段，無人機將通過兩輪篩選從在起點站獲取的任務中篩選出到達終點站之前可執行的候選任務列表，在第一輪篩選中，單個無人機先將從起點站獲取的任務放入以起點站為原點和以其巡航方向（巡航起點站和終點站之間的連線方向）為Y軸的新坐標系中，然后刪除縱坐標小于0以及與無人機巡航方向夾角余弦值小于0的任務，從而篩選出并生成單程巡航可執行的無折返任務列表（無折返任務取貨點的縱坐標總是小于它配送點的縱坐標，確保無人機總是先經過任務的取貨點再到達該任務的配送點），這一輪篩選是本文方法對任務與巡航方向相關性的第一層分析與利用。在第二輪篩選中，首先，單個無人機根據第一輪篩選出的任務的取貨點和配送點的縱坐標進行遞增排序，并生成該任務列表的軌跡序列，然后計算任務的能耗效用參數和時間緊迫性參數，并根據這兩個參數的綜合評估值從無折返任務列表中篩選出能耗效用參數值較小和時間緊迫性參數較大的任務，從而生成交互前的候選任務列表。

在基于共識的沖突解決階段，無人機之間進行信息交互（交互信息包括無人機的交互前候選任務列表，以及其他無人機信息），并根據交互的信息解決相互之間的任務沖突問題，以生成各自的無沖突任務列表。具體地，如果一個任務的原始坐標在多個無人機的交互前候選任務列表中，則該任務在這多個無人機之間存在沖突。當一個任務存在沖突時，本文方法根據該任務在不同無人機巡航方向上的能耗效用參數和時延性能參數的綜合評估值來選擇執行該任務的無人機，以解決任務沖突，這是本文方法對任務與巡航方向相關性的第二層分析與利用。

2基于任務與巡航方向相關性分析的任務分配

2.1任務篩選階段

任務篩選階段包含兩輪任務篩選：在第一輪篩選中，為了避免折返，無人機主要根據任務與其巡航方向夾角的余弦值來篩選無折返任務；在第二輪篩選中，為降低無人機能耗和時延，無人機主要根據任務的能耗效用參數和時間緊迫參數從無折返任務中來篩選出交互前候選任務列表。本文將以無人機wj為例對兩輪任務篩選進行詳細說明。

2.1.1第一輪任務篩選

在第一輪任務篩選中，無人機wj獲取其巡航起點站的任務集A后，需要篩選出飛往巡航終點站之前可執行的無折返任務列表Awj，其具體篩選步驟包括：a）無人機wj獲取任務集A中所有任務在以其巡航起點站Owj（x，y）為原點和以其巡航方向為Y軸的新坐標系中的坐標；b）無人機wj刪除A中縱坐標小于0以及與無人機wj巡航方向夾角余弦值小于0的所有任務（被刪除的任務一定存在于與無人機巡航方向夾角余弦值不小于0的，其他巡航方向上的無人機的無折返任務列表中，若被刪除的任務為緊急配送任務，則可由其他巡航方向上的無人機執行）。

上述步驟中涉及的坐標系變換過程如圖2所示，無人機wj以其巡航起點站Owj（x，y）為原點，以其巡航方向為Y軸，以巡航方向的垂線為X軸建立新坐標系X′-Owj-Y′。為了獲取任務集A中所有任務在新坐標系中的坐標，需要計算新坐標系X′-Owj-Y′相對于舊坐標系X-O-Y旋轉的角度和平移的距離。

根據無人機wj在舊坐標系X-O-Y內巡航起點站和終點站Owj（x，y）、Qwj（x，y）的坐標，可以計算出新坐標系X′-Owj-Y′相對于舊坐標系X-O-Y旋轉的角度φwj，計算公式為

φwj=π2-arctan（Qwj（y）-Owj（y）Qwj（x）-Owj（x））（3）

根據無人機wj在舊坐標系X-O-Y內巡航起點站Owj（x，y）的坐標，可計算出新坐標系X′-Owj-Y′相對于舊坐標系X-O-Y平移的距離，如圖2所示，新坐標系X′-Owj-Y′相對于舊坐標系X-O-Y向右平移的距離為Owj（x），向上平移的距離為Owj（y）。由此，將任務集A中任務的取貨點和配送點放入新坐標系X′-Owj-Y′內，任務集A中任意一個任務ai的取貨點Oai（x，y）轉換后的坐標Owjai（x，y）的計算公式為

Oai（x）=Owjai（x）×cos（φwj）+Owjai（y）×sin（φwj）+Owj（x）

Oai（y）=Owjai（y）×cos（φwj）-Owjai（x）×sin（φwj）+Owj（y） （4）

為避免無人機wj執行任務時發生折返，需要刪除取貨點或配送點縱坐標為負的任務，以及刪除任務方向與無人機wj巡航方向夾角余弦值為負（任務與無人機巡航方向夾角大于90°）的任務，計算公式為

cos（∠αwj，ai）=（（Qwjai（x）-Owjai（x））×（Qwjwj（x）-Owjwj（x））+（Qwjai（y）-Owjai（y））×（Qwjwj（y）-Owjwj（y）））（Qwjai（x）-Owjai（x））2+（Qwjai（y）-Owjai（y））2×（Qwjwj（x）-Owjwj（x））2+（Qwjwj（y）-Owjwj（y））2（5）

其中：∠αwj，ai表示任務ai與無人機wj巡航方向的夾角。

2.1.2第二輪任務篩選

在第二輪任務篩選中，當無人機wj的無折返任務列表Awj中所有任務完成總能耗大于無人機wj的能耗閾值Ewj時，它需要對Awj中任務的能耗效用參數和時間緊迫程度進行綜合評估，并根據評估結果進行任務刪除。

為了便于評估任務能耗以及避免任務執行過程中產生折返，無人機wj對任務列表Awj中的任務按照縱坐標排序進行路徑規劃。如圖3所示，無人機wj對任務列表Awj內的任務取貨點和配送點的縱坐標進行遞增排序，生成一條從無人機wj巡航起點站Owj（x，y）出發，經過Awj中所有任務的取貨點和配送點，并返回無人機wj巡航終點站Qwj（x，y）的軌跡序列FAwj。在軌跡序列FAwj中，每個任務的取貨點和配送點并不一定是一對連續的點，在第一輪任務篩選中通過刪除任務方向與無人機巡航方向夾角大于90°的任務，能夠確保每個任務取貨點的縱坐標總是小于其配送點的縱坐標，使得無人機總是先經過任務的取貨點再到達該任務的配送點。

為了避免產生迂回路徑，若存在縱坐標相同的軌跡點，則從這些橫坐標最大和最小的軌跡點中選出與軌跡序列中縱坐標最接近，且稍小于軌跡點最近的軌跡點作為這些軌跡點中的第一次序點（無人機最先經過的點）。如果第一次序點是這些軌跡點中橫坐標最大的，則其余軌跡點按照橫坐標遞減排序，否則按照橫坐標遞增排序，例如圖3中存在縱坐標相同的三個軌跡點F2Awj、F3Awj、F4Awj，其中橫坐標最大和最小的軌跡點分別為F2Awj、F4Awj，與F2Awj、F4Awj縱坐標最近且稍小的軌跡點為F1Awj，軌跡點F2Awj與F1Awj間的距離最近，所以F2Awj為F2Awj、F3Awj、F4Awj中的第一次序點，且F2Awj為橫坐標最大的軌跡點，由此在路徑規劃時這三個軌跡點按照橫坐標遞減排序。

無人機wj按照上述方法進行路徑規劃生成軌跡序列FAwj后，如果發現軌跡序列FAwj所需能耗超出其能耗閾值Ewj（若能耗未超出閾值Ewj，停止第二輪任務篩選，并直接將Awj作為無人機wj的交互前候選任務列表），需要根據任務在當前輪次的時間緊迫性參數以及它的一對軌跡點（任務的取貨點和配送點）在軌跡序列FAwj中的能耗效用參數來決定是否將該任務從軌跡序列FAwj中篩除。具體過程如算法1所示。

算法1第二輪任務篩選算法

輸入：任意一架無人機wj的無折返任務列表Awj，及其能量閾值Ewj。

輸出：任意一架無人機wj交互前候選任務列表A′wj。

1Awj中任務取貨點和配送點按照縱坐標遞增排序，生成Awj的軌跡序列FAwj

2if 任務取貨點和配送點縱坐標相同

3從這些橫坐標最大和最小的軌跡點中選出與軌跡序列中縱坐標最接近，且稍小于的軌跡點最近的軌跡點作為這些軌跡點中的第一次序點

4if 第一次序點是這些軌跡點中橫坐標最大的

5其余軌跡點按照橫坐標遞減排序

6else

7其余軌跡點按照橫坐標遞增排序

8end

9end

10根據式（10）計算任意一個任務ai在軌跡序列FAwj中的能耗效用參數和時間緊迫性參數的評估值PAwj，ai，并通過遍歷找出軌跡序列中最大的評估值作為無人機wj篩選任務的初始閾值ΘAwj

11while（EAwj-Ewjgt;ε）

12if PAwj，ai≥ΘAwj

13從Awj中刪除任務ai，及其在軌跡序列FAwj中的一對軌跡點，并計算軌跡序列FAwj的能耗EAwj

14else

15根據式（11）更新ΘAwj

16end

17end

在算法1中，對于Awj中任意一個任務ai，在當前輪次的時間緊迫參數DAwj，ai的計算如下：

DAwj，ai=1-11+e-T0-TaiC1（6）

其中：C1為常數，用來調節時延在區間上的分布；Tai表示任務ai要求的最晚配送時間；T0表示當前時刻。任務ai的時間緊迫性參數評估值越大，表示完成該任務的緊迫性越小，該任務越應該被刪除，由此根據任務ai的時間緊迫性參數評估值篩選任務，可以優化無人機完成任務的總時延。

對于Awj中任意一個任務ai，其取貨點Owjai（x，y）和配送點Qwjai（x，y）在Awj的軌跡序列FAwj中對應的軌跡點分別為FmAwj、FnAwj。在算法1中，當評估軌跡點FmAwj的能耗效用參數時，可根據軌跡點FmAwj相鄰的兩個軌跡點Fm-1Awj、Fm+1Awj進行評估，如圖4所示，三個相鄰的軌跡點Fm-1Awj、FmAwj、Fm+1Awj兩兩相連形成一個三角形，在該三角形中，軌跡點Fm-1Awj和FmAwj間飛行能耗與軌跡點FmAwj和Fm+1Awj間飛行能耗之和，與軌跡點Fm-1Awj和Fm+1Awj間飛行能耗的差值可以評估軌跡點FmAwj的能耗效用參數EFmAwj，計算公式為

EFmAwj=1-e-（EFm-1，mAwj+EFm，m+1Awj-EFm-1，m+1AwjC2）（7）

其中：C2為常數，用來調節能耗在區間上的分布；EFm-1，mAwj表示軌跡點Fm-1Awj和FmAwj間的飛行能耗，可通過軌跡點Fm-1Awj和FmAwj間距離LFm-1，mAwj與能耗的關系計算得出。在文獻［22］中無人機能耗和飛行距離的關系表示如下：

EFm-1，mAwj=LFm-1，mAwjVwj×f（Vwj）（8）

其中：f（Vwj）表示無人機wj以速度Vwj勻速飛行的功率，軌跡點Fm-1Awj和FmAwj間距離LFm-1，mAwj可通過歐氏距離求解得出。

同理，任務ai配送點Qwjai（x，y）在Awj的軌跡序列中對應的軌跡點FnAwj能耗效用參數為EFnAwj，任務ai能耗效用參數的評估值EAwj，ai的計算公式為

EAwj，ai=EFmAwj+EFnAwj2（9）

軌跡點的能耗效用參數反映的是軌跡點在軌跡序列中對整體能耗的影響，在軌跡序列FAwj中，軌跡點FmAwj、FnAwj的能耗效用參數EFmAwj、EFnAwj越大，表示選擇該軌跡點額外增加的能耗越多，軌跡點FmAwj、FnAwj在軌跡序列FAwj中越應該被刪除。由此根據任務ai取貨點和配送點在軌跡序列FAwj中對應的軌跡點FmAwj、FnAwj的能耗效用參數篩選任務可以優化無人機完成軌跡序列中任務的總能耗。

任務ai基于能耗效用參數EAwj，ai和時間緊迫性參數DAwj，ai的綜合評估值計算如下：

PAwj，ai=μ×DAwj，ai+（1-μ）×EAwj，ai（10）

其中：μ表示調節能耗效用參數和時間緊迫性參數的比重。

無人機wj從Awj的軌跡序列中篩選出能耗效用參數和時間緊迫性參數綜合評估值較大的任務，為此需要設定能耗效用參數和時間緊迫性參數評估的初始閾值ΘAwj，初始閾值可通過遍歷軌跡序列中所有軌跡點，計算其能耗效用參數和時間緊迫性參數的綜合評估值，選擇其中最大的評估值作為初始閾值，當任務能耗效用參數和時間緊迫性參數的綜合評估值大于等于該閾值時，將該任務取貨點和配送點對應的軌跡點從Awj的軌跡序列FAwj中刪除。在算法1中，每刪除一輪任務后，需要判斷軌跡序列FAwj中剩余軌跡所需的能耗是否滿足能耗約束。如果是，則更新ΘAwj值，繼續進行下一輪任務刪除，否則算法結束。ΘAwj迭代更新公式如下：

ΘAwj=（1-1en-e）×ΘAwj（11）

其中：n表示無人機wj刪除軌跡點的第n輪迭代（遍歷一次軌跡序列稱為一輪迭代）。閾值ΘAwj隨著迭代次數的增加不斷減少，隨著迭代次數的增加ΘAwj減少得越來越慢。

在算法1中，通過迭代更新閾值，不斷刪除能耗效用參數和時間緊迫性參數的綜合評估值大于閾值的任務，直到無人機軌跡序列內的任務的總能耗收斂，收斂條件如下所示。

|EAwj-Ewj|≤ε（12）

其中：EAwj表示無人機wj完成刪除任務后的無折返任務列表Awj內的任務總能耗；ε表示無人機wj完成Awj內任務的總能耗與無人機wj最大能量儲備的差值，當能耗差值收斂到［-ε，ε］時，則停止任務篩選，從而生成無人機wj的交互前候選任務列表A′wj，而未被選中的任務將在后續巡航中被執行，或者由其他無人機執行。

2.2基于共識的沖突解決階段

在基于共識的沖突解決階段，無人機間交互彼此的候選任務信息，再根據交互的信息解決任務沖突。交互的信息包括飛往巡航終點站之前可執行的交互前候選任務列表對應的軌跡序列中軌跡點的序列號、軌跡點的原始坐標、軌跡點轉換后的坐標，以及無人機的最大能量儲備。例如，無人機wj需要提供給其他無人機的交互信息包括飛往巡航終點站之前可執行的交互前候選任務列表A′wj、A′wj對應的軌跡序列FA′wj的序列號、軌跡序列FA′wj中每個軌跡點在舊坐標系X-O-Y內的原始坐標，以及軌跡序列FA′wj中每個軌跡點在新坐標系X′-Owj-Y′內轉換后的坐標，如表1所示。

表1無人機wj任務信息

Tab.1Tasks information of UAV wj

軌跡序列號原始坐標轉換后的坐標最大能量儲備

1Oa1（x，y）Owja1（x，y）

2Oa2（x，y）Owja2（x，y）Ewj

3Qa2（x，y）Qwja2（x，y）

4Qa1（x，y）Qwja1（x，y）

無人機根據任務對應軌跡點在舊坐標系內的原始坐標來判斷任務是否在無人機之間存在沖突。具體地，如果某個任務兩個軌跡點在舊坐標系X-O-Y內的原始坐標同時在多個無人機交互信息中出現，則說明該任務在這多個無人機之間存在沖突。

在圖5中，無人機wj收到了無人機wk和wl的交互信息后，然后根據三者的交互前候選任務列表A′wj、A′wk、A′wl的軌跡序列FA′wj、FA′wk、FA′wl的軌跡點在舊坐標系X-O-Y內的原始坐標來獲取在無人機wj、wk、wl之間發生沖突的任務。

當任務沖突發生在多個無人機之間，則需要判斷這多個無人機各自交互信息中包含的任務列表所需的能耗是否低于各自的能耗閾值，如果只有一個無人機的判斷結果為是，則該無人機直接被選定為該任務的執行者，如果存在兩個以上的無人機的判斷結果為是，則需要在兩個以上的無人機中執行任務沖突解決算法；如果這多個無人機的判斷結果都為否，則在這多個無人機之間執行任務沖突解決算法。

例如，無人機wj在無人機wk和wl之間執行任務沖突解決算法的具體過程如算法2所示。具體地，在算法2中，無人機wj根據交互信息自行判斷并生成沖突任務列表。沖突任務列表中的任務根據其配送點對應的軌跡點在舊坐標系X-O-Y內的Y坐標降序排列。在算法2中，無人機wj需要分別計算沖突任務在不同無人機巡航方向上（無人機wj、wk、wl的巡航方向）的能耗效用參數和時延性能參數，并根據這兩個參數綜合評估出沖突任務由哪架無人機執行。

算法2無人機共識沖突解決算法

輸入：任意一架無人機wj交互前候選任務列表A′wj，及其軌跡序列FA′wj的序列號，軌跡序列FA′wj中每個軌跡點在舊坐標系X-O-Y內的原始坐標，以及在新坐標系X′-Owj-Y′內轉換后的坐標。

輸出：任意一架無人機wj解決沖突后的任務列表Awj。

1遍歷無人機交互信息，當任務兩個軌跡點在舊坐標系X-O-Y內的原始坐標同時在多架無人機的交互信息中，把該任務放到無人機沖突任務列表Ao中

2計算每架無人機完成交互前候選任務列表的能耗，并判斷能耗是否低于各自的能耗閾值

3if只有一架無人機判斷結果為是

4該無人機直接選定為其所有沖突任務的執行者

5else if 存在兩個及以上的無人機判斷結果為是

6繼續執行算法解決任務沖突

7else if 判斷結果為否

8繼續執行算法解決任務沖突

9end

10while（Ao≠）

11根據沖突任務取貨點和配送點在軌跡序列中對應的軌跡點的縱坐標進行遞增排序，并從軌跡序號最大的任務開始解決沖突

12根據式（17）計算沖突任務在不同無人機巡航方向上能耗效用參數和時延性能參數的綜合評估值，基于該評估值最小的共識解決沖突

13更新任意一架無人機wj的任務列表A′wj、軌跡序列FA′wj以及沖突任務列表Ao

14end

15Awj=A′wj

下面將結合圖5對算法2處理沖突任務的過程進行詳細說明，例如任務ai為無人機wj的沖突任務列表中的一個任務，任務ai的取貨點和配送點在A′wj、A′wk、A′wl的軌跡序列FA′wj、FA′wk、FA′wl中對應的軌跡點分別為FmA′wj、FnA′wk、FqA′wl和Fm′A′wj、Fn′A′wk、Fq′A′wl，任務ai在無人機wj、wk、wl的巡航方向上能耗效用參數和時延性能參數是不同的，算法2將選擇能耗效用參數和時延性能參數綜合評估值最小的巡航方向對應的無人機作為任務ai的執行者。任務ai在A′wj的軌跡序列FA′wj中的時延性能參數計算公式為

TA′wj，ai=1-e-tA′wj，aiC3（13）

其中：c3為常數，用來調節時延在區間上的分布；tA′wj，ai表示任務ai在A′wj軌跡序列中時延的估計值。根據文獻［22］無人機能耗與時間的關系，計算公式為

tA′wj，ai=Ewj-EFm′A′wj→Qwjwj（x，y）f（Vwj）（14）

其中：Ewj為無人機wj的最大能量儲備；EFm′A′wj→Qwjwj（x，y）表示在A′wj的軌跡序列FA′wj中從軌跡點Fm′A′wj到達無人機wj航終點站Qwjwj（x，y）對應的軌跡點無人機的飛行能耗，再根據無人機wj的最大能量儲備Ewj與EFm′A′wj→Qwjwj（x，y）的差值估算完成任務ai的時延。

假設任務ai取貨點和配送點在A′wj的軌跡序列中對應的軌跡點分別為FmA′wj、Fm′A′wj，與任務篩選階段能耗效用參數的評估方法相同，任務ai在A′wj的軌跡序列中的能耗效用參數的評估值，可以通過ai的取貨點和配送點在A′wj的軌跡序列中對應的軌跡點FmA′wj、Fm′A′wj的能耗效用參數的評估值計算得出，其中軌跡點FmA′wj的能耗效用參數計算如下：

EFmA′wj=1-e-（EFm-1，mA′wj+EFm，m+1A′wj-EFm-1，m+1A′wjC2）（15）

同理，軌跡點Fm′A′wj對應的能耗效用參數為EFm′A′wj，任務ai在A′wj的軌跡序列FA′wj中（在無人機wj的巡航方向上）的能耗效用參數的評估值計算如下：

EA′wj，ai=EFmA′wj+EFm′A′wj2（16）

任務ai在A′wj、A′wk、A′wl的軌跡序列FA′wj、FA′wk、FA′wl中能耗效用參數和時延性能參數的綜合評估值計算如下：

UA′wj，ai=μ×TA′wj，ai+（1-μ）×EA′wj，ai（17）

UA′wk，ai=μ×TA′wk，ai+（1-μ）×EA′wk，ai（18）

UA′wl，ai=μ×TA′wl，ai+（1-μ）×EA′wl，ai（19）

無人機wj根據任務ai在無人機wj、wk、wl的巡航方向上能耗效用參數和時延性能參數的綜合評估值最小的共識解決沖突問題，選擇評估值最小的無人機執行沖突任務ai。無人機wj每解決一個沖突任務就需要更新無人機wj、wk、wl的任務列表A′wj、A′wk、A′wl及其對應軌跡序列FA′wj、FA′wk、FA′wl，后續沖突任務列表中沖突任務的時延性能參數和能耗效用參數的計算都是基于更新后的任務列表和軌跡序列進行的。

每個無人機在解決完所有沖突后，還需要判斷解決完所有沖突后的任務列表對應的軌跡序列所需要的能耗是否滿足自身的能耗約束，如果判斷結果為是，則需要添加新的任務。在添加任務的過程中既要滿足能耗約束，又要避免新的任務沖突。

本文繼續以無人機wj為例對任務添加過程進行說明，詳細過程如算法3所示。

算法3無人機沖突解決后的任務添加算法

輸入：任意無人機wj解決沖突后的任務列表Awj，無折返任務列表Awj。

輸出：無人機每輪巡航最終可執行的無沖突任務執行列表ARwj。

1ARwj=Awj

2if Ewj-EAwj≤ε

3無須添加任務，返回無沖突任務列表ARwj

4else

5根據式（21）計算任務能耗效用參數和時間緊迫性參數綜合評估值的閾值ΘAwj

6if 存在ai，ai∈Awjamp;amp;aiAwj的能耗效用參數和時間緊迫性參數的評估值PAwj，ailt;ΘAwj

7if 添加任務ai到無人機wj的任務列表Awj后的總能量EAwj≤Ewj

8選擇能耗效用參數和時延性能參數綜合評估值最小的任務ai添加到無人機wj的任務列表ARwj中

9 end

10end

11end

在算法3中，無人機wj從無折返任務列表Awj中選擇能耗效用參數和時間緊迫性參數的綜合評估值小于閾值ΘAwj的任務進行添加，約束如下：

PAwj，azlt;ΘAwj（20）

其中：PAwj，az表示任務az在Awj中能耗效用參數和時間緊迫性參數的綜合評估值，與任務篩選階段任務的綜合評估值計算方法相同；ΘAwj是在Awj中最后一輪迭代篩選任務的閾值與倒數第二輪迭代的閾值的平均值，計算為

ΘAwj=Θn-1Awj+ΘnAwj2（21）

其中：ΘnAwj表示任務篩選階段第n次迭代的閾值，即最后一輪迭代的閾值，它與第n-1輪迭代的閾值的平均值，為新添加任務在Awj中能耗效用參數和時間緊迫性參數綜合評估值的閾值。

若存在多個符合能耗效用參數和時間緊迫性參數約束的任務，則需選擇能耗效用參數和時延性能參數綜合評估值在Awj中最小的任務（為了避免產生新的任務沖突），與沖突解決階段任務的綜合評估值計算方法相同。此外，還需要判斷添加該任務到Awj后無人機wj的總能耗是否小于其最大能量儲備。

EAwj≤Ewj（22）

若能耗小于無人機的最大能量儲備，則可以添加該任務到無人機wj的無沖突任務列表ARwj中，直到不再滿足無人機wj能耗的約束條件，則停止添加任務。

3實驗評估

3.1參數設置

為了對本文方法的性能進行評估，在MATLAB中對相關算法進行實驗仿真，相關參數如表2所示。

為了評估本文方法，本文實驗將其與現有方法迭代啟發式隨機事件調度算法［8］和帶時間約束的分布式任務調度算法［21］進行平均能耗和平均時延的性能比較（其中文獻［8］算法是典型的集中式方法并在后文稱為對比算法1，文獻［21］算法是典型的分布式方法并在后文稱為對比算法2，平均能耗指的是單位距離任務的完成能耗，可通過總能耗除以任務的總距離計算得出，平均時延指的是單位距離任務的完成時延，可通過總時延除以任務的總距離計算得出，任務的總距離表示所有任務取貨點到配送點的距離之和）。其中，為了分析本文定義的能耗效用參數和時延參數對本文算法的影響，本文實驗對本文算法的參數進行了三種不同設置，可稱為本文算法的三種變體：只考慮能耗效用參數（在后文稱為變體1）、只考慮時延參數（在后文稱為變體2）以及同時考慮能耗效用參數和時延參數（在后文稱為變體3）。另外為了評估本文算法在不同應用場景中的性能，本文實驗設置三種可選場景，如圖6所示。這三種場景分別為巡航方向夾角為90°的場景1，巡航方向夾角為120°的場景2，巡航方向夾角為180°的場景3。

3.2不同算法的性能比較

3.2.1不同算法的任務平均能耗

在圖6（a）的場景下，本文算法的三種變體與兩種對比算法的任務平均能耗情況如圖7所示。隨著任務數增加，本文算法的三種變體和對比算法任務平均能耗先上升后趨于穩定，上升和穩定的任務區間較為相近，且本文算法的三種變體在平均能耗的性能上均明顯優于對比算法1和2。這是因為對比算法1和2都未考慮任務與無人機巡航方向的相關性對能耗的影響，而本文算法根據定義的能耗效用參數等計算任務與無人機巡航方向的相關性，避免無人機執行折返任務和能耗效用參數較大的任務。具體地，對比算法1的無人機由于需要不斷返回調度中心補充能量，增加了額外的任務接收成本，所以對比算法1的任務平均能耗高于本文算法的三種變體，而對比算法2由于采用局部的任務成本評估指標解決任務沖突，未考慮任務相互依賴關系對能耗的影響，也將導致任務的能耗成本增加，所以對比算法2的任務平均能耗高于本文算法的三種變體。

對于本文算法的三種變體，僅考慮能耗效用參數時（本文算法變體1）平均能耗最小，同時考慮能耗效用參數和時延參數時（本文算法變體3）平均能耗較大，僅考慮時延參數時（本文算法變體2）平均能耗最大，這是因為根據定義的能耗效用參數分配任務無人機接收任務的能耗成本更小。當任務數大于700時平均能耗趨于穩定，這是因為當任務足夠密集且均勻時，無人機接收任務的成本增加不明顯；當任務數小于700時平均能耗不斷增加，這是因為初始時刻任務稀疏，無人機優先完成能耗效用參數較小的任務，無人機接收任務的能耗成本隨著任務數的增加不斷變大。

3.2.2不同算法的任務平均時延

在圖6（a）的場景下，本文算法的三種變體與兩種對比算法的任務平均時延情況如圖8所示。隨著任務數增加，本文算法的三種變體和對比算法任務平均時延先不變而后不斷增加，不變和增加的任務區間不超過100，且本文算法的三種變體在平均時延的性能上均明顯優于對比算法1，較優于對比算法2。這是因為對比算法1和2都未考慮任務與無人機巡航方向的相關性對時延的影響，而本文算法根據定義的時間緊迫性參數和時延性能參數等計算任務與無人機巡航方向的相關性，避免無人機執行折返任務和時間緊迫性參數以及時延性能參數較大的任務。具體地，對比算法1的無人機需要不斷返回調度中心補充能量，增加額外的時間成本，因此對比算法1的任務平均時延明顯高于本文算法的三種變體；而對比算法2在任務篩選階段通過最小化等待時間生成預分配任務序列，減少了任務的完成時延，但依然忽視了任務相互依賴關系對時延的影響，因此對比算法2的任務平均時延較高于本文算法的三種變體。

對于本文算法的三種變體，僅考慮時延參數時（本文算法變體2）平均時延最小，同時考慮能耗效用參數和時延參數時（本文算法變體3）平均時延較大，僅考慮能耗效用參數時（本文算法變體1）平均時延最大，這是因為根據定義的時延參數分配任務無人機接收任務的時間成本更小。當任務數小于500時平均時延為0，這是因為任務數較少時無人機有足夠能量完成任務，當無人機能耗達到其最大能量儲備時，剩余任務可能由后續時間間隔內的無人機或者返程的無人機執行，當完成時間超過任務規定的最晚完成時間時，任務發生延遲且隨著任務數的增加平均時延不斷增加。

3.3不同場景下的性能比較

3.3.1不同場景下的任務平均能耗

本文算法在三種場景下的任務平均能耗的情況如圖9所示。隨著任務數的增加，本文算法在三種場景下的平均能耗都是先不斷增加而后趨于穩定。在任務數較少時三種場景下任務平均能耗相近，隨著任務數的增加三種場景下任務的平均能耗都是不斷增加后趨于穩定。這是因為本文算法定義的能耗效用參數在不同無人機的巡航方向上不同，三種場景下無人機的數量和巡航方向都不相同，無人機巡航方向的夾角越小，無人機數量越多，無人機執行任務的能耗越小。

在場景1中，根據任務的能耗效用參數進行任務篩選時，場景1不同充電站點的無人機間的夾角較小且密集，在篩選任務時，任務的能耗效用參數較小，在解決無人機間的沖突任務時，沖突任務的能耗效用參數在不同無人機間的最值更小，因此場景1任務平均能耗最小，場景2較大，場景3最大。

3.3.2不同場景下的任務平均時延

本文算法在三種場景下的任務平均時延的情況如圖10所示。隨著任務數的增加，本文算法在三種場景下的平均時延都是先不變后不斷增加。任務數較少時，三種場景下任務的平均時延都為0，隨著任務數的增加，三種場景下任務的平均時延不斷增加。這是因為本文算法定義的時間緊迫性參數和時延性能參數評估值在不同無人機的巡航方向上不同，三種場景下無人機的數量和巡航方向都不相同，無人機間巡航方向的夾角越小，無人機數量越多，無人機執行任務的時間越短。

在場景1中，根據任務的時間緊迫性參數和時延性能參數評估值進行任務篩選時，由于場景1中無人機間的夾角較小且密集，篩選出的任務完成時間較小，在解決無人機間的沖突任務時，沖突任務的時延性能參數評估值在不同無人機間的最值更小，因此場景1平均時延最小，場景2平均時延較大，場景3平均時延最大。

4結束語

本文提出了基于任務與巡航方向相關性分析的無人機任務分配方法。與現有方法不同的是，本文考慮了任務與無人機巡航方向之間的相關性對無人機任務能耗和時延的影響，在任務篩選階段根據任務方向與無人機巡航方向夾角的余弦值篩選任務，從而避免無人機折返，在任務沖突解決階段根據任務在不同無人機巡航方向上能耗效用參數和時延參數的綜合評估值不同從而解決任務沖突。實驗證明，本文方法可獲得更低的任務平均能耗和平均時延，后續筆者將關注和研究無人機的異構性對任務分配的影響。

參考文獻：

［1］Song B D，Park K.Persistent UAV delivery logistics：MILP formulation and efficient heuristic［J］.Computers amp; Industrial Engineering，2018，120：418-428.

［2］Fu Zhangjie，Mao Yuanhang，He Daojing，et al.Secure multi-UAV collaborative task allocation［J］.IEEE Access，2019，7：35579-35587.

［3］Jiao Ziqiang，Yao Peiyang，Zhang Jieyong，et al.MAV/UAV task coalition phased-formation method［J］.Journal of Systems Enginee-ring and Electronics，2019，30（2）：184-196.

［4］Wang Jian，Zhang Qianyin，Feng Gang，et al.Clustering strategy of UAV network based on deep Q-learning［C］//Proc of the 20th IEEE International Conference on Communication Technology.Piscataway，NJ：IEEE Press，2020：1684-1689.

［5］Gómez L J，Candia V A，Encina F.A new truck-drone routing problem for parcel delivery services aided by parking lots［J］.IEEE Access，2021，9：11091-11108.

［6］Huang Haiping，Hu Chengxi，Zhu Jie，et al.Stochastic task scheduling in UAV-based intelligent on-demand meal delivery system［J］.IEEE Trans on Intelligent Transportation Systems，2022，23（8）：13040-13054.

［7］Shao Jun，Cheng Jin，Xia Boyuan，et al.A novel service system for long-distance drone delivery using the “Ant Colony+A*” algorithm［J］.IEEE Systems Journal，2021，15（3）：3348-3359.

［8］Liu Zhaonian，Huang Gaofei，Zhong Qihong，et al.UAV-aided vehicular communication design with vehicle trajectory’s prediction［J］.IEEE Wireless Communications Letters，2021，10（6）：1212-1216.

［9］Wu Xueli，Yin Yanan，Xu Lei，et al.Multi-UAV task allocation based on improved genetic algorithm［J］.IEEE Access，2021，9：100369-100379.

［10］王冬冬，何勝學，路揚.考慮基站選址的UAV交通巡視路徑超級時空網絡模型［J］.計算機應用研究，2019，36（9）：2671-2674.（Wang Dongdong，He Shengxue，Lu Yang.UAV traffic patrolling path planning super-space-time network model considering base station location problem［J］.Application Research of Computers，2019，36（9）：2671-2674.）

［11］Luan Heyu，Xu Yitao，Liu Dianxiong，et al.Energy efficient task cooperation for multi-UAV networks：a coalition formation game approach［J］.IEEE Access，2020，8：149372-149384.

［12］Messous M，Senouci S.A game theory based efficient computation offloading in an UAV network［J］.IEEE Trans on Vehicular Techno-logy，2019，68（5）：4964-4974.

［13］Zhu Shichao，Gui Lin，Cheng Nan，et al.Joint design of access point selection and path planning for UAV-assisted cellular networks［J］.IEEE Internet of Things Journal，2020，7（1）：220-233.

［14］Duan Xiaojun，Liu Huiying，Tang Hong，et al.A novel hybrid auction algorithm for multi-UAVs dynamic task assignment［J］.IEEE Access，2020，8：86207-86222.

［15］Liang Jin.Research on distributed task allocation algorithm for unmanned aerial vehicles based on consensus theory［C］//Proc of Chinese Control and Decision Conference.2016：4892-4897.

［16］Lee H，Jung S，Kim J.Distributed and autonomous aerial data collection in smart city surveillance applications［C］//Proc of the 17th IEEE VTS Asia Pacific Wireless Communications Symposium.Piscata-way，NJ：IEEE Press，2021：1-3.

［17］Turner J，Meng Qinggang，Schaefer G，et al.Fast consensus for fully distributed multi-agent task allocation［C］//Proc of the 33rd Annual ACM Symposium.New York：ACM Press，2018：832-839.

［18］Zitouni F，Harous S，Maamri R.A distributed approach to the multi-robot task allocation problem using the consensus-based bundle algorithm and ant colony system［J］.IEEE Access，2020，8：27479-27494.

［19］Chen Xinye，Zhang Ping，Li Fang，et al.A cluster first strategy for distributed multi-robot task allocation problem with time constraints［C］//Proc of WRC Symposium on Advanced Robotics and Automation.2018：102-107.

［20］Zhao Wanqing，Meng Qinggang，Chung P.A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario［J］.IEEE Trans on Cybernetics，2016，46（4）：902-915.

［21］Turner J，Meng Qinggang，Schaefer G，et al.Distributed task reschedu-ling with time constraints for the optimization of total task allocations in a multirobot system［J］.IEEE Trans on Cybernetics，2017，48（9）：2583-2597.

［22］東方，吳媚，朱文捷，等.物聯網環境下面向能耗優化的無人機飛行規劃［J］.東南大學學報：自然科學版，2020，50（3）：555-562.（Dong Fang，Wu Mei，Zhu Wenjie，et al.Energy efficient flight plan for UAV in IoT environment［J］.Journal of Southeast University：Natural Science Edition，2020，50（3）：555-562.）

收稿日期：2022-03-22；修回日期：2022-05-20基金項目：國家自然科學基金資助項目（61802257）

作者簡介：何杏宇（1984-），女，湖南岳陽人，副教授，碩導，博士，主要研究方向為物聯網、群智計算和大數據分析等（sherri_he@163.com）；付沖（1996-），男，河南鄭州人，碩士研究生，主要研究方向為移動群智感知；楊桂松（1982-），男（通信作者），河南漯河人，副教授，碩導，博士，主要研究方向為物聯網與普適計算；趙子豪（2000-），男，本科生，主要研究方向為移動群智感知；李梓源（2001-），男，本科生，主要研究方向為移動群智感知.