鄭延斌，段領(lǐng)玉，李 波，梁 凱

(1.河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453007;2.智慧商務(wù)與物聯(lián)網(wǎng)技術(shù)河南省工程實(shí)驗(yàn)室，河南 新鄉(xiāng) 453007)

基于演化博弈懲罰機(jī)制的多智能體協(xié)作穩(wěn)定性研究*

鄭延斌1,2，段領(lǐng)玉1，李 波1，梁 凱1

(1.河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453007;2.智慧商務(wù)與物聯(lián)網(wǎng)技術(shù)河南省工程實(shí)驗(yàn)室，河南 新鄉(xiāng) 453007)

針對(duì)復(fù)雜、動(dòng)態(tài)環(huán)境中多Agent協(xié)作的穩(wěn)定性問(wèn)題，提出了一種基于博弈論及懲罰機(jī)制的協(xié)作方法，通過(guò)效用函數(shù)來(lái)選擇最優(yōu)策略，實(shí)現(xiàn)均衡協(xié)作；為了提高協(xié)作的穩(wěn)定性與成功率，引入懲罰機(jī)制，通過(guò)不斷調(diào)整懲罰系數(shù)來(lái)維護(hù)多Agent協(xié)作的穩(wěn)定性，并在形成協(xié)作團(tuán)隊(duì)時(shí)，充分考慮參與協(xié)作的Agent的信譽(yù)值。仿真結(jié)果表明，該方法能有效地降低任務(wù)完成時(shí)間，避免Agent在動(dòng)態(tài)協(xié)作中隨意退出，提高協(xié)作效率及協(xié)作穩(wěn)定性。

演化博弈;協(xié)作;懲罰機(jī)制;信譽(yù)值;Multi-agent

1 引言

協(xié)作問(wèn)題是多Agent系統(tǒng)研究的核心問(wèn)題之一，研究者提出了許多方法，如：任韶萱[1]提出一種基于蟻群算法的多智能體協(xié)作算法，湯瓊等[2]提出利用協(xié)作協(xié)進(jìn)化來(lái)實(shí)現(xiàn)多智能體之間協(xié)作機(jī)制，然而這些方法大多適用于靜態(tài)環(huán)境。在復(fù)雜環(huán)境中，隨著環(huán)境和任務(wù)的變換，Agent之間所形成的這種任務(wù)協(xié)作關(guān)系可能被打破，導(dǎo)致協(xié)作任務(wù)不能完成或者協(xié)作效率不高。因此，如何確保多Agent之間協(xié)作穩(wěn)定性、提高協(xié)作效率是復(fù)雜環(huán)境中多Agent協(xié)作研究的關(guān)鍵問(wèn)題之一。針對(duì)該問(wèn)題，唐賢倫等[3]提出將距離因子和控制因子引入蟻群算法的多Agent協(xié)作策略，為解決MAS(Multi-Agent Systems)在協(xié)作中可能出現(xiàn)的任務(wù)死鎖及協(xié)作效率不高提供了解決途徑;肖喜麗[4]把協(xié)進(jìn)化算法應(yīng)用到多Agent協(xié)作問(wèn)題中，通過(guò)個(gè)體適應(yīng)度評(píng)價(jià)與其他種群協(xié)作，并把協(xié)作行為應(yīng)用到目標(biāo)領(lǐng)域后對(duì)個(gè)體進(jìn)行評(píng)估，雖然能更好地協(xié)作，但是代表個(gè)體的選擇對(duì)協(xié)進(jìn)化算法效率的影響和如何減少計(jì)算量的問(wèn)題有待解決；Takahashi Y等[5]提出通過(guò)系統(tǒng)動(dòng)態(tài)環(huán)境的反饋來(lái)分配Agent角色的概念，框架中無(wú)直接合作的計(jì)劃，但每個(gè)Agent都會(huì)根據(jù)其他Agent的行為所產(chǎn)生出來(lái)的各類環(huán)境反饋來(lái)選擇自己的行為，從而實(shí)現(xiàn)協(xié)作的行為。由于多Agent系統(tǒng)環(huán)境的復(fù)雜多變，難以提取出有效的環(huán)境反饋定義來(lái)應(yīng)用此思想;Kazunori I等[6]將協(xié)作問(wèn)題描述為多Agent馬爾可夫決策過(guò)程MMDP(Multi-agent Markov Decision Processes)，采用強(qiáng)化學(xué)習(xí)來(lái)獲得Agent的策略，利用學(xué)習(xí)機(jī)制來(lái)減少協(xié)商過(guò)程中的不確定和不穩(wěn)定因素，但同樣由于環(huán)境的復(fù)雜性，使得學(xué)習(xí)周期變得十分長(zhǎng)。然而，上述方法大都基于Agent團(tuán)體理性的假設(shè)，即Agent本質(zhì)上愿意協(xié)作，忽略了Agent的個(gè)體理性的問(wèn)題，或者不允許Agent在任務(wù)執(zhí)行的過(guò)程中退出。由于在復(fù)雜環(huán)境中，任務(wù)是動(dòng)態(tài)加入的、Agent自身能力和偏好也會(huì)發(fā)生變化，因此Agent為了追求自身利益最大化，有可能退出當(dāng)前正在執(zhí)行的任務(wù)，去選擇執(zhí)行其它任務(wù)，導(dǎo)致當(dāng)前任務(wù)不能執(zhí)行，或者執(zhí)行效率降低。為了使協(xié)作任務(wù)正常執(zhí)行，確保協(xié)作的穩(wěn)定性，本文基于博弈論(Game Theory)方法，提出了一種懲罰機(jī)制，通過(guò)不斷調(diào)整懲罰系數(shù)來(lái)實(shí)現(xiàn)動(dòng)態(tài)的多Agent之間的協(xié)作穩(wěn)定性，Agent通過(guò)對(duì)懲罰的大小程度判斷選擇繼續(xù)協(xié)作或者接受懲罰并退出協(xié)作，實(shí)現(xiàn)均衡協(xié)作。

