基于DBSCAN聚類的異構(gòu)多智能體分層任務(wù)分配方法

張學(xué)軍，徐紅麗，李祥民，白 潔，郝東強(qiáng)

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

1 引 言

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

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

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

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

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

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

2 問題表述

某片區(qū)域存在N個待處理目標(biāo)任務(wù)點tpi，構(gòu)成待處理的任務(wù)集合TP為

式中，tpi={x，y}i，x和y表示目標(biāo)任務(wù)點位置坐標(biāo)信息。

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

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

通信距離約束可表述為

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

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

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

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

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

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

圖1 求解流程Fig.1 Solution process

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

3.1 聚類

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

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

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

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

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

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

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

3.2 全局任務(wù)分配

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

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

3.2.2 通信單元任務(wù)分配

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

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

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

3.3 局部任務(wù)分配

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

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

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

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

關(guān)于交叉變異操作，則是根據(jù)生成的執(zhí)行單元訪問目標(biāo)任務(wù)節(jié)點的父代個體序列，生成兩個不大于父代個體序列長度的隨機(jī)數(shù)，進(jìn)行幾種類型交叉操作，如圖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 通信單元局部任務(wù)分配

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

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

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

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

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

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

此時虛擬節(jié)點為

4 實 驗

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

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

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

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

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

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

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

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

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

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

圖8 通信單元訪問任務(wù)節(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 結(jié) 論

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