基于聚類分組的異構(gòu)多機(jī)器人任務(wù)分配算法研究

鄭習(xí)羽，徐梓毓，王京華，2*

(1. 長(zhǎng)春理工大學(xué) 機(jī)電工程學(xué)院，長(zhǎng)春 130022； 2. 長(zhǎng)春理工大學(xué) 跨尺度微納制造教育部重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)春 130022)

0 引 言

諸如無(wú)人機(jī)、 無(wú)人車(chē)的無(wú)人系統(tǒng)(機(jī)器人)近年來(lái)發(fā)展十分迅速，憑借其優(yōu)秀的自主規(guī)劃與執(zhí)行能力，在許多領(lǐng)域得到了廣泛應(yīng)用，包括救援搜索、 行星探索、 軍事行動(dòng)、 生產(chǎn)調(diào)度、 資源分配等?，F(xiàn)代的工程及軍事任務(wù)變得越來(lái)越復(fù)雜，往往一個(gè)總體任務(wù)包含許多個(gè)不同類型的子任務(wù)，如戰(zhàn)場(chǎng)環(huán)境中的任務(wù)包含探索、 打擊和毀傷評(píng)估等，單個(gè)機(jī)器人已經(jīng)無(wú)法滿足解決大范圍內(nèi)的復(fù)雜任務(wù)，需要構(gòu)建多機(jī)器人系統(tǒng)協(xié)同完成多項(xiàng)不同類型的子任務(wù)。

多機(jī)器人任務(wù)分配(MRTA)問(wèn)題是多機(jī)器人系統(tǒng)協(xié)同控制的一個(gè)重要研究方向。該問(wèn)題需要多個(gè)機(jī)器人在一定約束條件下，規(guī)劃出無(wú)沖突的任務(wù)分配策略，并獲得全局收益良好的解。這個(gè)問(wèn)題在規(guī)定時(shí)間內(nèi)求解是困難的，求解全局最優(yōu)解需要花費(fèi)大量的時(shí)間和計(jì)算量。當(dāng)分配問(wèn)題比較復(fù)雜時(shí)，解集無(wú)法窮舉出來(lái)，幾乎不可能求出最優(yōu)解，所以為了保證算法的效率，通常用近似算法提供一個(gè)可接受的次優(yōu)解。

任務(wù)分配方法可以分為集中式和分布式兩種。集中式方法需要中央處理器為整個(gè)系統(tǒng)生成任務(wù)計(jì)劃，然后將結(jié)果傳遞給各個(gè)機(jī)器人。蟻群算法、 粒子群算法、 遺傳算法等集中式智能優(yōu)化算法在解決MRTA問(wèn)題方面都具有較優(yōu)的解。雖然集中式方法結(jié)果全局較優(yōu)，但是依賴大量的通信負(fù)載和計(jì)算量。此外，集中式方法的魯棒性比較差，機(jī)器人容易出現(xiàn)單點(diǎn)故障，且對(duì)動(dòng)態(tài)變化的通信響應(yīng)較慢。分布式方法不需要中央處理器，每個(gè)機(jī)器人在內(nèi)部生成任務(wù)清單，再和周?chē)臋C(jī)器人通過(guò)通信解決沖突。分布式系統(tǒng)能夠快速響應(yīng)外部環(huán)境的變化、 對(duì)通信帶寬的依賴性比較小。雖然優(yōu)化結(jié)果不如集中式，但是算法效率和魯棒性更高，單點(diǎn)故障的影響更小，能夠很好地應(yīng)對(duì)野外復(fù)雜環(huán)境的不確定性。分布式方法主要分為基于博弈論的機(jī)制和基于市場(chǎng)的機(jī)制，其中博弈論需要相對(duì)更長(zhǎng)的收斂時(shí)間，目前基于市場(chǎng)機(jī)制的拍賣(mài)算法是廣泛應(yīng)用的高效方法。

Choi等結(jié)合拍賣(mài)機(jī)制和信息共識(shí)機(jī)制，提出了基于一致性的束算法(CBBA)，與傳統(tǒng)的拍賣(mài)算法不同，該算法不需要有中間拍賣(mài)商，每個(gè)機(jī)器人內(nèi)部具有一致的任務(wù)投標(biāo)規(guī)則。CBBA被證明可以在較短時(shí)間內(nèi)收斂于至少50%的納什均衡解。一些研究在CBBA的基礎(chǔ)上進(jìn)行了改進(jìn)，使其適應(yīng)更復(fù)雜的問(wèn)題。Johnson等提出了異步解決任務(wù)沖突的規(guī)則，減少不必要的通信，盡量降低通信負(fù)載，實(shí)現(xiàn)了CBBA的異步通信。Buckman等考慮到時(shí)間敏感和動(dòng)態(tài)出現(xiàn)的約束，提出一種重規(guī)劃的CBBA-RP，提高任務(wù)快速協(xié)調(diào)性?；谌蝿?wù)優(yōu)先級(jí)約束，Binetti等提出了一種分散關(guān)鍵任務(wù)分配算法(DCTAA)，將標(biāo)記的關(guān)鍵任務(wù)優(yōu)先分配給機(jī)器人，實(shí)現(xiàn)最大化獎(jiǎng)勵(lì)且保證關(guān)鍵任務(wù)被全部分配。Ye等考慮到任務(wù)之間的耦合約束，通過(guò)引入插入位置可行性處理有沖突的任務(wù)規(guī)劃，并改進(jìn)了任務(wù)規(guī)劃策略，減少不必要的任務(wù)選擇計(jì)算。一些研究受到CBBA的啟發(fā)，其中性能影響(PI)算法是針對(duì)搜救場(chǎng)景開(kāi)發(fā)的，在解決時(shí)間約束問(wèn)題上有良好的表現(xiàn)。但是過(guò)快的迭代容易使算法陷入局部最優(yōu)。Whitbrook等改進(jìn)PI算法，提出了PI-softmax算法，極大提高了算法的任務(wù)完成度和任務(wù)獎(jiǎng)勵(lì)，但算法的收斂時(shí)間在規(guī)模較大的人物場(chǎng)景中是難以接受的。