2 博弈論基礎(chǔ)

博弈論又稱“對(duì)策論”，它研究的是在決策者的行為之間發(fā)生相互作用時(shí)，各個(gè)決策者所作決策的問(wèn)題[7]。

定義1對(duì)于博弈我們可以用一個(gè)四元組進(jìn)行表示，即G={A，S，I，U}，其中，

A：協(xié)作參與者A={a1，a2，…，an}，是指協(xié)作的各方。

S：各協(xié)作參與者可行策略集S={S1，S2，S3，…，Sn}，是協(xié)作參與者可能采取的所有行為策略。

I：博弈信息，指的是參與者所擁有的信息特征。

U：收益函數(shù)是指博弈過(guò)程中參與協(xié)作博弈對(duì)象的收益，可以用U={u1,u2,u3,…，un}進(jìn)行表示。

Nash均衡是理性局中人之間利益沖突時(shí)達(dá)到的一種相對(duì)穩(wěn)定的狀態(tài)，且沒有一個(gè)行為主體可以單方面改變這種狀態(tài)。對(duì)于博弈中的每一個(gè)參與者，真正成功的措施應(yīng)該是針對(duì)對(duì)手的行為做出最有利于自己的行為，于是，每一個(gè)參與者應(yīng)采取的策略必定是對(duì)其他參與者策略預(yù)測(cè)的最佳反應(yīng)。

3 基于博弈論的多Agent協(xié)作方法

智能體在選擇形成協(xié)作團(tuán)隊(duì)時(shí)若能對(duì)協(xié)作智能體綜合考慮，就有可能避免局限性，提高協(xié)作的性能。為此本文提出了智能體的信譽(yù)值來(lái)輔助智能體協(xié)作團(tuán)隊(duì)的形成。考慮到任務(wù)是動(dòng)態(tài)的，Agent的能力、偏好等也會(huì)隨協(xié)作的進(jìn)行而有所改變，且每個(gè)Agent都是自私自利的，當(dāng)Agent間協(xié)作已經(jīng)建立又面臨其它更大獲益的協(xié)作請(qǐng)求時(shí)，出于對(duì)自身利益最大化的考慮，Agent可能放棄當(dāng)前的協(xié)作任務(wù)選擇獲利更大任務(wù)的協(xié)作請(qǐng)求。因此，為了維護(hù)系統(tǒng)穩(wěn)定性和其他協(xié)作Agent的利益，本文提出了一個(gè)懲罰機(jī)制，對(duì)于此類Agent給以懲罰以維護(hù)協(xié)作穩(wěn)定性，Agent判斷接受懲罰并退出當(dāng)前協(xié)作任務(wù)或者是迫于懲罰而繼續(xù)協(xié)作，Agent的信譽(yù)值也會(huì)隨之改變。另外，為了提高協(xié)作效率，對(duì)每件任務(wù)設(shè)定時(shí)限，以便當(dāng)協(xié)作Agent數(shù)量達(dá)不到任務(wù)要求時(shí)Agent放棄等待，避免Agent“死等”狀態(tài)。

