基于請求/服務(wù)協(xié)作模型的多Agent建模方法

宋昌統(tǒng)，王輝

0 引言

智能通信是人工智能領(lǐng)域中研究的一大熱點(diǎn)，在多Agent系統(tǒng)中，不同Agent之間的通信是非常必要的，這是實現(xiàn)協(xié)作的重要途徑。當(dāng)有多個Agent同時向同一個服務(wù)主體提出服務(wù)請求，或者Agent向一個正在為其他Agent服務(wù)的服務(wù)主體提出請求時，被請求的服務(wù)主體就需要尋求其他服務(wù)主體的幫助，就需要通信和協(xié)作，以同時滿足不同Agent的請求。因此，Agent具有自主性，反應(yīng)性，社會性和推理能力等特點(diǎn)，能夠用來解決傳統(tǒng)的人工智能所不能解決的環(huán)境適應(yīng)性、動態(tài)環(huán)境推理和規(guī)劃、信息不完全等問題，使用Agent方法已經(jīng)成為研究復(fù)雜系統(tǒng)的重要手段。

現(xiàn)實生活中大多數(shù)系統(tǒng)是屬于多Agent 系統(tǒng)，因此研究多 Agent 系統(tǒng)是一件非常有實際意義的事情。本文在ConGolog中顯式定義了通信動作，并提出一個請求/服務(wù)協(xié)作模型，這樣，Agent就可以在動態(tài)環(huán)境下進(jìn)行面向目標(biāo)的自主協(xié)作行為規(guī)劃。同時，在ConGolog中引入并發(fā)，解決了單個Agent所不能解決的問題。

1 情景的演算

情景的演算是人工智能大師McCarthy在1963年針對動態(tài)領(lǐng)域中的問題求解和邏輯程序設(shè)計首次提出的，是一個用一階謂詞邏輯描述世界的方法。情景演算方法可以在動態(tài)環(huán)境下進(jìn)行面向目標(biāo)的自主行為推理。直觀上，一個情景就是世界的一個快照，在情景演算中使用情景(situation)類表示，而情景的變化是動作(action)的結(jié)果，在本體論中，動作是改變事物狀態(tài)的基本手段，動作函數(shù) do表示為：action×situation→situation。如果在情景s下實行動作a將得到另一個情景s’，那么情景s’可表示為do(a,s)。更多情景演算的概念和情景演算的公理系統(tǒng)參見文獻(xiàn)[2]。

2 Golog與ConGolog

2.1 Golog

2.2 ConGolog

Golog語言是針對單個Agent的，其動作之間在時間上的關(guān)系只有順序，在實際的運(yùn)用中Golog語言受到很多的限制，例如沒有感知只能離線規(guī)劃，在規(guī)劃的過程中不能再次接受其他的規(guī)劃任務(wù)，尤其明顯的是在多Agent系統(tǒng)的開發(fā)過程中遇到的并發(fā)動作的處理上。為了解決上述的問題，出現(xiàn)了很多新的情景演算語言[5]，其中較為有影響的是 De Giacomo和Yves Lesperance等人提出了并發(fā)程序設(shè)計語言ConGolog。ConGolog在Golog的基礎(chǔ)上增加了并發(fā)處理，優(yōu)先級的并發(fā)以及中斷處理。在ConGolog中，初始情景可以不完全指定，而Agent可以根據(jù)情景演算的公理自己定義基本動作。

ConGolog被賦予了一種結(jié)構(gòu)化的操作語義，稱為計算語義。根據(jù)該語義的“單步變遷”的概念[6]，ConGolog引入了兩個特殊的謂詞 Final(δ,s)和 Trans(δ,s,δ’,s’)。其中 Final(δ,s)表示程序 δ可以合法的終止在情景 s。Trans(δ, s, δ’, s’)表示程序δ在情景s 下執(zhí)行一步(即執(zhí)行一個基本動作), 從而將情景s變化到情景s’, 并余下程序δ’未執(zhí)行。實際上，程序δ和情景s是一個配置空間(configuration)<δ,s ＞，而trans的作用是通過執(zhí)行一個可執(zhí)行的基本動作，將這個配置空間改變成另一個配置空間<δ’, s’＞。

使用final和trans謂詞的好處不僅在于可以描述Golog語言，更重要的是可以描述并發(fā)，帶優(yōu)先級的并發(fā)，中斷等。在Congolog中并發(fā)動作表示為δ1||δ2, δ1和δ2表示兩個并發(fā)執(zhí)行的動作，δ1 ＞＞δ2表示δ1和δ2是帶有優(yōu)先級的兩個并發(fā)動作，其中δ1的優(yōu)先級高于δ2，當(dāng)動作δ1執(zhí)行完或者不能執(zhí)行時才執(zhí)行動作δ2。δ||表示多個該動作δ并發(fā)執(zhí)行。Φ→δ表示中斷，Φ表示觸發(fā)條件，δ是中斷的處理程序，當(dāng)觸發(fā)條件滿足時就執(zhí)行程序δ，否則δ將不會被執(zhí)行。使用final和trans謂詞可以將這四種復(fù)雜動作表述為[7]：

