基于勢(shì)博弈的異構(gòu)多智能體系統(tǒng)任務(wù)分配和重分配

鞠鍇 冒澤慧 姜斌 馬亞杰

近年來(lái),多智能體系統(tǒng)在一致性安全控制、健康管理、編隊(duì)跟蹤等多個(gè)領(lǐng)域得到廣泛應(yīng)用[1?3].得益于智能體之間的分工與合作,多智能體系統(tǒng)在執(zhí)行大規(guī)模任務(wù)時(shí)可以提供比單個(gè)智能體更好的性能.通過(guò)采用任務(wù)分配算法,將具有不同要求的任務(wù)分配給最合適的異構(gòu)智能體,多智能體系統(tǒng)可以在能耗、任務(wù)效用等方面獲得最佳的整體性能.因此,任務(wù)分配問(wèn)題在多智能體系統(tǒng)的研究中引起了更多關(guān)注[4?6].

日益復(fù)雜的任務(wù)需求對(duì)任務(wù)分配問(wèn)題提出新的挑戰(zhàn).一方面,需要多種資源的任務(wù)通常無(wú)法由缺乏足夠配置的單個(gè)智能體處理,因此這些任務(wù)各自需要多個(gè)智能體協(xié)同執(zhí)行.在任務(wù)分配問(wèn)題的標(biāo)準(zhǔn)分類法中[7],這類任務(wù)稱為MR (Multi-robot)任務(wù),且對(duì)任務(wù)分配算法提出智能體間合作的要求.另一方面,任務(wù)價(jià)值的動(dòng)態(tài)變化和任務(wù)執(zhí)行時(shí)間限制等所施加的多重約束,使得任務(wù)分配問(wèn)題的求解更加困難.MR 需求和多重約束將大大擴(kuò)展可選分配方案的數(shù)量,因此算法需要在解質(zhì)量和計(jì)算時(shí)間之間找到平衡.此外,任務(wù)數(shù)量變化或智能體故障等突發(fā)情況對(duì)算法的實(shí)時(shí)性能提出考驗(yàn).面對(duì)這一系列難點(diǎn),傳統(tǒng)的任務(wù)分配算法,如蟻群算法[8]、粒子群算法[9]等不再適合復(fù)雜約束下的重規(guī)劃環(huán)境,特別受限于在大規(guī)模可行解空間內(nèi)尋優(yōu)難度幾何倍數(shù)遞增的問(wèn)題.因此,設(shè)計(jì)多重約束下更為實(shí)時(shí)、高效的任務(wù)分配算法具有重要意義.

針對(duì)MR 任務(wù)分配問(wèn)題,現(xiàn)有的一類編隊(duì)聯(lián)盟方法注重于任務(wù)的拆分、智能體聯(lián)盟的形成和將任務(wù)分配給合適的聯(lián)盟[10?12].在這些工作中,聯(lián)盟根據(jù)任務(wù)需求的拆分而形成,但是若任務(wù)之間的耦合足夠強(qiáng),拆分將無(wú)法進(jìn)行.通過(guò)設(shè)計(jì)按序分配任務(wù)的策略,基于市場(chǎng)的算法[13?15]可以用來(lái)分配MR 任務(wù).不幸的是,決定分配順序的過(guò)程通常取決于智能體對(duì)任務(wù)的效用,而這一值同樣來(lái)源于對(duì)任務(wù)的拆分.近年來(lái),博弈方法為智能體之間的合作與協(xié)商提供了良好的性能,因此廣泛應(yīng)用于優(yōu)化問(wèn)題[16?18].作為博弈方法的一種,勢(shì)博弈的特征為具有能夠?qū)⒅悄荏w策略的變化同等地反映在系統(tǒng)整體性能上的勢(shì)函數(shù)[19?21],這一特征為各智能體自主決策是否參與合作提供了便利.受到這一啟發(fā),本文致力于通過(guò)智能體間的通信協(xié)商,從整體的角度來(lái)分配強(qiáng)耦合的MR 任務(wù),從而能夠避免編隊(duì)聯(lián)盟方法與市場(chǎng)算法需要拆分任務(wù)的缺陷.因此,如何設(shè)計(jì)智能體博弈機(jī)制成為算法的重點(diǎn)和難點(diǎn).

在執(zhí)行之前將每項(xiàng)已知任務(wù)分配給合適智能體的過(guò)程稱為初始分配,之后智能體根據(jù)分配結(jié)果執(zhí)行任務(wù).任務(wù)需求的增加和工作環(huán)境的惡化,使得智能體在執(zhí)行任務(wù)過(guò)程中更容易出現(xiàn)故障.本文僅考慮永久故障,即故障智能體無(wú)法自恢復(fù),從而無(wú)法再執(zhí)行其剩余任務(wù),導(dǎo)致這些任務(wù)需要重新分配.在任務(wù)分配問(wèn)題中,任務(wù)需及時(shí)執(zhí)行以避免其效用嚴(yán)重下降,因此實(shí)時(shí)的容錯(cuò)能力對(duì)于任務(wù)重分配算法至關(guān)重要.Xu等[22]提出一種具有容錯(cuò)能力的動(dòng)態(tài)資源供應(yīng)方法,用以恢復(fù)云計(jì)算工作流的失敗任務(wù).Paul等[23]通過(guò)采用改進(jìn)的容錯(cuò)調(diào)度算法來(lái)減輕永久處理器故障對(duì)實(shí)時(shí)應(yīng)用程序的影響.

智能體故障可以通過(guò)硬件和軟件方法解決.硬件方法使用額外智能體替換故障智能體以供后續(xù)任務(wù)執(zhí)行,但在智能體數(shù)量或資源有限的情況下不可行.軟件方法使被故障終止的任務(wù)在健康智能體上恢復(fù)執(zhí)行,這一思想類似于在初始分配的基礎(chǔ)上處理任務(wù)數(shù)量的動(dòng)態(tài)變化,如Das等[24]通過(guò)并行分配和執(zhí)行來(lái)處理新任務(wù)或智能體的加入.由于方案調(diào)整的靈活性,拍賣方法在動(dòng)態(tài)環(huán)境中得到全面研究[25].然而,這些工作并沒(méi)有在任務(wù)分配問(wèn)題模型中嵌入智能體故障.為此,一些學(xué)者為多處理器系統(tǒng)解決了容錯(cuò)策略分配問(wèn)題,使得失敗的任務(wù)被遷移到不同的處理器上恢復(fù)執(zhí)行[26?27].這些工作考慮了智能體故障并以盡可能提高系統(tǒng)可靠性作為主要目標(biāo),但它們?nèi)狈?duì)任務(wù)執(zhí)行質(zhì)量的實(shí)質(zhì)性關(guān)注.

