復(fù)雜約束條件下異構(gòu)多智能體聯(lián)盟任務(wù)分配

唐嘉鈺,李相民,代進(jìn)進(jìn),薄 寧

(1.海軍航空大學(xué)岸防兵學(xué)院,山東煙臺(tái) 264001;2.中國(guó)人民解放軍91213部隊(duì),山東煙臺(tái) 264001)

1 引言

多智能體協(xié)同任務(wù)分配是實(shí)現(xiàn)多智能體協(xié)同控制的基礎(chǔ),其求解方法分為集中式和分布式[1–2].

依據(jù)文獻(xiàn)[3]提出的分類法,多智能體協(xié)同任務(wù)分配問(wèn)題等同于交叉調(diào)度的單任務(wù)多機(jī)器人時(shí)間擴(kuò)展任務(wù)分配問(wèn)題(cross-schedule dependent single task multi-robot time-extended task allocation,XDSTMRTA),其中交叉調(diào)度是指智能體是否執(zhí)行某個(gè)任務(wù)受其他智能體任務(wù)執(zhí)行情況影響;單任務(wù)是指智能體一次只能執(zhí)行一個(gè)任務(wù);時(shí)間擴(kuò)展則是指智能體在執(zhí)行任務(wù)之前預(yù)先進(jìn)行任務(wù)規(guī)劃.對(duì)XDSTMRTA問(wèn)題的研究中,文獻(xiàn)[2]采用集中式混合整數(shù)線性規(guī)劃算法(mixed-integer linear programming,MILP)解決了搜救任務(wù)中小組任務(wù)分配問(wèn)題.文獻(xiàn)[4]在MILP算法基礎(chǔ)上進(jìn)一步考慮了任務(wù)之間的時(shí)序關(guān)系、起始時(shí)間的同步需求及智能體等待懲罰等約束條件,對(duì)單任務(wù)多機(jī)器人時(shí)間擴(kuò)展任務(wù)分配問(wèn)題進(jìn)行了研究.在集中式框架中,中心節(jié)點(diǎn)計(jì)算獲得最優(yōu)解,并通過(guò)有效通信方式將最優(yōu)解發(fā)送給智能體.與分布式框架相比,集中式分配框架存在中央節(jié)點(diǎn)負(fù)荷大、系統(tǒng)魯棒性差等缺點(diǎn)[5].在對(duì)抗環(huán)境中,敵方可能會(huì)將目標(biāo)鎖定在中心節(jié)點(diǎn),分布式算法可以為中心節(jié)點(diǎn)或通信基礎(chǔ)設(shè)施失效引起的單點(diǎn)故障提供穩(wěn)健性.

基于市場(chǎng)的分布式求解方法已廣泛應(yīng)用于多機(jī)器人協(xié)同任務(wù)分配問(wèn)題.分布式求解框架中,為避免各智能體自主分配結(jié)果出現(xiàn)沖突,多智能體系統(tǒng)需要在態(tài)勢(shì)感知和(或)任務(wù)規(guī)劃上達(dá)成一致[6].文獻(xiàn)[7–9]將分布式競(jìng)標(biāo)與集中式拍賣相結(jié)合提出了基于拍賣的多無(wú)人機(jī)任務(wù)分配方法,通過(guò)一定的一致性協(xié)商機(jī)制對(duì)多無(wú)人機(jī)的競(jìng)標(biāo)進(jìn)行沖突消解,從而確定獲勝無(wú)人機(jī).

為了削弱拍賣者中心節(jié)點(diǎn)作用,提高分布式多智能體系統(tǒng)魯棒性,Choi H L等人提出了基于一致性的拍賣算法(consensus based auction algorithm,CBAA)解決分布式智能體系統(tǒng)中單任務(wù)分配問(wèn)題[10],試驗(yàn)表明該算法減輕了數(shù)據(jù)通信負(fù)擔(dān).CBAA算法解決了每個(gè)任務(wù)需要一個(gè)智能體完成的單一任務(wù)分配問(wèn)題.實(shí)際上,一個(gè)智能體可以執(zhí)行位置相近的多個(gè)任務(wù).因此,Choi H L等人將CBAA算法擴(kuò)展為一致性包算法(consensus based bundle algorithm,CBBA).CBBA算法中,各智能體將任務(wù)序列排列組合,并選擇效益最大的任務(wù)組合作為任務(wù)包(bundle).隨著相鄰智能體不斷構(gòu)建更有價(jià)值的任務(wù)包,各智能體不斷刪減或修正自身任務(wù)包.CBBA算法采取與CBAA算法相同的協(xié)商機(jī)制以獲得無(wú)沖突任務(wù)分配方案[10].