針對(duì)大規(guī)模的任務(wù)場(chǎng)景，上述研究無(wú)法獲得很好的分配結(jié)果。Fu等將機(jī)器人分成若干個(gè)組，每組各自生成任務(wù)計(jì)劃，再由每個(gè)組的領(lǐng)頭機(jī)器人傳遞給其他組，用兩層共識(shí)規(guī)則將大規(guī)模問(wèn)題細(xì)分為一個(gè)個(gè)小規(guī)模問(wèn)題。Jang等利用博弈論方法，自組織地將機(jī)器人按照距離和任務(wù)喜好進(jìn)行任務(wù)分配，解決了大規(guī)模機(jī)器人的分配問(wèn)題。但是機(jī)器人之間的通信量依然沒(méi)有減少，且算法效率也比較低。

本文針對(duì)大規(guī)模任務(wù)分配問(wèn)題，在有時(shí)間窗的約束下，改進(jìn)CBBA算法，提出一種基于聚類分組的一致性的束算法(C-CBBA)，解決了大規(guī)模問(wèn)題的有限通信問(wèn)題，在減少通信量的前提下，提高算法效率，保持任務(wù)分配結(jié)果具有較高的任務(wù)完成度和全局任務(wù)獎(jiǎng)勵(lì)。

本文的主要貢獻(xiàn)為：

(1) 任務(wù)點(diǎn)和機(jī)器人的聚類分組

基于距離因素，用K-means算法對(duì)任務(wù)點(diǎn)進(jìn)行分組，然后利用延遲接受(DA)算法將機(jī)器人分配給各個(gè)分組，減少任務(wù)分配算法消耗的通信量，提高算法效率。

(2) 改進(jìn)任務(wù)序列包添加策略

建立未選擇任務(wù)包，將未被選擇的任務(wù)盡可能加入任務(wù)序列包中，提高任務(wù)完成度。

1 問(wèn)題描述

本文的MRTA問(wèn)題屬于單任務(wù)單機(jī)器人延時(shí)分配(ST-SR-TA)問(wèn)題，即每個(gè)任務(wù)只需要一個(gè)機(jī)器人完成，每個(gè)機(jī)器人一次只能完成一個(gè)任務(wù)。作戰(zhàn)場(chǎng)景如圖1所示，場(chǎng)景中有異構(gòu)的無(wú)人機(jī)和無(wú)人車(chē)，要求在時(shí)間窗的約束下，分別完成多個(gè)任務(wù)。任務(wù)類型分為探索、 打擊和評(píng)估毀傷目標(biāo)。針對(duì)本文研究的任務(wù)環(huán)境，做如下假設(shè)：

假設(shè)1 每個(gè)機(jī)器人在地圖中都是勻速移動(dòng)的，具有相同的態(tài)勢(shì)感知(SA)，且通信數(shù)據(jù)不會(huì)丟失。

假設(shè)2 地圖中沒(méi)有任何障礙物，機(jī)器人和任務(wù)之間的距離由歐氏距離或曼哈頓距離表示。

圖1 城市作戰(zhàn)場(chǎng)景示意圖

1.1 異構(gòu)機(jī)器人和任務(wù)的類型

假設(shè)系統(tǒng)一共有個(gè)異構(gòu)機(jī)器人和個(gè)不同類型的任務(wù)，機(jī)器人和任務(wù)集合分別為

={,,, …,, …,}

(1)

={,,, …,, …,}

(2)

本文考慮四種機(jī)器人： 固定翼無(wú)人機(jī)、 旋翼無(wú)人機(jī)、 小型偵察車(chē)和大型武裝車(chē)。其中固定翼無(wú)人機(jī)和大型武裝車(chē)只能執(zhí)行打擊和毀傷評(píng)估任務(wù)，旋翼無(wú)人機(jī)和小型偵察車(chē)只能執(zhí)行探索和毀傷評(píng)估任務(wù)。規(guī)定任務(wù)分組的組數(shù)為。

由于時(shí)間窗的約束，機(jī)器人執(zhí)行任務(wù)的起始時(shí)間必須在規(guī)定的時(shí)間窗以內(nèi)，滿足：

(3)

(4)

1.2 大規(guī)模MRTA問(wèn)題目標(biāo)函數(shù)

