应急管理中自组织任务分配的博弈模型与应用

2022-10-31陈怡林张东煜

西安科技大学学报 2022年5期

苏军，陈怡林，张东煜

(西安科技大学理学院，陕西西安 710054)

0 引言

新冠疫情爆发以来，中国部分城市在必要时紧急采取封城管理，会导致决策迟缓、行动低效、物资调配困难等问题。群众自发组织快递人员及志愿者，根据防控态势自行确定“任务”，能有效地保障部分市民的交通、餐饮等各项服务。上述案例说明：在非常规突发事件发生后的短时间内，群众可通过自发、自愿组织形成团队并完成应急任务，这一基于自组织的应急管理方式发挥着至关重要的作用，进一步提高应急管理的时效性和科学性[1-3]。

多Agent系统(multi-agent system，MAS)[4-5]是一种以社会形式出现的分布式结构自组织系统，系统中没有中央权威或领导者，各Agent之间地位和作用平等、可以相互交流与合作，能有效地实现目标、共享资源和解决冲突。应急管理中的群众参与过程具有MAS的自组织特性[6-7]，各方往往会通过相互合作形成联盟，为社会产生最大利益。联盟形成博弈正是模拟这种行为的自然方式，但在联盟形成博弈或MAS的相关文献中[8-12]，很少有研究将应急管理自组织的问题与二者联系起来，文中的研究就是为了更好地建立这种联系。

Agent的联盟形成通常涉及3个过程：首先，每个Agent使用一些谈判程序自主加入联盟；其次，解决每个联盟的优化问题，使其效用最大化；最后，将每个联盟的价值公平分配给联盟中的成员[13]。自组织的联盟形成问题最突出的一类是任务分配问题，即Agent之间如何自发形成最大化系统效用或最小化偏离联盟动机的联盟结构，使得联盟结构中每个联盟各自对应一项或多项任务[14-19]。任务分配问题在众多背景中得到应用：ZHU等将复杂任务划分为多个子任务并提出一个实用的任务调度方案，包括任务调度机制、赢家联盟形成机制和报酬共享机制，实现有限云资源的合理调度[20]；YIN等在联盟形成的任务分配中考虑任务利润随时间流逝的情况，通过设计一种“退出-选择”机制以形成更多的联盟，从而提高系统的整体效用[21]；SUN等通过将多卫星系统中的自组织任务分配问题公式化为一个势博弈，提出一种基于博弈的分布式任务分配算法并证明博弈的每个纳什均衡是最大化执行任务数量的一个任务覆盖[22]。

在应急管理自组织系统中，Agent存在于一个特定的社交网络中，在无法独立完成某项任务时通常会充分调动自身资源，发动那些自己认识且有能力完成任务的Agent形成联盟，因此任意2个Agent之间并非彼此分散，而存在着一定的潜在关系，例如通信距离、信用度或组织层级等，可能会对博弈的效用和其他特征产生重大影响[23]。为刻画Agent之间的潜在关系及限制联盟形成过程的信息交互，文中在联盟形成过程中引入社交网络结构[24]。此外，许多现有的研究中假设每个Agent有且只能加入一个联盟并完成一项任务，但实际上系统中的部分Agent并没有贡献任何技能或资源，部分还有冗余，一对一的任务分配方式会导致大量资源浪费，因此在联盟形成过程中还考虑联盟的重叠属性[25]，用于解决传统的联盟形成过程中存在的问题并改进任务分配的结果。

笔者在应急管理自组织的大背景下，以合作博弈理论与MAS为基础，提出基于联盟形成的任务分配机制，通过找到使得系统效用最大的联盟结构，实现最优的任务分配，并设计联盟形成和优化的相关算法，最后在实际应用中检验模型和算法的可行性。

1 预备知识

1.1 基本概念

二元有序对(A,v)为A上的一个n人合作博弈，其中A={a1,a2,…,an}为参与人集合，特征函数v是定义在幂集2A上的一个实值集合函数v∶2A→R，v(Ø)=0，集合C⊆A称为一个联盟，特征函数值v(C)就表示联盟C中各参与人通过合作所能获得的价值。

