基于演化博弈惩罚机制的多智能体协作稳定性研究*

郑延斌，段领玉，李 波，梁 凯

(1.河南师范大学计算机与信息工程学院，河南 新乡 453007;2.智慧商务与物联网技术河南省工程实验室，河南 新乡 453007)

基于演化博弈惩罚机制的多智能体协作稳定性研究*

郑延斌1,2，段领玉1，李 波1，梁 凯1

(1.河南师范大学计算机与信息工程学院，河南 新乡 453007;2.智慧商务与物联网技术河南省工程实验室，河南 新乡 453007)

针对复杂、动态环境中多Agent协作的稳定性问题，提出了一种基于博弈论及惩罚机制的协作方法，通过效用函数来选择最优策略，实现均衡协作；为了提高协作的稳定性与成功率，引入惩罚机制，通过不断调整惩罚系数来维护多Agent协作的稳定性，并在形成协作团队时，充分考虑参与协作的Agent的信誉值。仿真结果表明，该方法能有效地降低任务完成时间，避免Agent在动态协作中随意退出，提高协作效率及协作稳定性。

演化博弈;协作;惩罚机制;信誉值;Multi-agent

1 引言

协作问题是多Agent系统研究的核心问题之一，研究者提出了许多方法，如：任韶萱[1]提出一种基于蚁群算法的多智能体协作算法，汤琼等[2]提出利用协作协进化来实现多智能体之间协作机制，然而这些方法大多适用于静态环境。在复杂环境中，随着环境和任务的变换，Agent之间所形成的这种任务协作关系可能被打破，导致协作任务不能完成或者协作效率不高。因此，如何确保多Agent之间协作稳定性、提高协作效率是复杂环境中多Agent协作研究的关键问题之一。针对该问题，唐贤伦等[3]提出将距离因子和控制因子引入蚁群算法的多Agent协作策略，为解决MAS(Multi-Agent Systems)在协作中可能出现的任务死锁及协作效率不高提供了解决途径;肖喜丽[4]把协进化算法应用到多Agent协作问题中，通过个体适应度评价与其他种群协作，并把协作行为应用到目标领域后对个体进行评估，虽然能更好地协作，但是代表个体的选择对协进化算法效率的影响和如何减少计算量的问题有待解决；Takahashi Y等[5]提出通过系统动态环境的反馈来分配Agent角色的概念，框架中无直接合作的计划，但每个Agent都会根据其他Agent的行为所产生出来的各类环境反馈来选择自己的行为，从而实现协作的行为。由于多Agent系统环境的复杂多变，难以提取出有效的环境反馈定义来应用此思想;Kazunori I等[6]将协作问题描述为多Agent马尔可夫决策过程MMDP(Multi-agent Markov Decision Processes)，采用强化学习来获得Agent的策略，利用学习机制来减少协商过程中的不确定和不稳定因素，但同样由于环境的复杂性，使得学习周期变得十分长。然而，上述方法大都基于Agent团体理性的假设，即Agent本质上愿意协作，忽略了Agent的个体理性的问题，或者不允许Agent在任务执行的过程中退出。由于在复杂环境中，任务是动态加入的、Agent自身能力和偏好也会发生变化，因此Agent为了追求自身利益最大化，有可能退出当前正在执行的任务，去选择执行其它任务，导致当前任务不能执行，或者执行效率降低。为了使协作任务正常执行，确保协作的稳定性，本文基于博弈论(Game Theory)方法，提出了一种惩罚机制，通过不断调整惩罚系数来实现动态的多Agent之间的协作稳定性，Agent通过对惩罚的大小程度判断选择继续协作或者接受惩罚并退出协作，实现均衡协作。

2 博弈论基础

博弈论又称“对策论”，它研究的是在决策者的行为之间发生相互作用时，各个决策者所作决策的问题[7]。

定义1对于博弈我们可以用一个四元组进行表示，即G={A，S，I，U}，其中，

A：协作参与者A={a1，a2，…，an}，是指协作的各方。

S：各协作参与者可行策略集S={S1，S2，S3，…，Sn}，是协作参与者可能采取的所有行为策略。

