博弈理论为研究多agent系统的协作奠定了坚实的基础,并逐步引入MAS(multi-agent systems)工程领域中^{[1, 2]},如王冠群等^[3]以非合作模式建立了船舶电力系统重构博弈方案;Pendharkar^[4]以合作和非合作模式分别建立了无线通信与制造业MAS的博弈选择;Feldman和 Tamir^[5]利用Nash均衡,验证了MAS中博弈平衡问题的稳定性;宋梅萍等^[6]采用Pareto占优解论证agent博弈学习的有效性.上述内容采用静态博弈的研究方法,以参与者同时选择各自本次博弈最优决策为基础,对MAS各阶段选择进行了相应的优化处理.但由于多智能体系统中,请求处理、决策及任务分配等活动具有随机性强、时效性高、系统工作周期动态变化的特征;同时agent具有理性与自私性^[7]两大特点,自私性致使agent具有一定的争先性^[8],即不遗余力地争取获得任何有利机会;理性的存在导致agent在决策时需考虑未来预期,在完成系统工作周期任务时,与其他agent的协作行为具有不确定性与无限性,并通过观测到其他agent的合作历史记录与选择动作序列抉择合作走向,因此静态博弈无法满足上述需求,需建立基于动态无限博弈的决策选择方法.

本文提出一种基于动态无限博弈的多agent合作机制,以多阶段邀请、考核模式形成无限次重复博弈.以协作优先级主动选取协作智能体,并提出信任基准控制agent博弈选取的自私性,使其理性计划阶段决策,通过博弈结果反馈调整优先级,实现闭环调控.

博弈本质体现的是参与者理性选择的冲突碰撞,而冲突结局可描述成参与者对利益追究的均衡态势. 重复博弈是一类特殊而又重要的动态博弈,由于博弈结构体多次重复出现,一些在一次性博弈中不可能出现的合作行为在重复博弈中却可能出现.

由于单一agent不具有足够的资源与能力完成指定任务,将启动请求计划,请求其他agent协助完成;主动性与交互性协助其他相关agent快速响应,接收请求,部署规划.而agent自私性使其在响应交互时受两个重要因素影响:一是当系统中同构agent较多时,任一agent害怕完成系统分配任务总量较少,长时期处于空置状态,导致系统阶段更新后,遭到淘汰;二是在与其他agent的交互合作中,请求与被请求的次数过低,影响其在系统或层级模块间的熟人等级排列,而遭冷落.由此agent在接收请求行为时有时对完成效果的思考欠缺,将导致对请求agent造成一定的损失,当请求agent察觉到接收agent具有盲目的行为决策后,将影响其之后的交互合作工作.因此MAS中的合作活动可抽象为图 1所示的多阶段博弈状态,通过多次邀请、考核形成博弈结构体,而将其扩展为MAS整体任务规划时,可演化为一种基于无限动态博弈的合作机制.

假设系统中存在n个agent,则存在2ⁿ种合作方式.图 1以系统中两个agent合作博弈为例.设agent i,agent j∈Γ;若agent i无法独立完成当前任务时,将请求agent j的帮助,同时agent i将给予agent j一定数额的奖励r,agent j若接收请求,将获得奖励r,否则它可以选择拒绝而加入其他agent的请求,由此产生机会成本C_op;当agent j基于理性选择接收agent i的请求时,可与agent i合作共同完成系统分配任务,不仅使agent j得到奖励r,也使agent i获得收益e,其净利润为e-r;若agent j接收请求时存在自私与盲目性,将导致合作项目无法进行,虽可继续获得收益r,但agent i将造成-r的经济损失.因此对agent的合作期望与自私性加以鼓励与限制将对合作博弈达到何种纳什均衡产生重要的影响.

图 1(Figure 1)

Fig. 1

图1 动态博弈结构体 Fig. 1 Dynamic game structure

在多智能体系统博弈中,其agent的个体收益不仅取决于一次博弈所带来的收益,同时也受博弈次数、长期合作历史记录及未来预期合作的影响.因此提出信任基准(trust benchmark)评价指标,控制agent的理性程度,提高agent的合作期望.信任基准评价agents间的相互信任程度,信任基准越高,数值越大,代表双方之间互信指数越高,对对方犯错的宽容度越大,且允许非合作或非理性选择的比率越高,越注重长远利益;反之则亦然.假设两个agents间总共申请合作的次数为AC(application cooperation),未合作成功的次数为NSC(not successful cooperation),未成功的原因可能由另一个agent的拒绝或盲目性造成.信任基准由式(1)所示.