MYERSON[26]引入图博弈，其可行联盟集合由无向图G(A,E)指定，其中，参与人A为无向图的节点，对任意ai,aj∈A，数对(ai,aj)∈E为无向图的边，表示参与人之间具有可促进合作的通信渠道或信任关系。当且仅当一个联盟C⊆A是由无向图G(A,E)所导出连通子图时，联盟才是可行的。图1反映标准合作博弈与图博弈中联盟的区别。

当联盟的收益同时受到联盟内外所有参与人的影响时，这种博弈称为具有外部性的合作博弈[27]。在具有外部性的合作博弈中，不相交的联盟组成的有限序列∏=(C1,C2,…,Cm)称为A的一个联盟结构，如果满足以下条件

1)∀i,j∈{1,2,…,m},i≠j,Ci∩Cj=Ø;

联盟结构的形成本质上是集合划分。

1.2 带技能的联盟形成博弈

联盟的价值v(C)可以用参与人所拥有的技能来定义：有一组技能S，每个参与人ai∈A技能集合为S(ai)⊆S，对于任意技能子集S′⊆S，技能价值函数f∶2S→R指定了拥有S′中所有技能的联盟可获得的收益，联盟C的值是v(C)=f(∪ai∈cS(ai))，这种博弈称为带技能的联盟形成博弈。

在带技能的联盟形成博弈中，联盟的价值还可通过技能和任务来表示。除了一套技能S，还有一套任务T，每个任务t∈T有技能诉求S(t)，参与人可将自身拥有的技能贡献给有相应技能诉求的任务，当单个参与人因技能不足或质量不够而无法完成任务时，可与其他参与人进行合作，直到满足任务的技能诉求。

对∀ai∈C，sj∈S(ai)，t∈T,q(ai,sj),p(ai,sj)为参与人ai使用技能sj的质量和成本，q(t,sj)为任务t对技能sj的质量需求。如果联盟满足以下2个条件，则为有效联盟，能成功完成至少一项任务。

1)联盟所拥有的技能集合包含任务诉求的技能集合，即对于∀ai∈C,t∈T

∪t∈TS(t)⊆∪ai∈CS(ai)

(1)

2)联盟中每一个参与人提供的任意一项技能质量都至少为任务所需的技能质量需求，即对于∀ai∈C,t∈T,sj∈S(ai)∩S(t)

q(ai,sj)≥q(t,sj)

(2)

对于任务T的每个子集T′⊆T，任务价值函数F∶2T→R指定完成所有任务T′的有效联盟可以获得的收益，而联盟C的值为任务T′的价值与联盟使用相应技能的总成本之差，即对于∀ai∈C,t∈T,sj∈S(ai)∩S(t)，当联盟C满足式(1)(2)时

(3)

这一博弈方式实现联盟与任务之间的对应，同时也优化联盟的价值。

2 基于联盟形成博弈的自组织任务分配机制

2.1 模型要素

假设参与人是群体理性的，都试图最大化公共效用。在一个超可加的环境中，理性的参与人更偏向于形成大联盟，当大联盟形成时再考虑成员之间的效用分配，然而在文中的模型背景中，成员间的效用分配不太重要或根本不存在，所以并不一定需要一个超可加性环境。

在自组织联盟形成的任务分配过程中引入MAS，将其建模为一个图限制下带技能的联盟形成博弈，下面给出模型的相关定义。

定义1 自组织系统中的社交网络G=(A,E)为一无向图，其中A={a1,a2,…,an}为Agent集合。Agent之间的关系由函数g∶A×A→{0,1}定义，若对∀ai,aj∈A,i≠j，g(ai,aj)=1为ai和aj存在关系，形成无向图的边(ai,aj)∈E；若g(ai,aj)=0，则表示ai和aj之间不存在关系。

