張學軍，徐紅麗，李祥民，白 潔，郝東強

（1. 中國電子科技集團公司第五十四研究所，石家莊 050081；2. 東北大學機器人科學與工程學院，沈陽 110819）

1 引 言

伴隨著多智能體技術和信息技術的發(fā)展，新的探測需求不斷產(chǎn)生，在多智能體的約束下，更多的挑戰(zhàn)也不斷涌現(xiàn)，相關研究方向也被不同學者廣泛關注［1］。當利用多智能體集群對多待探測點進行遍歷探測時，探測任務的分配問題是一個較為經(jīng)典的研究方向［2］。對應不同的使用場景，多智能體集群的任務分配可分為動態(tài)、靜態(tài)任務分配兩種［3］。在對動態(tài)目標進行探測時，常使用動態(tài)任務分配方式，因為此時待探測區(qū)域是未知的，探測任務總是不斷出現(xiàn)，所以只能邊探測、邊分配任務，很多學者也在相關領域進行了研究。例如，Bertuccelli 等針對傳感器存在噪聲的多智能體作戰(zhàn)場景問題，提出了一種基于增強CBBA（Consensus Based Bundle Algorithm，基于共識的捆綁算法）的動態(tài)任務規(guī)劃算法［4］。Capitan等針對多階段不確定條件下的規(guī)劃問題，提出了一種基于馬爾可夫決策過程（Markov Decision Process，MDP）的動態(tài)任務規(guī)劃算法［5］。上述問題沒有全局信息，任務分配時會著重考慮機器人的探測能力、通信延遲和能耗分配等因素［6-7］。在對靜態(tài)任務進行分配時，相關問題通常被建模為旅行商問題。例如，Abbasi 等人提出了啟發(fā)式艦隊合作算法，用以解決海洋棘冠海星集群處理問題［8］；Hooshangi 等提出了一種結合區(qū)間數(shù)VIKOR（多準則妥協(xié)解排序）和基于合約網(wǎng)絡協(xié)議（Contract Net Protocol，CNP）拍賣機制的多智能體任務規(guī)劃方法，用來解決災害環(huán)境中的救援問題［9］。上述工作通過使用能力更強的多智能體單元對待探測區(qū)域進行預掃描，憑借能力更強的實驗平臺改善了上述探測和能耗方面的部分缺點，然后再用多智能體集群進行探測任務，但是上述工作一方面需要大量可執(zhí)行通信和探測任務的多智能體單元，耗費偏高，且數(shù)量較少，每個多智能體單元分配的任務點數(shù)量較多，任務分配算法的計算效率和探測效率都比較低［10-11］。截至目前，不同場景下的探測任務仍然面臨很多問題，使用通信/探測的異構多智能體集群組合，對面向預探測后區(qū)域中的大規(guī)模探測點進行任務分配的工作還鮮有研究。

研究面向大規(guī)模探測點的異構多智能體集群組合的任務分配問題可以帶來很多好處，例如在能耗方面，異構多智能體單元組合各司其職，可實現(xiàn)更小的能源消耗，延長多智能體集群的工作時間［12］；在任務分配效率方面，負責通信的多智能體單元計算能力較強，可搭載更強的計算模塊，大幅提高任務分配效率［13］；在經(jīng)濟方面，執(zhí)行近距離探測任務的小型多智能體單元所配置傳感器的成本較低，和探測能力強的大型多智能體單元組合使用，能夠節(jié)省成本；在探測效率方面，異構集群可在單位時間內(nèi)探測更多的點位，增加單位時間內(nèi)的探測區(qū)域［14-15］。

但在研究過程中，仍面臨如下三個挑戰(zhàn)：首先是多智能體單元任務分配的均衡問題，考慮到隨著傳感器能力和探測需求的增加，預探測得到的點的數(shù)量越來越多，如何合理分配探測點給每個多智能體單元組群是一個挑戰(zhàn)。其次是異構多智能體單元間的配合問題，因為異構多智能體單元的功能各不相同，探測和通信等功能的多智能體單元需要在時間和空間域上進行協(xié)同，所以異構多智能體單元間的協(xié)同配合是一個挑戰(zhàn)。最后，多機器人任務分配問題是一個典型的NP-hard 問題，所以如何高效進行任務分配是一個挑戰(zhàn)。為了攻克上述挑戰(zhàn)，本文提出了一種新穎的基于聚類的混合求解方法（Cluster-based Hybrid Solution Method，CHM）。相比于直接使用遺傳算法（Genetic Algorithm，GA），該算法首先對所有任務節(jié)點進行聚類，其次設計了一套全局與局部相結合的分層任務分配算法，最后提出了一種異構多智能體單元配合算法。本文的貢獻如下：