本文主要的目標(biāo)是保證算法效率和通信量足夠低的基礎(chǔ)上，最大化每個(gè)分組的任務(wù)完成度和全局任務(wù)獎(jiǎng)勵(lì)。其目標(biāo)函數(shù)可以表示為

(5)

(6)

(7)

其約束為

(8)

(9)

(10)

C-CBBA算法整體流程框架如圖2所示。

圖2 C-CBBA算法整體流程框架

2 任務(wù)點(diǎn)聚類分組

在三維空間中，既有高空任務(wù)，也有地面任務(wù)。受限于地面機(jī)器人無(wú)法執(zhí)行高空任務(wù)，為了保證分配給各組的機(jī)器人能夠完成任務(wù)，在任務(wù)分組階段，將高空任務(wù)和地面任務(wù)區(qū)分開(kāi)，單獨(dú)劃分出高空任務(wù)，其他地面任務(wù)再進(jìn)行分組。即其中一組為高空組，剩余的-1組為地面任務(wù)組。

2.1 聚類算法

聚類算法屬于無(wú)監(jiān)督學(xué)習(xí)，通過(guò)對(duì)任務(wù)點(diǎn)坐標(biāo)值的無(wú)標(biāo)記樣本訓(xùn)練，對(duì)任務(wù)點(diǎn)的分組進(jìn)行區(qū)分?？紤]到訓(xùn)練的目標(biāo)只有任務(wù)點(diǎn)的坐標(biāo)值，本文用K-means的方法對(duì)任務(wù)點(diǎn)進(jìn)行分組。

K-means和K-medoid是兩種最常見(jiàn)的聚類分組算法。K-medoid對(duì)噪聲魯棒性比較好，可以避免“噪聲”對(duì)聚類結(jié)果的影響，但計(jì)算速度較慢。K-means的計(jì)算效率更高，針對(duì)大樣本學(xué)習(xí)的情況，少數(shù)的“噪聲”任務(wù)點(diǎn)對(duì)整體聚類中心的影響不大。所以, K-means更適應(yīng)大規(guī)模任務(wù)點(diǎn)的聚類分組。

2.1.1 預(yù)定義聚類中心

針對(duì)聚類分組問(wèn)題，K-means算法需要事先預(yù)定聚類中心，通常隨機(jī)尋找個(gè)任務(wù)點(diǎn)作為初始聚類中心。但在分布式系統(tǒng)中會(huì)造成不一致的分組，需要預(yù)定統(tǒng)一的初始聚類中心。

首先，定義高空任務(wù)組的初始聚類中心，假設(shè)任務(wù)點(diǎn)的出現(xiàn)在三維空間中服從高斯分布，將地圖正中心點(diǎn)作為高空組的初始聚類中心，組別為=1，其坐標(biāo)向量可以表示為

(11)

式中：,,分別為地圖極限值。

然后，定義剩余的-1組地面任務(wù)組的初始聚類中心。假設(shè)地面組的初始全局中心為

(12)

如圖3所示，以地面中心為圓心，各分組聚類中心圍繞其圓心均勻分布。各分組聚類中心三個(gè)坐標(biāo)軸的坐標(biāo)值分別表示為

(13)

(14)

(15)

式中：=π/4。

圖3 地面分組聚類中心分布

2.1.2 K-means聚類

根據(jù)任務(wù)點(diǎn)坐標(biāo)的樣本集={,, …,}，以及初始定義的任務(wù)聚類組={,, …,}，K-means的目的為最小化每個(gè)任務(wù)距離所在聚類分組的平方誤差：

(16)

算法流程如圖4所示，分別計(jì)算每個(gè)任務(wù)點(diǎn)距離聚類中心的距離，將任務(wù)點(diǎn)加入到距離最近的分組。循壞迭代訪問(wèn)直到分組聚類中心不再更新為止。

2.2 任務(wù)點(diǎn)分組重規(guī)劃

K-means只是對(duì)任務(wù)分組的初步規(guī)劃，僅依靠任務(wù)點(diǎn)的距離關(guān)系進(jìn)行分組，沒(méi)有考慮到分配給各組的異構(gòu)機(jī)器人的數(shù)量是否滿足每個(gè)組的任務(wù)需求。本文提出了任務(wù)分組重規(guī)劃?rùn)C(jī)制，最小化每個(gè)組的機(jī)器人數(shù)量需求總和，使每個(gè)組的任務(wù)需求能夠滿足提供的機(jī)器人數(shù)量，增大任務(wù)完成度。

2.2.1 分組任務(wù)類型

在任務(wù)點(diǎn)初步分組之后，計(jì)算每個(gè)組中三種任務(wù)的數(shù)量，表示為分組需求矩陣：

(17)

式中：，，分別為探索、 打擊、 毀傷評(píng)估任務(wù)的數(shù)量。