TB描述了agent博弈合作中的互信信息, 将信任基准赋予贴现特性,寻找博弈结构体纳什均衡时,TB根据定义可表示为[0, 1]区间,设被请求合作任务agent j在结构体各阶段博弈中,都出于理性选择,认为“执行合作”为最优决策,无限次重复博弈的纯收益现值为V^j_e,则V^j_e可由式(2)表示,并化为式(3).

设如果被请求agent j在接收任务时,存在盲目争先性,做出“不执行合作”的决定,不仅使请求agent i遭受损失,在以后的合作中做出不请求的决策,也会使其自身收益减少,信用等级有所降低.如agent j在博弈阶段认为“不执行”为最优选择,则收益现值V^j_une即为式(5).

对于agent j而言,任务选择执行合作认为对其自身价值与收益都有利时,V^j_e≥V^j_une,则

由式(7)可知,TB≥0,当r-C_op≥0时,也即agent i给予agent j的奖励大于等于其选择其他agent获得机会成本时,agent j认为在无限次重复博弈中,当合作收益满足其对合作的期望收益时,选择执行合作认为系统纳什均衡.

若请求者agent i在请求agent j合作时,都能得到agent j的帮助并顺利完成任务,则Vⁱ_e为

若请求者agent i在请求合作完成任务,发现agent j具有盲目性,并对其造成损失时,将会屏蔽agent i,停止合作任务,其收益现值Vⁱ_une为

对agent i而言,选择和agent j共同完成任务认为是最优选择时,Vⁱ_e≥Vⁱ_une,则

当e>r时,agent间合作可顺利建立,因此TB的最低限值可设为1,符合TB定义中数值的最高限制范围.因此,当合作请求满足合作可建条件时,即e>r,对于具有TB∈[0, 1]限定的agent i 和agent j双方,选择共同执行合作任务是系统博弈的纳什均衡.

由TB也可分析出agent间的信任程度与合作期望值.TB越小,允许非成功合作的次数越少,agent两者间更注重眼前利益,对对方的信任程度较低,当双方实际未完成合作次数大于TB预设值时,合作将不复存在;TB=0是双方合作的极限值,其描述的是“冷酷战略”情形^[9],即只要双方有一次合作未成功,从此将互不信任,取消合作,对agent间的理性选择提出极高的要求,不仅要求被请求agent有求必应,而且限定其按合作计划履行职责,完成任务,否则再无合作任务.TB越大,描述agent双方更注重长远利益,互信等级也将提高,只要双方拒绝合作或未执行合作的比率小于TB预设值时,请求合作agent将既往不咎,重新发起合作请求,被请求agent也将进行新一轮的博弈选择;TB=1是双方合作的另一个极限值,描述双方在不考虑合作历史记录下,进行无限次重复博弈合作.但由于极限值的存在将系统抽象成静态博弈环境,agent间博弈的选择具有极强的随机性与盲目性,导致系统完成任务效率降低,由此通过TB赋值可有效调控agent间的合作期望. 因此在MAS中引入基于信任基准的无限重复博弈理念,将对agent间的合作起到促进作用,通过协作优先级与信任基准的闭环互相调整,增强agent做出理性选择的能力.

1) MAS根据agent的工作特性,初始化TB,r,e,C_op数值,及agent协作的等级排序;

2) 接到分配任务后,分解任务,给予各agent相应的战略选择空间S_i与收益函数u_i(s₁,…,s_i,…,s_n);

3) 以两个agent为合作基本单元发起合作;

4) 进入博弈阶段,选择博弈策略,执行博弈,计算博弈结果,得到相应收入,如(0,C_op)，(e-r,r)，(-r,r)等.

5) 判断是否还需和其他agent合作,如果是将回到第3)步,重新组成博弈体,进入4)步,以3)步博弈结果产生的合作结构体(结构体中agent数量小于等于2)与新进agent进行合作博弈,否则进入第6)步;

6) 判断系统中是否还有合作任务,如果有,将进入第3)步,否则转入第7)步;

7) 计算各agent执行合作行为所得收益;

8) 根据第7)步输出的收益值,适当调整更新系统TB,r,e,C_op数值;

9) 结束MAS阶段任务分配.

实验采用九宫格游戏法,测试基于信任基准agent无限博弈合作机制的效用性.九宫格游戏如图 2所示可描述无限重复动态博弈的环境条件.以agent体的合作博弈作为九宫格测试基本单元,agent在格中的初始化位置设为MAS阶段任务分配的初始点,初始点为随机设置,agent的目标终点为MAS阶段任务分配的终止点;在agent的自由移动中,agent的相遇描述为MAS分发给agent系统任务,需要进行协商合作完成.Agent的合作并执行任务表示接受完成任务,agent的合作却不执行表示agent具有盲目性的选择特征,agent的不合作代表无法完成任务,由于系统中agent相遇的偶然随机性,表达了系统任务分配中合作博弈的动态与无限重复性;同时根据信任基准(TB)赋值的不同控制了agent博弈选择执行合作的理性程度.