本文提出一種將具有多重約束的任務(wù)最優(yōu)地分配給異構(gòu)多智能體系統(tǒng),并且具有快速有效地處理突發(fā)智能體故障能力的新算法.勢(shì)博弈思想貫穿于算法的整體設(shè)計(jì),主要貢獻(xiàn)總結(jié)如下.

1) 建立考慮多重約束和智能體故障率的MR任務(wù)分配問(wèn)題模型.建立基于勢(shì)博弈的框架,其中智能體是完全分布式的,且能獨(dú)立地作出影響全局任務(wù)效用的決策.

2) 基于勢(shì)博弈為無(wú)故障環(huán)境設(shè)計(jì)初始分配算法,之后將其推廣到針對(duì)永久智能體故障的任務(wù)重分配算法.智能體策略總是迭代地向納什均衡移動(dòng),且在納什均衡處獲得近似全局最優(yōu)分配.

3) 構(gòu)建與本文建立的任務(wù)分配問(wèn)題模型符合程度高的現(xiàn)實(shí)場(chǎng)景,并通過(guò)仿真結(jié)果驗(yàn)證所提出算法的有效性.

本文的剩余部分安排如下: 在第1 節(jié)中,給出問(wèn)題描述和優(yōu)化目標(biāo);在第2 節(jié)中,設(shè)計(jì)基于勢(shì)博弈的算法以完成無(wú)故障情況下所有已知任務(wù)的整體最優(yōu)分配,稱為初始分配;并在第3 節(jié)中將其推廣為重分配算法來(lái)處理任務(wù)執(zhí)行過(guò)程中的永久性智能體故障;在第4 節(jié)中,給出仿真結(jié)果來(lái)分析所提出算法的有效性;最后在第5 節(jié)中給出結(jié)論.

1 問(wèn)題描述

考慮最優(yōu)地將m項(xiàng)任務(wù)分配給n個(gè)異構(gòu)智能體的任務(wù)分配問(wèn)題.每個(gè)智能體在某一時(shí)刻至多參與一項(xiàng)任務(wù)的執(zhí)行,且每項(xiàng)任務(wù)需要由多個(gè)智能體同時(shí)執(zhí)行.智能體集合編號(hào)為A={A1,A2,···,An},任務(wù)集合編號(hào)為T={T1,T2,···,Tm}.任務(wù)之間相互獨(dú)立,且執(zhí)行任務(wù)Tj所需要的智能體數(shù)量定義為Nj,滿足 1≤Nj ≤n,j=1,2,···,m.忽略執(zhí)行任務(wù)所消耗的時(shí)間,即一旦所有Nj個(gè)參與執(zhí)行的智能體均到達(dá)任務(wù)Tj,則認(rèn)為該任務(wù)已完成.智能體之間在類型、資源等方面都可以是異構(gòu)的,表現(xiàn)為若執(zhí)行同一任務(wù)Tj則將提供不同的性能,且可以通過(guò)為各智能體Ai,i=1,2,···,n定義一個(gè)經(jīng)歸一化后值在0 到1 之間的變量λij,i=1,2,···,n,j=1,2,···,m來(lái)量化.任務(wù)Tj更可能由λij更大的智能體執(zhí)行,若λij等于0,則表示智能體Ai無(wú)法執(zhí)行任務(wù)Tj.智能體在執(zhí)行任務(wù)過(guò)程中可能遭受不可恢復(fù)的永久故障,且一旦發(fā)生,故障智能體無(wú)法再執(zhí)行后續(xù)任務(wù),從而產(chǎn)生任務(wù)的重分配需求.每項(xiàng)任務(wù)Tj都有一個(gè)效用函數(shù)uj,j=1,2,···,m,與任務(wù)分配方案、各智能體對(duì)該任務(wù)的貢獻(xiàn)、任務(wù)執(zhí)行時(shí)間等多種因素有關(guān).下面將分別量化這些因素對(duì)任務(wù)效用的影響,并建立任務(wù)分配問(wèn)題模型.

基于每項(xiàng)任務(wù)需要多個(gè)智能體合作執(zhí)行的需求,模型進(jìn)一步引入同步性約束,用來(lái)描述單個(gè)智能體的努力不足以啟動(dòng)單項(xiàng)任務(wù)的情況.在此約束下,僅當(dāng)所有參與執(zhí)行任務(wù)的智能體均到達(dá)時(shí),任務(wù)才視為完成.因此,任務(wù)的開始執(zhí)行時(shí)間由所有參與執(zhí)行的智能體中最晚的到達(dá)時(shí)間主導(dǎo),即

其中,tj為任務(wù)Tj的開始執(zhí)行時(shí)間;tij為智能體Ai到達(dá)任務(wù)Tj的時(shí)間;χij定義為二進(jìn)制決策變量,若智能體Ai參與執(zhí)行任務(wù)Tj,則χij設(shè)為1,否則設(shè)為0.鑒于此,智能體之間需要合作與協(xié)商,以關(guān)于任務(wù)執(zhí)行時(shí)間達(dá)成共識(shí).

因而,任務(wù)效用uj來(lái)源于所有參與執(zhí)行的智能體的貢獻(xiàn).貢獻(xiàn)隨著各智能體能力而不同,且計(jì)算為任務(wù)執(zhí)行的獎(jiǎng)勵(lì)和資源成本的線性組合[7].在本工作中,智能體Ai對(duì)任務(wù)Tj的貢獻(xiàn)定義為rij,表示為