3.1 信譽(yù)值

(1)

3.2 懲罰機(jī)制

對(duì)于多Agent，他們的協(xié)作關(guān)系形成后協(xié)作Agent為了自己的效益最大化，可能退出協(xié)作，因此為了保證協(xié)作過(guò)程的穩(wěn)定性，只有Agent完成任務(wù)后方可退出。如何實(shí)現(xiàn)協(xié)作過(guò)程的穩(wěn)定性是一個(gè)關(guān)鍵問(wèn)題。在動(dòng)態(tài)博弈過(guò)程中由于Agent大都是自私的，為了追求自身利益的最大化，可能隨著協(xié)作的進(jìn)行，參與Agent不滿足于對(duì)現(xiàn)階段的協(xié)作，或者經(jīng)過(guò)長(zhǎng)時(shí)間的協(xié)作仍然不能完成任務(wù)，參與Agent可能中途退出并參與收益比較大的任務(wù)，從而導(dǎo)致協(xié)作團(tuán)隊(duì)效率低下。為此本文允許協(xié)作者動(dòng)態(tài)地加入或退出當(dāng)前協(xié)作任務(wù)。

本文允許協(xié)作者動(dòng)態(tài)加入或退出系統(tǒng)以改善協(xié)作團(tuán)隊(duì)的協(xié)作效率，但如果Agent在發(fā)現(xiàn)自己可能獲得更大利益后就可以不加任何條件地退出當(dāng)前協(xié)作而加入新協(xié)作任務(wù)，反而會(huì)破壞協(xié)作的穩(wěn)定性，使當(dāng)前所在的協(xié)作團(tuán)隊(duì)中其它Agent蒙受損失，這樣將會(huì)形成惡性循環(huán)，導(dǎo)致協(xié)作團(tuán)隊(duì)的整體性能下降。所以，在改善協(xié)作效率的同時(shí)，還應(yīng)當(dāng)保證協(xié)作的相對(duì)穩(wěn)定性。為此，本文引入“懲罰機(jī)制”的概念，以維護(hù)協(xié)作任務(wù)的正常完成。退出當(dāng)前協(xié)作的Agent必須接受“懲罰”以彌補(bǔ)其它協(xié)作Agent的損失。如果某個(gè)Agent認(rèn)為自己退出當(dāng)前協(xié)作加入其他協(xié)作而獲取的收益，即使在接受懲罰的條件下，仍多于當(dāng)前協(xié)作可能獲得的收益，這時(shí)Agent會(huì)選擇退出當(dāng)前協(xié)作并接受懲罰。如果Agent發(fā)現(xiàn)退出后的收益小于當(dāng)前收益，就選擇留在當(dāng)前系統(tǒng)繼續(xù)協(xié)作。懲罰機(jī)制由下式確定：

(2)

如果協(xié)作Agent選擇退出當(dāng)前協(xié)作，則根據(jù)式(2)計(jì)算其要付出的懲罰代價(jià)，其中Δt越小，Agent付出的懲罰代價(jià)越大。

3.3 基于懲罰機(jī)制和博弈論的多Agent協(xié)作算法

(1)多Agent協(xié)作形成過(guò)程。

