Agent能力承諾協作的自適應圖規劃協議生成算法*

郭競知，劉 瑋，徐龍龍，陳 燈

(1.武漢工程大學計算機科學與工程學院，湖北 武漢 430073；2.智能機器人湖北省重點實驗室，湖北 武漢 430073)

1 引言

協作自適應系統CAS(Collective Adaptive System)由一些能夠在開放環境中為了實現系統全局目標而協作的具有自適應特征的組件構成[1-3]。CAS最重要的特性是自適應性和協作性[4]，即在動態環境下能夠調節自身能力或調節協作方式來完成系統全局目標。現有的多Agent預定義協作方法，主要通過已知或者能夠預測的條件信息在設計時制定多Agent協作機制，這類方法無法滿足運行時自適應協作的要求。

這個問題的解決方案之一是將設計時預定義的信息轉變為運行時的控制適應[5 - 7]。這類構建運行時模型方法都是建立在Agent能夠完成系統目標的基礎之上的，并沒有考慮Agent能力不足需要協作的情況[8]。在CAS中，若 Agent的可執行能力不能實現適應決策，就意味著 Agent無法單獨完成系統全局目標。此時，該Agent必須找到能夠為其提供所需能力的其他Agent進行協作。文獻[9]將能力(Capability)的概念引入適應方法，因為它可以代表動態和協作的特征。文獻[10]提出了在參與者之間創建承諾(Commitment)協議的方法來彌補只使用能力進行協作的缺陷。承諾表示多個能力為完成特定目標任務而進行的協作關系。文獻[11]引入承諾的概念來描述行為之間的邏輯關系。文獻[12]在承諾概念的基礎上提出了規范的操作語義，定義了一組適合于交際行為的語義。在此基礎上文獻[13]提出使用基于通信行為的Agent通信語言ACL(Agent Communication Language)，以改變現實的行為和行為的屬性。承諾具有規范的語義定義，在Agent行為交互時可以更大程度地表示協作。文獻[14]提出了一個能夠在運行時生成承諾協議的三階段框架，其中，動態創建共享協議通過生成、排序、協商協議來實現。然而，目前基于Agent行為的承諾協議在自適應效率以及在線生成方面仍存在局限。

為了應對Agent承諾協議在線運行時自適應的不足，研究人員提出了一種基于目標-能力-承諾GCC(Goal-Capability-Commitment)的元模型[15]。基于GCC的元模型使用能力描述Agent可執行操作，并加入承諾來表示Agent之間的能力協作，用以完成系統全局目標。使用GCC元模型，一方面使Agent能力在決策層上比Agent行為層能夠更好地匹配適應性目標，另一方面使用能力生成的承諾是在Agent相互理解對方能力的基礎上達成的協議，支持在線動態生成。

本文在此背景下，提出了一種基于能力承諾協作的自適應圖規劃協議CCGP(Capability Commitment collaboration Graph planning Protocol)生成算法。旨在保持自治Agent能適應動態環境優勢的同時，在能力/承諾失效情況下，通過量化能力和目標以及承諾和目標的匹配度來優化Agent能力承諾協作。本文以San Antonio Hospital使用的醫療垃圾AGV運輸系統MWT-AGV(the Medical Waste Automated Guided Vehicle Transportation)[16]為場景建立本體模型，來實現和驗證能力承諾協作圖規劃算法。

2 基礎概念

2.1 概念向量的語義相似度計算

單個Agent不能完成目標時，需要多個Agent協作，在協作時需要選擇使用能力、多個能力協作生成的承諾或者使用能力和承諾結合來完成目標。使用語義相似度計算，可以量化概念之間的匹配程度，在優化協作選擇的同時，還提高了選擇的精準度。文獻[17]提出基于相關節點的概念向量模型RNCVM(Relevancy Nodes based Concept Vector Model)來計算語義相似度。RNCVM將本體概念映射到樹結構中，通過概念節點的位置關系計算概念之間的語義相似度。