（1）提出一種基于通信距離約束的基于密度的聚類（Density-Based Spatial Clustering of Applications with Noise，DBSCAN）等效算法，對大規(guī)模任務進行分組等效處理。

（2）提出一種異構多智能體單元任務配合方法，可使異構多智能體單元系統(tǒng)在探測、通信共同約束下進行工作。

（3）針對虛擬的預探測點進行了大量的仿真模擬實驗，進一步驗證了算法的有效性和實用性。

2 問題表述

某片區(qū)域存在N個待處理目標任務點tpi，構成待處理的任務集合TP為

式中，tpi={x，y}i，x和y表示目標任務點位置坐標信息。

現(xiàn)有M1個通信單元cu，M2個執(zhí)行單元eu構成的集群單元U為

式中，執(zhí)行單元cu主要負責執(zhí)行具體的任務，通信單元eu主要負責給執(zhí)行單元提供通信支援，不需要直接參與任務執(zhí)行。執(zhí)行單元在執(zhí)行任務時，通信單元需要在執(zhí)行單元通信范圍內(nèi)提供通信支持。

通信距離約束可表述為

式中，Ci，j表示通信單元cui和執(zhí)行單元euj之間是否可以建立通信，Ci，j= 1 表示通信單元可以和執(zhí)行單元之間建立通信，反之則表示不能；di，j表示通信單元cui和執(zhí)行單元euj之間的距離，r表示通信單元cui的通信半徑。

執(zhí)行任務能力約束可表述為在時刻t時，執(zhí)行單元euj只能訪問一個任務節(jié)點，即

優(yōu)化目標為移動總距離

表示期望參與所有任務的裝備單元移動的總距離能夠最小，式中Lcui表示通信單元cui移動的總距離，Leuj表示執(zhí)行單元euj移動的總距離。

3 集群協(xié)同任務分配求解框架

執(zhí)行單元和通信單元需要協(xié)同完成對所有任務點的處理，且執(zhí)行單元與通信單元之間存在通信距離約束，受限于當前算力水平，直接進行任務分配求解很難在有限的時間內(nèi)得到相對最優(yōu)的任務分配結果。本文求解集群協(xié)同任務分配問題的流程如圖1所示。

圖1 求解流程Fig.1 Solution process

首先根據(jù)疑似目標節(jié)點的位置分布，按照通信距離約束信息對目標任務節(jié)點進行DBSCAN 聚類，并將聚類到一起的目標任務節(jié)點定義為一個任務簇。然后根據(jù)每個任務簇包含的目標任務節(jié)點屬性特征信息并結合裝備單元能力特征信息對所有任務簇進行等效模糊處理，得到能反映內(nèi)部各疑似目標節(jié)點信息的新的等效任務節(jié)點。接著根據(jù)得到的新的任務節(jié)點分別對通信單元和執(zhí)行單元進行全局任務分配。執(zhí)行單元任務分配問題可轉化為多旅行商問題，然后采用遺傳算法進行求解，通信單元任務分配問題需要考慮執(zhí)行單元在各個任務簇的時間信息，因而可以將其等效為帶時間窗口的多旅行商問題并采用遺傳方法進行求解。在完成針對通信單元和執(zhí)行單元的全局任務分配后，需要針對每個任務簇內(nèi)部所有目標任務節(jié)點進行任務分配，執(zhí)行單元任務分配問題等效轉化為旅行商問題，采用遺傳算法進行求解。然后根據(jù)執(zhí)行單元的訪問目標任務節(jié)點序列，規(guī)劃通信單元的虛擬訪問節(jié)點，從而完成執(zhí)行單元和通信單元的局部任務分配。

3.1 聚類

考慮到通信約束的影響，執(zhí)行單元必須在通信單元附近選擇可執(zhí)行的任務點，同時當任務規(guī)模變大，整體優(yōu)化將變得更加復雜，因此首先考慮通過通信距離約束將任務進行分組，從而將大規(guī)模任務與資源配置分配問題變成局部小規(guī)模問題，并以此來降低計算量。采用DBSCAN 方法對任務點進行分組，

式中，gi={tp1，tp2，…，tpl}，表示第i個任務簇有l(wèi)個目標任務點，k表示分組后的任務簇數(shù)目。

首先根據(jù)聚類結果和任務簇gi群組內(nèi)目標任務點tpi的分布情況，將其等效轉化為一個節(jié)點，然后對執(zhí)行單元euj完成任務簇gi的移動距離和耗費時間做等效近似處理。

任務簇gi等效節(jié)點Ex，y(gi)位置坐標為