文獻(xiàn)[11]結(jié)合具體無(wú)人機(jī)應(yīng)用場(chǎng)景,將無(wú)人機(jī)動(dòng)力學(xué)約束及任務(wù)間獨(dú)立性約束與CBBA算法相結(jié)合,提出了耦合約束條件下一致性包算法(coupled-constraint CBBA).文獻(xiàn)[12]證明了CBBA算法可收斂到納什均衡(Nash equilibrium)但非帕累托最優(yōu)(Pareto optimal)解,同時(shí)指出CBBA 算法可為單機(jī)器人單任務(wù)分配問(wèn)題[2](single-robot single task task allocation,SRSTTA)提供次優(yōu)解決方案.當(dāng)CBBA算法非負(fù)評(píng)分機(jī)制滿足邊際增益遞減(diminishing marginal gain,DMG)的收斂特性時(shí),CBBA算法相對(duì)于最優(yōu)目標(biāo)值可達(dá)到至少50%的最優(yōu)性[13].同時(shí),由于CBBA中投標(biāo)算法運(yùn)行時(shí)間為多項(xiàng)式時(shí)間,當(dāng)智能體和任務(wù)數(shù)量增多時(shí),CBBA算法的可擴(kuò)展性保證了其在實(shí)時(shí)動(dòng)態(tài)環(huán)境下的適用性[13].

綜合國(guó)內(nèi)外研究現(xiàn)狀可知，目前分布式多智能體任務(wù)分配研究主要有以下不足:

1)目前研究方法主要針對(duì)單任務(wù)單智能體場(chǎng)景,但在實(shí)際中單個(gè)復(fù)雜任務(wù)需要多智能體合作完成,例如多無(wú)人機(jī)協(xié)同搜索攻擊等作戰(zhàn)應(yīng)用中,對(duì)單個(gè)目標(biāo)的打擊任務(wù)需要偵察型和攻擊型無(wú)人機(jī)協(xié)同完成;

2)現(xiàn)有分布式多智能體協(xié)同任務(wù)分配研究中,各任務(wù)之間相互獨(dú)立,未考慮任務(wù)之間耦合約束關(guān)系.

基于國(guó)內(nèi)外研究現(xiàn)狀,本文針對(duì)任務(wù)載荷資源約束、任務(wù)耦合關(guān)系約束及執(zhí)行窗口約束等條件下的異構(gòu)多智能體聯(lián)盟任務(wù)分配問(wèn)題,對(duì)分布式一致性包理論進(jìn)行擴(kuò)展,提出了一致性聯(lián)盟算法.首先,各智能體綜合考慮任務(wù)時(shí)變收益、行程代價(jià)損耗,依據(jù)邊際效益最大的原則選擇有效任務(wù)構(gòu)造自身任務(wù)包;其次,基于改進(jìn)協(xié)調(diào)原則實(shí)現(xiàn)異構(gòu)多智能體聯(lián)盟任務(wù)分配決策的沖突調(diào)解;最后通過(guò)仿真試驗(yàn)驗(yàn)證了該方法的可行性.

2 多智能體聯(lián)盟任務(wù)分配問(wèn)題描述

其中T為子任務(wù)時(shí)序間隔矩陣.

以多無(wú)人機(jī)智能體協(xié)同執(zhí)行偵察攻擊型任務(wù)為例,子任務(wù)主要可分為偵察子任務(wù)和攻擊子任務(wù),對(duì)應(yīng)子任務(wù)關(guān)系矩陣為

對(duì)應(yīng)的時(shí)序間隔矩陣為

矩陣D和T的行(/列)元素按順序分別表示偵察子任務(wù)和攻擊子任務(wù),?tmin為執(zhí)行攻擊子任務(wù)前完成偵察子任務(wù)所需的最短時(shí)間.