環(huán)境中許多復(fù)雜的任務(wù)需要多個(gè)Agent相互協(xié)作來(lái)完成，當(dāng)一個(gè)Agent感知到一個(gè)自身不能完成而又期望完成的任務(wù)時(shí)，需要與其它Agent聯(lián)合形成一個(gè)協(xié)作團(tuán)隊(duì)來(lái)完成此任務(wù)，在選擇團(tuán)隊(duì)成員是要考慮要求參加團(tuán)隊(duì)的Agent的信譽(yù)值；同時(shí)，為了保證任務(wù)的正常執(zhí)行，對(duì)加入團(tuán)隊(duì)的成員使用懲罰機(jī)制來(lái)限制其退出團(tuán)隊(duì)的隨意性，確保協(xié)作的穩(wěn)定性。故協(xié)作形成過(guò)程描述如下：

①設(shè)系統(tǒng)中包含n個(gè)理性Agent，即A={A1，A2，A3，…，An}，和m個(gè)需要協(xié)作完成的任務(wù)T={Ta1，Ta2，…，Tam}；

②初始階段：ε0=(Ai,Taj,SN)，對(duì)于所有的Ai初始階段在系統(tǒng)中隨機(jī)找尋未完成的任務(wù)Taj，用SN來(lái)標(biāo)記Ai是否找到Taj，若SN值為真,則Ai在系統(tǒng)中發(fā)出協(xié)作請(qǐng)求；

③協(xié)作請(qǐng)求階段：ε1=(Ai,Taj,message(s,Agents,us))，Ai在“黑板”上發(fā)協(xié)作請(qǐng)求信息message(s,Agnets,us)，完成Taj需要s個(gè)協(xié)作Agent組成協(xié)作團(tuán)隊(duì)Agents，完成任務(wù)協(xié)作Agent獲得的收益為ui(i=1,2,…,s)；

④回應(yīng)請(qǐng)求階段：ε3=(Ai,t,s,Taj,fail(A,Taj))，Ai發(fā)出message(s,Agents,us)后，t時(shí)隙回應(yīng)請(qǐng)求數(shù)量達(dá)不到s則放棄Taj；

⑤協(xié)作形成階段：ε4=(Ai,t,e,s,Taj,sele(d,τ))，假設(shè)在時(shí)限t內(nèi)，同意協(xié)作請(qǐng)求Agent數(shù)量e>s，則Ai根據(jù)sele(d,τ)從e個(gè)Agent中挑選出s個(gè)協(xié)作Agent，其中Agent距離目標(biāo)任務(wù)的距離d越小，Agent的信譽(yù)值τ越大，被選中的可能性也越大；

⑦結(jié)束。

(2) 多Agent協(xié)作的演化博弈算法。

復(fù)雜環(huán)境中，由于資源限制和環(huán)境約束，協(xié)作中的每個(gè)Agent的行為選擇要受到其它Agent行為選擇的影響，即每個(gè)Agent的行為決策受到其它Agent行為決策的影響，博弈論為這種相互影響的決策行為給出了很好的數(shù)學(xué)模型。在協(xié)作的過(guò)程中，Agent之間的每次博弈都希望選擇使自身效用最優(yōu)的行為，但是由于博弈中可能存在多個(gè)平衡解，故當(dāng)Agent之間的行為選擇出現(xiàn)不協(xié)調(diào)時(shí)，每個(gè)Agent可能選擇其他行為或者脫離協(xié)作團(tuán)隊(duì)而選擇其他團(tuán)隊(duì)，而懲罰機(jī)制使得Agent不會(huì)輕易脫離協(xié)作團(tuán)隊(duì)，迫使它繼續(xù)選擇合適的行為，從不斷的調(diào)整中達(dá)到最優(yōu)，即得到穩(wěn)定的平衡，確保任務(wù)的順利執(zhí)行。

定義3多Agent協(xié)作問(wèn)題可以描述為一個(gè)協(xié)作博弈：G={A，S，I，U}。其中，A為參與協(xié)作的Agent集合A={A1，A2，…，An}；S為Agent的所有可能的策略或行動(dòng)的集合S={S1，S2，…，Sn}，每個(gè)參與者的策略可以形式化為Si：Ai→ai(i=1，2，…，n)，其中ai為參與者Ai采取的行動(dòng)；I是每個(gè)Agent擁有的信息；U是效用函數(shù)，標(biāo)記Agent在行為組合或策略組合條件下的得失情況，U={u1,u2,…，un}。

多Agent協(xié)作的演化博弈方法描述如下：