式中，fr(gi)表示包含任務簇gi內(nèi)所有目標任務節(jié)點tpi的最小覆蓋圓的圓心坐標。

執(zhí)行單元訪問完任務簇gi內(nèi)所有任務目標節(jié)點tpi的等效近似移動距離Ed為

執(zhí)行單元完成該群組的等效近似時間Et為

3.2 全局任務分配

3.2.1 執(zhí)行單元任務分配

通過聚類將滿足通信約束的任務點聚類為若干個可供執(zhí)行單元組選擇的任務簇gi，此時全局執(zhí)行單元euj任務分配問題為多旅行商問題，將所有執(zhí)行單元的最小移動距離作為優(yōu)化目標函數(shù)，采用遺傳算法求解每個執(zhí)行單元相對最優(yōu)的任務簇訪問序列結果。優(yōu)化目標形式為

3.2.2 通信單元任務分配

通信單元需要和執(zhí)行單元協(xié)同完成對任務點的處理，根據(jù)執(zhí)行單元的全局分配結果對通信單元進行任務分配，由于各任務簇的任務數(shù)量不同，執(zhí)行單元在處理各任務簇時需要的時間也各不相同，因而通信單元到達各個任務簇節(jié)點存在的時間約束為

式中，wj= max(0，ei-aj)，aj是通信單元到達任務簇節(jié)點的時間，wj表示通信單元等待的時間，ej表示執(zhí)行單元開始執(zhí)行第j個節(jié)點的時間，Δij表示通信單元從節(jié)點i到達節(jié)點j的時間。

根據(jù)各個任務簇的時間約束，此時通信單元的全局任務分配問題為帶時間窗口的多旅行商問題，將所有通信單元cui的最小移動距離作為優(yōu)化目標函數(shù)，采用遺傳算法求解每個執(zhí)行單元的相對最優(yōu)訪問任務簇序列。優(yōu)化目標函數(shù)的形式為

3.3 局部任務分配

在執(zhí)行任務過程中，通信單元不直接參與對任務點的處理，僅負責與執(zhí)行單元完成通信，即不需要到達任務點位置。群組內(nèi)任務分配首先采用遺傳算法對執(zhí)行單元進行任務分配，然后根據(jù)對執(zhí)行單元的任務分配結果對通信單元進行任務規(guī)劃。

3.3.1 執(zhí)行單元局部任務分配

執(zhí)行單元的局部任務分配問題屬于固定起止點的旅行商問題，將執(zhí)行該任務簇的執(zhí)行單元最小移動距離作為優(yōu)化目標函數(shù)，然后采用遺傳算法求解相對最優(yōu)的目標任務節(jié)點訪問序列。優(yōu)化目標函數(shù)設置為

式中，disi，j表示從目標任務節(jié)點tpi到目標任務節(jié)點tpj之間的距離。遺傳算法求解步驟如下：

關于交叉變異操作，則是根據(jù)生成的執(zhí)行單元訪問目標任務節(jié)點的父代個體序列，生成兩個不大于父代個體序列長度的隨機數(shù)，進行幾種類型交叉操作，如圖2所示。

圖2 兩個基因位置交換交叉操作示意圖Fig.2 Schematic diagram of crossover operation of two gene positions

變異操作則是舍棄原父代個體，重新生成一個新的子代個體，如圖3所示。

圖3 變異操作示意圖Fig.3 Schematic diagram of mutation operation

3.3.2 通信單元局部任務分配

由于通信單元不需要到達任務位置點，因而根據(jù)執(zhí)行單元處理的任務位置點添加虛擬節(jié)點vx，y，來規(guī)劃通信單元的訪問節(jié)點位置。虛擬節(jié)點添加情況類型如圖4所示。

圖4 虛擬節(jié)點類型示意圖Fig.4 Diagram of the virtual node type

類型Ⅰ：當任務簇gi內(nèi)部所有任務節(jié)點tpi都在執(zhí)行該任務簇的通信單元cui通信范圍內(nèi)，有

式（14）、式（15）表示此時虛擬節(jié)點vx，y的坐標為包含任務簇gi內(nèi)所有任務節(jié)點tpi的最小覆蓋圓的圓心坐標。

類型Ⅱ：當任務簇gi內(nèi)部部分任務節(jié)點tpi都在執(zhí)行該任務簇的通信單元cui通信范圍內(nèi)時，根據(jù)執(zhí)行單元euj執(zhí)行任務節(jié)點順序，對當前任務組任務節(jié)點進行二次分組為

