一種基于３ＡＰＬ的多ａｇｅｎｔ合作系統(tǒng)

摘要：提出了一種新的基于3APL的多agent合作系統(tǒng)。引入合作規(guī)劃表達式給出基于擴展巴克斯范式(EBNF)個體agent的3APL語法。利用推理規(guī)則、結構結合變換規(guī)則等概念提出新的多agent合作操作語義。并深入研究多agent合作慎思循環(huán)過程，通過例子說明了多agent間如何合作產生和修正規(guī)劃的過程。

關鍵詞：3APL；合作；變換規(guī)則；合作慎思循環(huán)

中圖分類號：TP18文獻標志碼：A

文章編號：1001－3695(2008)03－0779－03

面向agent的理論與技術研究是人工智能、軟件工程、并行與分布計算、Internet技術、機器人技術等眾多研究領域的重要研究內容。面向agent程序設計(AOP)是agent理論與技術研究內容之一[1]。最早提出面向agent程序設計概念的是Shoham[2]。到目前為止，人們已經提出了多種面向agent程序設計語言。根據語言實現技術的差異主要分為三類[3]：a）基于LISP技術，如agent－0、agentK等；b）基于邏輯技術，如CONGOLOG、AOPLID、3APL；c）基于對象技術，如JAL等。這些語言大多存在缺乏對合作問題求解的具體考慮和難以實現等問題。由于多agent系統(tǒng)是分布式人工智能的重要研究方向之一，其主要研究目標是協(xié)調和組織多個agent完成一個共同的目標。本文基于3APL提出一種新的多agent合作系統(tǒng)。

3APL是一個結合了命令式程序設計語言思想和邏輯程序設計思想的面向agent程序設計語言。其平臺[4]由Java實現。它繼承了傳統(tǒng)命令式程序設計的許多結構和機制，將agent視為由信念和目標兩個認知部件構成的智能計算實體。信念描述了agent對所處的外部世界的認識和理解，目標則反映了agent期望實現的某種狀態(tài)。Agent對信念庫的查詢借鑒了邏輯程序設計的思想，將它視為一個證明的過程。Hindriks等人[5]利用實用推理規(guī)則(practical reasoning rule)來動態(tài)地管理和修正agent規(guī)劃和目標，從而使得agent能夠表現出一定的理性思考能力。3APL通過變換系統(tǒng)(transition system)方式定義其操作語義。另一種面向agent程序設計語言的代表作是郭磊等人[1]基于開放式情景演算OSC(open situation calculus)提出的一種意向驅動式面向agent程序設計語言AOPLID。雖然3APL[5，6]與AOPLID都有各自的特點和適應性，但都缺乏對多agent合作機制的刻畫。本文基于3APL提出一種新的多agent合作系統(tǒng)，并提出由變換系統(tǒng)定義的多agent合作操作語義。深入研究并刻畫了多agent合作慎思循環(huán)過程，通過實例說明了其合作求解過程，拓展了Hindriks等人的工作。

1語法

假設L是邏輯聯(lián)結詞為┐、∧的一階語言。表示邏輯蘊涵，┬表示重言式，┴表示矛盾式。信念語言LB，目標語言LG，規(guī)劃語言LP，有LB，LG，LPL。

交互推理規(guī)則用于產生實現目標的規(guī)劃。規(guī)劃推理規(guī)則類似于目標推理規(guī)則，用于修正和放棄規(guī)劃。

定義4Agent是一個五元組〈σ，γ，R，τ，ξ〉。其中：信念σ∈LB；目標γ∈LG；agent規(guī)則集R=2GR×2IR×2PR；動作信念更新函數τ:BasicActions×LB→LB，表示agent執(zhí)行某一基本動作而對原有信念產生的影響；ξ為與其他agent共享的環(huán)境。有〈σ，γ，R，τ，ξ〉B βσβ，〈σ，γ，R，τ，ξ〉Gκγκ。

定義5棧(stack)：agent棧S=s|s.S。“.”表示壓棧。棧元素s=〈，π，δ，ρ〉。其中：當前要實現的目標∈LG；實現所采用的規(guī)劃π∈LP，對應于實現的交互推理規(guī)則δIR和規(guī)劃推理規(guī)則ρPR。

定義6 結構(configuration)：個體agent結構是元組〈σ，r，S〉。其中：σ、r、ξ同定義4，S同定義5。多agent合作系統(tǒng)結構是元組〈A1，…，An，ξ〉。其中：Ai(1≤i≤n)是個體agent結構；ξ是多agent系統(tǒng)共享環(huán)境。