算法1 任務(wù)點(diǎn)初始分組算法輸入: 任務(wù)坐標(biāo)點(diǎn)樣本集D、 聚類分組數(shù)K輸出: 任務(wù)點(diǎn)分組劃分S過(guò)程: (1)按式(11)～(15)計(jì)算每個(gè)組的初始聚類中心μ(2)while(3)初始化Ss=?(1≤s≤K)(4)for j=1, 2, …, NT do(5)計(jì)算任務(wù)j與各分組中心μs的距離: djs=dj-μs2(6)根據(jù)距離確定任務(wù)j的分組ξj=argmins∈{1, 2, …, K}djs(7)將任務(wù)j歸入相應(yīng)的分組: Sξj=Sξj∪{j}; (8)end for(9)for s=1, 2, …, K do(10)計(jì)算新的分組聚類中心μ′s=1Ss∑d∈Ssd; (11)if μ′s≠μs then(12)μi←μ′i(13)else(14)保持當(dāng)前分組聚類中心不變(15)end if(16)end for(17)until當(dāng)前分組聚類中心不再更新(18)end

2.2.2 機(jī)器人供應(yīng)數(shù)量問(wèn)題模型

(18)

目的是最小化機(jī)器人供應(yīng)數(shù)量，目標(biāo)函數(shù)為

(19)

其約束為

(20)

(21)

(22)

≤

(23)

(24)

(25)

式中：為每個(gè)機(jī)器人可執(zhí)行的最大任務(wù)數(shù)量；為旋翼無(wú)人機(jī)與小型偵察車(chē)數(shù)量之和；為固定翼無(wú)人機(jī)與大型武裝車(chē)數(shù)量之和。

當(dāng)機(jī)器人數(shù)量需求不滿足式(23)～(25)時(shí)，則需求數(shù)量超量，此時(shí)需要將某些分組的任務(wù)點(diǎn)調(diào)整到其他分組，降低機(jī)器人數(shù)量需求。建立每個(gè)分組可接受任務(wù)的余量矩陣：

(26)

任務(wù)點(diǎn)分組重規(guī)劃算法如圖5所示，先判斷機(jī)器人數(shù)量是否超量，然后確定超量機(jī)器人的類型，選擇任務(wù)余量空間最大的分組，將多余的任務(wù)分配到其他有余量的分組。

算法2 任務(wù)點(diǎn)分組重規(guī)劃輸入: 分組需求矩陣Ω、 機(jī)器人數(shù)量分布Φ、 余量矩陣Ψ、 任務(wù)聚類分組S輸出: 分組需求矩陣Ω?、 機(jī)器人數(shù)量分布Φ?、 余量矩陣Ψ?、 任務(wù)聚類分組S?過(guò)程: (1)if式(23)～(25)不成立 then(2)尋找需要調(diào)整的任務(wù)點(diǎn)分組s?=argmaxs∈{1, 2, …, K}ms(3)計(jì)算需要調(diào)整的任務(wù)點(diǎn)數(shù)量nad=LT-ms?(4)while(5)for j=1→Ss組對(duì)應(yīng)任務(wù)類型數(shù)量do(6)選擇距離最近的轉(zhuǎn)移分組ξj=argmins∈{1, 2, …, K}{s?}djs(7)if djs

循環(huán)迭代地執(zhí)行算法2，直到式(23)～(25)滿足約束條件為止，則可以保證每個(gè)組的任務(wù)理論上可以全部完成。

3 機(jī)器人分組調(diào)配

假設(shè)任務(wù)開(kāi)始時(shí)，所有機(jī)器人已經(jīng)分布在地圖上，按照距離最近的原則，將機(jī)器人分配到相應(yīng)的任務(wù)分組上。

3.1 機(jī)器人分組問(wèn)題模型

目的是最小化機(jī)器人到對(duì)應(yīng)的分組的距離之和，為了簡(jiǎn)化計(jì)算，以機(jī)器人和各分組聚類中心的距離作為機(jī)器人與各分組的距離，其目標(biāo)函數(shù)為

(27)

其約束為

(28)

(29)

式中：為機(jī)器人距離分組的距離；∈{0, 1}為機(jī)器人分配組別的決策變量；為分配給每個(gè)組的機(jī)器人總數(shù)。

3.2 延遲接受(DA)算法

將機(jī)器人分配到各任務(wù)分組的問(wèn)題建模為一對(duì)多類型的穩(wěn)定匹配問(wèn)題，匹配度由機(jī)器人到聚類分組中心的距離決定。

初始定義機(jī)器人分組表示為

={,, …,}

(30)

圖6為機(jī)器人分組算法，即延遲接受(DA)。首先每個(gè)機(jī)器人計(jì)算與聚類分組中心的距離，然后每個(gè)分組都系統(tǒng)性地從上到下遍歷機(jī)器人的最近距離分組，選擇距離自己最近的若干機(jī)器人，若機(jī)器人和另外的分組更匹配，則將該機(jī)器人讓給其他分組。經(jīng)過(guò)多輪迭代后得到一個(gè)穩(wěn)定的匹配結(jié)果。

算法3機(jī)器人分組算法輸入: 機(jī)器人集合R、 任務(wù)聚類分組S、 機(jī)器人數(shù)量分布Φ輸出: 機(jī)器人聚類分組A過(guò)程: (1) while(2)for i=1→NR do(3)ζi=argmins∈{1, 2, …, K}dis(4)將機(jī)器人i與分組ζi匹配(5)if分組機(jī)器人需求數(shù)沒(méi)滿 then(6)Aζi=Aζi∪{i}(7)else if分組機(jī)器人需求數(shù)已滿 then(8)分組Aζi刪除組內(nèi)距離最遠(yuǎn)的機(jī)器人k(9)Aζi=Aζi{k}, Aζi=Aζi∪{i}(10)end if(11)end for(12) until所有機(jī)器人都已分配到各聚類分組