式中，g′i={tpj|di，j≤r}，g′i表示對任務簇單元gi內(nèi)任務節(jié)點tpi根據(jù)通信單元cui通信范圍重新聚類而成的新的小任務簇，a表示對任務簇gi二次聚類生成的新的任務簇數(shù)目。

此時虛擬節(jié)點為

4 實 驗

本文算法仿真計算機配置為：CPU型號為Intel（R） Core（TM） i7-6500U CPU@ 2.50 GHz 2.59 GHz，內(nèi)存8.00 GB。

設區(qū)域大小為10 km×10 km，執(zhí)行單元數(shù)目為3 個，通信單元數(shù)目為2 個，通信距離為300 m，執(zhí)行單元移動速度為2 m/s，通信單元移動速度為4 m/s，實驗結構如表1～3所示。

表1 任務簇數(shù)目約為40時不同規(guī)模任務節(jié)點數(shù)Table 1 Comparison of the number of task nodes of different sizes when the number of task clusters is about 40

表2 任務簇數(shù)目約為50時不同規(guī)模任務節(jié)點數(shù)Table 2 Comparison of the number of task nodes of different sizes when the number of task clusters is about 50

表3 任務簇數(shù)目約為60時不同規(guī)模任務節(jié)點數(shù)Table 3 Comparison of the number of task nodes of different sizes when the number of task clusters is about 60

圖5和圖6分別表示不同任務規(guī)模和求解時間及移動總距離之間的關系，通過實驗結果可知，在10 km×10 km區(qū)域內(nèi)，當目標任務節(jié)點數(shù)小于等于500 時，在求解得到的移動距離相近的情況下，本文算法所用的求解時間相較于直接使用遺傳算法提升了70%以上。當任務節(jié)點數(shù)大于500 時，隨著任務節(jié)點數(shù)的增加，本文方法求解得到的相對最優(yōu)解明顯優(yōu)于直接使用遺傳算法，而且求解時間減少了6 倍以上。這足以說明，本文所提出的方法在求解大規(guī)模集群協(xié)同問題上能夠有效求解相對最優(yōu)的任務分配結果。

圖5 目標任務節(jié)點數(shù)與求解時間之間關系Fig.5 Relationship between the number of target task nodes and the solving time

圖6 目標任務節(jié)點數(shù)與移動總距離之間關系Fig.6 Relationship between the number of target task nodes and the total distance moved

以10 km×10 km 區(qū)域1000 個任務節(jié)點為例，3 個執(zhí)行單元和2個通信單元協(xié)同任務分配結果如圖7～9所示。

圖7 執(zhí)行單元訪問任務節(jié)點序列示意圖Fig.7 Schematic diagram of execution unit access task node sequence

圖7、圖8 分別表示3 個執(zhí)行單元遍歷訪問1000 個任務節(jié)點情況和2 個通信單元協(xié)同遍歷訪問虛擬節(jié)點情況。圖9表示執(zhí)行單元和通信單元協(xié)同訪問節(jié)點序列，執(zhí)行單元依次遍歷圖中所有任務節(jié)點，通信單元根據(jù)執(zhí)行單元訪問任務節(jié)點序列，同步規(guī)劃遍歷圖中虛擬節(jié)點，協(xié)同完成整個任務。從圖中可以看出，本文所提算法能有效解決具有通信約束的多異構集群協(xié)同任務分配問題。

圖8 通信單元訪問任務節(jié)點序列示意圖Fig.8 Schematic diagram of communication unit access task node sequence

圖9 執(zhí)行單元與通信單元協(xié)同訪問節(jié)點序列示意圖Fig.9 Schematic diagram of execution unit and communication unit co-access node sequence

5 結 論

本文針對具有通信距離約束的多異構集群大規(guī)模協(xié)同任務分配問題中存在的任務規(guī)模大、協(xié)同復雜難點，采用分而治之和全局與局部相結合的思想，提出了一種聚類和啟發(fā)式算法相結合的方法。實驗結果表明，相較于直接求解方法，本文所提算法不僅解決了大規(guī)模集群協(xié)同任務分配問題，還可以在保證優(yōu)化目標值相近的情況下，縮短70%以上的求解時間，較快得到相對最優(yōu)的任務分配結果。此外，本文所提方法不僅適用于水下場景的多異構集群的協(xié)同任務分配問題，而且也可以擴展應用到農(nóng)業(yè)領域的無人機集群采摘任務作業(yè)問題等。目前，本文所研究的集群任務分配問題聚焦于具有聚集特點的任務分布形式，然而在現(xiàn)實中任務分布形式多種多樣，未來將繼續(xù)研究在不同分布形式下（比如均勻分布、隨機分布和高斯分布等）異構集群協(xié)同任務分配方式。