基于DBSCAN聚類的異構多智能體分層任務分配方法

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

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

1 引 言

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

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

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

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

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

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

2 問題表述

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

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

現有M1個通信單元cu，M2個執行單元eu構成的集群單元U為

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

通信距離約束可表述為

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

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

優化目標為移動總距離

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

3 集群協同任務分配求解框架

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

圖1 求解流程Fig.1 Solution process

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

3.1 聚類

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

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

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

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

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

執行單元訪問完任務簇gi內所有任務目標節點tpi的等效近似移動距離Ed為

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

3.2 全局任務分配

3.2.1 執行單元任務分配

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

3.2.2 通信單元任務分配

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

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

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

3.3 局部任務分配

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

3.3.1 執行單元局部任務分配

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

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

關于交叉變異操作，則是根據生成的執行單元訪問目標任務節點的父代個體序列，生成兩個不大于父代個體序列長度的隨機數，進行幾種類型交叉操作，如圖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 通信單元局部任務分配

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

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

類型Ⅰ：當任務簇gi內部所有任務節點tpi都在執行該任務簇的通信單元cui通信范圍內，有

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

類型Ⅱ：當任務簇gi內部部分任務節點tpi都在執行該任務簇的通信單元cui通信范圍內時，根據執行單元euj執行任務節點順序，對當前任務組任務節點進行二次分組為

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

此時虛擬節點為

4 實 驗

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

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

表1 任務簇數目約為40時不同規模任務節點數Table 1 Comparison of the number of task nodes of different sizes when the number of task clusters is about 40

表2 任務簇數目約為50時不同規模任務節點數Table 2 Comparison of the number of task nodes of different sizes when the number of task clusters is about 50

表3 任務簇數目約為60時不同規模任務節點數Table 3 Comparison of the number of task nodes of different sizes when the number of task clusters is about 60

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

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

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

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

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

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

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

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

5 結 論

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