語義相似度表示2個概念具有共同特性的程度，利用RNCVM來計算核心概念節點的相似度。如圖1所示，以部分本體模型為例，以CartInfo為目標節點，將本體概念節點映射到樹結構中。以C1～C7表示能力概念，C1～C7為能力概念的向量化表示，dj為節點j(1≤j≤7)的局域密度。

Figure 1 Ontology structure instance representation圖1 本體結構實例表示

根據RNCVM可將實例中的概念向量表示為C1=(1,3,3,3,2,2,1),C2=(1,3,0,0,2,2,1),C3=(1,0,3,0,0,0,0),C4=(1,0,0,3,0,0,0),C5=(1,3,0,0,2,0,1),C6=(1,3,0,0,0,2,0),C7=(1,3,0,0,2,0,1)。此時，使用RNCVM計算給定的概念節點i和j對應的概念向量Ci,Cj的相似度。

因此，當給定本體結構，通過確定概念節點的向量數值，利用概念向量相似度計算公式能夠計算出任意2個概念節點之間的相似度數值。在多Agent協作完成復雜任務時，進行目標匹配不可避免地會遇到多種匹配選擇的情況，利用能力、承諾和目標的概念向量之間的相似度計算來提升規劃的容錯性。

2.2 上下文狀態的相似度計算

協作自適應系統中，上下文狀態特指自適應系統中的動態環境。GCC模型主要包含目標、能力、承諾和上下文狀態4個核心概念。上下文狀態是GCC模型的核心，是連接目標、能力、承諾的橋梁，既表示核心概念的屬性，又表述運行狀態。上下文狀態使用語義Web規則語言SWRL(Semantic Web Rule Language)的Atoms表示[18]。

SWRL中的原子有CA(ClassAtom)和IPA(IndividualProperty Atom) 2種表示形式。CA表示系統環境上下文狀態，IPA表示Agent個體上下文狀態。一個CA表示為一個二元組：CA=〈arg,classPredicate〉。一個IPA表示為一個三元組：IPA=〈arg1,propertyPredicate,arg2〉。因系統環境與Agent個體屬性狀態共同作用完成Agent協作，二者之間不涉及擇優，因此不同類型的上下文狀態之間不需要進行相似度計算。

圖2為領域場景中能力、目標、承諾和上下文狀態的部分實例。其中，能力(Capability)的實例由輸入約束(hasInConstraints)和輸出約束(hasOutConstraints)表示；目標(Goal)的實例由觸發條件(hasTriggerConditions)和最終狀態(hasFinalStates)表示；承諾(Commitment)實例由前提(hasAntecedent)和結果(hasConsequence)表示；上下文狀態的IPA實例由參數1(argument1)、參數2(argument2)和屬性謂詞(propertyPredicate)表示；上下文狀態的CA實例由參數1(argument1)和類謂詞(classPredicate)表示。

以圖2中的實例為例，介紹上下文狀態的相似度計算。

Figure 2 Some instances in the domain scene圖2 領域場景中的部分實例

2種類型的上下文狀態在計算相似度時都是根據對應參數的概念向量相似度來進行計算的。如果上下文狀態表示為CA類型，實例cs2=〈pickupPosition,Obtained〉和cs4=〈agvCall,Available〉的相似度計算可能存在3種情況：當classPredicate相同時，cs2和cs4參數因子的概念向量相似度決定了2個上下文狀態的相似度計算結果；當sim(pickupPosition,agvCall)=1時，2個上下文狀態相似度為1；而sim(pickupPosition,agvCall)≠1時，參數因子的概念向量相似度值就是2個上下文狀態相似度的值。其中，pickupPosition和agvCall分別為pickupPosition和agvCall的向量化表示。

3 能力承諾協作的自適應圖規劃協議生成算法

在自適應圖規劃方法中,Agent協作遇到多條路徑時需要進行選擇，根據能力和目標以及承諾和目標之間的語義匹配度結果來完成擇優。

下面以圖2中的領域場景能力、目標、承諾和上下文狀態的部分實例為例，來介紹目標和能力(或者承諾)之間的語義匹配度計算方法。