图 2(Figure 2)

Fig. 2

图2 九宫格agent移动状态及移动坐标(☆为agent终点) Fig. 2 Moving state and coordinates of agents in grids(☆ is agent terminal position

本文采用4个agent组成的MAS系统作为测试基本单元,该基本单元较好地描述了agent间的合作关系,将合作形式根据发起者不同形成64种组合.并根据完成任务先后、合作与执行任务状态、博弈选择的理性程度,将agent间的合作细化为312种形式,图 2所示agent A,agent B,agent C与agent D的动作选择空间为{up,down,left,right}四种动作,行为选择为随机选择;战略选择空间表示各决策点的位置坐标,将九宫格转换为X-Y坐标系,以每个格子的中点坐标作为决策选择坐标位置(如图 2所示),则S_i={(1,1),(1,3),…,(5,5)},单一战略S_i表示agent A,agent B,agent C与agent D在九宫格中位置状态.agent A,agent B,agent C与agent D起点分别为(1,1),(5,1),(1,5),(5,5);终点分别为(5,5),(1,5),(5,1),(1,1).

为测试信任基准的有效性,实验假设agent A为合作的发起人,在agent A与其他agent相遇时,agent A向其他agent发起合作,若两者选择合作,将保留在同一个格子中,若合作者理性执行完成合作任务,各获得(e-r,r)的纳什均衡收益;若合作者具有选择争先盲目性,并没有按合作决定执行任务时,agent将得收益为(-r,r),对合作请求者造成一定的损失;反之,合作者选择不进行合作,各agent将返回上一步选择的格子中,获得(0,C_op)的纳什均衡收益;当4个agent均完成系统分配的所有任务时,MAS将结束系统阶段任务分配活动,此实验结束节点设为4个agent均到达终点.

实验中初始信任基准数值设为1,描述静态博弈环境,agent以均等概率理性选择,具有理性与自私性;在评价系统协作等级排序中,根据agent的收益情况,采用式(13)作为评价标准.其中α为权重比例,R_se为实际执行应答合作任务的收益,R_ac为请求合作任务均被执行时的收益,R_pc为应答合作任务均被执行时的收益.

式(13)可化简为式(14),

se/ac为合作任务中实际执行的次数与申请合作次数的比值,描述了信任基准不同时对agent间合作信任等级的评估;se/pc为合作任务中实际执行的次数与同意合作次数的比率,刻画了信任基准对agent博弈选择中理性程度的限制.采用比率组合方式作为系统协作等级排序标准,增加agent间的可比性,同时消除系统中组合概率的随机性.当agent A为合作申请者时,系统考虑AB,AC,AD,ABC,ABD,ACD,ABCD七种合作形式,对信任基准赋值工况的不同,进行100次测试,将平均值计入测试结果(由于实验中ABCD相遇次数较低,实验分析将不予以考虑),α为0.5.

表 1为静态系统中AB,AC,AD,ABC,ABD,ACD六种合作方式的合作情况,表 2为根据合作情况的不同,产生系统阶段协作等级排序评估.静态博弈系统中,理性选择即完成合作任务的实际执行率不受信任基准限制,按等概率执行选择.当系统阶段任务分配完成时,根据系统阶段协作排序等级,MAS中合作申请者将对合作者进行信任基准重置,重置结果如表 3所示,同时agent为提高自身协作等级,增强合作收益与合作次数,防止其他agent的冷漠对待及系统的定期淘汰,将对理性选择加以限定,其中理性选择比率为选择执行合作任务的权重,见表 3.

表1

Table 1

表1(Table 1)

表1 TB为1时测试结果 Table 1 Test results with TB=1 序号 信任 基准 理性 选择 执行合作 次数 申请合作 次数 合作次数 AB 1 0.5 0.41 2.96 0.75 AC 1 0.5 0.45 3.30 0.75 AD 1 0.5 0.34 3.41 0.72 ABC 1 0.5 0.04 0.1 0.07 ABD 1 0.5 0.01 0.13 0.03 ACD 1 0.5 0.03 0.14 0.08

表1 TB为1时测试结果 Table 1 Test results with TB=1

表2

Table 2

表2(Table 2)

表2 TB为1时合作情况测试结果 Table 2 Test results cooperation with TB=1 序号 信任 基准 理性 选择 执行申请 成功率 执行合作 成功率 综合 评价 协作排序 AB 1 0.5 0.1385 0.5467 0.3426 3 AC 1 0.5 0.1364 0.6000 0.3682 2 AD 1 0.5 0.0997 0.4722 0.2860 5 ABC 1 0.5 0.4000 0.5714 0.4857 1 ABD 1 0.5 0.0769 0.3333 0.2051 6 ACD 1 0.5 0.2143 0.3750 0.2946 4

表2 TB为1时合作情况测试结果 Table 2 Test results cooperation with TB=1

表3

Table 3

表3(Table 3)

表3 系统阶段信任基准更新 Table 3 Updating TB in stage of system 序号 协作排序 信任基准 理性选择 ABC 1 1.00 0.5 AC 2 0.75 0.6 AB 3 0.75 0.6 ACD 4 0.50 0.8 AD 5 0.50 0.8 ABD 6 0.25 1.0

表3 系统阶段信任基准更新 Table 3 Updating TB in stage of system

表 3所示,系统根据agent协作等级排序对信任基准赋值各异.协作排序越高,信任基准越大,agent间允许非合作或非执行的宽容度越大,体现agent间更注重长期合作的意愿;当信任基准较低时,agent在MAS中公信度较低,因此为提高自身协作等级,理性选择将给予较高数值,当理性选择为1时,描述agent将全部完成做答应的合作任务,属于完全理性博弈者,不存在任何自私或盲目的思想.当理性选择为0.5时,表示agent具有较高的协作等级,对自身各阶段博弈具有较强自主选择性与自私性,根据收益与机会成本较为灵活地选择是否执行合作任务.根据表 3系统阶段更新赋值,产生MAS新阶段合作情况,如表 4所示. 表 5为系统新阶段协作测试结果.

表4

Table 4

表4(Table 4)

表4 系统新阶段合作情况测试结果 Table 4 Test results of cooperation in the new stage 序号 信任 基准 理性 选择 执行合作 次数 申请合作 次数 合作次数 ABC 1 0.5 0.03 0.10 0.13 AC 0.75 0.6 0.49 3.42 0.79 AB 0.75 0.6 0.42 3.14 0.67 ACD 0.5 0.8 0.03 0.05 0.04 AD 0.5 0.8 1.27 3.84 1.50 ABD 0.25 1.0 0.06 0.13 0.06

表4 系统新阶段合作情况测试结果 Table 4 Test results of cooperation in the new stage

表5

Table 5

表5(Table 5)

表5 系统新阶段协作测试结果 Table 5 Test results of collaboration in the new stage 序号 协作 排序 执行申请 成功率 执行合作 成功率 综合 评价 新协作排序 ABC 1 0.4000 0.5714 0.4857 3 AC 2 0.1433 0.6203 0.3818 5 AB 3 0.1338 0.6269 0.3803 6 ACD 4 0.6000 0.7500 0.6750 1 AD 5 0.3307 0.8467 0.5887 2 ABD 6 0.4615 1.0000 0.4615 4

表5 系统新阶段协作测试结果 Table 5 Test results of collaboration in the new stage

分析表 4和表 5可得,由于系统阶段信任基准的更新,致使MAS中各agent对理性选择进行相应调整.以ACD,AD,ABD三种合作方式为例,理性选择的提高有助于系统以较高的比率执行并完成合作任务,执行合作任务频率的上升,促使申请合作任务中应答合作的概率提高,从而提高合作次数与执行申请成功比率,使agent向理性博弈者模式转化,并提高协作等级排序席位.而ABC,AC,AB三种组合方式具有较高的信任基准,在合作选择中具有较强的灵活性与争先性,使其在系统阶段更新后,排名有所变动,也反映出该实验可较好地描述agent在MAS运行中具有较高的自主性.

因此,通过变换系统中信任基准数值,可调整MAS中智能体的合作趋势与选择能力,使系统中各agent具有较强的合作性与竞争性,保证系统的高效稳定运行.

本文提出了基于动态无限博弈的多agent合作机制．以多阶段邀请、考核模式形成无限次重复博弈，以协作优先级主动选取协作智能体，并提出信任基准控制agent博弈选取的自私性，使其理性计划阶段决策，通过博弈结果反馈调整收益函数，控制协作优先级，实现闭环调控．最后以九宫格博弈实验，测试以4个agent作为基本单元采用动态无限次重复博弈时，信任基准对合作完成任务的影响程度．实验表明，信任基准可有效调整agent间的信任等级，促进系统中agent合作频率的提高，有利于提升ＭＡＳ完成客户请求任务的效率与系统的稳定性．