分布式語義自動(dòng)協(xié)商與博弈機(jī)制研究

何雨青 朱俊武 李開榮

摘? ?要：文章在語義集成中引入了協(xié)商—博弈機(jī)制。各個(gè)Agents由于對領(lǐng)域的認(rèn)知程度不同，因此，他們構(gòu)建本體的“可信度”也是不同的。本體“可信度”越高，基于本體語義進(jìn)行的檢索準(zhǔn)確率就越高。注意到每個(gè)Agent構(gòu)建的本體與最終本體之間相似度可以看作Agent的收益，Agents之間如果通過協(xié)商與博弈來形成均衡，那么這個(gè)均衡就是所有Agents最能接受的結(jié)果，即“可信度”最高的本體。因此，模擬Agents之間的協(xié)商與博弈，構(gòu)建更“可信”的本體，是完全可行的。

關(guān)鍵詞：機(jī)制設(shè)計(jì);協(xié)商—博弈;本體論

當(dāng)兩個(gè)本體之間存在語義關(guān)聯(lián)時(shí)，就可以通過本體映射來將源本體的實(shí)例映射到目標(biāo)本體，從而解決異構(gòu)本體的共享和重用問題[1]?，F(xiàn)有的本體映射工作并不能適用于那些規(guī)模較大的本體通信與共享的情況。本文擬設(shè)計(jì)一種新穎的本體合并方法，即把多個(gè)同主題領(lǐng)域的本體相結(jié)合，從而構(gòu)建一個(gè)規(guī)模更大的語義共享空間。那就是本體構(gòu)建者對領(lǐng)域知識的認(rèn)知程度不同。由于認(rèn)知程度較低的Agent所構(gòu)建出的本體可信度不高，基于該現(xiàn)狀，在設(shè)計(jì)的本體合并方法基礎(chǔ)上增加“可信度”這樣一個(gè)概念是必要的。

1? ? Agent協(xié)商系統(tǒng)

在Agent協(xié)商與博弈的情形下，大多數(shù)學(xué)者沒有考慮到一個(gè)事實(shí)，那就是Agent之間的知識共享[2]。知識共享在協(xié)商—博弈系統(tǒng)中是非常有必要的，在協(xié)商階段進(jìn)行知識共享，可以更有效地達(dá)成一致，從而進(jìn)行下一個(gè)階段，即博弈階段。在博弈階段，知識共享能幫助博弈雙方根據(jù)對方的知識對自己的策略進(jìn)行改良，從而使得自己的收益盡可能大。

現(xiàn)有的Agent協(xié)商系統(tǒng)中，協(xié)商環(huán)境復(fù)雜、動(dòng)態(tài)，Agent存在異構(gòu)的可能。Agent對于特定的協(xié)議和領(lǐng)域具有依賴性，因此，沒有辦法讓協(xié)議與領(lǐng)域無關(guān)[3]。選擇適當(dāng)?shù)男问交ぞ呙枋鰠f(xié)商Agent的交互和規(guī)則問題，使得協(xié)商Agent不依賴于特定的協(xié)商和博弈機(jī)制，如何做到領(lǐng)域無關(guān)是極具研究價(jià)值的問題[4]。

2? ? 協(xié)商—博弈本體定義

協(xié)商和博弈本體（Negotiation/Game Ontology，NO/GO）分別對協(xié)商領(lǐng)域和博弈領(lǐng)域進(jìn)行建模，提供了Agent互相之間可以進(jìn)行共享的協(xié)商或博弈知識庫，使得Agent與領(lǐng)域知識、協(xié)商/博弈協(xié)議相分離，能夠在加入?yún)f(xié)商或博弈時(shí)自動(dòng)獲取該領(lǐng)域的知識本體并通過自身的推理機(jī)制解析協(xié)商/博弈對象、協(xié)商/博弈規(guī)則等通信信息從而更適用于語義Web的環(huán)境，能夠參與任何領(lǐng)域的協(xié)商/博弈活動(dòng)。

描述邏輯（Description Logic）是基于對象的知識表示的形式化，建立在概念和關(guān)系之上，具有很強(qiáng)的表達(dá)能力與可判定性?；诿枋鲞壿?，將本體定義為一個(gè)二元組，即O=（Tbox，Abox），其中，Tbox=（C，R，P）包含內(nèi)涵知識用于描述概念的一般性質(zhì)，（C，R，P）分別表示概念（concept）、角色（role）和屬性（property）;Abox包含外延知識（又稱斷言知識）用于某個(gè)特定個(gè)體。

構(gòu)建了如下的協(xié)商本體和博弈本體，如圖1—2所示。