定义2 ∀ai∈A由四元组〈S(ai),P(ai),L(ai),Q(ai)〉构成，其中P(ai)={p(ai,sj)|∀sj∈S(ai)}为ai的技能成本向量；L(ai)={aj|g(ai,aj)=1}为ai的邻居集合；Q(ai)={q(ai,sj)|∀sj∈S(ai)}为ai的技能质量向量，q(ai,sj)越高，说明ai所拥有的技能sj越强。

定义3 ∀t∈T由四元组〈S(t),I(t),Q(t),F(t)〉构成，其中I(t)为任务t的发起者；Q(t)={q(t,sj)|∀sj∈S(t)}为技能质量需求向量；F(t)为任务t的价值函数。

为避免资源的浪费，允许拥有冗余技能的Agent加入不同的联盟，因此联盟会出现重叠，即对任意2个联盟Ci,Cj⊆A,i≠j，允许Ci∩Cj≠Ø.文中引入虚拟Agent的概念，将重叠联盟形成问题转化为非重叠的联盟形成问题。

2.2 联盟形成博弈模型

将自组织的任务分配问题建模为带技能的联盟形成博弈(N,v)，其中N为虚拟Agent集合。根据式(3)，对任意t∈T，联盟Ct的价值定义为

(4)

式(4)中的任务价值函数F与式(3)含义一致，两式区别在于式(4)中联盟Ct所能完成的任务至多只有一项，且v(C0)=0。

在联盟结构∏中，每个联盟Ct都会完成相应的任务，当一批任务被完成后，可获得一定的系统效用，定义为

(5)

即系统效用是∏中所有联盟价值之和。

通过建立联盟形成博弈模型(N,v)，在虚拟Agent集合N中形成不相交的联盟结构∏，实现任务与虚拟Agent联盟之间的一一对应，从而构建一个合理的任务分配机制。

注：模型中形成的联盟除空闲联盟C0外都是有效的，这是实现合理任务分配的前提。

2.3 优化模型

基于Agent群体理性的特性，任务分配的目标就是寻找某个使得系统效用最大的联盟结构∏*∈arg maxU(∏)。

建立优化模型

(6)

约束条件 ∀t∈T,ai∈Ct,sj∈S(ai)∩S(t)，

∪su(ai,sj)=1sj⊆S(ai)

(7)

S(t)⊆∪ai∈CtS(ai)

(8)

q(ai，sj)≥q(t,sj)

(9)

式中su(ai,sj)=1为ai贡献了技能sj，式(7)表示每个ai在各个任务中的技能分配总和包含于自身所拥有的技能；式(8)表示联盟Ct的技能集合包含任务t的技能诉求；式(9)表示联盟中每个ai提供任意一项技能sj的质量都至少为任务t对技能sj的质量需求。

联盟结构的优化过程基于虚拟Agent的偏好顺序。在该模型中，虚拟Agent的偏好顺序由系统效用U(∏)决定，并根据偏好顺序选择加入或离开哪个联盟。

注：只有有效联盟结构之间才可进行稳定性的比较，虚拟Agent的转移为可行转移时，优化才有意义。

2.4 算法设计

联盟结构的形成与优化，意味着搜索N上所有的有效联盟结构空间，直到找到使得系统效用最大的某个联盟结构∏*。引入相关算法描述上述过程，可分为以下2个步骤。

1)生成初始的有效联盟结构。

2)依次更新当前的有效联盟结构，寻得最优。

2)at与某一邻居ap∈L(at)拥有不同的技能sj和si，且si∈S(ap)∩S(t)，q(ap,si)≥q(t,si)，则将ap直接加入集合Ct，将ap的新技能si加入集合S(Ct)。

重复上述步骤，直到找到所有的Ct和S(Ct)，并生成初始的有效联盟结构∏。具体算法如下。

算法1 初始联盟结构形成

∏←Ø

for allt∈Tdo

for allsj∈S(at) do

ifsj∈S(t) andq(at,sj)≥q(t,sj) then

S(Ct)←S(Ct)∪{sj}

S(at)←S(at)/sj

end if

end for

L=L(at)

whileL≠Ø and |S(Ct)|<|S(t)| do

