基于迭代尋優(yōu)策略合同網(wǎng)協(xié)議的任務(wù)分配算法

姚亞寧,楊風(fēng)暴,吉琳娜,呂紅亮,白永強(qiáng)

(中北大學(xué)信息與通信工程學(xué)院,山西 太原 030051)

“體系韌性”是未來(lái)高動(dòng)態(tài)強(qiáng)對(duì)抗戰(zhàn)場(chǎng)態(tài)勢(shì)環(huán)境下完成使命的主要保證?，F(xiàn)代戰(zhàn)爭(zhēng)場(chǎng)景復(fù)雜多變,戰(zhàn)術(shù)行動(dòng)形式多樣,但共同的特點(diǎn)是反應(yīng)敏捷,決策靈活。當(dāng)作戰(zhàn)體系中作戰(zhàn)單元被摧毀或作戰(zhàn)單元間通信鏈路中斷時(shí),需要快速對(duì)任務(wù)處理流程進(jìn)行重構(gòu),提升極端情況下的任務(wù)保障能力,實(shí)現(xiàn)彈性可伸縮的保障服務(wù)。完備的集中式指揮作戰(zhàn)體系由多個(gè)異構(gòu)的作戰(zhàn)節(jié)點(diǎn)和指揮中心構(gòu)成,因此，作戰(zhàn)體系的重構(gòu)問題可轉(zhuǎn)化為多智能體系統(tǒng)(Multi-Agent System,MAS)滿足快速性條件下的任務(wù)分配問題。

作戰(zhàn)體系重構(gòu)的核心是在有限的時(shí)間內(nèi)實(shí)現(xiàn)合理的任務(wù)遷移和分配,合同網(wǎng)協(xié)議作為一種研究多智能體間任務(wù)分配的算法,其收斂性和求解質(zhì)量已被廣泛認(rèn)同[1]。張?？2]等根據(jù)參考閾值響應(yīng)模型引入信任度參數(shù),提出了動(dòng)態(tài)合同網(wǎng)協(xié)議,在招標(biāo)過程階段直接向信任度高的智能體進(jìn)行投標(biāo),減輕了系統(tǒng)通信壓力,提升了其處理大規(guī)模任務(wù)集的綜合性能。在此基礎(chǔ)上,李明[3]等提出了再招標(biāo)的策略,使信任度高但重載的智能體能將標(biāo)書再次分發(fā),避免因拒標(biāo)而導(dǎo)致信任度降低的情況,使其下次投標(biāo)不受影響。姜繼嬌[4]等通過限制智能體接收標(biāo)書的數(shù)目、提出任務(wù)優(yōu)先度優(yōu)化任務(wù)分配模型,縮短協(xié)商過程的通信次數(shù)。楊影[5]等以無(wú)人戰(zhàn)斗機(jī)為研究對(duì)象,將復(fù)雜自適應(yīng)系統(tǒng)理論與合同網(wǎng)協(xié)議結(jié)合,構(gòu)造損失函數(shù)和約束條件，建立了合作任務(wù)分配模型,通過求解一個(gè)非線性規(guī)劃問題得到任務(wù)分配方案,仿真結(jié)果表明該算法可以實(shí)現(xiàn)全局優(yōu)化。

上述研究重點(diǎn)多集中于改善算法中的決策過程,未考慮決策依據(jù)的真實(shí)性對(duì)決策結(jié)果的影響,即忽略了協(xié)作過程中智能體之間存在的欺騙行為。多智能體協(xié)作過程中,自身利益必然是一個(gè)理性智能體的重要目標(biāo)[6]。全局利益和自身利益沖突時(shí),智能體可能做出欺騙舉動(dòng)來(lái)最大化自身利益。針對(duì)這個(gè)問題,本文以經(jīng)典合同網(wǎng)協(xié)議為研究基礎(chǔ),提出一種迭代尋優(yōu)策略,強(qiáng)迫智能體的投標(biāo)信息在迭代過程中逼近真實(shí)數(shù)據(jù),所有智能體連續(xù)兩次投標(biāo)信息完全一致后算法收斂,得到欺騙行為下的最優(yōu)任務(wù)分配方案。

1 合同網(wǎng)協(xié)議框架

