多Agent聯(lián)合滅火救援協(xié)同組織研究

劉 靜， 程 樺

（1.中國人民武裝警察部隊學院 消防指揮系，河北 廊坊 065000；2.安徽大學 資源與環(huán)境工程學院，安徽 合肥 230601）

多Agent系統(tǒng)中，Agent之間的協(xié)作是最關鍵、最具特色的一個環(huán)節(jié)。在多Agent系統(tǒng)中，單個Agent往往非獨立完成某項任務，它必須通過和其他Agent相互協(xié)作，完成既定作戰(zhàn)任務［1］。多個Agent的交互會表現(xiàn)為相互合作，但在此過程中也會出現(xiàn)沖突行為，如何消除由于交互而產(chǎn)生的沖突，是一個重要的研究課題［2］。對于聯(lián)合滅火救援協(xié)作的假設如下：① 對于給定的任務Task，需要解決問題的能力和資源超出單個Agent所能提供的能力和資源；② 單個Agent完成某個單項任務所具備的信息、知識是不全面的。

部隊作戰(zhàn)是為了達成一定的作戰(zhàn)目的，所有兵力（包括參戰(zhàn)兵力裝備、通信保障和后勤輔助兵力）在指揮員統(tǒng)一指揮下而進行的一系列軍事活動，包括作戰(zhàn)方案制定和作戰(zhàn)計劃實施2個主要過程［3］。本文的軍隊組織結(jié)構(gòu)特指多Agent系統(tǒng)的協(xié)作和協(xié)調(diào)方法，目的是利用該方法建立描述作戰(zhàn)Agent聯(lián)合滅火救援的模型。

1 作戰(zhàn)Agent的協(xié)作及聯(lián)合行動

作戰(zhàn)型Agent組織中的Agent特點如下：①Agent是利他的，這是軍事指揮的一個重要特征，首先完成上級Agent命令它承擔的角色，然后再追求自身的目標；②Agent的個性不同，具有不同知識和技能，如水罐編成和泡沫編成具有不同作戰(zhàn)優(yōu)勢；③ 具有作戰(zhàn)組織結(jié)構(gòu)設計所需要的基本知識和技能。

1.1 聯(lián)合滅火救援任務

各Agent在相互協(xié)作的過程中，實時感知救援環(huán)境；根據(jù)協(xié)同作戰(zhàn)需要，與其他作戰(zhàn)Agent進行適時信息交互；根據(jù)所擁有的關于參戰(zhàn)力量的協(xié)作信息，在具體作戰(zhàn)規(guī)則（如消防部隊戰(zhàn)斗條令、相關作戰(zhàn)指揮知識等）指導下，制定協(xié)作決策方法，使自身在整個作戰(zhàn)行動中能夠完成與其他Agent的協(xié)作；根據(jù)制定的協(xié)作決策，調(diào)用系統(tǒng)的相應功能模塊并執(zhí)行，同時接受外界協(xié)作環(huán)境對其產(chǎn)生的影響，完成預期作戰(zhàn)目標；在協(xié)作過程中，對協(xié)作決策進行動態(tài)調(diào)整，使其狀態(tài)和動作能夠適應復雜的聯(lián)合滅火救援協(xié)同作戰(zhàn)要求。

1.2 聯(lián)合滅火救援角色功能

聯(lián)合滅火救援將任務分解為7類，即成員交互類A、環(huán)境感知類B、協(xié)作群體結(jié)構(gòu)類C、信息緩存類D、協(xié)作綜合態(tài)勢類E、動態(tài)協(xié)作類F及協(xié)作決策類G，相應的角色功能和責任見表1所列。

表1 聯(lián)合滅火救援任務分解表

（1）A類角色包含6個角色，職責是進行參數(shù)測量，這6個角色具有獨立性，不存在相互之間的通信和依賴。

（2）B類角色包含3個角色，相互獨立，不存在任何相互關系。

（3）C類角色包含7個角色，Cl、C3、C4、C5、C6、C7之間具有獨立性，但均依賴于C2。

（4）D類角色包含10個角色，相互獨立，不存在任何相互關系。

（5）E類角色包含3個角色，相互獨立，不存在任何相互關系。