其中,rj為任務(wù)Tj的基礎(chǔ)效用;dij為智能體Ai當(dāng)前位置與任務(wù)Tj的距離;α和β分別為智能體能力和距離的權(quán)重系數(shù),取值取決于各自的相對(duì)重要性.

進(jìn)一步引入時(shí)效性約束來(lái)強(qiáng)調(diào)隨時(shí)間不斷提升抵抗智能體行為能力,導(dǎo)致智能體的可獲得效用不斷衰減的任務(wù)類型.在此約束下,每項(xiàng)任務(wù)限制在其出現(xiàn)和截止時(shí)間之間的時(shí)間窗內(nèi)執(zhí)行.任務(wù)Tj的出現(xiàn)時(shí)間定義為,對(duì)于起始存在的任務(wù)該值為0.利用以任務(wù)執(zhí)行時(shí)間為變量的指數(shù)函數(shù)來(lái)表征時(shí)效性約束對(duì)任務(wù)效用的影響.當(dāng)一項(xiàng)任務(wù)尚未被執(zhí)行但其基礎(chǔ)效用已經(jīng)隨時(shí)間衰減到固定閾值時(shí),該任務(wù)宣告失敗,相應(yīng)時(shí)間稱為任務(wù)截止時(shí)間,即

其中,折扣系數(shù)μj決定時(shí)效性約束對(duì)任務(wù)效用的影響程度;δ為決定任務(wù)能否被成功執(zhí)行的閾值.

由于各項(xiàng)任務(wù)均需求多個(gè)智能體和盡可能早的執(zhí)行時(shí)間,時(shí)效性約束使得一項(xiàng)任務(wù)的分配對(duì)智能體和可用執(zhí)行時(shí)間的占用會(huì)導(dǎo)致競(jìng)爭(zhēng)失敗的任務(wù)被迫推遲其執(zhí)行時(shí)間,從而導(dǎo)致個(gè)體乃至全局效用的衰減,這一耦合特性使得分配每項(xiàng)任務(wù)時(shí)均需要考慮其他任務(wù)所受的影響.兩項(xiàng)約束式(1)和式(3)的引入,將從任務(wù)的執(zhí)行順序和執(zhí)行時(shí)間方面大大增加可選任務(wù)分配方案的數(shù)量,使得對(duì)最優(yōu)解的搜索更加困難.

注 1.以空地協(xié)同作戰(zhàn)、火災(zāi)救援、流水線工作等復(fù)雜任務(wù)為代表的任務(wù)分配問(wèn)題,均受到單項(xiàng)任務(wù)由多種類型的智能體協(xié)同執(zhí)行的同步性約束和任務(wù)價(jià)值隨時(shí)間衰減的時(shí)效性約束的限制.因此,考慮在模型中同時(shí)引入這兩項(xiàng)約束具有現(xiàn)實(shí)意義.

根據(jù)同步性約束式(1)和時(shí)效性約束式(3),任務(wù)Tj的效用計(jì)算為

其中,tj在分配中要求不超過(guò).

此外,對(duì)智能體故障率建模來(lái)提升系統(tǒng)可靠性和期望任務(wù)執(zhí)行質(zhì)量.永久故障發(fā)生的可能性會(huì)被智能體已執(zhí)行任務(wù)的特性加劇.定義智能體Ai執(zhí)行任務(wù)Tj時(shí)發(fā)生永久故障的可能性為fij,與Tj和智能體Ai已經(jīng)完成的任務(wù)有關(guān).利用Guo等[26]給出的通用可靠性模型,fij表示為

其中,ωi為智能體Ai的可靠性系數(shù);σf為給定正常數(shù);(Tj) 為智能體Ai在執(zhí)行任務(wù)Tj前已經(jīng)完成的任務(wù)集合.如果任意參與智能體在執(zhí)行一項(xiàng)任務(wù)時(shí)故障,則將該任務(wù)終止且將其效用式(4)置0.盡管后續(xù)將通過(guò)重分配嚴(yán)格保證該任務(wù)的成功執(zhí)行,但建模中的這一處理將盡可能地提升系統(tǒng)可靠性.因此,任務(wù)Tj的期望效用計(jì)算為

根據(jù)式(4)～式(6),任務(wù)分配問(wèn)題模型寫為

式(10)保證執(zhí)行每項(xiàng)任務(wù)的智能體數(shù)量滿足要求,式(11)保證每項(xiàng)任務(wù)能在截止時(shí)間前成功執(zhí)行.式(12)、式(13)用以確保任意智能體到達(dá)待執(zhí)行任務(wù)的時(shí)間足夠覆蓋所需的路程,其中τi(l1,l2)代表智能體Ai從l1到l2的位置所需的時(shí)間.至此,異構(gòu)多智能體系統(tǒng)的任務(wù)分配問(wèn)題轉(zhuǎn)化為在同步性約束式(1)和時(shí)效性約束式(3)下,考慮故障率式(5),以最大化式(8),即全局最優(yōu)分配為目標(biāo)的問(wèn)題.

由式(7)～式(13)可見,該任務(wù)分配問(wèn)題是一個(gè)多重約束下的優(yōu)化問(wèn)題,很少有找到最優(yōu)解的方法,即使有,也需要承擔(dān)大量的計(jì)算資源成本.因此,本文追求式(7)的近似全局最優(yōu),使得算法能夠在分配方案解質(zhì)量和計(jì)算時(shí)間之間取得平衡.

2 無(wú)故障初始環(huán)境下的任務(wù)分配

在無(wú)故障情況下,將所有任務(wù)T最優(yōu)地分配給處于起始位置的智能體集合A的過(guò)程稱為初始分配.初始分配完成后,每項(xiàng)任務(wù)將由負(fù)責(zé)它的智能體執(zhí)行.對(duì)于多智能體系統(tǒng)任務(wù)分配問(wèn)題,算法大多在健康情況下進(jìn)行設(shè)計(jì)和實(shí)現(xiàn).在故障發(fā)生后,若能根據(jù)健康情況下的算法進(jìn)行容錯(cuò)的重分配,則算法的工作量和計(jì)算量將大大減少,效率更會(huì)提高.因此,本文將首先研究無(wú)故障情況下的任務(wù)分配算法,后續(xù)將其推廣到故障情況,以表明所提出的算法具有很好的普適性.