協(xié)商Agent根據(jù)分工的不同可分為negotiation participant和negotiation host，兩者分別表示協(xié)商的參與者以及對協(xié)商過程進(jìn)行監(jiān)督的主持者。其中，對協(xié)商過程進(jìn)行監(jiān)督的主持者又可根據(jù)職責(zé)分為3種類型：validator用于判定各個(gè)規(guī)則是否合理、updater用于更新反饋結(jié)果、agreement make根據(jù)終態(tài)時(shí)得到最終的協(xié)商結(jié)果。協(xié)商中有3種狀態(tài)，即初始狀態(tài)、中間狀態(tài)和最終狀態(tài);當(dāng)?shù)竭_(dá)最終狀態(tài)時(shí)，Agent達(dá)成一致（agreement）或矛盾（conflict），協(xié)商結(jié)束。這樣一個(gè)由多種協(xié)商Agent進(jìn)行的，從初始狀態(tài)到最終狀態(tài)的過程，就是一個(gè)完整的協(xié)商過程。

與協(xié)商本體類似，博弈的參與者有兩類，分別是game host和game participant;策略是博弈參與者在進(jìn)行博弈時(shí)可選擇的行動(dòng)集合，而策略的選擇又依賴于外界環(huán)境和參與者所掌握的信息的影響。博弈規(guī)則是指博弈的約束，博弈規(guī)則指導(dǎo)著博弈的進(jìn)行。收益是指參與者在采取策略后所得到的利益。

3? ? 本體語義支撐的協(xié)商-博弈機(jī)制

自動(dòng)協(xié)商的靜態(tài)成分可以用一組協(xié)議來表示〈Pad，Pal，Pag〉，其中，Pad是規(guī)范如何進(jìn)入（admission）協(xié)商的協(xié)議，Pal是協(xié)商進(jìn)行時(shí)參與者如何交互（alternate）的協(xié)議，Pag是交互完成時(shí)，協(xié)商一致（agreement）如何生成的協(xié)議。

其中，對于任何的協(xié)議，都可以用元組〈Ag，Ac，W， w0，T，L，u〉進(jìn)行刻畫。其中，Ag={α1，…αn}是協(xié)議的使用者（Agent）的集合;Ac={Ac1，…Acn}是使用者的行動(dòng)（Action）的集合，其中Aci是αi的行動(dòng)結(jié)合;W是使用本協(xié)議交互過程中，可能達(dá)到的狀態(tài)的集合;w0是初始的狀態(tài)，T是結(jié)束時(shí)可能的終態(tài)集合;L是一組函數(shù)，其中，函數(shù)Li：W+＼T→2Aci被稱為αi在特定狀態(tài)下的合法行動(dòng)集合，規(guī)定了αi在某一非終狀態(tài)下能采取的交互行動(dòng)。函數(shù)u：W×A1×…×An→W被稱為狀態(tài)更新函數(shù)，決定了在某個(gè)狀態(tài)下，Agent采取一定的行動(dòng)，狀態(tài)將如何遷移。至此，本文定義了協(xié)商協(xié)議的統(tǒng)一理論數(shù)學(xué)模型。

但是此模型應(yīng)用在開放市場協(xié)商環(huán)境下卻有相當(dāng)大的局限性，比如協(xié)議中的行動(dòng)集合、狀態(tài)集合可能非常龐大甚至是無限集。因此，狀態(tài)遷移函數(shù)也有可能難以表示。這意味著很難對協(xié)商的領(lǐng)域知識進(jìn)行擴(kuò)充，使得協(xié)商協(xié)議的應(yīng)用場景受限，可重用性下降。而且在現(xiàn)實(shí)的協(xié)商環(huán)境中，存在多個(gè)協(xié)議負(fù)責(zé)約束不同的交互，遵守協(xié)議存在時(shí)序關(guān)系，而此數(shù)學(xué)模型難以表達(dá)協(xié)議之間的層級、執(zhí)行順序關(guān)系，這對自動(dòng)協(xié)商程序的編寫造成了極大的困難。

而使用共享協(xié)商本體則可以很好地解決上述問題，對開放環(huán)境下的自動(dòng)協(xié)商過程進(jìn)行抽象分析，一般而言，自動(dòng)協(xié)商可以被抽象成如下3個(gè)階段：（1）協(xié)商申請階段。（2）協(xié)商交互階段。（3）協(xié)商一致生成階段。

本體語義支撐的協(xié)商機(jī)制可用上述定義的協(xié)商本體進(jìn)行描述，具體如下。

3.1? 協(xié)商申請階段

協(xié)商申請階段可以被認(rèn)為是有意愿參加本次協(xié)商的Agent和協(xié)商的主持者Host之間的溝通，具體體現(xiàn)為以下幾點(diǎn)。