3.1 語義匹配度計算

計算一個能力Capability和一個目標Goal之間的語義匹配度SMD(Semantic Matching Degree)，實質是對此能力和目標的上下文實例進行相似度計算。本文在計算上下文狀態相似度的基礎上，提出一個能力Capability和一個目標Goal的語義匹配度計算公式為：

SMD(Capability,Goal)=

(1)

其中，csi∈In-constraints，csj∈TrigConditions，a是In-constraints中上下文狀態的數量,In-constraints為能力的輸入約束，TrigConditions為目標的觸發條件；csp∈FinalStates，csq∈Out-constraints，b是FinalStates中上下文狀態的數量，FinalStates為目標的最終狀態，Out-constraints為能力的輸出約束。例如，圖2實例中，C7和G13進行語義匹配度計算，a為3，b為1，SMD(C7,G13)=1.0。

同理，一個承諾Commitment和一個目標Goal的語義匹配度的計算公式為：

SMD(Commitment,Goal)=

(2)

其中，csi∈Antecedent，csj∈TrigConditions，m是Antecedent中上下文狀態的數量,Antecedent為承諾的前提；csp∈FinalStates，csq∈Consequent，n是FinalStates中上下文狀態的數量,Consequent為承諾的結果。例如，圖2中，Co和G13進行語義匹配度計算，m為3，n為1，SMD(Co,G13)=0.5。

3.2 能力承諾協作的自適應圖規劃協議

Agent根據系統需求進行任務分配和協作，以實現特定的系統全局目標。基于能力承諾協作的自適應圖規劃協議是為了尋找一條從初始狀態到目標狀態的最優路徑。在圖規劃的過程中，若某一目標可以由能力單獨完成，就使用能力進行規劃；若某一目標需要多個能力協作才能完成，且存在承諾的前提并滿足目標的觸發條件，就可以使用該承諾代替能力的協作來完成目標。

自適應圖規劃中用語義匹配度來判斷是否需要能力協作。根據計算出的匹配度數值范圍，將匹配分為3種類型：數值為1時，為精確匹配(Complete Match)；數值為(0，1)時，為包含匹配(Contained Match)；數值為0時，為不相交匹配(Disjoint Match)。同樣地，當圖規劃中存在能力協作時，根據承諾和目標的語義匹配度來判斷承諾是否能完成目標。

Agent能力承諾協作的自適應圖規劃算法以概念間的語義匹配度為基礎。從規劃的初始節點開始，取GCC模型中的能力集合與目標集合中的能力和目標，進行語義匹配程度的計算，根據匹配類型，選擇完成目標所需要的能力或是承諾來進行規劃。

圖規劃中的能力承諾協作核心規劃算法表示如算法1所示。該算法的輸入參數為初始狀態集合CSInit和目標狀態集合CSGoal，輸出為規劃圖gp。

算法1圖規劃中的能力承諾協作算法

輸入：MWT-GCC模型中的初始狀態集合CSInit,目標狀態集合CSGoal。

輸出：規劃圖gp。

1.Filef

2.OutputStreamout

3.GraphPlanninggp

4.foreachCSInit

5.doifisCo(CSInit)=truethen

6.caList←getNextCapability(CSInit)

7.inisList←getNextInitialStates(caList,CSInit)

8.iniToGoalCa(inisList,caList,CSGoal)

9.elseifisCo(CSInit)=falsethen

10.coList←getNextCommitment(CSInit)

11.inisList←getComNextInitialStates(coList,CSInit)

12.iniToGoalCo(inisList,coList,CSGoal)

13.out.close( )

14.returnf

15.gp←Proba(f)

16.returngp

算法第1～3行：定義文件f、字節輸出流out和規劃圖gp。第4行：遍歷上下文狀態判斷使用哪種協作圖規劃。第5～8行：進行能力協作圖規劃。如果該上下文狀態不能進行承諾協作，就使用能力進行協作圖規劃。第9～12行：進行能力承諾協作圖規劃。如果該上下文狀態存在承諾協作，就使用能力和承諾協作進行圖規劃。第13和14行：關閉字節輸出流返回文件f。第15行：使用Proba(f)方法對文本圖形描述語言Dot圖規劃語句進行解析繪制。第16行：返回使用Graphviz繪制出的規劃圖gp。