為了描述多agent間的合作，以下引入合作規(guī)劃表達式〈co_plans〉，給出了基于EBNF (extended backusnaur form)個體agent的3APL語法。〈co_plans〉刻畫了多agent間發(fā)送消息并行同步合作關系。EBNF擴展了巴克斯范式，是一種語法規(guī)范。“::=”表示賦值語句，也可以寫成“:=”；“”間表示關鍵字或符號；〈〉間為表達式；“?”表示前面的表達式出現0次或1次；“*”表示前面的表達式出現n次(n≥0)；“|” 表示可選擇的。本文使用〈atom〉表示原子公式，該原子公式可以包含形如[a，b，[5，c]]、 [X|Y] 或[a，[f，c，n]|T]的類prolog表[7]；〈ground_atom〉表示沒有變量的原子公式；〈Atom〉表示首字母大寫的謂詞表達式；〈ident〉表示字符串；〈var〉表示變量；〈query〉是信念、目標查詢表達式。

Load可以載入外部的prolog文件，如多agent合作共享的環(huán)境信息。

能力(〈capabilities〉)描述agent相信先條件(信念查詢語言〈query〉)時，有能力執(zhí)行〈Atom〉并使得執(zhí)行后的結果為后條件(〈literals〉)。

信念庫(〈beliefs〉)描述了agent對外部環(huán)境的認知和理解，為制度規(guī)劃提供知識依據。如信念庫BeliefBase：{on(a，b). on(b，c). on(c，fl).Top(Y):not(on(X，Y)).}表明agent相信木塊a在b上、木塊b在c上、木塊c在地板上。如果沒有其他東西在一木塊上，那么該木塊就處于最高處。在3APL程序設計過程中，不同的agent均可以用load結構載入用prolog程序寫的初始信念文件[7]。

目標庫(〈goals〉)描述了agent期望實現的某種狀態(tài)，并為之努力。如目標庫GoalBase：{on(b，fl) and on(c，a) ，on(a，fl)}表明agent有兩個目標，即實現木塊b在地板上且木塊c在a上與實現a在地板上。

規(guī)劃生成規(guī)則(〈p_rules〉)用于產生與實現目標匹配的規(guī)劃庫。κ←β|π∈IR表示agent相信β并有具體目標κ，那么由規(guī)劃生成規(guī)則集可以得到規(guī)劃π。如果κ為空目標，那么得到的π為agent純反應行為。

規(guī)劃修正規(guī)則(〈r_rules〉)用于修正和放棄原有的規(guī)劃。πh←β|πb∈PR表示agent有規(guī)劃πh并且相信β，那么agent根據規(guī)劃修正規(guī)則集PR用πb替代πh。如果πh是規(guī)劃π的前綴(如π=πh、π′)，那么替換的結果就是πb、π′。

多agent合作規(guī)劃的協(xié)商和協(xié)調規(guī)劃執(zhí)行通過send(receiver、performance、content)和JavaSync(classname、method、retList)完成。因為3APL 平臺[4]由Java實現，在這里調用Java類方法實現多agent合作間的同步，將返回值存入列表retList。

2語義

3APL多agent合作語義是一種操作語義。該操作語義由變換系統(tǒng)[8]來定義。變換系統(tǒng)是一個結構到另一個結構間的轉換并相對應一個簡單的計算步驟，可以表示為二元組〈Γ，→〉。其中：Γ為agent結構集，→Γ×Γ。以下給出了基于變換規(guī)則的多agent合作操作語義：

TR1描述了agent非空棧的執(zhí)行，單個棧元素轉換到復合棧元素的過程。顯然，當S=E時，上下變換等價。

TR2描述了agent初始棧(空棧)到非空棧的變換。如果agent相信β，是實現γ的子目標，┬←β|屬于agent目標推理規(guī)則并且〈θ，δ，ρ〉屬于agent規(guī)則R，那么agent初始棧就轉換為棧元素〈，Ω，δ，ρ〉。

TR3描述了參與合作的多agent系統(tǒng)結構的轉換，合作環(huán)境共享信息由ξ轉換為ξ′。

TR4描述了多agent合作規(guī)劃的產生。參與合作的多agent通過交互推理規(guī)則產生實現共同目標的規(guī)劃π‖π′，自身agent只執(zhí)行規(guī)劃π，其他合作agent(s)執(zhí)行規(guī)劃π′。δ′是δ移除已經應用過的規(guī)劃交互規(guī)則，為的是不讓agent多次重復產生相同合作規(guī)劃。

TR5描述了agent執(zhí)行規(guī)劃的首動作a后，根據動作信念更新函數移除已經實現的目標κ，同時更新信念σ′、目標γ′和棧里的元素π。

TR6描述了多agent合作規(guī)劃的修正。參與合作的多agent通過各自合作規(guī)劃修正推理規(guī)則，分別使各自的規(guī)劃πh‖π′h轉換為規(guī)劃πb‖π′b，而后續(xù)非合作規(guī)劃的內容π保持不變。