①判斷協(xié)作是否成功，若成功則轉(zhuǎn)④；

②若協(xié)作成員不到位，則等待成員加入，轉(zhuǎn)①；

④進(jìn)入初始狀態(tài)，時(shí)段為t；

⑤計(jì)算當(dāng)前狀態(tài)下所有的博弈均衡解；

⑥Agent從均衡解中選擇自己的行為；

⑦觀察團(tuán)隊(duì)中其它成員的行為，計(jì)算在此聯(lián)合行為下所獲得的效用；

⑩根據(jù)觀察到的團(tuán)隊(duì)中其它成員前面的行為選擇歷史，計(jì)算其它成員的行為選擇概率，利用該概率值估計(jì)其它成員下一階段可能的行為選擇；

如果多Agent形成一個(gè)完成復(fù)雜任務(wù)的協(xié)作團(tuán)隊(duì)，則由Nash均衡理論知，該協(xié)作博弈一定存在Nash均衡解。因此，從該算法中可以看出，由于均衡解不是唯一的，因此協(xié)作成員在選擇均衡行為時(shí)可能出現(xiàn)偏差，導(dǎo)致行為組合不是一個(gè)均衡解。這是Agent根據(jù)其他成員以往行為選擇的概率，來(lái)預(yù)測(cè)其他成員將來(lái)的行為選擇，以此求出自己的最佳反應(yīng)，達(dá)到均衡解，獲得期望收益。由Nash均衡的穩(wěn)定性知，成員的行為選擇一旦達(dá)到均衡后，每個(gè)成員沒有動(dòng)力去打破這種平衡來(lái)獲取更高的回報(bào)。但是，均衡的獲取需要一個(gè)過(guò)程，懲罰機(jī)制的使用確保每個(gè)成員都有足夠的耐心，不會(huì)隨意脫離協(xié)作團(tuán)隊(duì)，因此該算法在協(xié)作團(tuán)隊(duì)一旦形成后，可以確保協(xié)作的穩(wěn)定性，使得協(xié)作任務(wù)能夠順利執(zhí)行。

4 仿真實(shí)驗(yàn)

追捕問(wèn)題是一類最基本的多Agent協(xié)作問(wèn)題，因其實(shí)現(xiàn)簡(jiǎn)單，規(guī)則、約束少，在問(wèn)題的求解中具有代表性，受到許多研究者的重視。為了驗(yàn)證所提算法的有效性，在Matlab R2010a環(huán)境下基于以上的模型和算法，對(duì)多Agent協(xié)作追捕獵物問(wèn)題進(jìn)行仿真，假設(shè)環(huán)境中分布著能力相同的14個(gè)同質(zhì)Agent；分布著難度系數(shù)不同的4個(gè)動(dòng)態(tài)獵物，當(dāng)多個(gè)Agent形成的協(xié)作團(tuán)隊(duì)成功追捕獵物后，系統(tǒng)會(huì)隨機(jī)產(chǎn)生不同難度系數(shù)的新獵物，使獵物總數(shù)保持不變，獵物自身帶有被捕獲所需的Agent數(shù)量及自身的價(jià)值，多Agent協(xié)作追捕獵物根據(jù)相應(yīng)獵物的價(jià)值獲得不同的收益。系統(tǒng)所產(chǎn)生的動(dòng)態(tài)獵物最少由4個(gè)Agent協(xié)作完成追捕，最多由7個(gè)Agent協(xié)作完成追捕，不考慮其他情況。Agent在協(xié)作的過(guò)程當(dāng)中能夠從當(dāng)前協(xié)作中動(dòng)態(tài)地加入或退出。假設(shè)選擇在500×500大小的矩形場(chǎng)地內(nèi)，按10×10的尺寸劃分成數(shù)量為50×50的柵格，障礙物由系統(tǒng)隨機(jī)生成。

圖1為不同信譽(yù)值τ下Agent的任務(wù)完成率(Completion Rate)情況。其中N表示協(xié)作進(jìn)行的次數(shù)，Completion Rate表示Agent協(xié)作成功完成任務(wù)占總?cè)蝿?wù)的比率。從圖1中可以看出，Completion Rate隨著τ的增長(zhǎng)而明顯提高，說(shuō)明多Agent的Completion Rate隨Agent的τ增長(zhǎng)而得到了提高改進(jìn)，當(dāng)τ>0.8時(shí)，其Completion Rate接近為1。當(dāng)τ接近0時(shí)，其Completion Rate降為0。