（1）Agent向協(xié)商主持者Host提交參加本次協(xié)商的申請。（2）Host收到申請后，向該Agent發(fā)送共享協(xié)商本體（包括：角色、協(xié)商協(xié)議等）。（3）Agent收到貢獻(xiàn)給協(xié)商本體，對本體進(jìn)行解析，向Host發(fā)送信任狀，表明自己是否可以理解遵循協(xié)商本體所描述的協(xié)商規(guī)則。（4）Host收到Agent的信任狀，根據(jù)信任狀的結(jié)果判斷是否允許該Agent參加本次協(xié)商，并將判決結(jié)果發(fā)送給Agent。（5）Agent收到Host的判決結(jié)果，如不同意，則離開本次協(xié)商;如同意，則進(jìn)入本次協(xié)商，等待協(xié)商進(jìn)入下一階段。

具體的交互流程如圖3所示。

3.2? 協(xié)商交互階段

在參與者通過協(xié)商申請階段后，Host會(huì)根據(jù)start_rule判定協(xié)商何時(shí)進(jìn)入?yún)f(xié)商交互階段。協(xié)商交互階段本質(zhì)上是參與者之間、參與者與Host之間，Host內(nèi)部各功能Agent之間，根據(jù)協(xié)商協(xié)議進(jìn)行交互的過程。這樣的過程可以抽象成如下6個(gè)基本步驟。

（1）Host的子Agent—terminal_checker會(huì)根據(jù)terminal_rule判斷當(dāng)前狀態(tài)下協(xié)商是否達(dá)到了最終狀態(tài)，如果是，則進(jìn)入?yún)f(xié)商過程的第3階段（協(xié)商一致生成狀態(tài)），否則進(jìn)入步驟2。

（2）Host根據(jù)voice_rule判定此時(shí)哪些協(xié)商參與者可以發(fā)言，協(xié)商參與者根據(jù)proposal_rule計(jì)算自己此時(shí)可以提出proposal。

（3）協(xié)商參與者向Host提交自己的proposal，Host只會(huì)接受在步驟2中判定的可以發(fā)言的協(xié)商者的消息。

（4）Host將接收到的proposal提交給子功能Agent—validator，validator根據(jù)proposal_rule判定各個(gè)參與者提交的proposal是否合理，如果不合理，則validator根據(jù)規(guī)則隨機(jī)生成一個(gè)proposal并發(fā)送給Host，并重復(fù)步驟4。如果合理，則把proposal提交給Host的子功能Agent—updater，進(jìn)入步驟5。

（5）updater收到validator發(fā)送的proposal，根據(jù)proposal對本次協(xié)商的各元素進(jìn)行信息更新，并將更新結(jié)果反饋給Host。

（6）Host收到來自updater的更新反饋結(jié)果，Host根據(jù)inform_rule判斷更新結(jié)果的哪些部分應(yīng)該告訴哪些協(xié)商參與者，并告知相應(yīng)的參與者，進(jìn)入步驟1。

具體協(xié)商流程如圖4所示。

3.3? ?協(xié)商一致生成階段

當(dāng)Host的子功能Agent—terminal_checker監(jiān)測到協(xié)商當(dāng)前達(dá)到了終態(tài)時(shí)，協(xié)商從交互階段進(jìn)入到協(xié)商一致生成階段。在此階段，Host的子功能Agent—agreement_maker根據(jù)終態(tài)時(shí)的proposal情況得到最終的協(xié)商結(jié)果（包括一致agreement和不一致confict兩方面）。并將信息反饋給Host，由Host根據(jù)inform_rule告知協(xié)商的參與者。

4? ? 結(jié)語

本文設(shè)計(jì)了分布式語義自動(dòng)協(xié)商與博弈機(jī)制，能有效提高效率。但是，這仍是非常復(fù)雜的問題，僅設(shè)計(jì)出機(jī)制是不夠的。后續(xù)還將對該機(jī)制進(jìn)行求解。

[參考文獻(xiàn)]

[1]KALFOGLOU Y，SCHORLEMMER M.Ontology mapping：the state of the art[J].Knowledge Engineering Review，2003（1）：1-31.

[2]NOY N.Semantic integration：a survey of ontology-based approaches[J].Sigmod Record，2004（4）：65-70.

[3]唐杰，梁邦勇，李涓子，等.語義Web中的本體自動(dòng)映射[J].計(jì)算機(jī)學(xué)報(bào)，2006（11）：1956-1976.

[4]FRIDMAN N，MUSEN M A.Prompt：algorithm and tool for automated ontology merging and alignment[C].Austin：Proceedings of Seventeenth National Conference on Artificial Intelligence（AAAI—2000），2000.