（6）F類角色包含6個角色，相互獨立，不存在任何相互關系。

（7）G類包括4個角色，相互獨立，各角色對應實際協(xié)同模式中的實體。

1.3 聯(lián)合滅火救援協(xié)作結(jié)構(gòu)

聯(lián)合滅火救援多Agent系統(tǒng)的協(xié)作結(jié)構(gòu)，是系統(tǒng)中各個實體Agent相互配合、協(xié)同工作所表現(xiàn)出來的組織形態(tài)［4］。有什么樣的協(xié)作結(jié)構(gòu)就有相對應的協(xié)作機制，它決定系統(tǒng)自適應、協(xié)調(diào)及自治等特征形式和實現(xiàn)方法［5］。

Agent協(xié)作結(jié)構(gòu)種類很多，最常用的是對等網(wǎng)絡、聯(lián)盟和黑板結(jié)構(gòu)3種模型［6］。對等網(wǎng)絡結(jié)構(gòu)是指多Agent系統(tǒng)中的各成員具有相同的角色和地位，不設協(xié)調(diào)者，相互之間通過對等的通信和交互實現(xiàn)信息共享［7］。成員內(nèi)部只有局部信息，通信和狀態(tài)都是固定的［8］。黑板結(jié)構(gòu)是指系統(tǒng)中存在多個知識源，Agent通過黑板內(nèi)容的增減和修改來公布信息共享和Agent協(xié)作情況［9－11］。本文采用聯(lián)盟結(jié)構(gòu)確定聯(lián)合滅火救援的組織協(xié)同，如圖1所示。

圖1 多Agent聯(lián)合滅火救援的協(xié)作結(jié)構(gòu)模型

處于組織層的指揮Agent等對其下屬的控制具有強制性，作戰(zhàn)Agent和指揮Agent都是彼此獨立的，他們按照系統(tǒng)要求，接受并執(zhí)行各自的任務?？梢姸郃gent聯(lián)合滅火救援3層協(xié)作結(jié)構(gòu)本質(zhì)上是一種動態(tài)自組織結(jié)構(gòu)，這也是多Agent系統(tǒng)特點的集中體現(xiàn)。該結(jié)構(gòu)明確了聯(lián)合滅火救援中作戰(zhàn)Agent和指揮Agent相互間的控制關系，使復雜系統(tǒng)在結(jié)構(gòu)上更為簡化，而各層在控制上更具靈活性和可靠性。該結(jié)構(gòu)能使聯(lián)合滅火救援作戰(zhàn)實現(xiàn)全局最優(yōu)，在聯(lián)合滅火救援作戰(zhàn)指揮領域具有一定的通用性。

2 動態(tài)任務分配協(xié)作算法

2.1 合同網(wǎng)協(xié)議

文獻［12－13］提出合同網(wǎng)協(xié)議，主要用于研究分布式問題求解，其基本思想是利用招標－投標－中標這一機制，將系統(tǒng)任務進行分配，通過招標方和投標方的雙向選擇，相互協(xié)商，避免資源和知識等發(fā)生沖突，提高系統(tǒng)完成任務的質(zhì)量，降低系統(tǒng)代價［14－15］。

2.2 作戰(zhàn)Agent分配原則

（1）火場主要方面原則。首先將兵力分配給火場主要方面，并且優(yōu)先分配給作戰(zhàn)能力最強的Agent。

（2）到達救援現(xiàn)場時間最少原則。按照消防部隊執(zhí)勤戰(zhàn)斗條令要求和消防部隊5個“第一”要求，組織實施滅火與應急救援行動。

（3）救援人員安全第一原則。盡量避免滅火救援人員和裝備受到高溫、輻射、爆炸、倒塌及中毒傷害。

（4）多種因素兼顧原則。在前3條原則無法同時滿足的情況下，應兼顧各原則，這是多目標優(yōu)化問題。

（5）戰(zhàn)勤人員決策優(yōu)先原則。無論何時，保證戰(zhàn)勤人員的決策比計算機優(yōu)先級高，戰(zhàn)勤人員可以隨時干預與更改計算機給出的火力分配方案。

2.3 術語和約定

（1）A為m個作戰(zhàn)Agent集合，A＝ ｛a1，a2，…，am｝。