定義U ?T為未分配任務(wù)集合.所有m項(xiàng)任務(wù)最初都標(biāo)記為未分配,即U=T,且所有智能體均未被分配任務(wù).算法每輪將從U中選擇一項(xiàng)任務(wù)以最大化式(6)為目標(biāo)完成最優(yōu)分配,并將該任務(wù)添加到所分配智能體的任務(wù)包中,直到U為空集,則通過(guò)m輪將最終確定使式(8)近似最大的全局最優(yōu)分配.

2.1 單項(xiàng)任務(wù)最優(yōu)分配搜索

首先,算法將設(shè)計(jì)智能體間針對(duì)單項(xiàng)任務(wù)的博弈方法,以為每項(xiàng)未分配任務(wù)Tj∈U尋找最優(yōu)分配,即從智能體集合A中選擇如式(10)要求的Nj個(gè)對(duì)應(yīng)能力λij不為0 的智能體,使得它們合作執(zhí)行Tj所能獲得的期望任務(wù)效用式(6)最大.

從博弈論角度而言,智能體為博弈參與者,基于其位置、運(yùn)動(dòng)狀態(tài)、能力、時(shí)間戳等信息參與任務(wù)博弈.要求每個(gè)智能體博弈所依據(jù)的到達(dá)任務(wù)時(shí)間tij均滿足約束式(11)～式(13),以確保經(jīng)由同步性約束式(1)得到的任務(wù)執(zhí)行時(shí)間tj同樣滿足式(11)～式(13).此外,要求任意兩個(gè)智能體之間的通信可達(dá)且穩(wěn)定,以確保博弈能夠隨時(shí)進(jìn)行.

定 義博 弈Γ=(A,S,{uij}) ,A仍然為第1節(jié)定義的智能體集合.S=S1×S2×···×Sn表示策略空間,其中Si ?2T,i=1,2,···,n為智能體Ai關(guān)于是否執(zhí)行T中各項(xiàng)任務(wù)的所有可選策略集合[28].si∈Si,i=1,2,···,n為其中一項(xiàng)可選策略,對(duì)應(yīng)分配給智能體Ai的一組任務(wù).當(dāng)且僅當(dāng)式(8)中的任務(wù)分配決策變量χij為1 時(shí),有Tj∈si,即si={Tj|Tj∈T,χij=1},i=1,2,···,n. s=(s1,s2,···,sn) 代表所有智能體策略的集合,也可寫為s=(si,s?i),其中s?i表示除Ai之外其他所有智能體的策略集合.s對(duì)應(yīng)唯一的決策變量矩陣χ,從而代表唯一的全局任務(wù)分配,決定期望全局效用式(8)的值.據(jù)此,式(6) 所描述的期望任務(wù)效用也可表示為(si,s?i).uij表示智能體Ai執(zhí)行其策略si中任務(wù)Tj的效用函數(shù),其值依賴于合作智能體到達(dá)該任務(wù)的時(shí)間,因此uij與所有智能體的策略相關(guān),可寫為uij(si,s?i).uij(si,s?i) 來(lái)源于任務(wù)Tj的期望效用,但由于如式(1)和式(4)所示其與合作智能體效用的耦合特性,uij(si,s?i) 的值不能直接計(jì)算為貢獻(xiàn)rij占的比例.根據(jù)單個(gè)智能體對(duì)任務(wù)的邊際貢獻(xiàn)[15],uij(si,s?i) 定義為

其中,si,0表示智能體Ai不參與執(zhí)行任何任務(wù).顯然若Tjsi,有uij(si,s?i)=0.

效用函數(shù)uij(si,s?i) 的定義為智能體的獨(dú)立決策提供基礎(chǔ).根據(jù)式(14),單個(gè)智能體對(duì)任務(wù)的邊際貢獻(xiàn)僅和該智能體以及參與該任務(wù)的其他智能體相關(guān),因此單個(gè)智能體在對(duì)一項(xiàng)任務(wù)博弈時(shí)僅需要少量鄰居智能體的信息,并能據(jù)此作出是否參與任務(wù)的決策,這使得系統(tǒng)能在分布式結(jié)構(gòu)下工作.算法將尋求利用勢(shì)博弈搭建uij(si,s?i)與期望任務(wù)效用(si,s?i) 之間的聯(lián)系,使得(si,s?i) 能通過(guò)尋找各智能體Ai的最優(yōu)策略si,以u(píng)ij(si,s?i)為媒介達(dá)到最大化.如下給出勢(shì)博弈的定義.

則Γ為勢(shì)博弈,P為相應(yīng)的勢(shì)函數(shù).

根據(jù)定義1,在勢(shì)博弈中,每個(gè)智能體由策略變化引起的效用函數(shù)變化會(huì)等量地反映在勢(shì)函數(shù)上.如果能利用智能體效用函數(shù)構(gòu)造勢(shì)博弈,使得勢(shì)函數(shù)P為期望任務(wù)效用式(6),則各智能體能通過(guò)僅改變自身策略來(lái)不斷提高式(6).在這一框架下,個(gè)體智能體的目標(biāo)能夠與全局目標(biāo)保持一致.具體地,所有智能體的策略均被隨機(jī)初始化.每個(gè)智能體Ai∈A在其他智能體的策略s?i保持不變的條件下,總是朝著提升自身智能體效用uij(si,s?i) 的方向迭代調(diào)整策略si.若沒(méi)有智能體能作出更好的策略選擇,則作為勢(shì)函數(shù)的期望任務(wù)效用式(6)達(dá)到最大化.這意味著當(dāng)所有智能體的策略迭代完成時(shí),任何智能體都無(wú)法再通過(guò)獨(dú)自調(diào)整自身策略來(lái)獲取更高的效用,稱此時(shí)的策略集合s為納什均衡,如下給出其定義.