4 分組任務(wù)分配

利用CBBA算法對(duì)每個(gè)機(jī)器人-任務(wù)分組進(jìn)行任務(wù)分配規(guī)劃，得到最終的任務(wù)規(guī)劃解。

4.1 基線CBBA

CBBA的主要工作是，首先利用貪婪選擇算法構(gòu)建任務(wù)序列包，然后使用共識(shí)規(guī)則建立任務(wù)沖突協(xié)商機(jī)制來(lái)解決機(jī)器人任務(wù)包之間的沖突。

4.1.1 任務(wù)包的建立

任務(wù)序列包的建立是在每個(gè)機(jī)器人內(nèi)部并行運(yùn)行的，然后通過(guò)投標(biāo)信息解決沖突。投標(biāo)信息主要包括：

(1)任務(wù)包∈(∪{?})，儲(chǔ)存了機(jī)器人選擇的任務(wù)。

(2)任務(wù)序列包∈(∪{?})，代表按執(zhí)行順序排列的任務(wù)集合。

(3)任務(wù)的中標(biāo)報(bào)價(jià)列表∈()，其中∈(=1, 2, …,)為執(zhí)行任務(wù)的最高報(bào)價(jià)，表示每個(gè)機(jī)器人內(nèi)部執(zhí)行該任務(wù)的獎(jiǎng)勵(lì)。在共識(shí)協(xié)商階段，每個(gè)機(jī)器人之間對(duì)任務(wù)進(jìn)行報(bào)價(jià)競(jìng)爭(zhēng)，更新當(dāng)前最高的任務(wù)獎(jiǎng)勵(lì)(最高報(bào)價(jià))。

(4)中標(biāo)機(jī)器人列表∈(∪{?})為對(duì)任務(wù)報(bào)價(jià)最高的機(jī)器人，表示在共識(shí)協(xié)商階段，機(jī)器人獲取任務(wù)的執(zhí)行權(quán)，將其序號(hào)儲(chǔ)存在中標(biāo)機(jī)器人列表中。

任務(wù)序列包構(gòu)建階段，機(jī)器人利用貪婪算法，每次將當(dāng)前獎(jiǎng)勵(lì)值最大的任務(wù)添加到包中，直到不能再繼續(xù)添加任務(wù)。每添加一個(gè)任務(wù)，除了將任務(wù)序號(hào)記錄在任務(wù)包和任務(wù)序列包中，還會(huì)在報(bào)價(jià)列表中記錄其任務(wù)獎(jiǎng)勵(lì)，作為對(duì)任務(wù)的競(jìng)標(biāo)報(bào)價(jià)，并在中標(biāo)機(jī)器人列表中記錄自己的機(jī)器人序號(hào)。

4.1.2 共識(shí)協(xié)商機(jī)制

在沖突協(xié)商階段，機(jī)器人利用共識(shí)協(xié)商策略調(diào)節(jié)任務(wù)沖突，即出價(jià)最高的機(jī)器人獲得任務(wù)的執(zhí)行權(quán)，其他落選機(jī)器人將包中的任務(wù)刪除，之后所有機(jī)器人更新中標(biāo)報(bào)價(jià)列表和中標(biāo)機(jī)器人列表，記錄當(dāng)前最高的報(bào)價(jià)(任務(wù)獎(jiǎng)勵(lì))和中標(biāo)機(jī)器人序號(hào)。共識(shí)規(guī)則如表1所示。列表和的更新操作可以表示為

(31)

式中： update為中標(biāo)報(bào)價(jià)和中標(biāo)機(jī)器人兩個(gè)列表進(jìn)行更新，保存當(dāng)前最高報(bào)價(jià)和提供報(bào)價(jià)的機(jī)器人序號(hào)。Reset為當(dāng)前任務(wù)進(jìn)行重置，刪除列表相關(guān)任務(wù)的數(shù)據(jù)。Leave為不做任何修改，保持列表原有報(bào)價(jià)不變。

顯然，將大規(guī)模機(jī)器人和任務(wù)進(jìn)行分組以后，每個(gè)機(jī)器人內(nèi)部可選擇的任務(wù)減少了，同時(shí)省略了不同分組機(jī)器人之間的多余通信，大大降低了算法中機(jī)器人的通信總量。

4.2 任務(wù)獎(jiǎng)勵(lì)函數(shù)

基線CBBA的任務(wù)獎(jiǎng)勵(lì)函數(shù)是嚴(yán)格基于邊際增益函數(shù)(DMG)計(jì)算的，當(dāng)任務(wù)執(zhí)行時(shí)間超過(guò)任務(wù)開(kāi)啟時(shí)間，獎(jiǎng)勵(lì)函數(shù)將趨于0，導(dǎo)致任務(wù)無(wú)法選擇。在計(jì)算任務(wù)點(diǎn)獎(jiǎng)勵(lì)時(shí)設(shè)置固定獎(jiǎng)勵(lì)，使得獎(jiǎng)勵(lì)永遠(yuǎn)大于成本代價(jià)，保證每個(gè)任務(wù)盡量被選擇。目標(biāo)獎(jiǎng)勵(lì)函數(shù)表示為