（2）T為需要完成的子任務集合，T＝ ｛t1，t2，…，tn｝，T0＝T∪ ?。其中，? 為虛擬任務集，表示任務隊列中的開始節(jié)點或終止節(jié)點。由于虛擬任務集?沒有執(zhí)行過程，因此開始執(zhí)行時間為0，占用時間也為0。

（3）Ai為符合任務ti要求備選的作戰(zhàn)Agent集合，ti∈T，Ai?A。

（4）Cji表示任務Agentaj（aj∈A，1≤j≤m）完成任務ti所付出的代價。

（6）Nsj（t）表示Agentaj在t時刻所具有的作戰(zhàn)能力。

（7）Hjα為子任務組合效益權(quán)重；Wij為對應任務的權(quán)重。

（8）Qik、Lj為潛在任務分配組和正式組。

（9）sj為共同占用作戰(zhàn)組，S為共同占用作戰(zhàn)組集。

要保證聯(lián)合滅火救援任務分配使整個部隊付出的代價最小，目標函數(shù)為：

在能夠完成上級Agent分配任務的前提下，要爭取最大收益，付出最小代價，即

（2）式使某一作戰(zhàn)任務只能執(zhí)行一次，即作戰(zhàn)任務具有不可再現(xiàn)性，一旦任務分配給某個作戰(zhàn)Agent或者一組作戰(zhàn)Agent并執(zhí)行，這個任務即宣告結(jié)束，無需進行再次分配。當任務執(zhí)行結(jié)束后，后續(xù)任務只能有一個，該后續(xù)任務可以是虛擬任務；（3）式確保作戰(zhàn)Agent的任務隊列中的起始節(jié)點唯一；（4）式確保作戰(zhàn)Agent的任務 隊列中任務執(zhí)行時間不會重疊，前任任務和后續(xù)任務與當前任務ti共同占用作戰(zhàn)Agentsj。

要確保任務執(zhí)行能力和資源需求，當作戰(zhàn)Agentsj在t時刻開始執(zhí)行任務時，其作戰(zhàn)能力和資源要大于、等于該任務所要求的力量總數(shù)，否則任務將無法完成，即

2.4 任務優(yōu)化分配算法

上級Agent分配任務的原則是在能夠完成任務的前提下，以最小的作戰(zhàn)代價和消耗獲取最大的作戰(zhàn)效果。

（1）作戰(zhàn)Agentaj（aj∈A，1≤j≤m）向上一級指揮Agentc公布所能完成的任務集Tj，Tj?T。

（3）aj給出Tj中完成所有子任務所付出的代價，即Cjk（1≤k≤l，l＝｜Tj｜，tk∈Tj），將結(jié)果返回給上一級Agentc，這里Cjk就是sj完成任務tk需要的作戰(zhàn)能力。此處的作戰(zhàn)能力是任務tk在Tj中某一位置，aj完成任務所付出的代價。雖然作戰(zhàn)任務相同，例如同是火情偵察，但由于在不同的作戰(zhàn)階段，或者在同一作戰(zhàn)階段，但偵察范圍不同，完成此項偵察任務需要的力量和付出的代價也不同。因此，作戰(zhàn)任務tk在不同任務序列或同一任務序列不同位置時，在時間環(huán)境等約束條件下，aj完成任務付出的代價可能是不一樣的。

（5）將潛在任務組集合表示為Qj＝｛qj1，qj2，…，qjα｝，其中，1≤α≤2｜Tj｜－1，則作戰(zhàn)付出的代價值表為SCj＝｛scj1，scj2，…，scjα，｝，對qjα中的任務是按Tj中任務執(zhí)行時間順序遞增排列的。

（6）將各作戰(zhàn)Agent給出的代價值Cjk（aj∈A，1≤j≤m）發(fā)送給指揮Agentc，指揮Agentc得到每一子任務的最小代價值為ek（1≤k≤n），構(gòu)成最小代價值表為E＝｛e1，e2，…ek，…，en｝，并返回給T的回應者。其中，ek＝min｛apjα｜tk∈qjα；1≤α≤2｜Tj｜－1；1≤j≤m｝，k＝1，2，…，n。

