多Agent系統(tǒng)中的信任模型概述

張旭升

摘 要： MAS（多Agent系統(tǒng)）環(huán)境同人類社會(huì)類似，充斥著大量不確定因素，因此，在MAS環(huán)境中引入信任對(duì)agent之間的交互至關(guān)重要。信任通常來(lái)源于直接信任和信譽(yù)兩種途徑，信譽(yù)系統(tǒng)是用于支持信任評(píng)價(jià)的機(jī)制。本文從信任的相關(guān)概念出發(fā)，針對(duì)幾個(gè)重要的信任模型做了簡(jiǎn)要的分析。

關(guān)鍵詞： 多Agent系統(tǒng) 信任 信任模型

各種各樣的網(wǎng)絡(luò)計(jì)算系統(tǒng)（例如網(wǎng)格，語(yǔ)義網(wǎng)和點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)）都可以被看做是一個(gè)多Agent系統(tǒng)（MAS），在MAS中的個(gè)體為了實(shí)現(xiàn)自己的目標(biāo)執(zhí)行自治、靈活的行為。這些系統(tǒng)的一個(gè)重要特征就是開(kāi)放性：系統(tǒng)中的各個(gè)agent由追求各自利益的不同擁有者（stakeholder）所擁有，并且可以隨時(shí)隨地自由地加入和離開(kāi)系統(tǒng)。因此在開(kāi)放的MAS中，agents具有自私性和不可靠性，同時(shí)沒(méi)有agent能確知環(huán)境的一切信息，也不存在一個(gè)中心控制agent可以控制所有的agent。在MAS系統(tǒng)中，一個(gè)agent往往需要另一個(gè)agent提供服務(wù)以實(shí)現(xiàn)自己的目標(biāo)，提供服務(wù)的agent稱為provider，接受服務(wù)的稱為consumer。由于上述的不確定性，agent提供服務(wù)的質(zhì)量并不是一成不變的，因此如何選擇服務(wù)質(zhì)量?jī)?yōu)異、穩(wěn)定可靠的agent是一個(gè)重要問(wèn)題。信任和名譽(yù)代表了agent服務(wù)質(zhì)量的期望值，通過(guò)對(duì)agent的信任和名譽(yù)的比較可以確定其服務(wù)的優(yōu)劣和可靠性，因而其研究越來(lái)越受到重視。

1.信任的相關(guān)概念

MAS中的信任還沒(méi)有一個(gè)統(tǒng)一定義，MAS中的信任是以合作為背景的，agent的合作需要交互，可以從合作中獲得收益。Agent在交互前需要通過(guò)評(píng)價(jià)，選擇能滿足其交互目的合作者，決定何時(shí)、同誰(shuí)及如何進(jìn)行交互。這種信任主要考察合作者能否完成所委托的任務(wù)，是以agent的能力、意圖等內(nèi)部特征為基礎(chǔ)的信任。由于評(píng)價(jià)在前，而收益要待合作完成后通過(guò)觀察才能得到，因此信任是站在評(píng)價(jià)者角度的一種主觀判斷，面臨判斷不準(zhǔn)確的風(fēng)險(xiǎn)。為方便表述，實(shí)施信任評(píng)價(jià)的主體稱為評(píng)價(jià)Agent a，被評(píng)價(jià)的合作者稱為目標(biāo)Agent b。

同人類社會(huì)類似，信任通常來(lái)源于兩種途徑：一種是直接信任，是評(píng)價(jià)agent依靠自己的知識(shí)和以往交互中獲得的直接經(jīng)驗(yàn)判斷得出的信任，反映評(píng)價(jià)agent的主觀觀點(diǎn)；另一種稱為信譽(yù)，是通過(guò)收集評(píng)價(jià)agent所處的社會(huì)中其他agent對(duì)目標(biāo)agent的觀點(diǎn)，經(jīng)推理得出的信任。顯然，信譽(yù)是信任的一個(gè)組成部分，但信譽(yù)又是基于別的agent的直接信任產(chǎn)生的，信譽(yù)來(lái)自于信任，直接信任強(qiáng)調(diào)評(píng)價(jià)agent自己的觀點(diǎn)，而信譽(yù)是來(lái)自社會(huì)其他成員觀點(diǎn)的匯總。另外，信譽(yù)可以針對(duì)個(gè)體，也可以針對(duì)群體。