3 一致性聯(lián)盟算法

CBBA算法主要考慮單個(gè)任務(wù)由一個(gè)智能體執(zhí)行的應(yīng)用場(chǎng)景,在需要多智能體協(xié)同執(zhí)行復(fù)雜任務(wù)的場(chǎng)景下具有局限性.本節(jié)在CBBA算法基礎(chǔ)上提出了一致性聯(lián)盟算法(consensus based coalition algorithm,CBCA),旨在解決異構(gòu)多智能體協(xié)同執(zhí)行復(fù)雜任務(wù)時(shí)聯(lián)盟分組問(wèn)題.CBCA算法分為兩階段:智能體任務(wù)包構(gòu)建和基于一致性的沖突消解.

3.1 算法關(guān)鍵要素

在CBCA算法中,首先明確定義智能體i任務(wù)分配信息的關(guān)鍵要素:

1)執(zhí)行路徑列表pi.

2)任務(wù)包bi.

3)獲勝智能體矩陣Zi.

Zi為Na×NT維矩陣,其元素=1表示智能體i認(rèn)為智能體k是任務(wù)j的投標(biāo)獲勝者;否則=0.Zi中第j列非零元素?cái)?shù)量之和Sumj=代表了智能體i認(rèn)為執(zhí)行任務(wù)j的智能體總數(shù).

4)獲勝投標(biāo)值矩陣Y i.

Y i存儲(chǔ)智能體i視角下各項(xiàng)任務(wù)聯(lián)盟成員的投標(biāo)值,矩陣中各元素與Zi一一對(duì)應(yīng).當(dāng)智能體i認(rèn)為任務(wù)j沒(méi)有獲勝者時(shí),yij=0.

5)時(shí)間戳列表si.

3.2 任務(wù)包構(gòu)建

在任務(wù)包構(gòu)建過(guò)程中,各智能體迭代選擇任務(wù)添加到自身任務(wù)包中.每個(gè)智能體以最大化自身任務(wù)收益增量為選擇原則.設(shè)智能體i初始任務(wù)包為bi,i選擇收益邊際增益最大的任務(wù)j?∈J加入到bi中.任務(wù)選擇過(guò)程持續(xù)到任務(wù)包已滿或無(wú)可選任務(wù).但智能體只對(duì)滿足時(shí)序約束和載荷資源約束的有效任務(wù)進(jìn)行投標(biāo).

智能體i任務(wù)分配總收益為

式中rij(pi)為任務(wù)執(zhí)行收益.考慮任務(wù)動(dòng)態(tài)時(shí)效性,采用時(shí)間折扣收益來(lái)計(jì)算,即

式中:dij為智能體i與任務(wù)j之間的直線距離,γ為行程代價(jià)系數(shù).

依據(jù)新任務(wù)j′加入bi前后的收益,可獲得j′的邊際增益為

式中:n表示j′在pi中所有可能位置;|pi|為列表長(zhǎng)度;pi⊕n{j′}表示將j′插入到路徑列表pi中第n位,原路徑列表中第n位及其以后的元素保持原順序不變,依次后移.

在多智能體聯(lián)盟任務(wù)分配中,考慮到單項(xiàng)復(fù)雜任務(wù)需要多智能體協(xié)同完成,因此CBBA算法中單純比較邊際增益與當(dāng)前任務(wù)獲勝投標(biāo)值的方法并不適用.

當(dāng)numj=1時(shí),任務(wù)j為單智能體執(zhí)行型,投標(biāo)過(guò)程與CBBA算法相同.當(dāng)numj>1時(shí),任務(wù)j需要多智能體組成聯(lián)盟協(xié)同完成,此時(shí)任務(wù)j可分為兩種情況:1)競(jìng)標(biāo)執(zhí)行任務(wù)j的智能體數(shù)量已滿足聯(lián)盟智能體數(shù)量需求,即Sumj=numj,此時(shí)任務(wù)j分配滿荷;2)分配執(zhí)行任務(wù)j的智能體數(shù)量未滿足數(shù)量需求,即Sumj

任務(wù)j分配已滿荷時(shí),智能體將自身邊際增益與當(dāng)前任務(wù)最小獲勝投標(biāo)值作比較,當(dāng)