4 實驗結果與分析

為了驗證本文提出的基于圖規劃的能力承諾協作規劃算法的效率，以醫療垃圾AGV運輸仿真系統(MWT-AGV)為場景進行實驗。MWT-AGV場景中的多種Agent需要通過協作跨樓層完成醫療垃圾的運輸。場景主要包括5類Agent構件，分別是：Cart(裝載醫療垃圾)、Pickup(放置裝有醫療垃圾的Cart)、Cart Sensor(檢測Cart信息的傳感器)、AGV(運輸醫療垃圾)、Cart Elevator(運載Cart和Pickup到其他樓層的電梯)。場景中設置有多個Pickup放置點，每個Pickup放置點均有一個有效Cart Sensor可用于讀取RFID標簽信息。進行醫療垃圾運輸時，即醫療垃圾裝在Cart中，放置在醫院指定的Pickup上。此時，Cart Sensor感應到Pickup上放有Cart且裝載的醫療垃圾在荷載范圍內，會自動讀取Cart以及Cart內的醫療垃圾信息，并向Decision Agent發出調用通知，Decision Agent會選擇調用距離最近的空閑AGV來執行運輸任務。若到達目的地需要進行跨樓層運輸，就需要借助Cart Elevator來完成運輸任務。

本文使用Protégé工具構建場景GCC模型，然后設計2組實驗從不同的角度分析本文算法的性能。實驗環境包括Windows 7 64位操作系統，處理器為Intel(R) Core(TM) i5-6000，主頻為3.70 GHz，內存為8 GB，使用Dot語言繪制規劃圖。

Figure 3 Capability commitment collaboration generated adaptive graph-planning圖3 能力承諾協作生成的自適應規劃圖

首先，使用能力協作、能力承諾協作分別生成自適應規劃圖。如圖3所示，圖3a為能力協作生成的自適應規劃圖，圖3b為能力承諾協作生成的自適應規劃圖，方框中C表示能力，橢圓cs表示上下文狀態，Co表示承諾。接下來，進行2組實驗來驗證CCGP的效率，并且通過實驗來觀察CCGP在哪種情況下可以實現效率最大化。

實驗1加入承諾的能力協作。

實驗1通過控制在規劃中加入承諾與否，分析只使用能力進行規劃的能力規劃CG(Capability Graph planning)和加入承諾后的能力-承諾規劃CCG(Capability-Commitment Graph planning)在規劃步數和執行時間上的表現。

為了評估加入承諾后的圖規劃在執行步數和運行時間上的效率，采用控制變量的方法進行對比實驗。在相同場景和能力數量下，比較只使用能力進行圖規劃和能力中加入承諾進行圖規劃的表現。使用10個能力和9個目標作為場景基礎進行實驗，為減少實驗數據受時間和實驗設備的干擾，每組實驗均取3組不同時間測量的10次實驗的平均值作為結果，實驗結果中的規劃步數以步為單位，執行時間以ms為單位。

進行實驗后發現，只使用能力進行規劃的CG規劃步數為9，執行時間為1 264.3 ms；而加入承諾后的CCG規劃步數為8，執行時間為1 233.0 ms。分析可知：加入承諾的圖規劃在規劃步數和執行時間上都優于只使用能力的圖規劃，加入承諾的圖規劃在規劃步數上并沒有較大的改善，但在執行時間上大約提高了40 ms。可見，多個Agent協作完成復雜目標的效率更高。

縮短規劃的執行時間對于提高圖規劃的效率至關重要。為了驗證能力-承諾規劃的算法在不同規模中的效率，進行了另一組實驗，比較CG和CCG隨著能力個數增加時，執行時間的表現。當領域場景模型中的能力個數增加至20,30,40時，在同一條件下，觀察CG和CCG的執行時間。