(32)

≥·

(33)

=

(34)

式中：和分別為機(jī)器人執(zhí)行任務(wù)的獎(jiǎng)勵(lì)和代價(jià)；為機(jī)器人到任務(wù)點(diǎn)的距離公式，根據(jù)機(jī)器人的異構(gòu)性，空中機(jī)器人采用三維歐氏距離，地面機(jī)器人采用二維曼哈頓距離；為距離代價(jià)常系數(shù)；為任務(wù)固定獎(jiǎng)勵(lì)；為及時(shí)完成任務(wù)的獎(jiǎng)勵(lì)。本文假設(shè)獎(jiǎng)勵(lì)函數(shù)是非負(fù)的，所以固定獎(jiǎng)勵(lì)不小于代價(jià)。

表1 機(jī)器人i與機(jī)器人k的共識(shí)協(xié)商規(guī)則

4.3 任務(wù)選擇優(yōu)化

基線CBBA中，機(jī)器人在每次迭代過(guò)程中選擇任務(wù)時(shí)，總是要從上到下依次遍歷所有任務(wù)，這樣會(huì)造成已經(jīng)競(jìng)價(jià)失敗的任務(wù)重新添加到包中，且容易忽略到后續(xù)被所有機(jī)器人都忽略的任務(wù)，使任務(wù)完成度較低。

算法4 任務(wù)序列包構(gòu)建算法輸入: 迭代次數(shù)t-1過(guò)程中的bi(t-1), Pi(t-1), yi(t-1), zi(t-1),ti(t-1)輸出: 迭代次數(shù)t過(guò)程中的bi(t), Pi(t), yi(t), zi(t), ti(t)過(guò)程: (1)bi(t)=bi(t-1), Pi(t)=Pi(t-1), yi(t)=yi(t-1), zi(t)=zi(t-1), ti(t)=ti(t-1)(2)構(gòu)建任務(wù)未選包bnoi: bnoi=T∩(P1∪P2∪…∪Pa)(3)whilebi(t)≤LT do(4)cij(Pi) = maxn≤PiViPin{ j}-ViPi(5)hij=Π(cij>yij)(6)Ji=argmaxj(cij(Pi)×hij)(7)ni, Ji=argmaxjVPi⊕n{j}i(8)ti, ni, Ji=max[ti, ni, Ji-1+(Vni, Jii-Vni, Ji-1i)/vi, t0, ni, Ji](9)bi=bi⊕end{Ji}, Pi=Pi⊕ni, Ji{Ji}(10)yi, Ji(t)=ci, Ji, zi, Ji(t)=i, ti, Ji(t)=ti, ni, Ji(11)end while

通過(guò)改進(jìn)的任務(wù)序列包構(gòu)建算法，在每次任務(wù)訪問(wèn)階段，都優(yōu)先搜索還沒(méi)有被選擇的任務(wù)，提高任務(wù)完成度的同時(shí)，也減少了無(wú)用任務(wù)訪問(wèn)的頻次，提高算法效率。通過(guò)任務(wù)序列包構(gòu)建和共識(shí)協(xié)商兩個(gè)階段的循環(huán)迭代，最終收斂到任務(wù)完成度最大的無(wú)沖突分配方案。

5 算法仿真實(shí)驗(yàn)

為了測(cè)試C-CBBA的性能，在Intel(R) Core(TM) i7-10700K CPU @ 3.80 GHz and 16 GB RAM的PC上，用MATLAB2019a進(jìn)行仿真。并和基線CBBA、 具有任務(wù)耦合約束的CBBA(TCC)進(jìn)行對(duì)比。

5.1 場(chǎng)景參數(shù)設(shè)置

在5 km×5 km×1 km的三維場(chǎng)景下，異構(gòu)機(jī)器人團(tuán)隊(duì)在總體時(shí)間窗[0, 5 000 s]內(nèi)完成任務(wù)的調(diào)度。機(jī)器人最大任務(wù)數(shù)量=15，任務(wù)固定獎(jiǎng)勵(lì)=30，任務(wù)完成獎(jiǎng)勵(lì)=100，任務(wù)價(jià)值隨時(shí)間衰減因子=0.1。實(shí)驗(yàn)中，模擬了五種機(jī)器人-任務(wù)點(diǎn)規(guī)模，分別為10-100，30-300，50-500，80-800，100-1 000，任務(wù)和機(jī)器人分組組數(shù)=5。每種規(guī)模分別進(jìn)行了100次蒙特卡洛隨機(jī)模擬，每次模擬時(shí)算法的迭代次數(shù)最多為100次，當(dāng)任務(wù)規(guī)劃迭代次數(shù)超過(guò)100，算法將強(qiáng)制停止，輸出當(dāng)前的最優(yōu)解。此外，為了顯示預(yù)設(shè)分組組數(shù)對(duì)任務(wù)分配結(jié)果的影響，對(duì)30-300規(guī)模的分配問(wèn)題，分別模擬了分組組數(shù)為3, 4, 5, 6四種情況下的實(shí)驗(yàn)。

5.2 算法結(jié)果展示