應(yīng)用勢(shì)博弈的關(guān)鍵在于,當(dāng)任意智能體Ai∈A的策略si迭代時(shí),其他智能體的策略s?i必須保持不變.然而,在第1 節(jié)所搭建的MR 任務(wù)分配問(wèn)題模型中,每項(xiàng)任務(wù)都需要固定數(shù)量的智能體合作執(zhí)行,這導(dǎo)致一個(gè)智能體的策略變化必然會(huì)要求另一個(gè)智能體的策略同步變化以維持任務(wù)所需智能體數(shù)量.為此,在迭代時(shí)令策略中包含該任務(wù)的智能體與所有策略中不包含該任務(wù)的智能體一一替換,將兩個(gè)策略改變的智能體視為一個(gè)整體考慮,以便其他智能體的策略能夠視為不變.據(jù)此如下定理成立.

定理 1.針對(duì)目標(biāo)任務(wù)Tj∈U,考慮由智能體集合A為最大化式(6)所描述的期望任務(wù)效用所進(jìn)行的博弈Γ.如果將某次迭代中具有替換關(guān)系的兩個(gè)智能體視為一個(gè)整體參與博弈,則可以將博弈Γ構(gòu)造為勢(shì)博弈,且勢(shì)函數(shù)推導(dǎo)為期望任務(wù)效用.經(jīng)過(guò)有限次迭代,所有智能體執(zhí)行任務(wù)Tj的策略將收斂到使最大的納什均衡.

根據(jù)定義1,博弈Γ為勢(shì)博弈,且為勢(shì)函數(shù).

因此,在所構(gòu)造的博弈Γ中,算法只需要朝著提升智能體效用之和式(19)的方向成對(duì)地迭代調(diào)整各智能體的策略,就能實(shí)現(xiàn)期望任務(wù)效用式(6)的增加.由于智能體效用隨著策略的調(diào)整呈現(xiàn)單調(diào)變化,且勢(shì)博弈必然存在納什均衡點(diǎn)[28],算法會(huì)使得各智能體的策略必然收斂為使式(6)最大的納什均衡策略.根據(jù)勢(shì)博弈的有限遞增屬性[19],任何單方面改進(jìn)的序列都會(huì)在有限時(shí)間內(nèi)收斂于納什均衡,則本算法所設(shè)計(jì)的迭代過(guò)程一定會(huì)在有限的迭代步內(nèi)實(shí)現(xiàn)收斂. □

注 2.在一致性聯(lián)盟算法[29]中,各智能體僅根據(jù)個(gè)體收益以貪婪算法思想將任務(wù)添加到自身策略中,從而導(dǎo)致分配到該任務(wù)的智能體數(shù)大于實(shí)際所需數(shù)量的沖突.雖然后續(xù)設(shè)計(jì)該智能體間沖突的消除方法,但也重復(fù)消耗算法資源.而本節(jié)所設(shè)計(jì)的算法則利用智能體間博弈始終維持分配到任務(wù)的智能體數(shù)量,從而在分配過(guò)程中避免這類沖突現(xiàn)象.

每項(xiàng)未分配任務(wù)Tj∈U的最優(yōu)分配能最大化其期望效用式(6),但與所有其他任務(wù)的成功執(zhí)行之間可能存在沖突.任務(wù)的允許執(zhí)行時(shí)間受時(shí)效性約束式(3)限制,因此應(yīng)用一項(xiàng)任務(wù)的最優(yōu)分配后,其他任務(wù)可能缺乏足夠式(10)要求數(shù)量的能在截止時(shí)間前到達(dá)任務(wù)的智能體,從而無(wú)法滿足式(11).第2.2 節(jié)將設(shè)計(jì)消除這類沖突的方法.

2.2 沖突消除

線性表用來(lái)存儲(chǔ)所有待定次優(yōu)解,選擇次優(yōu)解的過(guò)程一般化為線性表中結(jié)點(diǎn)的添加和刪除.添加的方案要求不與表中現(xiàn)存的方案或曾刪除的方案重復(fù).最初,線性表為空.在某一輪得到一項(xiàng)任務(wù)的最優(yōu)分配后,將其添加入線性表并進(jìn)行檢測(cè).如果應(yīng)用該最優(yōu)分配后會(huì)存在沖突,則刪除該方案并將其分支下的勢(shì)博弈待定次優(yōu)解添加入線性表.從表中選取對(duì)應(yīng)期望任務(wù)效用最大的方案作為次優(yōu)解,并檢測(cè)沖突是否消除.若已消除,則用其替換最優(yōu)分配,否則重復(fù)此過(guò)程,直到搜索到可行方案.如果直到線性表再次為空也沒(méi)有找到合適的方案,則意味著對(duì)該被檢測(cè)任務(wù)的任何分配都會(huì)導(dǎo)致與其他未分配任務(wù)的沖突.在這種情況下,被檢測(cè)任務(wù)在這一輪中不允許被分配,而是在下一輪重新考慮.圖1描述了利用線性表選擇勢(shì)博弈次優(yōu)解的過(guò)程,其中不會(huì)引發(fā)沖突的最終可行分配被標(biāo)記為.

圖1 勢(shì)博弈次優(yōu)解的選擇過(guò)程Fig.1 The process of selecting the suboptimal solution of the potential game

2.3 全局最優(yōu)分配搜索

基于第2.1 節(jié)和第2.2 節(jié)的結(jié)果,本節(jié)將定義各項(xiàng)任務(wù)的優(yōu)先級(jí)來(lái)描述一項(xiàng)任務(wù)的最優(yōu)分配趨向于全局最優(yōu)的程度,并分配具有最高優(yōu)先級(jí)的未分配任務(wù).一項(xiàng)任務(wù)的分配對(duì)多個(gè)智能體的占用,會(huì)導(dǎo)致其他任務(wù)在時(shí)效性約束下所能獲得最大期望效用的衰減.值得一提的是,智能體的故障率與其曾經(jīng)執(zhí)行的任務(wù)有關(guān),隨分配過(guò)程動(dòng)態(tài)變化,其影響同樣包含在這一衰減中.因此,該任務(wù)的優(yōu)先級(jí)取決于其他任務(wù)受到該任務(wù)分配的影響程度,那么為盡可能最大化式(8),應(yīng)當(dāng)首先分配所導(dǎo)致衰減最小的任務(wù).實(shí)際上,這表示該任務(wù)的最優(yōu)分配相比于其他任務(wù)更趨近于全局最優(yōu).針對(duì)某一輪中的任意未分配任務(wù)Tj∈U,令其通過(guò)第2.1 節(jié)和第2.2節(jié)得到的最大期望效用為.假設(shè)任務(wù)Tj按其個(gè)體的最優(yōu)方案完成分配,且方案中參與智能體的位置、速度、加速度和時(shí)間戳得到更新,在此基礎(chǔ)上計(jì)算所有其他未分配任務(wù)Tk∈U,kj在下一輪所能獲得的最大期望效用的變化量化了任務(wù)Tk受到任務(wù)Tj分配影響的程度,據(jù)此,任務(wù)Tj的優(yōu)先級(jí)權(quán)值定義為其對(duì)所有其他未分配任務(wù)所造成的最嚴(yán)重影響,即