由隨能力增加的執行時間實驗結果(如圖4所示)可知：當場景模型中的能力個數為30時，使用CCG算法的時間消耗比CG算法少105.4 ms，而當能力個數增加至40時,CG的效率卻高于CCG。當能力個數為40時，加入承諾圖規劃的遍歷次數增加，效率反而降低。分析可知：加入承諾的圖規劃CCG算法的最佳應用場景是能力為20～30個，過于簡單或過于復雜的場景下，使用加入承諾的能力-承諾圖規劃算法無法得到最佳效率。系統中能力個數過少，規劃時可選擇完成目標的能力就越少，增加了完成目標時間；而能力個數太多，選擇時需要進行計算和匹配的時間將增加，效率降低。

Figure 4 Graph-planning execution efficiency based on CG and CCG methods圖4 基于CG和CCG方法的圖規劃執行效率

實驗2加入語義相似度計算的協作。

實驗2在CCG算法的基礎上，在規劃的過程中控制是否加入語義相似度計算，通過對比使用相似度SD(Similarity Degree)計算和不使用相似度NSD(No Similarity Degree)計算以及使用字符串匹配SMM(String Matching Method)的執行時間，來驗證本文算法的有效性。

圖規劃過程中加入相似度計算可以更好地進行規劃路徑擇優。在相同場景和能力數量下，比較SD方法進行圖規劃和NSD方法進行圖規劃的表現，同時加入使用SMM的實驗進行對比。為了增強實驗數據可靠性，本實驗為減少實驗數據受時間和實驗設備的干擾，每組實驗均取3組不同時間測量的10次實驗的平均值作為結果，實驗結果中執行時間以ms為單位。如圖5所示，在場景模型能力個數為10,20,30,40的情況下分別進行了4組對比實驗。

Figure 5 Graph planning execution efficiency based on SD, NSD and SMM methods圖5 基于SD、NSD、SMM方法的圖規劃執行效率

由實驗結果可知：加入相似度計算的SD方法進行圖規劃消耗的時間遠遠小于未加入相似度計算的NSD方法消耗的時間，而使用字符串匹配的SMM方法在時間消耗上沒有比NSD方法好太多。在場景中的能力個數為20和40時，3種方法消耗的時間相差較大，在40個能力時SD方法效率最高，能力個數為30時效率相對較低。分析可知：在圖規劃中加入相似度計算可以明顯提高圖規劃效率，在較簡單和較復雜的場景下使用都可以提高效率。能力個數影響相似度計算的效率，能力個數過少可加快計算選擇；能力個數過多，使用相似度計算精確匹配，可提高效率。

通過2組對比實驗發現，本文提出的能力承諾協作規劃算法可以有效減少圖規劃中的決策時間，提高圖規劃效率。而之前提出的基于能力的規劃算法進行規劃時，首先會生成多條路徑，然后再根據能力和目標匹配選取優化路徑，決策時間長；基于能力承諾協作規劃的算法，通過計算相似度來選擇最優的能力或承諾進行規劃，直接生成決策，不僅減少了規劃步數，還大幅縮短了決策時間。

5 結束語

本文提出的基于能力承諾協作的自適應圖規劃協議生成算法(CCGP)主要有兩方面貢獻：第一，使用工具完善領域場景的目標-能力-承諾(GCC)建模，將目標和能力進行匹配，動態生成承諾；以能力和承諾協作來完成系統目標，在能力失效的情況下生成承諾，以能力和承諾2種方式來完成協作。第二，對概念向量進行語義相似度計算，通過計算能力、目標、承諾之間的匹配度來量化協作的選擇；計算能力和目標、承諾和目標之間的匹配度，在進行協作選擇時，選擇匹配度較高的進行協作，從而做出最優協作決策。

接下來，將致力于找到一種方法，在上下文狀態建模時引入時間的概念，使得在完善的自適應場景中，上下文狀態隨時間的推移發生變化，從而引發動態規劃。在此基礎上進行的動態協作規劃將更能滿足自適應系統的需要。