為了清晰地展示機(jī)器人的任務(wù)路線圖，選擇展示在10-100規(guī)模下=5時(shí)的某一次實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)中最小的規(guī)模為10-100，其任務(wù)執(zhí)行路線圖比較清楚，且在=5的情況下，任務(wù)分組的結(jié)果比較稀疏，有利于最終結(jié)果的觀察。相關(guān)信息如表2～3所示。

表2 機(jī)器人相關(guān)信息

表3 任務(wù)目標(biāo)相關(guān)信息

圖8為任務(wù)分配路線圖，為了便于觀察，忽略了高度，只顯示二維平面的路線軌跡。表4為機(jī)器人分配方案，即機(jī)器人執(zhí)行任務(wù)順序。

其中，算法收斂時(shí)間0.311 s，任務(wù)完成度100%，通信量(通信頻次)150次，全局任務(wù)獎(jiǎng)勵(lì)4 083.396。

5.3 不同規(guī)模的算法性能對(duì)比

不同規(guī)模下機(jī)器人及任務(wù)的類型數(shù)量分布采用相同的比例構(gòu)成，任務(wù)分組組數(shù)都為=5。表5為機(jī)器人和任務(wù)的類型數(shù)量分布情況與編號(hào)對(duì)應(yīng)的類型，四種機(jī)器人的類型比例分布為0.3∶0.2∶0.3∶0.2，三種任務(wù)的類型數(shù)量比例分布為0.33∶0.33∶0.34。

通過(guò)算法在五種不同規(guī)模下的仿真，總體性能由算法收斂時(shí)間、 通信量(通信頻次)、 任務(wù)完成度、 全局任務(wù)獎(jiǎng)勵(lì)、 任務(wù)平均花費(fèi)時(shí)間五個(gè)方面體現(xiàn)。

其中算法收斂時(shí)間的計(jì)算從系統(tǒng)開(kāi)始分組到最終輸出任務(wù)分配結(jié)果結(jié)束，運(yùn)行時(shí)間依賴于實(shí)驗(yàn)PC條件。多機(jī)器人之間的通信量依賴于系統(tǒng)通信模型、 機(jī)器人通信方式、 機(jī)器人拓?fù)溥B接方式、 通信損耗等多方面的因素，研究簡(jiǎn)化了其通信量的計(jì)算，用機(jī)器人之間的通信頻次(沖突解調(diào)階段機(jī)器人之間的通信次數(shù))作為通信量的計(jì)算依據(jù)，兩個(gè)機(jī)器人之間的一次沖突解調(diào)為1個(gè)通信頻次。每一次任務(wù)包構(gòu)建和沖突解調(diào)的迭代為一輪通訊，一輪通訊中的通信頻次依賴于拓?fù)溥B接形式，本文按照全連接的形式進(jìn)行通信，故一輪通訊的通信頻次為(-1)2，為每個(gè)分組的機(jī)器人數(shù)量。

表6～10分別表示不同規(guī)模下，五個(gè)性能指標(biāo)的仿真實(shí)驗(yàn)結(jié)果對(duì)比。可見(jiàn)在算法收斂時(shí)間、 通信量、 任務(wù)完成度方面，C-CBBA的性能是最優(yōu)的，可以解決大規(guī)模任務(wù)分配問(wèn)題的最大化算法效率和最小化通信量問(wèn)題，并能保證大部分任務(wù)被機(jī)器人選中并執(zhí)行。

圖8 各聚類分組的機(jī)器人任務(wù)路線圖

(1) 算法收斂時(shí)間和通信量方面，預(yù)先對(duì)任務(wù)和機(jī)器人進(jìn)行了分組，每個(gè)分組的規(guī)模都變小了，任務(wù)分配算法需要計(jì)算訪問(wèn)的對(duì)象縮減，提高了收斂的效率，同時(shí)也減少了機(jī)器人之間通信的總量，每個(gè)機(jī)器人只需要和自己組內(nèi)的機(jī)器人進(jìn)行通信。

(2) 任務(wù)完成度方面，在每次任務(wù)規(guī)劃階段，重點(diǎn)考慮了全局未被選擇的任務(wù)，所以C-CBBA可以規(guī)劃出接近100%的任務(wù)完成度，而基線CBBA和TCC需要頻繁地刪除任務(wù)重新規(guī)劃。三種算法的任務(wù)獎(jiǎng)勵(lì)都是按照邊際效益遞減的規(guī)律進(jìn)行計(jì)算的，為了貼合實(shí)際任務(wù)執(zhí)行時(shí)，開(kāi)始時(shí)間越晚，收益越低的情況，引入了邊際效益遞減因子。因此，算法對(duì)時(shí)間的增加比較敏感，CBBA算法的任務(wù)獎(jiǎng)勵(lì)會(huì)隨著時(shí)間的增加快速降低，沒(méi)有任務(wù)固定獎(jiǎng)勵(lì)，收益將小于0，導(dǎo)致任務(wù)無(wú)法選擇。而TCC雖然也引入了固定獎(jiǎng)勵(lì)，但是算法執(zhí)行時(shí)依然要頻繁地刪除任務(wù)，也會(huì)導(dǎo)致任務(wù)完成度不高。C-CBBA算法在引入固定獎(jiǎng)勵(lì)的基礎(chǔ)上，還加入了未選任務(wù)優(yōu)先訪問(wèn)機(jī)制，盡量將全局未選擇的任務(wù)加入任務(wù)序列包中。