Figure 1 Task completion rate influenced by the credibility value

圖2為實(shí)驗(yàn)仿真100次不同懲罰系數(shù)k下的協(xié)作追捕完成率Completion Rate情況。從圖2中可以看出，對(duì)于不同的懲罰系數(shù)，Agent會(huì)選擇不同的行為。在懲罰系數(shù)k=0時(shí)，由于參加協(xié)作的Agent都是理性Agent，為了爭(zhēng)取自身利益最大化自由選擇退出當(dāng)前協(xié)作；隨著懲罰系數(shù)的不斷增長(zhǎng)，完成率Completion Rate有明顯的提高，說(shuō)明隨著對(duì)協(xié)作Agent選擇退出行為的嚴(yán)厲懲罰，迫于威懾使得協(xié)作Agent很少作出退出協(xié)作的決策。

Figure 2 Agent collaboration hunt completion rates under different punishment coefficients

圖3是本文算法與遺傳算法、合同網(wǎng)協(xié)議、強(qiáng)化學(xué)習(xí)等算法的比較結(jié)果。本文算法中設(shè)懲罰系數(shù)k設(shè)為0.75，信譽(yù)值τ設(shè)為0.85，捕獲時(shí)間閾值設(shè)為500 s。

Figure 3 Comparison of different methods in prey amount-hunting time

從圖3可以看出，在多Agent協(xié)作追捕獵物的任務(wù)中，利用博弈論方法在追捕時(shí)間上有明顯的優(yōu)勢(shì)。在獵物數(shù)量較少時(shí)，Q-learning算法與合同網(wǎng)協(xié)議算法捕獲時(shí)間比較接近，博弈方法的捕獲時(shí)間最少。在獵物數(shù)量較多時(shí)，前幾種算法在獵物數(shù)量在7個(gè)左右時(shí)因?yàn)椴东@時(shí)間達(dá)到規(guī)定閾值，不得不退出當(dāng)前協(xié)作。而利用博弈算法可以在規(guī)定時(shí)間內(nèi)較好地完成任務(wù)。因?yàn)槔貌┺恼摲椒ǎ總€(gè)Agent在執(zhí)行動(dòng)作前，要參考其他Agent及獵物的歷史策略選擇，來(lái)計(jì)算自己的最優(yōu)效用函數(shù)，最終選擇一個(gè)期望的最優(yōu)策略組合，Agent在參與協(xié)作的每一步將保證博弈的最優(yōu)狀態(tài)，盡可能使總收益值最大，任務(wù)完成時(shí)間最短。

5 結(jié)束語(yǔ)

本文利用博弈論方法來(lái)研究復(fù)雜動(dòng)態(tài)環(huán)境中的多Agent協(xié)作問(wèn)題，提出了一種基于懲罰機(jī)制的協(xié)作方法，并通過(guò)不斷地調(diào)整懲罰系數(shù)值來(lái)提高多Agent動(dòng)態(tài)協(xié)作的協(xié)作效率及其協(xié)作穩(wěn)定性，協(xié)作Agent根據(jù)懲罰程度的不同來(lái)判斷選擇繼續(xù)協(xié)作或者是退出當(dāng)前協(xié)作并接受相應(yīng)的懲罰，實(shí)現(xiàn)協(xié)作均衡；與此同時(shí)，引入智能體的信譽(yù)值，在協(xié)作的初始階段作為智能體選擇其它Agent形成協(xié)作團(tuán)隊(duì)的一個(gè)重要參考因素。仿真結(jié)果表明，本文提出的懲罰機(jī)制，能有效地避免Agent在動(dòng)態(tài)協(xié)作中隨意退出，提高了協(xié)作效率及協(xié)作穩(wěn)定性。

[1] Ren Shao-xuan. Multi-robot cooperation and coordination based on ant colony algorithm[J]. Journal of Shenyang Ligong University,2011,30(5):49-53.(in Chinese)