（8）經(jīng)過計算得出潛在任務組完成任務的權(quán)重集合，比較找出權(quán)重最大的潛在任務組qjk，即qjk滿足如下條件：（Hjk／scjk）≥（Hjα／scjα），1≤α≤｜Qj｜，并將qjk及對應的權(quán) 重Wjk／scjk反饋給Agentc。此時，出現(xiàn)權(quán)重最大的任務組可能有2個或者2個以上，表明具備完成此任務的作戰(zhàn)Agent可能有多個，則進一步選擇實際開始執(zhí)行時間st最早的任務組，即選擇能盡快到達指定救援現(xiàn)場或者救援陣地的作戰(zhàn)Agent。

例如，假設得到權(quán)重最大任務組有和由于任務組中任務是按原Tj中任務執(zhí)行時間順序遞增排列的，即Tj＝｛t1，t2，t3，…，tl｝，l＝｜Tj｜。因此，確定由哪個任務組最終完成作戰(zhàn)任務，取決于任務組中開始執(zhí)行的時間，對2個任務組中的第1個任務進行比較，此時都為t1，實際開始執(zhí)行時間一樣，繼而對第2個任務進行比較，對應為t2和t3。在Tj中，st2＞st3，故選擇以此類推，直到找出權(quán)重最大并開始執(zhí)行時間最早的任務組，即為所選任務組，這個任務組既有較強的作戰(zhàn)能力，同時又會以較快的速度到達救援現(xiàn)場，體現(xiàn)了消防部隊準確迅速的作戰(zhàn)原則。

（9）指揮Agentc計算得到權(quán)重最大的潛在任務組qj′k，即qj′k滿足條件：（Hj′k／scj′k）≥（Hjα／scjα），sj∈S，1≤j≤m，將向所有作戰(zhàn) Agent發(fā)出通告，qj′k為作戰(zhàn) Agentaj′的長期任務組。

（10）aj′同樣也會收到該通告，之后將qj′k添加到其長期任務組列表Lj′，對于其他的作戰(zhàn)Agent，在收到qj′k為作戰(zhàn) Agentaj′的長期任務組通告后，將把任務組qjα從Qj中刪除，即對?j，α，qjα∩qj′k≠?時，刪除權(quán)重Hjα／scjα，返回步驟（8），進行循環(huán)計算，這時潛在任務組為刪除qjα之后剩余的任務隊列，同理找出最大權(quán)值，直到Qj＝?。

3 算法在火場進攻中的應用

某次作戰(zhàn)行動中，設任務T對某一火點進行強攻，分解為4個獨立的子任務t1、t2、t3、t4，采用強行破拆、正面進攻、側(cè)翼進攻及后方供水，有3個作戰(zhàn)Agent完成此任務。

（1）作戰(zhàn)Agent完成作戰(zhàn)任務的能力為：

完成作戰(zhàn)任務矩陣為：

（3）aj給出作戰(zhàn)子任務集Tj中所有完成作戰(zhàn)子任務時付出代價值Cjk（1≤k≤l，l＝｜Tj｜，tk∈Tj），并反饋給上級指揮Agent。其中

（4）對子任務的可能性完全組合，可得潛在作戰(zhàn)子任務集為：

（5）a1、a2、a3對應潛在作戰(zhàn)子任務的代價值為：SC1＝｛2，3.2，4｝，SC2＝｛1.8，3.5，4｝，SC3＝｛1.8，2，3｝。

（6）給出最小代價指標E為：

（7）對所有Qj中潛在任務組，計算各權(quán)重Hjα／scjα，即H11／sc11＝ 1，H12／sc12＝ 0.75，H13／sc13＝1.10，H21／sc21＝1，H22／sc22＝0.60，H23／sc23＝1.23，H31／sc31＝ 1，H32／sc32＝ 1，H33／sc33＝1.26。

（8）作戰(zhàn)Agent向指揮Agent反饋其最大權(quán)重為：

（9）找出最大權(quán)s3：W33／sc33，并向其他作戰(zhàn)Agent宣布q33為長期任務組。