表4 不同規(guī)模下機(jī)器人及任務(wù)的類型數(shù)量分布

表5 機(jī)器人任務(wù)分配方案

表6 三種算法的收斂時(shí)間

表7 三種算法的通信量(通信頻次)

表8 三種算法的任務(wù)完成度

表9 三種算法的全局任務(wù)獎(jiǎng)勵(lì)

表10 三種算法的任務(wù)平均用時(shí)

(3) 全局任務(wù)獎(jiǎng)勵(lì)和平均任務(wù)花費(fèi)時(shí)間方面，由于聚類分組本身會(huì)縮小分配解集，可能會(huì)將最優(yōu)的解排除，所以C-CBBA的總獎(jiǎng)勵(lì)并不是最高的，說(shuō)明分配策略的獎(jiǎng)勵(lì)不是最高的。其原因?yàn)镃-CBBA的任務(wù)完成度高，機(jī)器人需要執(zhí)行的任務(wù)多，任務(wù)平均花費(fèi)時(shí)間相應(yīng)增加，在時(shí)間窗約束下，部分任務(wù)的執(zhí)行時(shí)間無(wú)法在任務(wù)開(kāi)啟時(shí)立刻執(zhí)行，導(dǎo)致任務(wù)獎(jiǎng)勵(lì)不能達(dá)到理論最大值。

5.4 不同分組規(guī)模的仿真

不同的分組組數(shù)對(duì)算法也有影響，對(duì)30-300規(guī)模的機(jī)器人-任務(wù)組進(jìn)行仿真，分別將其劃分為3, 4, 5, 6組。

不同組數(shù)的算法性能如表11所示。在不同分組組數(shù)下，隨著組數(shù)的增加，算法收斂時(shí)間和通信量明顯降低，任務(wù)完成度和全局任務(wù)獎(jiǎng)勵(lì)變小。這是因?yàn)榉纸M越細(xì)，默認(rèn)忽略的分配解集越多，增加算法收斂速度，降低了解的質(zhì)量。所以在不同場(chǎng)合，應(yīng)該根據(jù)不同的需求進(jìn)行取舍。

表11 不同組數(shù)的算法性能

結(jié)合前兩種仿真情況，C-CBBA在收斂時(shí)間、 通信量、 任務(wù)完成度方面具有優(yōu)勢(shì)，算法的設(shè)定條件是任務(wù)的位置和類型預(yù)先已知，機(jī)器人提前布置在任務(wù)環(huán)境中，且機(jī)器人和任務(wù)的類型數(shù)量是提前設(shè)定好的，這意味著在任務(wù)分配前的機(jī)器人分組調(diào)配必須是有解的，否則將造成算法失效。本文適用于具有時(shí)間窗約束的大型任務(wù)場(chǎng)景下的大規(guī)模任務(wù)分配問(wèn)題中，最大化任務(wù)完成度及最小化的收斂時(shí)間的情況。表6顯示，從規(guī)模80-800開(kāi)始，算法收斂時(shí)間超過(guò)了60 s，針對(duì)超大規(guī)模的任務(wù)分配問(wèn)題，C-CBBA算法只能適用于靜態(tài)任務(wù)，不再適用于動(dòng)態(tài)任務(wù)。針對(duì)規(guī)模小于50-100的問(wèn)題，C-CBBA算法具有較好的適應(yīng)能力。

6 結(jié) 論

本文針對(duì)具有時(shí)間窗約束的大規(guī)模MRTA問(wèn)題，提出了基于聚類分組的一致性的束算法(C-CBBA)，解決算法效率和降低通信量的問(wèn)題。首先利用K-means算法對(duì)任務(wù)點(diǎn)按照距離分組，并用任務(wù)點(diǎn)重規(guī)劃?rùn)C(jī)制最小化所需機(jī)器人資源，然后用DA算法將機(jī)器人分配到各聚類分組，最后改進(jìn)CBBA算法，求解劃分好的若干小規(guī)模問(wèn)題。仿真實(shí)驗(yàn)結(jié)果表明，該算法能夠在較短的時(shí)間內(nèi)，用較少的通信量達(dá)到可接受的任務(wù)完成度和全局任務(wù)獎(jiǎng)勵(lì)。但是在性能檢驗(yàn)方面，通信量受系統(tǒng)通信模型、 機(jī)器人拓?fù)溥B接方式等多種因素影響，本文對(duì)通信量的計(jì)算比較理想化，未來(lái)研究還應(yīng)考慮實(shí)際情況，對(duì)通信進(jìn)一步細(xì)化研究。而且聚類分組可能會(huì)忽略全局最優(yōu)解，在更大范圍內(nèi)，機(jī)器人并不能獲得所有其他機(jī)器人的信息。未來(lái)將考慮機(jī)器人之間的具體通信模型，并改進(jìn)任務(wù)和機(jī)器人分組機(jī)制，在最小化資源需求的基礎(chǔ)上，最大化全局任務(wù)獎(jiǎng)勵(lì)。