信譽(yù)系統(tǒng)（reputation system）是用于支持信任評(píng)價(jià)的機(jī)制，在信譽(yù)系統(tǒng)中，由于評(píng)價(jià)agent的能力有限，僅使用直接信任不足以甚至不能完成評(píng)價(jià)，必須參照社會(huì)中其他agent提供的信譽(yù)信息。當(dāng)只涉及直接信任時(shí)，信譽(yù)系統(tǒng)只需要解決如何表達(dá)信任和如何計(jì)算信任的問(wèn)題，引入信譽(yù)后，還要解決如何收集并匯總信譽(yù)的問(wèn)題。這樣就產(chǎn)生另外一個(gè)難題，自利（self-interest）的agent可能會(huì)通過(guò)提供不真實(shí)的信息以得到高額回報(bào)，評(píng)價(jià)agent需要識(shí)別出不精確信息并采取有效措施，免受其負(fù)面影響而遭受損失.

2.信任模型

2.1FIRE模型

FIRE模型是一個(gè)集成信任（trust）與信譽(yù)（reputation）的獨(dú)立于應(yīng)用的開(kāi)放MAS中的分布式信譽(yù)系統(tǒng)模型，采用4種部件共同完成信任的評(píng)價(jià)，這4種部件分別為：（1）基于直接經(jīng)驗(yàn)的交互信任（interaction trust，IT）；（2）根據(jù)評(píng)價(jià)agent與目標(biāo)agent角色定義的基于規(guī)則的信任（role—based trust，RT）；（3）由證人提供的信息計(jì)算得到的證人信譽(yù)（witness reputation，WR）；（4）由目標(biāo)agent主動(dòng)向評(píng)價(jià)agent提供的第三方參考（certified reputation，CR）。前兩種部件是直接信任，而后兩種是信譽(yù)。

2.1.1 Interaction Trust

Interaction trust（IT）表示了兩個(gè)agent之間直接交互（服務(wù)與被服務(wù)）所形成的信任關(guān)系，來(lái)源于Regret模型。設(shè)Agent a是接受服務(wù)的Agent，b是提供服務(wù)的Agent。在a接受b的服務(wù)后，類似于商業(yè)交易，a根據(jù)b的服務(wù)質(zhì)量、價(jià)格、完成時(shí)間等給出如下形式的評(píng)價(jià)：r =（a ，b， i ，c， v），a和b分別代表Agent a及Agent b，i表示a和b本次交互的時(shí)間或序號(hào)，v是a給出的對(duì)b的服務(wù)的評(píng)價(jià)，v∈[-1，1]，-1意味服務(wù)絕對(duì)得差，1相反，0表示居中。c是a給出評(píng)價(jià)v的條件，表示服務(wù)質(zhì)量、價(jià)格、完成時(shí)間等。

2.1.2 Role-based trust

RT來(lái)源于現(xiàn)實(shí)中的agent關(guān)系，例如屬于同一個(gè)組織，agent的擁有者是友好關(guān)系或有相關(guān)性。RT表示了這種現(xiàn)實(shí)中的agent關(guān)系。因?yàn)楹茈y找到通用的這種關(guān)系表示方法，F(xiàn)IRE模型應(yīng)用“規(guī)則（rules）”來(lái)表示RT。規(guī)則的形式：rul=（rolea，roleb， c ，e ，v）， rolea與roleb分別表示Agent a與Agent b的角色，v是在條件c下的a給予b的信任值，e∈[0，1]是該規(guī)則對(duì)結(jié)果RT的影響程度或者是Agent a對(duì)于這條規(guī)則的信心程度，也是該規(guī)則的加權(quán)系數(shù)。可能的規(guī)則例如 rul1 =（buyer，seller，quality，-0.2，0.3）， rul2 =（-，government-seller ，quality，0，0.8）。規(guī)則1表示普通的seller出售的產(chǎn)品的質(zhì)量比承諾的要低一些（-0.2），但該規(guī)則本身的可靠性較低（0.3）。規(guī)則2表示一個(gè)更可靠的規(guī)則（0.8）：政府seller出售的產(chǎn)品質(zhì)量與承諾的一致。

2.1.3 Witness reputation

系統(tǒng)中可能有多個(gè)agent與Agent b合作過(guò)，因此，Agent a可以向相關(guān)agent查詢以獲取他們對(duì)b的評(píng)價(jià)，其結(jié)果稱為witness reputation。其過(guò)程如下：