I：博弈信息，指的是参与者所拥有的信息特征。

U：收益函数是指博弈过程中参与协作博弈对象的收益，可以用U={u1,u2,u3,…，un}进行表示。

Nash均衡是理性局中人之间利益冲突时达到的一种相对稳定的状态，且没有一个行为主体可以单方面改变这种状态。对于博弈中的每一个参与者，真正成功的措施应该是针对对手的行为做出最有利于自己的行为，于是，每一个参与者应采取的策略必定是对其他参与者策略预测的最佳反应。

3 基于博弈论的多Agent协作方法

智能体在选择形成协作团队时若能对协作智能体综合考虑，就有可能避免局限性，提高协作的性能。为此本文提出了智能体的信誉值来辅助智能体协作团队的形成。考虑到任务是动态的，Agent的能力、偏好等也会随协作的进行而有所改变，且每个Agent都是自私自利的，当Agent间协作已经建立又面临其它更大获益的协作请求时，出于对自身利益最大化的考虑，Agent可能放弃当前的协作任务选择获利更大任务的协作请求。因此，为了维护系统稳定性和其他协作Agent的利益，本文提出了一个惩罚机制，对于此类Agent给以惩罚以维护协作稳定性，Agent判断接受惩罚并退出当前协作任务或者是迫于惩罚而继续协作，Agent的信誉值也会随之改变。另外，为了提高协作效率，对每件任务设定时限，以便当协作Agent数量达不到任务要求时Agent放弃等待，避免Agent“死等”状态。

3.1 信誉值

(1)

3.2 惩罚机制

对于多Agent，他们的协作关系形成后协作Agent为了自己的效益最大化，可能退出协作，因此为了保证协作过程的稳定性，只有Agent完成任务后方可退出。如何实现协作过程的稳定性是一个关键问题。在动态博弈过程中由于Agent大都是自私的，为了追求自身利益的最大化，可能随着协作的进行，参与Agent不满足于对现阶段的协作，或者经过长时间的协作仍然不能完成任务，参与Agent可能中途退出并参与收益比较大的任务，从而导致协作团队效率低下。为此本文允许协作者动态地加入或退出当前协作任务。

本文允许协作者动态加入或退出系统以改善协作团队的协作效率，但如果Agent在发现自己可能获得更大利益后就可以不加任何条件地退出当前协作而加入新协作任务，反而会破坏协作的稳定性，使当前所在的协作团队中其它Agent蒙受损失，这样将会形成恶性循环，导致协作团队的整体性能下降。所以，在改善协作效率的同时，还应当保证协作的相对稳定性。为此，本文引入“惩罚机制”的概念，以维护协作任务的正常完成。退出当前协作的Agent必须接受“惩罚”以弥补其它协作Agent的损失。如果某个Agent认为自己退出当前协作加入其他协作而获取的收益，即使在接受惩罚的条件下，仍多于当前协作可能获得的收益，这时Agent会选择退出当前协作并接受惩罚。如果Agent发现退出后的收益小于当前收益，就选择留在当前系统继续协作。惩罚机制由下式确定：

(2)

如果协作Agent选择退出当前协作，则根据式(2)计算其要付出的惩罚代价，其中Δt越小，Agent付出的惩罚代价越大。

3.3 基于惩罚机制和博弈论的多Agent协作算法

(1)多Agent协作形成过程。

环境中许多复杂的任务需要多个Agent相互协作来完成，当一个Agent感知到一个自身不能完成而又期望完成的任务时，需要与其它Agent联合形成一个协作团队来完成此任务，在选择团队成员是要考虑要求参加团队的Agent的信誉值；同时，为了保证任务的正常执行，对加入团队的成员使用惩罚机制来限制其退出团队的随意性，确保协作的稳定性。故协作形成过程描述如下：

①设系统中包含n个理性Agent，即A={A1，A2，A3，…，An}，和m个需要协作完成的任务T={Ta1，Ta2，…，Tam}；

②初始阶段：ε0=(Ai,Taj,SN)，对于所有的Ai初始阶段在系统中随机找寻未完成的任务Taj，用SN来标记Ai是否找到Taj，若SN值为真,则Ai在系统中发出协作请求；