（10）s3將q33＝｛0.6t3，t4｝從Q3中取出，加入到L1。a3將滿足q32∩q33≠? 的q31、q32，q33刪除，H31／sc31、H32／sc32和H33／sc33也被刪除，刪除后的｜Q3｜＝?；同理，其他作戰(zhàn)Agent也采用此過程，將滿足qj2∩q33≠?（j≠1）中的qjα和其權(quán)重刪除，返回步驟（8），對刪除后的潛在子任務集進行新一輪計算，從中比較篩選出最大權(quán)值。此時，由 于最 大權(quán)重H23／sc23＝1.23，刪除后，｜Q1｜＝｜Q2｜，所以，對潛在作戰(zhàn)子任務重新進行計算，L2為｛0.6t2，0.4t3｝，L3為｛t1，0.4t2｝，經(jīng)過3次循環(huán)，?Qj＝?，結(jié)束。

由所有作戰(zhàn)子任務分配可知，由Agent1獨立完成作戰(zhàn)任務t1，Agent2獨立完成作戰(zhàn)任務t4，作戰(zhàn)任務t2由Agent1和Agent2協(xié)作完成，作戰(zhàn)任務t3由Agent2和Agent3協(xié)作完成，整個作戰(zhàn)任務分配完成。

4 結(jié)束語

本文在分析聯(lián)合滅火救援組織機制基礎上，結(jié)合軍事指揮特點，研究了作戰(zhàn)型Agent的特點。根據(jù)多Agent聯(lián)合滅火救援組織特點，采用物理分解和功能分解相結(jié)合的方法，對系統(tǒng)任務進行分解。利用聯(lián)盟協(xié)作結(jié)構(gòu)，基于角色協(xié)作模型，與指揮層次相對應。給出了動態(tài)任務分配協(xié)作算法、指揮Agent與作戰(zhàn)Agent動態(tài)任務處理流程和指揮Agent與作戰(zhàn)Agent的協(xié)作算法，并結(jié)合戰(zhàn)例分析算法在火場進攻中的應用，以證明該算法對解決實際作戰(zhàn)問題的能力。

［1］ 李建華，康青春，商靠定，等.滅火戰(zhàn)術［M］.北京：群眾出版社，2004：15－27.

［2］ 公安部政治部.滅火應用戰(zhàn)術［M］.北京：警官教育出版社，1998：215－218.

［3］ 公安部消防局.中國消防手冊：第9卷.［M］.上海：上?？茖W技術出版社，2006：371.

［4］ 莫于川.中華人民共和國突發(fā)事件應對法釋義［M］.北京：中國法制出版社，2007：26－31.

［5］ 季慎強.法國滅火救援的組織指揮［J］.浙江消防，2000（2）：36－38.

［6］ 張 羽.論聯(lián)合戰(zhàn)斗［M］.北京：國防大學出版社，2003：18－23.

［7］ 司光亞.戰(zhàn)略決策綜合集成研討與模擬環(huán)境研究與實現(xiàn)［D］.長沙：國防科技大學，2000.

［8］ 薛宏濤.基于協(xié)進化機制的多智能體系統(tǒng)體系結(jié)構(gòu)及多智能體協(xié)作方法研究［D］.長沙：國防科技大學，2002.

［9］ 胡曉峰.戰(zhàn)爭模擬引論［M］.北京：國防大學出版社，2004：7－11.

［10］ 史越東.指揮決策學［M］.北京：解放軍出版社，2005：40－46.

［11］ 縱 恒，王文偉，陳陽娟.大型石油化工儲罐區(qū)消防安全系統(tǒng)設計［J］.合肥工業(yè)大學學報：自然科學版，2012，35（9）：1259－1263.

［12］ 楊瑞平，郭齊勝，趙宏緒，等.C3I系統(tǒng)建模與仿真［M］.北京：國防工業(yè)出版社，2006：17－22.

［13］ 李常洪.多Agent合作機制與合作結(jié)構(gòu)研究［D］.天津：天津大學，2002.

［14］ 龐國峰，郝愛民，梁曉輝.一種計算機生成兵力系統(tǒng)自治實體行 為描述 原語 ［J］.系 統(tǒng)仿真 學 報，2000，12（4）：300－304.

［15］ 張 毅，胡勤友，施朝健.HLA與MAS在分布式仿真應用領域的應用比較［J］.計算機技術與發(fā)展，2006，16（l）：150－153.