2.1.3.1Agent a向它的“熟人”中有可能與目標(biāo)合作過(guò)的nBF個(gè)熟人發(fā)出形式如（-，b， c，-，-）的查詢。

2.1.3.2（2）收到查詢的熟人agent查詢自己的本地IT數(shù)據(jù)庫(kù)，如果有相同形式的記錄，則意味著它們?cè)?jīng)與Agent b有過(guò)交互，此時(shí)，將相應(yīng)記錄返回。

2.1.3.3如果沒(méi)有，則向a返回它自己可能與目標(biāo)合作過(guò)的nBF個(gè)熟人，以便Agent a繼續(xù)查詢。

2.1.3.4不斷重復(fù)上述過(guò)程，直到收集到足夠的記錄，或者查詢被轉(zhuǎn)發(fā)的次數(shù)超過(guò)事先的設(shè)定值nRL。

2.1.4 Certified Reputation

當(dāng)agent沒(méi)有與目標(biāo)Agent合作過(guò)（使用其服務(wù)），并且查詢熟人因?yàn)榉N種原因未找到相關(guān)記錄，系統(tǒng)中也缺乏RT規(guī)則，例如一個(gè)剛加入系統(tǒng)的agent可能遭遇這種狀況，那么CR的存在就可以讓信任與名譽(yù)的計(jì)算繼續(xù)。

2.1.5 總體性能

2.2改進(jìn)的CR （certified reputation）

在FIRE模型中的CR已經(jīng)取得很好的性能，但是由于第三方Agent（referee）的自私性可能與目標(biāo)Agent合謀導(dǎo)致其說(shuō)謊，這樣的話CR的性能就會(huì)大大降低。為此，我們提出了改進(jìn)的CR。

在改進(jìn)的CR模型里增加一個(gè)機(jī)制，該機(jī)制用來(lái)評(píng)估第三方Agent （referee）的可信度，以此評(píng)估它所提供的目標(biāo)Agent的信息的可靠性。通過(guò)記錄第三方Agent過(guò)去所提供目標(biāo)Agent的信息的可靠程度評(píng)定第三方Agent（referee）的信任度。

2.3基于維護(hù)的信任評(píng)估模型

現(xiàn)有的信任評(píng)估模型已經(jīng)很多并且都各具優(yōu)缺點(diǎn)?；诰S護(hù)的信任模型的提出就是為了提高現(xiàn)有的評(píng)估模型。該模型主要有兩個(gè)特點(diǎn)：首先，agents之間根據(jù)以前的交互歷史進(jìn)行交互合作。將所獲得的評(píng)定等級(jí)收集起來(lái)用以評(píng)估一個(gè)特定Agent的信任值。評(píng)定一個(gè)未知的Agent（與該Agent無(wú)交互歷史），我們通過(guò)第三方Agent（consulting agent）提供的信息來(lái)評(píng)定。我們的評(píng)定依據(jù)主要有時(shí)間性（time recency）、交互強(qiáng)度（interaction strength）、精確性（accuracy）。其次，評(píng)價(jià)Agent（trustor）在與目標(biāo)Agent直接交互一段時(shí)間以后執(zhí)行一個(gè)維護(hù)過(guò)程，該維護(hù)過(guò)程根據(jù)第三方Agent（consulting agent）提供的信息與目標(biāo)Agent實(shí)際的表現(xiàn)來(lái)修改第三方Agent的可信度。如果第三方Agent（consulting agent）提供的信息與目標(biāo)第三方Agent（consulting agent）提供的信息實(shí)際的表現(xiàn)相差超過(guò)預(yù)先設(shè)定的閾值，評(píng)價(jià)Agent（trustor） 就會(huì)修改它對(duì)第三方Agent（consulting agent）提供的信息的可信度值。這樣評(píng)價(jià)Agent（trustor）就會(huì)可以根據(jù)此可信度值來(lái)選擇最為可信的第三方Agent，從而選擇出信任值最好的目標(biāo)Agent。

2.4通過(guò)STEREOTYPES評(píng)估信任

