Agent能力承諾協(xié)作的自適應圖規(guī)劃協(xié)議生成算法*

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

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

1 引言

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

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

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

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

2 基礎概念

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

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

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

Figure 1 Ontology structure instance representation圖1 本體結(jié)構實例表示

根據(jù)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計算給定的概念節(jié)點i和j對應的概念向量Ci,Cj的相似度。

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

2.2 上下文狀態(tài)的相似度計算

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

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

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

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

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

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

3 能力承諾協(xié)作的自適應圖規(guī)劃協(xié)議生成算法

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

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

3.1 語義匹配度計算

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

SMD(Capability,Goal)=

(1)

其中，csi∈In-constraints，csj∈TrigConditions，a是In-constraints中上下文狀態(tài)的數(shù)量,In-constraints為能力的輸入約束，TrigConditions為目標的觸發(fā)條件；csp∈FinalStates，csq∈Out-constraints，b是FinalStates中上下文狀態(tài)的數(shù)量，F(xiàn)inalStates為目標的最終狀態(tài)，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中上下文狀態(tài)的數(shù)量,Antecedent為承諾的前提；csp∈FinalStates，csq∈Consequent，n是FinalStates中上下文狀態(tài)的數(shù)量,Consequent為承諾的結(jié)果。例如，圖2中，Co和G13進行語義匹配度計算，m為3，n為1，SMD(Co,G13)=0.5。

3.2 能力承諾協(xié)作的自適應圖規(guī)劃協(xié)議

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

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

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

圖規(guī)劃中的能力承諾協(xié)作核心規(guī)劃算法表示如算法1所示。該算法的輸入?yún)?shù)為初始狀態(tài)集合CSInit和目標狀態(tài)集合CSGoal，輸出為規(guī)劃圖gp。

算法1圖規(guī)劃中的能力承諾協(xié)作算法

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

輸出：規(guī)劃圖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、字節(jié)輸出流out和規(guī)劃圖gp。第4行：遍歷上下文狀態(tài)判斷使用哪種協(xié)作圖規(guī)劃。第5～8行：進行能力協(xié)作圖規(guī)劃。如果該上下文狀態(tài)不能進行承諾協(xié)作，就使用能力進行協(xié)作圖規(guī)劃。第9～12行：進行能力承諾協(xié)作圖規(guī)劃。如果該上下文狀態(tài)存在承諾協(xié)作，就使用能力和承諾協(xié)作進行圖規(guī)劃。第13和14行：關閉字節(jié)輸出流返回文件f。第15行：使用Proba(f)方法對文本圖形描述語言Dot圖規(guī)劃語句進行解析繪制。第16行：返回使用Graphviz繪制出的規(guī)劃圖gp。

4 實驗結(jié)果與分析

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

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

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

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

實驗1加入承諾的能力協(xié)作。

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

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

進行實驗后發(fā)現(xiàn)，只使用能力進行規(guī)劃的CG規(guī)劃步數(shù)為9，執(zhí)行時間為1 264.3 ms；而加入承諾后的CCG規(guī)劃步數(shù)為8，執(zhí)行時間為1 233.0 ms。分析可知：加入承諾的圖規(guī)劃在規(guī)劃步數(shù)和執(zhí)行時間上都優(yōu)于只使用能力的圖規(guī)劃，加入承諾的圖規(guī)劃在規(guī)劃步數(shù)上并沒有較大的改善，但在執(zhí)行時間上大約提高了40 ms?？梢?，多個Agent協(xié)作完成復雜目標的效率更高。

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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