算法2.優(yōu)先級(jí)權(quán)值計(jì)算

健康環(huán)境下整體初始分配的流程圖如圖2 所示.算法每輪通過(guò)第2.1 節(jié)～第2.3 節(jié)這3 個(gè)步驟完成一項(xiàng)優(yōu)先級(jí)最大的任務(wù)Tp的分配.所有參與該任務(wù)執(zhí)行的智能體的狀態(tài)與時(shí)間戳信息應(yīng)當(dāng)被更新,以進(jìn)行下一輪博弈.任務(wù)Tp標(biāo)記為已分配并且不會(huì)參與后續(xù)計(jì)算.將未分配任務(wù)集合U迭代為UTp,智能體集合A針對(duì)U中所有剩余任務(wù)重復(fù)這3 個(gè)步驟.經(jīng)過(guò)m輪最終得到所有任務(wù)的全局近似最優(yōu)分配,此時(shí)U為空.

圖2 健康環(huán)境下的初始任務(wù)分配流程圖Fig.2 The flow chart of the initial task allocation in the healthy environment

注 3.從整個(gè)初始分配算法的設(shè)計(jì)過(guò)程中可以總結(jié)出所提出算法的優(yōu)越性.一方面,智能體作為整體對(duì)單項(xiàng)MR 任務(wù)進(jìn)行博弈,從而避免編隊(duì)聯(lián)盟方法[10?12]和市場(chǎng)算法[13?15]所面對(duì)的任務(wù)難以拆分的問(wèn)題.另一方面,算法根據(jù)博弈過(guò)程對(duì)分配方案進(jìn)行優(yōu)劣排序,從而確定任務(wù)優(yōu)先級(jí),解決任務(wù)間的耦合.與傳統(tǒng)群體智能算法[8?9]尋優(yōu)方向的隨機(jī)性相比,所提出算法等效為在一定程度上對(duì)尋優(yōu)方向具有導(dǎo)向性,因此具有較低的尋優(yōu)難度.

至此,算法完成健康環(huán)境下所有任務(wù)的初始分配.算法的設(shè)計(jì)追求包含全局效用最大化和所有任務(wù)成功執(zhí)行的目標(biāo),同時(shí)能夠在解質(zhì)量和計(jì)算時(shí)間之間取得較好的平衡.通過(guò)循環(huán)由這3 個(gè)步驟構(gòu)成的算法,全局最優(yōu)式(7)由分布式結(jié)構(gòu)中智能體之間的合作與協(xié)商來(lái)近似實(shí)現(xiàn).

3 故障情況下的任務(wù)重分配

在無(wú)故障情況下已經(jīng)完成所有任務(wù)的初始分配,隨后每個(gè)智能體根據(jù)其策略執(zhí)行任務(wù).智能體在任務(wù)執(zhí)行過(guò)程中可能會(huì)發(fā)生永久故障,以致故障智能體無(wú)法再執(zhí)行剩余任務(wù).因此,這些任務(wù)需要重分配,即智能體需要實(shí)時(shí)調(diào)整策略.特別地,當(dāng)協(xié)同執(zhí)行具有多重約束式(1)和式(3)的MR 任務(wù)時(shí),單個(gè)智能體策略的改變可能會(huì)導(dǎo)致整個(gè)系統(tǒng)策略的改變.如果每發(fā)生故障就對(duì)所有任務(wù)重新分配,則盡管結(jié)果會(huì)更優(yōu),但所有智能體策略的動(dòng)態(tài)重置將導(dǎo)致分配方案解空間的非線性劇增,消耗大量的算法資源,降低重分配的實(shí)時(shí)性能和效率.因此,本節(jié)將健康環(huán)境下的任務(wù)分配算法推廣到故障情況下,同時(shí)將健康環(huán)境下的分配結(jié)果作為重分配的依據(jù),以減少工作量和計(jì)算量.算法推廣的基礎(chǔ)是在健康情況下,一項(xiàng)任務(wù)只能在緊跟著前一項(xiàng)任務(wù)的位置之后被添加到智能體策略中,而在故障情況下,重分配任務(wù)將被提供若干個(gè)可添加位置供其選擇.

如下給出一些服務(wù)于算法的準(zhǔn)備和說(shuō)明.所有任務(wù)Tj∈T按照初始分配方案下的任務(wù)執(zhí)行時(shí)間tj從小到大進(jìn)行排序,依次重新編號(hào)為∈T,其中任務(wù)的執(zhí)行時(shí)間寫作,k=1,2,···,m.

待重分配的任務(wù)需要從初始分配下的智能體策略中移除.如式(4)所示,任務(wù)效用與執(zhí)行時(shí)間有關(guān).移除由智能體故障終止的任務(wù)后,剩余未執(zhí)行任務(wù)的執(zhí)行時(shí)間需要進(jìn)行調(diào)整以最大化期望全局效用式(8).具體地,調(diào)整方法是以排序后執(zhí)行時(shí)間的順序依次決定剩余任務(wù)能否被提前執(zhí)行.