③协作请求阶段：ε1=(Ai,Taj,message(s,Agents,us))，Ai在“黑板”上发协作请求信息message(s,Agnets,us)，完成Taj需要s个协作Agent组成协作团队Agents，完成任务协作Agent获得的收益为ui(i=1,2,…,s)；

④回应请求阶段：ε3=(Ai,t,s,Taj,fail(A,Taj))，Ai发出message(s,Agents,us)后，t时隙回应请求数量达不到s则放弃Taj；

⑤协作形成阶段：ε4=(Ai,t,e,s,Taj,sele(d,τ))，假设在时限t内，同意协作请求Agent数量e>s，则Ai根据sele(d,τ)从e个Agent中挑选出s个协作Agent，其中Agent距离目标任务的距离d越小，Agent的信誉值τ越大，被选中的可能性也越大；

⑦结束。

(2) 多Agent协作的演化博弈算法。

复杂环境中，由于资源限制和环境约束，协作中的每个Agent的行为选择要受到其它Agent行为选择的影响，即每个Agent的行为决策受到其它Agent行为决策的影响，博弈论为这种相互影响的决策行为给出了很好的数学模型。在协作的过程中，Agent之间的每次博弈都希望选择使自身效用最优的行为，但是由于博弈中可能存在多个平衡解，故当Agent之间的行为选择出现不协调时，每个Agent可能选择其他行为或者脱离协作团队而选择其他团队，而惩罚机制使得Agent不会轻易脱离协作团队，迫使它继续选择合适的行为，从不断的调整中达到最优，即得到稳定的平衡，确保任务的顺利执行。

定义3多Agent协作问题可以描述为一个协作博弈：G={A，S，I，U}。其中，A为参与协作的Agent集合A={A1，A2，…，An}；S为Agent的所有可能的策略或行动的集合S={S1，S2，…，Sn}，每个参与者的策略可以形式化为Si：Ai→ai(i=1，2，…，n)，其中ai为参与者Ai采取的行动；I是每个Agent拥有的信息；U是效用函数，标记Agent在行为组合或策略组合条件下的得失情况，U={u1,u2,…，un}。

多Agent协作的演化博弈方法描述如下：

①判断协作是否成功，若成功则转④；

②若协作成员不到位，则等待成员加入，转①；

④进入初始状态，时段为t；

⑤计算当前状态下所有的博弈均衡解；

⑥Agent从均衡解中选择自己的行为；

⑦观察团队中其它成员的行为，计算在此联合行为下所获得的效用；

⑩根据观察到的团队中其它成员前面的行为选择历史，计算其它成员的行为选择概率，利用该概率值估计其它成员下一阶段可能的行为选择；

如果多Agent形成一个完成复杂任务的协作团队，则由Nash均衡理论知，该协作博弈一定存在Nash均衡解。因此，从该算法中可以看出，由于均衡解不是唯一的，因此协作成员在选择均衡行为时可能出现偏差，导致行为组合不是一个均衡解。这是Agent根据其他成员以往行为选择的概率，来预测其他成员将来的行为选择，以此求出自己的最佳反应，达到均衡解，获得期望收益。由Nash均衡的稳定性知，成员的行为选择一旦达到均衡后，每个成员没有动力去打破这种平衡来获取更高的回报。但是，均衡的获取需要一个过程，惩罚机制的使用确保每个成员都有足够的耐心，不会随意脱离协作团队，因此该算法在协作团队一旦形成后，可以确保协作的稳定性，使得协作任务能够顺利执行。

4 仿真实验

追捕问题是一类最基本的多Agent协作问题，因其实现简单，规则、约束少，在问题的求解中具有代表性，受到许多研究者的重视。为了验证所提算法的有效性，在Matlab R2010a环境下基于以上的模型和算法，对多Agent协作追捕猎物问题进行仿真，假设环境中分布着能力相同的14个同质Agent；分布着难度系数不同的4个动态猎物，当多个Agent形成的协作团队成功追捕猎物后，系统会随机产生不同难度系数的新猎物，使猎物总数保持不变，猎物自身带有被捕获所需的Agent数量及自身的价值，多Agent协作追捕猎物根据相应猎物的价值获得不同的收益。系统所产生的动态猎物最少由4个Agent协作完成追捕，最多由7个Agent协作完成追捕，不考虑其他情况。Agent在协作的过程当中能够从当前协作中动态地加入或退出。假设选择在500×500大小的矩形场地内，按10×10的尺寸划分成数量为50×50的栅格，障碍物由系统随机生成。