(1)并發(fā)

(2)優(yōu)先級并發(fā)

(3)多個相同動作并發(fā)

可見，多個相同動作的并發(fā)是參照了基本的并發(fā)動作的語義進(jìn)行解釋的。

(4)中斷表示當(dāng)允許中斷時(interrupts_running為真)，如果觸發(fā)條件滿足的話就執(zhí)行程序δ，否則就為false。

3 請求/服務(wù)協(xié)作的模型

3.1 模型的簡介

在請求/服務(wù)協(xié)作模型中，Agent被分為兩種類型，分別為請求 Agent(ReqAgt)和服務(wù) Agent(SerAgt)。其中，請求Agent可以向任何服務(wù)Agent提出服務(wù)請求，服務(wù)Agent也可以為任何請求Agent服務(wù)，多個服務(wù)Agent之間通過通信動作[8]以協(xié)作的方式，共同為請求 Agent提供服務(wù)。請求/服務(wù)協(xié)作模型，如圖1所示：

圖1 請求/服務(wù)協(xié)作模型

在該模型中，當(dāng)有請求Agent向服務(wù)Agent提出請求時，服務(wù)Agent首先要判斷自己能不能完成該請求，如果可以，則不用請求其他Agent，直接交由規(guī)劃部分進(jìn)行規(guī)劃。如果不能完成，此時服務(wù)Agent就通過通信方式，請求其他的服務(wù) Agent來完成。也就是說，此時服務(wù) Agent對請求Agent的請求負(fù)有責(zé)任，由ServAgt1負(fù)責(zé)請求另外的一個服務(wù)Agent(ServAgt2)完成。ServAgt2接到請求后也會根據(jù)自己是否能完成該請求來給 ServAgt1進(jìn)行回復(fù)。ServAgt1接到ServAgt2的回復(fù)后，根據(jù)回復(fù)內(nèi)容進(jìn)行操作，如果 ServAgt2不同意，那么 ServAgt1就需要詢問另外一個服務(wù)Agent(ServAgt3)，直到有服務(wù)Agent答應(yīng)為RequAgti服務(wù)，如果其他所有的服務(wù)Agent都被詢問過了，而且沒有收到肯定的答復(fù)，那么就告知 RequAgti系統(tǒng)忙；如果ServAgt2同意提供服務(wù)，則將請求中的服務(wù)對象換成ServAgt2，然后進(jìn)入規(guī)劃。就是說，如果ServAgt2同意提供服務(wù)，就表示可以讓規(guī)劃部分安排其為RequAgti服務(wù)。

例如，在送咖啡的例子中，請求 Agent1(bill)向服務(wù)Agent(waiter1)提出請求 wantCoffee(bill,waiter1)，要一杯咖啡，而在waiter1還沒有為bill服務(wù)完的時候，請求Agent2也向waiter1提出請求wantCoffee(sue,waiter1)。此時，waiter1就需要向其他的服務(wù)Agent請求協(xié)作，waiter1首先向waiter2提出請求，如果waiter2同意協(xié)作，那么就會把自己的名字作為此次通信的結(jié)果告知waiter1，waiter1就會將sue的請求waiter1的名字換成waiter2的名字，然后進(jìn)入規(guī)劃；如果waiter2在為另一個請求 Agent服務(wù)，那么就不同意協(xié)作，回答impossible。waiter1在得到impossible的回復(fù)后就會請求另外的服務(wù) Agent(waiter3)，直到詢問過所有的服務(wù)Agent，如果還沒有肯定的答復(fù)，那么則告知sue，此時系統(tǒng)忙，請稍后再次請求。一個服務(wù)Agent對于請求Agent的請求的處理過程，如圖2所示：

圖2 服務(wù)Agent對請求的處理流程

3.2 請求/服務(wù)模型的協(xié)作實現(xiàn)

請求Agent向服務(wù)Agent提出請求時，如果Cond條件滿足，那么請為我執(zhí)行任務(wù) Task。接收者Receiver收到該消息后，對條件進(jìn)行判斷，即 holds(Cond,H)，如果條件成立，那么將通信結(jié)果賦值為愿意完成，如果不成立，則賦值為不愿意。代碼，如圖3所示：

圖3 對請求的處理過程

根據(jù)通信方式，對于消息的回復(fù)，服務(wù)Agent只需要將結(jié)果賦值給通信結(jié)果，不必再進(jìn)行一次通信。如果發(fā)送愿意的消息，那么就表示此次通話的結(jié)果是請求得到滿足，那么就把同意者的ID賦值給通話的結(jié)果，如果不愿意，那么就將另一個結(jié)果賦值給通話結(jié)果，此處的賦值用戶可自定義，本文使用impossible表示不愿意。代碼，如圖4所示：