時(shí),智能體i可以投標(biāo)(hij=1),并將最小獲勝投標(biāo)值替換為自身投標(biāo)值;否則,智能體i放棄任務(wù)j.當(dāng)智能體i投標(biāo)值與最小獲勝投標(biāo)值相同時(shí),選擇身份標(biāo)識(shí)小的智能體.

智能體不斷構(gòu)造自身任務(wù)包直至任務(wù)包已滿或沒(méi)有滿足約束條件的有效任務(wù).具體CBCA任務(wù)包構(gòu)造算法如算法1所示.

算法1CBCA算法任務(wù)包構(gòu)造階段.

3.3 基于一致性的沖突消解

任務(wù)包構(gòu)建過(guò)程結(jié)束后,為獲得無(wú)沖突任務(wù)分配結(jié)果,智能體需要與相鄰智能體共享獲勝智能體矩陣、獲勝投標(biāo)矩陣和時(shí)間戳列表等信息,并按照一定的行動(dòng)規(guī)則更新相應(yīng)信息以獲得無(wú)沖突任務(wù)分配.本文假設(shè)在一致性協(xié)商階段,各智能體之間采用同步通信機(jī)制,關(guān)于異步通信機(jī)制下多智能體任務(wù)分配研究詳見(jiàn)文獻(xiàn)[16].

在沖突消解階段,智能體利用時(shí)間戳列表si來(lái)確定接收到的最新信息.每當(dāng)智能體i接收到來(lái)自相鄰智能體k的信息時(shí),對(duì)該信息標(biāo)記如下時(shí)間戳:

式中:gik=1表示智能體i與智能體k之間存在通信鏈接,否則gik=0,特別地,gii=1;τr為智能體i接受到信息的時(shí)刻.具體沖突消解過(guò)程如算法2所示.

算法2CBCA算法沖突消解階段.

當(dāng)numj=1時(shí),智能體采用CBBA第2階段的沖突消解方式(算法2中第4–6行).numj >1時(shí),CBCA沖突消解(算法2中第7–26行)可分為兩部分:首先接收者i將自身獲勝投標(biāo)信息與發(fā)送者k的獲勝投標(biāo)信息進(jìn)行比較(算法2中第7–11行),skm >sim表明發(fā)送者k信息更新,通過(guò)第1階段與發(fā)送者k信息對(duì)比后,接收者i可確認(rèn)自身存儲(chǔ)信息是當(dāng)前最新的;隨后依據(jù)對(duì)比結(jié)果,智能體i對(duì)自身信息進(jìn)行調(diào)整(算法2 中第12–26行),當(dāng)發(fā)送者k認(rèn)為智能體m()執(zhí)行任務(wù)j,且接收者i認(rèn)為m不執(zhí)行任務(wù)j時(shí)(算法2 中13–14行),接收者i需要判斷是否有足夠智能體執(zhí)行任務(wù)j(算法2中第15行),若接收者i認(rèn)為分配給任務(wù)j的智能體數(shù)量未滿足任務(wù)需求,則進(jìn)行更新(算法2中第16–17行).由于在任務(wù)包構(gòu)造過(guò)程中智能體只對(duì)符合約束條件的任務(wù)進(jìn)行投標(biāo),因此當(dāng)i將聯(lián)盟內(nèi)成員替換時(shí),新成員與舊成員之間均符合任務(wù)載荷資源需求.表明任務(wù)j有多余分配空間,并且當(dāng)時(shí),任務(wù)j需要攜帶載荷資源agem的智能體m;若任務(wù)j分配已滿荷,則需要判斷現(xiàn)有聯(lián)盟內(nèi)成員的投標(biāo)值是否小于m的投標(biāo)值(算法2中第19行),且二者有重疊載荷資源類型,即

成立時(shí),將當(dāng)前任務(wù)聯(lián)盟內(nèi)投標(biāo)值較低的智能體替換為智能體m.為避免造成死鎖,當(dāng)投標(biāo)值相同時(shí),選擇標(biāo)識(shí)較小的智能體.

3.4 算法收斂性