待重分配的任務(wù)被全部移除后,應(yīng)當(dāng)各自重插入到智能體策略中.與初始分配時(shí)智能體始終將任務(wù)放置在其策略末尾來(lái)參與博弈不同,待重分配任務(wù)的可重插入位置并不唯一.考慮重插入一項(xiàng)任務(wù),其按執(zhí)行時(shí)間排序后的編號(hào)為.若將插入至一個(gè)智能體的策略中,算法需要決定其插入位置.通過(guò)拆分任務(wù)的可執(zhí)行時(shí)間窗來(lái)討論可選重插入位置.若距離故障時(shí)刻tf最近的已執(zhí)行任務(wù)其排序后的編號(hào)為,則有p=m?mr?c+1種位置使得任務(wù)執(zhí)行的順序不同,其中mr為待重插入任務(wù)數(shù).

如果重插入不會(huì)推遲任何任務(wù)的執(zhí)行,則期望全局效用式(8)不會(huì)減少,否則會(huì)導(dǎo)致由時(shí)效性約束式(3)引起的效用衰減.任務(wù)總是包含在多個(gè)智能體的策略中,因此在被推遲的任務(wù)數(shù)量方面影響可能較為嚴(yán)重.那么,重插入所引起的期望全局效用變化量不僅與自身的效用有關(guān),還與后續(xù)任務(wù)被推遲執(zhí)行的程度有關(guān),計(jì)算為

圖3 故障情況下的任務(wù)重分配流程圖Fig.3 The flow chart of the task reallocation in the faulty case

仍然討論上例.給定智能體A4在執(zhí)行后永久故障,則和需要重新分配.重分配方案為判斷和是否可以提前執(zhí)行,之后依次重插入和.移除和重插入任務(wù)的具體過(guò)程已在上文分析,這里不再贅述.可以發(fā)現(xiàn)在此例中,算法僅需要調(diào)整、的執(zhí)行時(shí)間和、的分配.這表明通過(guò)推廣健康環(huán)境下的分配算法并結(jié)合故障信息,重分配問(wèn)題被簡(jiǎn)化為對(duì)少量任務(wù)的調(diào)整,而不需要重啟所有任務(wù)的分配.從這種意義上說(shuō),算法能夠避免不必要的時(shí)間消耗.至此,本節(jié)已經(jīng)完成具有容錯(cuò)能力的任務(wù)重分配算法設(shè)計(jì),同時(shí)算法解質(zhì)量和實(shí)時(shí)性能得到保證.

4 仿真結(jié)果

構(gòu)建一個(gè)多個(gè)智能體攻擊多個(gè)任務(wù)目標(biāo)的軍事場(chǎng)景,以驗(yàn)證所提出算法的可行性和有效性.每個(gè)任務(wù)目標(biāo)具有針對(duì)智能體行為的初始防御能力,防御能力越弱對(duì)應(yīng)該任務(wù)的基礎(chǔ)效用越高.防御工事隨時(shí)間加強(qiáng),因此智能體攻擊目標(biāo)越晚,則可獲得的效用越低.如果超過(guò)截止時(shí)間,則來(lái)自智能體的攻擊無(wú)法穿透防御,該任務(wù)宣告失敗.每個(gè)目標(biāo)都由所需數(shù)量的智能體同時(shí)攻擊以確保火力的集中程度,且完成攻擊后這些智能體立刻各自前往下一個(gè)目標(biāo).所構(gòu)建的場(chǎng)景顯然非常契合本文所建立的任務(wù)分配問(wèn)題模型.任務(wù)目標(biāo)為最大化期望全局效用,且確保所有任務(wù)成功完成.算法僅在XOY平面上進(jìn)行仿真,且表1、表2 給出了某次仿真中智能體和任務(wù)的參數(shù).這樣的設(shè)定和參數(shù)選擇僅是為了使實(shí)驗(yàn)結(jié)果中智能體的軌跡清晰,實(shí)際上智能體和任務(wù)可在場(chǎng)景中隨機(jī)分布,且數(shù)量和所有參數(shù)均可調(diào).

表1 智能體初始信息Table 1 Initial information of agents

表2 任務(wù)初始信息Table 2 Initial information of tasks

圖4 給出了無(wú)故障情況下的初始最優(yōu)分配和相應(yīng)的智能體軌跡.以Minimum snap 為目標(biāo)[30],基于貝塞爾曲線優(yōu)化智能體軌跡[31],使其保持光滑和連續(xù).在任務(wù)分配和重分配階段,軌跡規(guī)劃均在完成一項(xiàng)任務(wù)的分配或重分配后進(jìn)行.以分配完成上一項(xiàng)任務(wù)時(shí)智能體的位置、速度、加速度為起點(diǎn)約束,同時(shí)以新分配任務(wù)的執(zhí)行時(shí)間為終點(diǎn)約束,結(jié)合最大速度和加速度約束,軌跡優(yōu)化問(wèn)題實(shí)質(zhì)上被轉(zhuǎn)化為能用MATLAB 直接求解的凸二次規(guī)劃問(wèn)題,因此不再贅述.每項(xiàng)任務(wù)的執(zhí)行時(shí)間在任務(wù)點(diǎn)旁邊標(biāo)注.由圖4 易得各智能體的最優(yōu)策略分別為s1={T3,T4},s2={T2,T1},s3={T2,T3},s4={T1,T4}. 以A2的軌跡為例說(shuō)明任務(wù)執(zhí)行的同步性.A2首先在282.0 s 時(shí)與A3同時(shí)到達(dá)T2并合作攻擊T2,相似地隨后在408.0 s 時(shí)與A4共同攻擊T1.可以看出,每組合作智能體都滿足同步性約束,且智能體的軌跡連續(xù)光滑.

任務(wù)分配算法第2.1 節(jié)的目標(biāo)是獲得所有未分配任務(wù)的最優(yōu)分配,首先考慮第2.1 節(jié)分配單項(xiàng)任務(wù)的性能.對(duì)于某個(gè)需要兩個(gè)智能體執(zhí)行的單項(xiàng)任務(wù),圖5、圖6 分別給出了在不同智能體數(shù)量n下采用勢(shì)博弈算法和枚舉法的可得最大期望任務(wù)效用和所需迭代次數(shù).針對(duì)每種情況進(jìn)行50 次重復(fù)實(shí)驗(yàn)并取平均值,其中智能體和任務(wù)的位置隨機(jī)分布.可以看出,基于勢(shì)博弈的算法能提供與枚舉法相同的性能,也就是說(shuō),所提出算法的第1 步可以獲得任意單項(xiàng)任務(wù)的最優(yōu)分配.相反,算法復(fù)雜度的差異很大.枚舉法和勢(shì)博弈算法的復(fù)雜度分別為O(n2)和O (n),因此勢(shì)博弈算法的復(fù)雜度顯著減少.此外,隨著智能體數(shù)量的增加,可能會(huì)出現(xiàn)能力更強(qiáng)或距離更近的智能體,從而導(dǎo)致可獲得的任務(wù)效用增加.