TR7描述了agent或多agent合作成功后棧元素的移除，將已經實現的目標移出棧。當agent完成所有目標后(TR7的特殊情景)，此時γ為空，S=E。

3合作慎思循環(huán)

前面已經詳細敘述了基于3APL的多agent合作語法和語義。為了運行3APL平臺，需要用一個解釋器來判定應用哪個規(guī)則、什么時候執(zhí)行動作或更新信念。慎思循環(huán)過程在這里充當解釋器的角色。

圖1是多agent合作慎思循環(huán)過程結合Wooldridge等人[9]提出的合作問題求解過程4階段的流程圖。合作意識產生后首先匹配IR生產規(guī)劃，然后匹配PR應用規(guī)劃修正規(guī)則，直至有agent認為可以完成目標的規(guī)劃，否則掛起等待新消息到來。執(zhí)行規(guī)劃后，檢查目標是否實現，如果實現則退出；否則根據環(huán)境變化繼續(xù)循環(huán)匹配IR。

4舉例分析

Agent a和agent b要合作取得處在高處的apple。初始公共環(huán)境信念有a和b在椅子旁、a比b高、如果一物體上沒有其他東西，那么該物體處于頂部。表示如下：

σa=σb={near(chair，a)，near(chair，b)，taller(a，b)，high(apple)，top(Y):-not(on(X，Y))}

γa=γb={get(apple)}

=near(chair，apple)

//根據TR2，得到當前目標

π‖π′=movenear(chair，apple)‖Ω

//根據TR4產生合作規(guī)劃

//a、b發(fā)現椅子上有一木塊block

πh‖π′h←┐top(chair)|{movenear(chair，apple)‖move(block，floor)}

//根據TR6得到合作修正規(guī)劃a搬椅子，b搬木塊

┬←top(chair)|{movenear(chair，apple)‖goto(apple)}

//根據TR4

π‖π′=buttress(chair)‖climb(chair)

//根據TR4

πh‖π′h←taller(a，b)|{climb(chair)‖buttress(chair)}

//根據TR6得到合作修正規(guī)劃

最后由a完成，實現目標

上述例子研究了兩個agent從對公共環(huán)境的認識到合作求解的過程。由當前目標產生合作規(guī)劃，再根據合作修正規(guī)劃產生新的規(guī)劃直至完成目標。

5結束語

本文基于3APL提出一種新的多agent合作系統(tǒng)。通過引入合作規(guī)劃表達式給出基于EBNF個體agent的3APL語法。利用推理規(guī)則、結構結合變換規(guī)則等概念給出新的多agent合作操作語義。結合經典多agent合作問題求解過程，深入研究多agent合作慎思循環(huán)過程，并通過例子說明了多agent間如何合作產生和修正規(guī)劃的過程。

此后的工作為了適應動態(tài)的、不可預知的環(huán)境因素，著重研究動態(tài)變化規(guī)劃生成規(guī)則與規(guī)劃修正規(guī)則；另一方面，多agent合作協(xié)商邏輯、尋找合作規(guī)劃最優(yōu)等問題也是后續(xù)文章研究的重點。

參考文獻：

[1]郭磊，戈也挺，陳世福，等.一種意向驅動式面向agent程序設計語言[J].軟件學報， 2003，14(3):383－391.

[2]SHOHAM Y.Agentoriented programming[J].Artificial Intelligence，1993，60:51－92.

[3]毛新軍.面向主體的軟件開發(fā)[M]. 北京：清華大學出版社，2005.

[4]DASTANI M.3APL platform:UserGuide [EB/OL]. http:// www. cs.uu.nl/3apl /download.html.

[5]HINDRIKS K V，BOER F S de，HOEK W van der，et al.Agent programming in 3APL[J].Int J of Autonomous Agents and MultiAgent Systems，1999，2(4):357－401．

[6]RIEMSDIJK M B van，DASTANI M，MEYER J J C，et al.Goaloriented modularity in agent programming[C]//Proc of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems.[S.l.]:ACM Press，2006.

[7]DASTANI M，RIEMSDIJK M B van，MEYER J J C.Programming multiagent systems in 3APL.BORDINI R H， DASTANI M，DIX J， et al.[C]//Proc ofMultiagent Programming: Languages， Platforms and Applications. Berlin:Springer，2005.

［8］PLOTKIN G D.A structural approach to operational semantics[M].Denmark: DAIMI， 1981.

[9]WOOLDRIDGEM，JENNINGS N R.The cooperative problem solving process[J].Journal of Logic Computation，1999，9(4):563－592.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”