图1为不同信誉值τ下Agent的任务完成率(Completion Rate)情况。其中N表示协作进行的次数，Completion Rate表示Agent协作成功完成任务占总任务的比率。从图1中可以看出，Completion Rate随着τ的增长而明显提高，说明多Agent的Completion Rate随Agent的τ增长而得到了提高改进，当τ>0.8时，其Completion Rate接近为1。当τ接近0时，其Completion Rate降为0。

Figure 1 Task completion rate influenced by the credibility value

图2为实验仿真100次不同惩罚系数k下的协作追捕完成率Completion Rate情况。从图2中可以看出，对于不同的惩罚系数，Agent会选择不同的行为。在惩罚系数k=0时，由于参加协作的Agent都是理性Agent，为了争取自身利益最大化自由选择退出当前协作；随着惩罚系数的不断增长，完成率Completion Rate有明显的提高，说明随着对协作Agent选择退出行为的严厉惩罚，迫于威慑使得协作Agent很少作出退出协作的决策。

Figure 2 Agent collaboration hunt completion rates under different punishment coefficients

图3是本文算法与遗传算法、合同网协议、强化学习等算法的比较结果。本文算法中设惩罚系数k设为0.75，信誉值τ设为0.85，捕获时间阈值设为500 s。

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

从图3可以看出，在多Agent协作追捕猎物的任务中，利用博弈论方法在追捕时间上有明显的优势。在猎物数量较少时，Q-learning算法与合同网协议算法捕获时间比较接近，博弈方法的捕获时间最少。在猎物数量较多时，前几种算法在猎物数量在7个左右时因为捕获时间达到规定阈值，不得不退出当前协作。而利用博弈算法可以在规定时间内较好地完成任务。因为利用博弈论方法，每个Agent在执行动作前，要参考其他Agent及猎物的历史策略选择，来计算自己的最优效用函数，最终选择一个期望的最优策略组合，Agent在参与协作的每一步将保证博弈的最优状态，尽可能使总收益值最大，任务完成时间最短。

5 结束语

本文利用博弈论方法来研究复杂动态环境中的多Agent协作问题，提出了一种基于惩罚机制的协作方法，并通过不断地调整惩罚系数值来提高多Agent动态协作的协作效率及其协作稳定性，协作Agent根据惩罚程度的不同来判断选择继续协作或者是退出当前协作并接受相应的惩罚，实现协作均衡；与此同时，引入智能体的信誉值，在协作的初始阶段作为智能体选择其它Agent形成协作团队的一个重要参考因素。仿真结果表明，本文提出的惩罚机制，能有效地避免Agent在动态协作中随意退出，提高了协作效率及协作稳定性。

[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)

附中文参考文献：

[1] 任韶萱.蚁群算法在多机器人协作中的应用[J].沈阳理工大学学报,2011,30(5):49-53.

[2] 汤琼,杨东勇.基于协作协进化的多智能体机器人协作研究[J].计算机工程与应用,2004,32(28):64-66.

[3] 唐贤伦,李亚楠,樊峥.未知环境中多Agent自主协作规划策略[J].系统工程与电子技术,2013,35(2):345-349.

[4] 肖喜丽.基于协进化的多智能体协作研究[D].南京：南京邮电大学，2012.

[7] 朴松昊，孙立宁，钟秋波.动态环境下的多智能体机器人协作模型[J].华中科技大学学报(自然科学版)，2008，36(10)：39-52.

郑延斌(1964-),男,河南内乡人，博士，教授，研究方向为虚拟现实、多智能体系统和对策论。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基金项目：河南省重点科技攻关项目(122102210086,132102210537,132102210538)

TP18

A

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

通信地址：453007 河南省新乡市河南师范大学计算机与信息工程学院

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