文獻(xiàn)[10]中已證明CBBA分配策略收斂至集中式順序貪婪算法(sequential greedy algorithm,SGA).為滿足單個(gè)任務(wù)多智能體執(zhí)行的任務(wù)需求,本文提出了改進(jìn)順序貪婪算法(improved sequential greedy algorithm,ISGA),如算法3 所示,其中

算法3改進(jìn)順序貪婪算法.

輸入:智能體集I,任務(wù)集J.

輸出:智能體i ∈I的任務(wù)包bi.

由參考文獻(xiàn)[10]可知,采用分布式一致協(xié)商算法完成網(wǎng)絡(luò)直徑為D的分布式多智能體系統(tǒng)任務(wù)分配,且每個(gè)智能體采用DMG評(píng)分機(jī)制,當(dāng)沖突消解階段迭代次數(shù)為t時(shí),有

定理1當(dāng)靜態(tài)網(wǎng)絡(luò)半徑為D的多智能體系統(tǒng)采用同步通信機(jī)制,且各智能體采用DMG評(píng)分機(jī)制時(shí),CBCA算法收斂于ISGA算法,即

證依據(jù)結(jié)論5)和引理1,?nNmin,沖突消解階段經(jīng)過(guò)nD輪通信后,所有智能體都認(rèn)同ISGA中前n項(xiàng)解.由結(jié)論3)可知,這些解在后續(xù)迭代中不會(huì)發(fā)生改變.因此經(jīng)過(guò)NminD輪迭代后,CBCA算法收斂于ISGA算法.證畢.

4 仿真結(jié)果及分析

以多架偵察型無(wú)人機(jī)(unmanned search aerial vehicle,USAV)和攻擊型無(wú)人機(jī)(unmanned combat aerial vehicle,UCAV)依次執(zhí)行偵察與攻擊任務(wù)為例,對(duì)文中提出的CBCA算法進(jìn)行仿真驗(yàn)證,算例1對(duì)CBCA算法的可行性進(jìn)行驗(yàn)證,算例2對(duì)CBCA算法和CBBA算法進(jìn)行比較,算例3將分布式CBCA算法與分布式合同網(wǎng)協(xié)議算法進(jìn)行比較.

設(shè)定多無(wú)人機(jī)之間為全連通通信網(wǎng)絡(luò).仿真實(shí)驗(yàn)均在Intel(R)Core(TM)i7–2630QM CPU 2.00 GHz 計(jì)算機(jī)上運(yùn)行.

4.1 CBCA算法仿真結(jié)果分析

算例1中共有5架無(wú)人機(jī)對(duì)9個(gè)目標(biāo)進(jìn)行攻擊,任務(wù)空間范圍設(shè)定為5 km×5 km×2 km,仿真中無(wú)人機(jī)和目標(biāo)初始狀態(tài)信息如表1和表2所示.目標(biāo)依據(jù)所需執(zhí)行任務(wù)共分為3類:偵察類目標(biāo)(需2架USAV)、攻擊類目標(biāo)(需2架UCAV)及偵察攻擊類目標(biāo)(需2架USAV和1架UCAV).?tmin=10 min.

表1 無(wú)人機(jī)參數(shù)設(shè)定Table 1 Initial settings of UAVs

各UAV 分配的任務(wù)路徑如表3 所示,任務(wù)時(shí)序如圖1所示.對(duì)察打型目標(biāo)Task1,首先UAV1和UAV3進(jìn)行偵察,偵察任務(wù)結(jié)束后UAV5執(zhí)行攻擊任務(wù);對(duì)察打型目標(biāo)Task5,同樣首先UAV1和UAV3進(jìn)行偵察,偵察任務(wù)結(jié)束后UAV5 執(zhí)行攻擊任務(wù);此外均有兩架USAV執(zhí)行純偵察類任務(wù);兩架UCAV執(zhí)行純攻擊類任務(wù).此時(shí)算法收益值為1805.01.

表2 任務(wù)空間參數(shù)設(shè)定Table 2 Initial settings of tasks

表3 聯(lián)盟任務(wù)分配結(jié)果Table 3 Assignment results of CBCA

圖1 異構(gòu)多無(wú)人機(jī)聯(lián)盟任務(wù)路徑Fig.1 Path lists of heterogeneous multiple UAVs