在一個(gè)開(kāi)放的、動(dòng)態(tài)的多Agent系統(tǒng)中，agent之間可能為了實(shí)現(xiàn)某一目標(biāo)而臨時(shí)組成一個(gè)組織，在這種情況下，信任和信譽(yù)對(duì)于agent之間進(jìn)行能夠有效交互就顯得至關(guān)重要。Agent要依據(jù)其他agent的信任值去避免與一個(gè)不守信的agent合作。然而，這個(gè)臨時(shí)組織的生存周期很短，所以agents也許沒(méi)有足夠的時(shí)間對(duì)它們的合作者建立一個(gè)有效的信任評(píng)估。一種情況就是當(dāng)一個(gè)agent進(jìn)入一個(gè)組織時(shí)，其他的agent還沒(méi)有與它進(jìn)行交互所以不能評(píng)估它的信任值。我們將剛進(jìn)入該組織的那個(gè)agent稱作新來(lái)者（new comer）。另一種情況就是當(dāng)臨時(shí)組織中的各個(gè)agent剛剛加入到該組織的時(shí)候，因?yàn)檫€沒(méi)有開(kāi)始交互（也就是還沒(méi)有交互歷史），我們稱這個(gè)時(shí)期為“冷開(kāi)始問(wèn)題”（cold-start），這樣的話就無(wú)法獲得agent的信任值，從而無(wú)法正確選擇合作者而導(dǎo)致結(jié)果的低效。

基于上述情況，提出STEREOTYPES方法。該方法就是對(duì)于每一個(gè)agent，根據(jù)它以前的交互情況來(lái)評(píng)估它的信任值，然后給它分配一個(gè)信任等級(jí)（例如信任、不信任、不確定、基值），在這個(gè)信任等級(jí)中的基值是對(duì)一個(gè)新的agent（在所有的多Agent系統(tǒng)里都沒(méi)有交互歷史的agent）分配一個(gè)基本值（例如信任值為0.5）。我們把每個(gè)agent的信任等級(jí)作為STEREOTYPES。對(duì)于上述兩種情況（new comer），我們可以根據(jù)它的STEREOTYPES來(lái)作為我們選擇合作者的依據(jù)。該方法在多Agent系統(tǒng)中的agents交互時(shí)有一個(gè)信任評(píng)估的學(xué)習(xí)階段L，在此階段該方法的性能不是很好，但是接下來(lái)的時(shí)間里該方法表現(xiàn)出很強(qiáng)的性能，所以L的選擇就非常重要。

3.結(jié)語(yǔ)

由于開(kāi)放的多Agent系統(tǒng)的不確定性，使得信任在agent交互中起到了至關(guān)重要的作用?，F(xiàn)有的信任模型已經(jīng)取得了很好的效果，但是仍然有待提高。通過(guò)STEREOTYPES評(píng)估信任模型里L(fēng)值的確定是事先定義的，我們需要改進(jìn)的就是通過(guò)自動(dòng)計(jì)算來(lái)得到該值。當(dāng)然，正是信任如此重要，所以我們有更大的動(dòng)力提高這一點(diǎn)。

參考文獻(xiàn)：

[1]C. Burnett，T. J. Norman and K. Sycara， Bootstrapping Trust Evaluations through Stereotypes， Proc. of 9th Int. Conf. on Autonomous Agents and Multiagent Systems （AAMAS 2010），10-14，2010， Toronto， Canada， pp.

[2]Paul-Amaury Matt， Maxime Morge and Francesca Toni， Combining statistics and arguments to compute trust， Proc. of 9th Int.Conf. on Autonomous Agents and Multiagent Systems （AAMAS 2010）， 10-14， 2010， Toronto， Canada， pp.209-216.

[3]Babak Khosravifar，Maziar Gomrokchi，Jamal Bentahar，Philippe Thiran. Maintencance-based Trust for Multi-Agent System， Proc. of 8th Int. Conf. on Autonomous Agents and Multiagent Systems （AAMAS 2009）， 10-15 2009， Budapest， Hungary， pp.1017-1024.

[4]T. Dong-Huynh， N.R. Jennings and N.R. Shadbolt. Certified reputation： How an agent can trust a stranger. In Proceedings of The 5th International Joint Conference on Autonomous Agents and Multiagent Systems， pp. 1217-1224， Japan， 2006.

[5]T. Dong-Huynh， N.R. Jennings and N.R. Shadbolt. Fire： An integrated trust and reputation model for open multi-agent systems. Journal of Autonomous Agents and Multi-Agent Systems 13（2）：119-154， 2006.

[6]P. Dondio and S. Barrett. Presumptive selection of trust evidences. In AAMAS， 2007.