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

張旭升

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

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

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

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

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

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

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

2.信任模型

2.1FIRE模型

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

2.1.1 Interaction Trust

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

2.1.2 Role-based trust

RT來源于現(xiàn)實(shí)中的agent關(guān)系，例如屬于同一個組織，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）”來表示RT。規(guī)則的形式：rul=（rolea，roleb， c ，e ，v）， rolea與roleb分別表示Agent a與Agent b的角色，v是在條件c下的a給予b的信任值，e∈[0，1]是該規(guī)則對結(jié)果RT的影響程度或者是Agent a對于這條規(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表示一個更可靠的規(guī)則（0.8）：政府seller出售的產(chǎn)品質(zhì)量與承諾的一致。

2.1.3 Witness reputation

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

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

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

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

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

2.1.4 Certified Reputation

當(dāng)agent沒有與目標(biāo)Agent合作過（使用其服務(wù)），并且查詢熟人因?yàn)榉N種原因未找到相關(guān)記錄，系統(tǒng)中也缺乏RT規(guī)則，例如一個剛加入系統(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)致其說謊，這樣的話CR的性能就會大大降低。為此，我們提出了改進(jìn)的CR。

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

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

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

2.4通過STEREOTYPES評估信任

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

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

3.結(jié)語

由于開放的多Agent系統(tǒng)的不確定性，使得信任在agent交互中起到了至關(guān)重要的作用。現(xiàn)有的信任模型已經(jīng)取得了很好的效果，但是仍然有待提高。通過STEREOTYPES評估信任模型里L(fēng)值的確定是事先定義的，我們需要改進(jìn)的就是通過自動計(jì)算來得到該值。當(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.