仿真結(jié)果表明CBCA算法可解決考慮載荷資源約束、子任務(wù)耦合關(guān)系及時(shí)間窗約束下的異構(gòu)多智能體聯(lián)盟任務(wù)分配問(wèn)題.

4.2 多智能體任務(wù)分配性能對(duì)比

為了進(jìn)一步比較CBCA算法對(duì)多智能體聯(lián)盟任務(wù)分配場(chǎng)景的適用性,算例2設(shè)定1至10架UCAV對(duì)20個(gè)地面目標(biāo)進(jìn)行攻擊,任務(wù)靜態(tài)收益均為100,時(shí)間折扣因子為0,?tmin=0.具體分為以下3種場(chǎng)景:

1)每個(gè)目標(biāo)只需1架UCAV(CBBA);

2)每個(gè)目標(biāo)需要2架UCAV(CBCA);

3)10 個(gè)目標(biāo)需要1 架UCAV,10 個(gè)目標(biāo)需要2 架UCAV(Hybrid).

UCAV參數(shù)設(shè)定同算例1,任務(wù)空間參數(shù)設(shè)定一致,分別記錄了3種場(chǎng)景中算法總收益值、一致協(xié)商通信次數(shù)(所有UAV完成雙向通信記為一次)和算法運(yùn)行時(shí)間,對(duì)比結(jié)果如圖2–4所示.

圖2 算法總收益值對(duì)比結(jié)果Fig.2 Comparison of total score

圖3 一致協(xié)商通信次數(shù)對(duì)比結(jié)果Fig.3 Comparison of consensus communication steps

圖4 算法運(yùn)行時(shí)間對(duì)比結(jié)果Fig.4 Comparison of computational run time

由圖2對(duì)比結(jié)果可知,隨著UAV數(shù)量不斷增加,各場(chǎng)景對(duì)應(yīng)的算法收益值不斷增加;但當(dāng)UAV數(shù)量增加到一定程度時(shí),由于任務(wù)數(shù)量有限,智能體數(shù)量過(guò)飽和導(dǎo)致隨著UAV數(shù)量增加,CBBA算法收益值保持不變.由圖3和圖4可以看出,CBCA算法平均運(yùn)行時(shí)間更長(zhǎng),為獲得一致無(wú)沖突分配結(jié)果所進(jìn)行的協(xié)商次數(shù)更多.造成這一結(jié)果的原因是聯(lián)盟任務(wù)分配復(fù)雜度更高.

4.3 算法性能評(píng)估

為了進(jìn)一步評(píng)估CBCA算法質(zhì)量,將CBCA算法與基于合同網(wǎng)協(xié)議(contract net protocol,CNP)的分布式任務(wù)分配算法[17]進(jìn)行比較,分別記錄算法平均總收益值和平均運(yùn)行時(shí)間,從而對(duì)CBCA算法性能進(jìn)行評(píng)估.

算例3中5架無(wú)人機(jī)對(duì)9個(gè)目標(biāo)進(jìn)行攻擊,隨機(jī)產(chǎn)生無(wú)人機(jī)和目標(biāo)的初始位置,任務(wù)空間范圍設(shè)定為5 km×5 km×2 km,任務(wù)靜態(tài)收益均為100,時(shí)間折扣因子為0,?tmin=10 min.設(shè)定蒙特卡洛仿真次數(shù)為50次.對(duì)比結(jié)果如圖5和圖6所示.

圖5 CNP算法與CBCA算法平均收益值對(duì)比Fig.5 Comparison of average total score based on CNP algorithm and CBCA

圖6 CNP算法與CBCA算法平均任務(wù)完成時(shí)間對(duì)比Fig.6 Comparison of average mission time based on CNP algorithm and CBCA