經(jīng)典合同網(wǎng)協(xié)議由Reid G.Smith[7]于1980年提出的,是一種適用于多智能體間任務(wù)分配的算法。算法中拍賣雙方智能體分為投標(biāo)者和管理者,協(xié)商過程模擬交易流程,其流程可分為如下四個(gè)階段。

1)招標(biāo):管理者初始化標(biāo)書,以廣播的形式向各投標(biāo)者發(fā)送招標(biāo)信息;

2)投標(biāo):投標(biāo)者接收標(biāo)書后根據(jù)自身情況投標(biāo)或拒標(biāo);

3)評(píng)估:管理者根據(jù)投標(biāo)信息選出最佳投標(biāo)者,向其發(fā)送中標(biāo)訊息,并拒絕其他投標(biāo)者標(biāo)書;

4)通告:管理者廣播合同簽訂情況。

合同網(wǎng)協(xié)議流程可用UML順序圖描述如圖1。

圖1 合同網(wǎng)協(xié)議UML時(shí)序圖

2 基于迭代尋優(yōu)策略合同網(wǎng)協(xié)議的任務(wù)分配算法

2.1 任務(wù)描述

經(jīng)典合同網(wǎng)協(xié)議中,中標(biāo)的是單一的個(gè)體,導(dǎo)致中標(biāo)的智能體承擔(dān)龐雜的任務(wù)造成過載情況。假設(shè)待遷移任務(wù)滿足文獻(xiàn)[8]中部分任務(wù)分解原則,即待分解任務(wù)本身具有可分解的多層抽象結(jié)構(gòu);分解之后的子任務(wù)應(yīng)盡可能保持獨(dú)立。基于任務(wù)分解的策略,將復(fù)雜的任務(wù)分解為多個(gè)具有高并行度的子任務(wù),將其分發(fā)到多個(gè)智能體,使體系中負(fù)載更加均衡。

本文使用二元組描述任務(wù),其中T表示完成此任務(wù)需要的能力,L表示此任務(wù)帶來(lái)的負(fù)載。

任務(wù)需求向量T定義為式(1),Tq表示智能體承擔(dān)第q個(gè)子任務(wù)需要的能力大小,值越大，代表此任務(wù)需求越高。

(1)

任務(wù)帶來(lái)的負(fù)載向量L定義為

(2)

式中，Lq表示承擔(dān)第q個(gè)子任務(wù)會(huì)帶來(lái)的負(fù)載,值越大代表帶來(lái)負(fù)載越重。

2.2 智能體描述

(3)

(4)

智能體信任度向量α定義為式(5),αi表示指揮中心對(duì)Ai的信任度,表征Ai過去完成任務(wù)的情況。信任度越高,表示智能體過去完成任務(wù)情況越好。

(5)

任務(wù)完成后,根據(jù)完成情況根據(jù)式(6)更新信任度。

(6)

式中，αaward和αpenalty分別為獎(jiǎng)懲因子,都為常數(shù),通常滿足αaward?αpenalty。

2.3 智能體欺騙行為描述

Alision R.Panission[9]等將智能體的欺騙行為分為三類:撒謊、廢話、詭計(jì)。撒謊是智能體對(duì)某事的虛假陳述,目的是使其他智能體得到與事實(shí)相反的結(jié)論。廢話是指智能體通信過程中通過釋放大量冗余數(shù)據(jù),使其他智能體無(wú)法得到需要的有效信息。詭計(jì)是一個(gè)更復(fù)雜的過程,通過誘導(dǎo)其他智能體利用先驗(yàn)知識(shí)和推理能力自發(fā)得出某些錯(cuò)誤結(jié)論,實(shí)現(xiàn)其更深層次的陰謀。