ap←first(L)

for allsi∈S(ap) do

if ∃si=sj,q(ap,sj)≥q(t,sj) then

ifp(at,sj)>p(ap,sj) then

S(ap)←S(ap)/sj

S(at)←S(at)∪sj

end if

else if ∃si∈S(t) andq(ap,si)≥q(t,si) then

S(Ct)←S(Ct)∪{si}

S(ap)←S(ap)/si

end if

L←L/{ap}

L←append(L,L(ap))

end for

end while

if |S(Ct)|=|S(t)| then

∏←∏∪{Ct}

end if

end for

return ∏

重复上述迁移过程，如果没有一个虚拟Agent在其他虚拟Agent策略不变的情况下移动，则称当前联盟结构是纳什稳定的，这样的联盟结构使得系统效用最大，其中的所有虚拟Agent都不愿意离开当前所处联盟或加入任何其它联盟。具体算法如下。

算法2 联盟结构优化

REPEAT

if ∏′ is a effective coalition structure then

∏i,j=∏′;U(∏i,j)=U(∏′)

end if

UNTIL the partition is a Nash-stable partition

3 实验设计

3.1 背景及参数设置

新冠肺炎疫情爆发期间，群众自组织抗疫的成功案例数不胜数，其中最具代表性的自组织团队之一是“互联网人YO！群”，这是由77位来自不同公司的互联网人自发组织的临时性抗疫志愿服务团队。他们从社交媒体上了解到疫情一线的物资极度匮乏，便通过微信群等社交工具发动各自亲友加入组织。为缓解物资短缺的情况，他们将团队成员分成了3个组，分别是资源组：负责筹集和对接各类资源；医院组：负责收集医院信息及发放物资；财务组：负责记录财务和筹集善款。YO！群中的成员各司其职，充分发挥自身作用并不断发动自我社交网络中的好友加入组织，最终在7天时间内成功救助49家医院，为抗疫做出巨大贡献。

在互联网人YO!群的自组织救灾活动中引入MAS，以Agent的交互行为及合作关系模拟互联网人自发组织、协作分工、供需对接的自我管理方式，建模如下：假设MAS中共有6个不同的Agent，即A={a1,a2,a3,a4,a5,a6}，社交网络如图3所示，3项救灾任务为T={A,B,C}，其中任务A：筹集和对接各类资源、任务B：收集医院信息及发放物资、任务C：记录财务和筹集善款。Agent共拥有8种技能，其中每位成员的技能质量与成本不同，且种类不低于2种，不超过5种。记技能集合为S={s1,s2,…,s8}，对于∀ai∈A，S(ai)⊆S且|S(ai)|∈[2,5]，ai贡献技能sj的成本p(ai,sj)是[10,20]的随机数，质量q(ai,sj)是[0,1]的随机数，指定任务发起者为：I(A)=a1，I(B)=a2，I(C)=a5。

3.2 结果分析

首先给定任务所需的技能及相应质量，见表1，并随机生成每个Agent的技能配置信息、技能质量和成本，分别见表2和表3。

表1 任务所需技能质量

表2 Agent技能质量

表3 Agent技能成本

实验结果表明，互联网人YO!群的任务分配机制可在MAS中建模为一个带技能的联盟形成博弈，其中的社交网络结构充分反映社会分布式网络环境的真实情况、降低联盟结构形成的复杂度、加快优化过程的收敛速度；同时，通过算法1可找到合理的初始联盟结构，实现任务与联盟的一一对应，从而验证算法的有效性和模型的适用性。

应急管理中群众的自组织救灾机制不同于传统的自上而下管理机制，尽管自组织系统本身是杂乱无章的，但带技能的联盟形成博弈模型要求群众根据任务的技能需求形成对应联盟，其实质是自组织系统中遵循的一种特定规则，可使得系统从无序走向有序、从低效走向高效，符合应急管理的宏观秩序，能为组织化救援创造一定的缓冲时间。同时，该模型也实现了应急管理、博弈论和人工智能3个领域的结合。