基于勢博弈的異構多智能體系統(tǒng)任務分配和重分配

鞠鍇 冒澤慧 姜斌 馬亞杰

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

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

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

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

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

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

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

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

3) 構建與本文建立的任務分配問題模型符合程度高的現實場景,并通過仿真結果驗證所提出算法的有效性.

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

1 問題描述

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

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

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

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

其中,rj為任務Tj的基礎效用;dij為智能體Ai當前位置與任務Tj的距離;α和β分別為智能體能力和距離的權重系數,取值取決于各自的相對重要性.

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

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

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

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

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

其中,tj在分配中要求不超過.

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

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

根據式(4)～式(6),任務分配問題模型寫為

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

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

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

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

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

2.1 單項任務最優(yōu)分配搜索

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

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

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

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

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

則Γ為勢博弈,P為相應的勢函數.

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

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

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

根據定義1,博弈Γ為勢博弈,且為勢函數.

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

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

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

2.2 沖突消除

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

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

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

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

算法2.優(yōu)先級權值計算

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

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

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

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

3 故障情況下的任務重分配

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

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

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

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

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

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

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

4 仿真結果

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

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

表2 任務初始信息Table 2 Initial information of tasks

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

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

圖6 分配單項任務的所需迭代次數對比Fig.6 Comparison of the required number of iterations for allocating a single task

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

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

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

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

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

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

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

5 結論

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