本文研究的重點(diǎn)是智能體的撒謊行為。在集中式作戰(zhàn)體系中,某智能體在執(zhí)行作戰(zhàn)任務(wù)時(shí)被敵摧毀,偵察單元檢查其負(fù)載的任務(wù)信息后上傳到指揮中心。在各智能體數(shù)據(jù)未知的情況下,指揮中心通過與體系中其他智能體通信得到各項(xiàng)數(shù)據(jù),在一定時(shí)間內(nèi)將此任務(wù)遷移到匹配度最高的智能體，但承擔(dān)任務(wù)意味著自身負(fù)載加重,智能體可能在通信過程中通過撒謊行為弱化自身,逃避任務(wù)。合同網(wǎng)協(xié)議下，具體的撒謊行為描述為:指揮中心將任務(wù)需求信息廣播,若智能體自身狀態(tài)能夠承擔(dān)任務(wù),不會(huì)拒標(biāo)(所有智能體拒標(biāo),任務(wù)處理流程將無(wú)法完成重構(gòu),體系面臨崩潰的危險(xiǎn))。收到指揮中心的招標(biāo)信息后,智能體以高于任務(wù)需求、低于自身能力之間的虛假數(shù)據(jù)投標(biāo),期望降低被選中的概率,指揮中心根據(jù)虛假數(shù)據(jù)選出的最優(yōu)智能體可能與實(shí)際情況不符。本文假定欺騙行為的投標(biāo)公式如下:

(7)

2.4 作戰(zhàn)聯(lián)盟組建

假定體系中智能體數(shù)目為N。指揮中心收到偵察單元的消息后,首先對(duì)將任務(wù)進(jìn)行分解。然后以子任務(wù)需求作為招標(biāo)信息向體系中所有智能體進(jìn)行初次招標(biāo),篩選出能夠承擔(dān)子任務(wù)的n個(gè)智能體,組建作戰(zhàn)聯(lián)盟,為后續(xù)子任務(wù)分配奠定基礎(chǔ)。智能體收到招標(biāo)信息后,判斷自身能力和負(fù)載狀況,若滿足式(8)條件,則向指揮中心投標(biāo),否則拒標(biāo)。

(8)

上式意義為，智能體投標(biāo)的條件是任一子任務(wù)下智能體對(duì)應(yīng)的能力值不能低于任務(wù)需求,且承擔(dān)任務(wù)后自身不會(huì)超載。

2.5 評(píng)價(jià)函數(shù)

指揮中心收到投標(biāo)后,通過式(9)對(duì)智能體進(jìn)行評(píng)價(jià)。

(9)

2.6 迭代尋優(yōu)策略

在作戰(zhàn)聯(lián)盟組建完畢的基礎(chǔ)上,迭代尋優(yōu)策略表述為:指揮中心以智能體Ai投標(biāo)信息中的能力值作為任務(wù)需求的招標(biāo)信息,再次向其招標(biāo)。當(dāng)指揮中心再次招標(biāo)時(shí),由于存在全體拒標(biāo)導(dǎo)致任務(wù)無(wú)法遷移的危險(xiǎn),智能體無(wú)法拒標(biāo),投標(biāo)信息更新為高于此次招標(biāo)數(shù)據(jù)低于真實(shí)數(shù)據(jù)的信息。隨迭代進(jìn)行,指揮中心得到的信息逐漸逼近智能體真實(shí)數(shù)據(jù),直到某次指揮中心得到智能體真實(shí)信息。通過對(duì)比連續(xù)兩次所有智能體投標(biāo)信息,判定算法收斂(收斂標(biāo)識(shí)con_var=1),通過式(9)計(jì)算出每個(gè)子任務(wù)對(duì)應(yīng)智能體綜合評(píng)價(jià)值,排序后得到最符合當(dāng)前任務(wù)的智能體,據(jù)此生成全局最優(yōu)的任務(wù)分配方案。算法收斂標(biāo)識(shí)con_var計(jì)算公式由式(10)給出。

(10)

算法UML時(shí)序圖如圖2所示。

圖2 基于改進(jìn)合同網(wǎng)協(xié)議的任務(wù)分配算法UML時(shí)序圖

3 算例分析

假定某作戰(zhàn)體系由指揮中心和十一個(gè)智能體構(gòu)成。作戰(zhàn)過程中某智能體被摧毀,指揮中心需在一定時(shí)間內(nèi)對(duì)任務(wù)遷移分配,將體系中原有任務(wù)流程重構(gòu)。為簡(jiǎn)化分析,考慮智能體的欺騙行為為謊報(bào)能力的情況。基于Netlogo對(duì)體系建模,其包含元素如圖3所示。

圖3 作戰(zhàn)體系元素示意圖