算例3中CBCA算法平均收益值為1641.32,平均任務(wù)完成時(shí)間為101.3 min;合同網(wǎng)算法平均收益值為1701.803,平均任務(wù)完成時(shí)間為136.5 min.仿真結(jié)果表明,CNP 算法任務(wù)分配收益值略高于CBCA 算法,但CBCA算法平均任務(wù)完成時(shí)間明顯縮短,更符合快速高效的打擊任務(wù)需求.造成這一結(jié)果的主要原因在于:1)CNP算法中拍賣智能體作為管理者,接收滿足資源需求的競(jìng)拍智能體標(biāo)書,依據(jù)全局最大效能原則構(gòu)造聯(lián)盟,而基于貪婪策略的分布式CBCA算法中每個(gè)智能體并不掌握周圍相鄰智能體的信息,以個(gè)體邊際效益最大為投標(biāo)原則,因而導(dǎo)致CBCA算法收益值相對(duì)較低;2)CNP算法中拍賣智能體需向通信范圍內(nèi)的智能體發(fā)送目標(biāo)位置信息和所需資源信息作為合同,收到合同的智能體根據(jù)合同判斷是否有能力執(zhí)行該任務(wù).若具備該目標(biāo)所需資源,則成為競(jìng)拍智能體并向拍賣智能體投遞包括預(yù)期路徑長(zhǎng)度和所攜資源等信息的標(biāo)書.拍賣智能體根據(jù)收到的標(biāo)書決定聯(lián)盟成員,并發(fā)送中標(biāo)和落標(biāo)信息.智能體間的廣播招標(biāo)與投標(biāo)導(dǎo)致CNP算法通信量較大,任務(wù)分配效率降低,而CBCA算法中各智能體僅需廣播自身任務(wù)分配信息,算法通信量較小,適用于實(shí)時(shí)動(dòng)態(tài)的戰(zhàn)場(chǎng)環(huán)境.

進(jìn)一步地,采用基于蒙特卡洛多次試驗(yàn)結(jié)果的算法評(píng)估準(zhǔn)則對(duì)算法整體優(yōu)劣性進(jìn)行評(píng)估[1],即

式中:Nm為蒙特卡洛試驗(yàn)次數(shù);Qi為算法單次試驗(yàn)分?jǐn)?shù);Q為算法總試驗(yàn)分?jǐn)?shù);α和β分別為算法規(guī)劃結(jié)果最優(yōu)性和規(guī)劃快速性權(quán)重系數(shù);Rmax為蒙特卡洛試驗(yàn)中最大收益值;R(i)為第i次試驗(yàn)任務(wù)分配收益值;tmin為蒙特卡洛試驗(yàn)中算法最短運(yùn)行時(shí)間;t(i)為第i次試驗(yàn)算法運(yùn)行時(shí)間.設(shè)定Nm=50,并分別設(shè)置3種權(quán)重系數(shù)組合:

1)α=0.6,β=0.4;

2)α=0.5,β=0.5;

3)α=0.4,β=0.6.

算法評(píng)估結(jié)果如圖7所示.

圖7 CNP算法與CBCA算法性能對(duì)比結(jié)果Fig.7 Performance comparison of CNP Algorithm and CBCA

由上述結(jié)果可知,CBCA算法總體性能優(yōu)于CNP算法,當(dāng)算法規(guī)劃快速性權(quán)重由0.4增至0.6時(shí),CBCA算法相對(duì)于CNP算法得分差值由?0.135增加至2.82;當(dāng)算法快速性權(quán)重與結(jié)果最優(yōu)性權(quán)重相同時(shí),CBCA算法相對(duì)于CNP算法得分差值為1.592.因此,在保證求解質(zhì)量的前提下,CBCA算法與CNP算法相比實(shí)時(shí)性較強(qiáng).

5 結(jié)論

針對(duì)復(fù)雜任務(wù)需要攜帶不同載荷資源的異構(gòu)多智能體協(xié)同完成且任務(wù)之間存在耦合關(guān)系的問(wèn)題,對(duì)一致性包算法的數(shù)據(jù)結(jié)構(gòu)和沖突消解規(guī)則進(jìn)行了改進(jìn),提出了一致性聯(lián)盟算法.仿真結(jié)果表明該方法可有效解決考慮任務(wù)窗口約束、任務(wù)時(shí)序約束及任務(wù)載荷資源需求等條件下的異構(gòu)多智能體聯(lián)盟任務(wù)分配問(wèn)題;在保證求解質(zhì)量的同時(shí)算法實(shí)時(shí)性較強(qiáng).一致性聯(lián)盟算法在動(dòng)態(tài)不確定任務(wù)環(huán)境下的應(yīng)用將是下一步研究的內(nèi)容.