圖4 根據(jù)愿意/不愿意給通話結(jié)果賦值

4 實例

為了在 VRML中展現(xiàn)多 Agent的協(xié)作行為，本文在VRML虛擬場景中進(jìn)行了仿真。針對送咖啡的例子，模擬多Agent請求，本實例定義了3個服務(wù)Agent，waiter1、waiter2和 waiter3。giveCoffee(Person,Rob)表示主體 Rob把咖啡交給了用戶 Person。startGo(Loc1,Loc2,Rob)表示主體 Rob從Loc1走向Loc2，Loc1和Loc2都是地點(diǎn)名稱，本文中的地點(diǎn)名稱可能是咖啡機(jī) cm，也可能是用戶的辦公室office(Person)。 下面是Agent之間的協(xié)作流程。

(1)流

流的初始值的定義可以使用initially(Fluent,Value)來定義，is_busy(Rob)表示服務(wù)Agent忙，needServe(Person,Rob)則表示Person需要Rob為其服務(wù)，hasCoffee(Person)表示用戶Person此時已經(jīng)有了咖啡。

(2)外部動作

Exog_action(wantCoffee(person,Rob)):-isPerson(Person),isRob(R ob).其中isPerson(Person),isRob(Rob)是對用戶的輸入做檢查。wantCoffee(bill,waiter1)是合法的外部動作，表示bill請求waiter1為其倒一杯咖啡。

(3) 多Agent交互部分

首先對Agent的請求進(jìn)行檢查exog_action_check/3，看Agent請求的服務(wù)Agent(Rob)在當(dāng)前情景下是否有空，沒空的話，那么被請求的 Agent就開始同其他的服務(wù) Agent進(jìn)行交互，請求他們?yōu)樵?Agent服務(wù)，isRob(Rob2),+(Rob2=Rob1)就表示Rob2是另外的一個服務(wù)Agent，請求的消息為 inform(Rob1,Rob2, request(is_busy(Rob2)=off,H,serve_for(Person)),R_Result)，表示Rob1，即被用戶Person請求但目前忙的服務(wù)Agent，向Rob2發(fā)送消息，內(nèi)容為請求Rob2，如果在當(dāng)前情景下 Rob2不忙，那么請為Person服務(wù)，請求的結(jié)果存儲在變量 R_Result中，如果該變量值不是一個服務(wù) Agent的 ID，那么重新選擇一個服務(wù) Agent再次開始請求，如果是，那么就顯示成功，將Rob2為Person服務(wù)的事情放入動作規(guī)劃中。

5 結(jié)束語

本文基于情景演算理論，在Golog的基礎(chǔ)上增加了多Agent的協(xié)作，形成ConGolog語言.同時結(jié)合中斷操作和并發(fā)優(yōu)先，提出一個請求/服務(wù)協(xié)作模型.為多Agent在響應(yīng)服務(wù)請求時提供了模型支持。解決了ConGolog交替并發(fā)和虛擬場景中多Agent動作并發(fā)之間的矛盾，使得虛擬場景中虛擬人可以流暢的、并發(fā)的執(zhí)行規(guī)劃動作?；谇榫把菟憷碚撎接懙恼埱?服務(wù)協(xié)作模型還處于初步階段，可以做進(jìn)一步地深入研究。而且，由于協(xié)作模型有很多種，可以繼續(xù)探討情景演算是否適合于其它協(xié)作模型。

[1]楊愛琴,朱玲玲、程學(xué)云.基于流演算的多Agent 請求/服務(wù)協(xié)作模型的研究[J].計算機(jī)工程與設(shè)計,2011,32(2):681-684.

[2]Wooldridge, M.and Simon Parsons.Language for Negotiation [C].Proc.of 14th European Conf.on Artificial Intelligence, 2000.

[3]Thielscher M.Reasoning robots:The art and science of programmingrobotic agents[M].Germany:Springer Berlin,2005.

[4]ThielscherM.FLUX:A logic programmingmethod for reasoningagents [J].Theory and Practice of Logic Programming, 2005,5(4-5):533-565.

[5]Schiffel S,Thielscher M.Interpreting golog programs in flux[C].7th International Symposium on Logical Formalizations of Commonsense Reasoning,2005:193-198.

[6]Cohen P R, Perrault CR.Elements of a plan-based theory of speech acts[J].Cognitive Science,1979,3(3):177-212.

[7]Reiter R.Knowledge in action: logical foundations for specifyingand implementing dynamical systems[M].MIT Press,2001.

[8]楊愛琴.基于流演算的多agent 通信動作的研究[J].計算機(jī)工程與設(shè)計,2010,31(1):221-224.