圖3中飛機(jī)區(qū)域?yàn)橹笓]中心,黃色三角為被摧毀智能體,藍(lán)色三角為體系中正常運(yùn)作的智能體,黑色三角為偵察單元。表1數(shù)據(jù)為體系中智能體的真實(shí)能力值,行表示不同的智能體,列表示每個(gè)智能體不同類型的能力。表2數(shù)據(jù)為各智能體與能力對(duì)應(yīng)的五種不同類型的真實(shí)負(fù)載狀況,行表示不同的智能體,列表示每個(gè)智能體不同類型的負(fù)載狀況。由兩表數(shù)據(jù)可知,A1-A9為藍(lán)色智能體,A10為體系中的偵察單元,不接受任務(wù)的遷移。

表1 智能體真實(shí)能力值表

表2 智能體真實(shí)負(fù)載表

基于FIPA-ACL(Foundation For Intelli-gent Physical Agents-Agent Communacation Language)通信語(yǔ)言描述智能體間通信流程,算法的仿真過程如圖4。圖4中左半部分為體系模型:白色三角表示被摧毀的智能體,由黃色變?yōu)榘咨硎救蝿?wù)分配方案產(chǎn)生;粉色三角表示最優(yōu)分配方案生成后即將承擔(dān)任務(wù)的智能體;黑色三角依然為偵察單元。圖中右側(cè)監(jiān)視窗口為各子任務(wù)迭代尋優(yōu)的過程,air1_best到air_5best圖中曲線表示由式(9)得到的對(duì)應(yīng)子任務(wù)T1到T5的最優(yōu)智能體評(píng)價(jià)值的迭代過程(初始化αi=0.5,λ1=λ2=0.5);con_var圖中的曲線表示迭代過程收斂標(biāo)識(shí),曲線值為1代表前后兩次迭代各子任務(wù)最優(yōu)智能體信息一致,算法收斂,尋得全局最優(yōu)解。

圖4 Netlogo仿真過程

查詢通信信息將通信數(shù)據(jù)繪制成折線圖。圖5中,最優(yōu)智能體的評(píng)價(jià)值逐漸增大后穩(wěn)定,表示有智能體隱藏了真實(shí)能力,但隨迭代過程的進(jìn)行,其投標(biāo)信息逐漸逼近真實(shí)信息,最后以真實(shí)信息進(jìn)行投標(biāo)。第五次迭代、第六次迭代和真實(shí)信息重合,表示第五次迭代后已經(jīng)得到了符合實(shí)際情況的最優(yōu)任務(wù)分配方案。圖6為智能體A1的投標(biāo)信息中能力值的變化,各項(xiàng)投標(biāo)能力值隨迭代進(jìn)行逐漸上升,第五次迭代后,投標(biāo)信息不再變化,與真實(shí)能力值相符。

圖5 子任務(wù)迭代尋優(yōu)

圖6 A1投標(biāo)能力迭代

最優(yōu)的任務(wù)分配方案在迭代過程不斷更新。變化過程如圖7所示。

圖7 分配方案迭代過程

第一次智能體投標(biāo)后,指揮中心依據(jù)收到的信息計(jì)算各智能體綜合評(píng)價(jià)值,產(chǎn)生的分配方案為A9承擔(dān)子任務(wù)T1,A6承擔(dān)子任務(wù)T2和子任務(wù)T3,A1承擔(dān)子任務(wù)T4,A5承擔(dān)子任務(wù)T5,此時(shí)為欺騙行為下經(jīng)典合同網(wǎng)協(xié)議生成的分配方案。五次迭代后,算法尋得符合實(shí)際情況的最優(yōu)解,最終分配方案為A2、A6、A6、A5、A1依次承擔(dān)五個(gè)子任務(wù)。

4 結(jié)束語(yǔ)

本文以戰(zhàn)場(chǎng)態(tài)勢(shì)重構(gòu)中任務(wù)分配問題為研究背景,對(duì)多智能體協(xié)作過程中的欺騙行為進(jìn)行了分析,以經(jīng)典合同網(wǎng)協(xié)議為基礎(chǔ)提出了一種欺騙行為下的任務(wù)分配算法。所提算法能在有限的迭代次數(shù)內(nèi)收斂,得到與真實(shí)情況一致的全局最優(yōu)分配方案。不足之處在于本文沒有考慮更復(fù)雜的欺騙行為,下一步工作將從此處開展。