圖6 分配單項(xiàng)任務(wù)的所需迭代次數(shù)對(duì)比Fig.6 Comparison of the required number of iterations for allocating a single task

考慮第2 節(jié)中完整的無(wú)故障情況下的任務(wù)分配算法.仍然用枚舉法作為比較,圖7、圖8 分別給出了在不同任務(wù)數(shù)量m和不同智能體數(shù)量n下通過(guò)使用勢(shì)博弈算法所能獲得的最大期望全局效用相對(duì)于枚舉法的衰減量.兩個(gè)實(shí)驗(yàn)分別在m=4和n=4的條件下進(jìn)行,每個(gè)實(shí)驗(yàn)重復(fù)50 次取平均值,其中智能體和任務(wù)的位置隨機(jī)分布.由圖可見,所提出算法仍然可以提供與枚舉法相似的性能.隨著任務(wù)數(shù)量增加,所提出算法的性能相對(duì)降低,這是由于每輪在計(jì)算每項(xiàng)任務(wù)的優(yōu)先級(jí)時(shí),只考慮分配該任務(wù)將造成的下一輪效用衰減量,而未考慮后續(xù)輪次的效用同樣會(huì)受到影響.特別地,如果任務(wù)分配的總輪數(shù)為1 或2,則算法等同于已經(jīng)考慮所有輪次的影響.因此,由圖7 可見,當(dāng)任務(wù)數(shù)量為1 或2 時(shí),所提出算法能夠獲得與枚舉法相同的最佳效用.可以推斷,若在計(jì)算優(yōu)先級(jí)時(shí)考慮某一輪分配對(duì)更多后續(xù)輪次的影響,所提出算法會(huì)提供更好的性能,而代價(jià)是計(jì)算復(fù)雜度的提升.相反,隨著智能體數(shù)量的增加,所提出的算法將提供更好的性能.這是因?yàn)榭捎糜谌蝿?wù)執(zhí)行的智能體越多,在相鄰兩輪中選擇的兩項(xiàng)任務(wù)就越有可能由完全不同的智能體執(zhí)行,則基于優(yōu)先級(jí)的框架帶來(lái)的效用衰減越低.

圖7 不同任務(wù)數(shù)量下的最大期望全局效用衰減Fig.7 Reductions of the maximum expected global utility under different number of tasks

圖8 不同智能體數(shù)量下的最大期望全局效用衰減Fig.8 Reductions of the maximum expected global utility under different number of agents

圖9 給出了第2 節(jié)提出的任務(wù)分配算法與枚舉法的迭代次數(shù)的比值隨智能體數(shù)量和任務(wù)數(shù)量的變化圖.可以總結(jié)出當(dāng)任務(wù)數(shù)量滿足m ≥4 時(shí),勢(shì)博弈算法的迭代次數(shù)已不足枚舉法迭代次數(shù)的1%.考慮在無(wú)故障情況下將均需要兩個(gè)智能體協(xié)同執(zhí)行的m項(xiàng)任務(wù)分配給n個(gè)智能體的初始分配問(wèn)題,枚舉法的算法復(fù)雜度為,而所提出勢(shì)博弈算法的復(fù)雜度為綜上所述,所提出的算法在能有效獲得令人滿意的任務(wù)效用的同時(shí)具有較低的復(fù)雜度.

圖9 所提出算法與枚舉法迭代次數(shù)的比值Fig.9 The ratio of the number of iterations between the proposed algorithm and the enumeration method

為驗(yàn)證重分配算法的容錯(cuò)能力,在故障情況下進(jìn)行仿真.如圖4 所示無(wú)故障情況下任務(wù)分配算法的仿真結(jié)果被用作初始條件.給定A2在300 s 時(shí)故障并且無(wú)法從故障中恢復(fù)運(yùn)行,此時(shí)A2已經(jīng)執(zhí)行完T2,則T1需要重新分配.重分配方案和相應(yīng)的智能體軌跡如圖10 所示,其中用虛線表示無(wú)故障情況下的仿真結(jié)果作為參考.

圖10 故障情況下的最優(yōu)任務(wù)重分配方案Fig.10 The optimal task reallocation scheme in the faulty case

5 結(jié)論

基于勢(shì)博弈解決異構(gòu)多智能體系統(tǒng)的任務(wù)分配問(wèn)題.多重約束和智能體故障率同時(shí)被建模,這給任務(wù)執(zhí)行時(shí)間帶來(lái)嚴(yán)格的限制.所構(gòu)建的勢(shì)博弈框架允許合作和協(xié)商,從而為無(wú)故障和故障情況下的分布式任務(wù)分配和重分配算法設(shè)計(jì)奠定基礎(chǔ).然后,在保證所有任務(wù)成功執(zhí)行的前提下,通過(guò)較少次迭代達(dá)到近似全局最優(yōu),并且可以在健康的智能體上恢復(fù)被智能體故障終止的任務(wù),這表明所提出算法具有容錯(cuò)性能.針對(duì)能夠模擬所研究模型特征的攻擊任務(wù)場(chǎng)景進(jìn)行仿真,與枚舉法的比較結(jié)果表明所提出算法在期望全局效用和算法復(fù)雜度方面的有效性.算法的一個(gè)局限是需要持續(xù)通信,這在大規(guī)模系統(tǒng)或惡劣環(huán)境中可能不可行,從而導(dǎo)致博弈無(wú)法以最佳方式進(jìn)行.智能體在通信范圍受限和通信故障時(shí)進(jìn)行博弈的方法,將在以后的工作中討論.