[2] Tang Qiong,Yang Dong-yong. A study of multi-agent cooperation mechanism based on cooperative co-evolution[J].Computer Engineering and Applications,2004,32(28):64-66.(in Chinese)

[3] Tang Xian-lun,Li Ya-nan,Fan Zheng.Multi-agent autonomous cooperation planning strategy in unknown environment[J].Systems Engineering and Electronics,2013,35(2):345-349.(in Chinese)

[4] Xiao Xi-li. Research on multi-agent cooperation based on co-evolution algorithm[D].Nanjing:Nanjing University of Posts and Telecommunications,2012.(in Chinese)

[5] Takahashi Y，Tamura T，Asada M．Cooperation via environmental dynamics caused by multi-robots in a hostile environment[C]∥Proc of the 4th IFAC Symposium on Intelligent Autonomous Vehicles, 2001:413-418.

[6] Kazunori I, Kazushi I, Hideake S. A statistical property of multiagent learning based on Markov decision process[J]. IEEE Transactions on Neural Networs, 2006,17(4):829-842.

[7] Piao Song-hao,Sun Li-ning,Zhong Qiu-bo,et al. The model

of multi-agent cooperation in the dynamic environment[J].Journal of Huazhong University of Science and Technology(Nature Science Edition),2008，36(10)：39-52.(in Chinese)

附中文參考文獻(xiàn)：

[1] 任韶萱.蟻群算法在多機(jī)器人協(xié)作中的應(yīng)用[J].沈陽(yáng)理工大學(xué)學(xué)報(bào),2011,30(5):49-53.

[2] 湯瓊,楊東勇.基于協(xié)作協(xié)進(jìn)化的多智能體機(jī)器人協(xié)作研究[J].計(jì)算機(jī)工程與應(yīng)用,2004,32(28):64-66.

[3] 唐賢倫,李亞楠,樊崢.未知環(huán)境中多Agent自主協(xié)作規(guī)劃策略[J].系統(tǒng)工程與電子技術(shù),2013,35(2):345-349.

[4] 肖喜麗.基于協(xié)進(jìn)化的多智能體協(xié)作研究[D].南京：南京郵電大學(xué)，2012.

[7] 樸松昊，孫立寧，鐘秋波.動(dòng)態(tài)環(huán)境下的多智能體機(jī)器人協(xié)作模型[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2008，36(10)：39-52.

鄭延斌(1964-),男,河南內(nèi)鄉(xiāng)人，博士，教授，研究方向?yàn)樘摂M現(xiàn)實(shí)、多智能體系統(tǒng)和對(duì)策論。E-mail:zybcgf@163.com

ZHENG Yan-bin,born in 1964,PhD,professor,his research interests include virtual reality, multi-agent systems, and game theory.

Research on multi-agent cooperation stability based on the punishment mechanism of evolutionary games

ZHENG Yan-bin1,2,DUAN Ling-yu1,LI Bo1,LIANG Kai1

(1.College of Computer and Information Technology,Henan Normal University,Xinxiang 453007;2.Engineering Laboratory of Intellectual Business and Internet of Things Technologies,Xinxiang 453007,China)

The coordination stability problem in complex environments is one of the key problems in the research of multi-agent cooperation. We present a multi-agent cooperation stability method on the basis of game theory methods and punishment mechanism. To maintain the stability of multi-agent cooperation and achieve a balanced cooperation, a punishment is introduced and continuous adjustment of the penalty factors is performed. Agent credit values are fully considered when the cooperation team is formed. Simulation results show that the proposal can not only reduce task completion time effectively, but also avoid agent exits in the dynamic cooperation, thus improving the cooperation efficiency and stability..

evolutionary games;cooperation;punishment mechanism;credit value;multi-agent

1007-130X(2015)09-1682-06

2014-09-12;

2015-03-02基金項(xiàng)目：河南省重點(diǎn)科技攻關(guān)項(xiàng)目(122102210086,132102210537,132102210538)

TP18

A

10.3969/j.issn.1007-130X.2015.09.014

通信地址：453007 河南省新鄉(xiāng)市河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院

Address:College of Computer and Information Technology,Henan Normal University,Xinxiang 453007,Henan,P.R.China