基于加权协同算法的Robocup救援协作方法

摘要

本发明提供一种基于加权协同算法的Robocup救援协作方法，通过定义基于角色的加权协同图，并对单个智能体能力和多个智能体协作能力建模；建立智能体协作团队，对智能体交互性进行有效地建模；使用加权协同图学习算法估算执行任务的最优角色分配。学习算法从平时仿真中角色任务分配的例子、比赛中得到的观测值以及一个接近最优的角色任务分配策略算法中获得一个加权协同图学习算法。该方法用于Robocup救援比赛平台，大量的实验仿真测试结果表明，加权协同图的方法能够形成一个近似最优的智能体协作团队。

说明书

技术领域

本发明涉及一种基于加权协同算法的Robocup救援协作方法。

背景技术

在很多动态情况下，由于任务的要求和环境条件的限制，拥有着不同功能和 职责的异构智能体会集中起来一起合作完成复杂的任务。作为Robocup的一个 新领域，RobocupRescue仿真比赛提供了一系列标准任务，来促进分布式人工智 能、智能机器人技术及其相关领域的研究和发展。

Robocup救援仿真系统(RCRSS)的主要目的是通过建立多智能体搜救和协 作体系，在发生灾难的时候，在仿真平台上通过集成灾难信息，火势预测、行为 规划等方法来提供对灾难情况下的决策支持。RCRSS中具有六类可控制智能体， 分别为医院(Ambulance Centre简称：AC)，医疗队(Ambulance Team简称：AT)、 警察局(Police Office简称：PO)、警察(Police Force简称：PF)、消防局(Fire  Station简称：FS)、消防队(Fire Bridge简称：FB)，另外系统中存在市民智能 体(Civilian)，它是需要救助的对象。其多智能体系统仿真环境如图1所示。

目前赛场中针对协作救援，有以下几种方法：

智能体对任务投标，效益最高的投标者将获得任务的任务拍卖技术；

ASyMTRe算法，对智能体功能和模式进行建模，任务被定义成一组输出函 数的同时，形成了一组为完成任务的多智能体团队，其中可行的队伍根据效用函 数进行优先级排序；

多机器人任务分配(MTRA)方法，它利用任务分配后的完成情况估算协作 的价值来给角色间分配多种任务；

基于拍卖的MRTA技术同样应用广泛，机器人的能力被建模成一组服务资 源后进行角色分配；

最近提出了如何将具有一定自主性的智能体通过学习从而和一个未知的队 友协作的问题，它的任务角色的分配和通过观察某特定智能体后学习效果有关； 卡耐基梅隆大学的Somchaya Liemhetcharat曾提出过利用图的模型并智能体协作 中的训练数据制定一种基于图模型的学习方法。

上述这些方法都没有对智能体团队的协作效果进行建模。而在RCRSS仿真 中，更需要关心的是如何在Robocup rescue救援仿真动态环境下如何形成一个有 效的智能体救援队策略，而不是只是只专注于单个智能体的行为和动作。

由于在RCRSS中，智能体遇到问题是随机的并且在初始时刻，单个智能体 的能力、多个智能体之间的合作均是未知的，为了找到一种能够完成单个任务并 且获得最大的收益的任务分配策略，因此，在动态的环境下，应当专注于两个问 题：1、如何单个智能体如何通过学习来适应一个未知的队友2、如何在动态环 境中，形成一个高效的智能体团队。因此观测协同图中智能体和智能体团队之间 的相互作用，获得基于智能体功能的协作和任务分配加权协同图。

发明内容

本发明的目的是提供一种基于加权协同算法的Robocup救援协作方法，解 决在动态救援仿真环境下，机器人智能体团队在初始情况下的个人能力和团队协 作能力是未知的，如何快速地形成一个高效的多智能体团队，从而为智能体找到 最优的角色任务分配策略的问题。

本发明的技术解决方案是：

一种基于加权协同算法的Robocup救援协作方法，

定义基于角色的加权协同图，并对单个智能体能力和多个智能体协作能力建 模；

建立智能体协作团队，对智能体交互性进行建模；

使用加权协同图学习算法估算执行任务的最优角色分配。

进一步地，对智能体在救援初始时刻的处理单个任务能力进行建模，将智能 体协作执行某一任务的效果进行量化：F(A)，若F({PF，FB})>F({PF，AT})，选 择(PF，FB)组合完成任务。

进一步地，对智能体协同状态建模，引入兼容函数φ，定义φ： 其中φ是单调递减函数，输入距离参数，输出兼容性，距离越 短代表兼容性越高，兼容性越高表示协同效果越好。

进一步地，加权协同图模型S是一个多元数组{G,C}，其中：

G＝{V,E}是一个加权连通图；

每个a_i∈A都会用一个顶点v_i∈V表示，a_i代表一个智能体；

e＝(v_i，v_j，w_i，j)∈E是顶点v_i,v_j之间带有权重w_i,j∈Z⁺的边；

每个顶点都有一个绕回自己的圈；

${\forall a}_i\in A,\exists C_i\in C$使得C_i＝{C_i，1，...，C_i，M，其中，是a_i在角色r_a中的能力。

进一步地，利用加权协同图模型，把PF，FB，AT三种智能体在动态变化的 灾难模型中的能力用正态分布表示；

智能体团队协同函数：一个角色策略π：R→A分配的智能体团队协同 关系为：

$S\left(\pi \right)=\frac{1}{\left(\begin{array}{c}\left|R\right|\\ 2\end{array}\right)}·\underset{r_{\alpha },r_{\beta }\in R}{\Sigma }{S}_2(\pi \left(r_{\alpha }\right),\pi \left(r_{\beta }\right),r_{\alpha },r_{\beta })---\left(4\right)$

协同函数返回一个正态分布，代表智能体团队在角色分配策略下的表现。

进一步地，在加权协同图基础上利用逼近算法获得最佳的救援团队：利用分 区的思想假设一个任务需要智能体的个数是固定的，且该任务的子任务所需智能 体个数也是固定的，假如队伍的人数n是未知的，利用逼近算法不断将递增的n 迭代运算，返回所有适合的n值，然后选择最优的个数。

进一步地，在加权协同图中，将代表智能体能力的正态分布转化为它们的均 值，来选择最优的队伍。

进一步地，由加权协同图的学习算法得到最优加权协同图：

随机生成初始加权协同图，用实例T来估计智能体的处理任务的能力；

智能体团队执行救援策略，基于实例的对数似然估计函数得到最优的加权协 同图。

进一步地，加权协同图的学习算法具体为：

随机生成初始加权协同图，生成顶点，并在图中随机加了任意权重的边，让 协作图连通，每个顶点都有自循环的边；

在智能体进行消防灭火的时候，探索加权协作图的空间，通过以下四种情况 生成一个相邻的图结构：

在小于最大权值时，随机对一个边的权值增加1；

在大于最小权值时，随机对一个边的权值减小1；

在两个顶点间增加一条新边；

把一个不影响图连通的边消除；

若相邻空间解劝协同图有更好的消防表现，则取代现有加权协同图；最后得

到最优的加权协同图。

本发明的有益效果是：提出了一个学习算法，该学习算法从平时仿真中角色 任务分配的例子、比赛中得到的观测值以及一个接近最优的角色任务分配策略算 法中获得一个加权协同图学习算法。将上述方法用于Robocup救援比赛平台， 大量的实验仿真测试结果表明，加权协同图的方法能够形成一个近似最优的智能 体协作团队。

附图说明

图1实施例的Robocup Rescue仿真环境。

图2是一个基于任务关系的救援仿真全通图。

图3是修正后的协作图。

图4是带有兼容性的协同图。

图5是简单救援加权协同图模型。

图6是最优分配策略算法流程图。

图7是救援智能体协作简图。

图8是加权协同图交互学习对比曲线。

图9是救援智能体随机救援的效果。

图10是使用加权协同图后。

图11是比赛仿真初期。

图12是使用加拍卖算法同图。

图13是使用加权协同图。

图14是加权协同图与拍卖算法和一个随机协作策略进行比较后的分数统计 图。

具体实施方式

下面结合附图详细说明本发明的优选实施例。

实施例利用加权协同图对救援仿真平台的六种智能体角色进行建模，并使用 加权图的结构组成理想团队并测试不同的角色分配对整个救援团队的救援效果 的影响。

实施例利用加权协同图模型，把PF，FB，AT三种智能体在动态变化的灾难 模型中的能力用正态分布表示。智能体协作团队用一个集合表示，在协同图模型 的基础上加上权重来提高模型的表达能力，其中关于学习算法，利用较少的数据 域进行训练学习，每个角色的智能体只用到了1个数据点，同时，模拟了不同团 队形成是如何影响任务完成城市救援效果的，然后估算出了最优的团队和任务分 配策略，解决方案分为三个步骤：

A、定义基于角色的加权协同图，并对单个智能体能力和多个智能体协作能 力建模；

B、建立智能体协作团队，对智能体交互性进行有效地建模；

C、使用加权协同图学习算法估算执行任务的最优角色分配。

在Robocup救援仿真环境下的加权协同图，首先，定义任务环境；在救援仿 真环境下定义加权协同图；建立基于加权协同图的救援仿真模型。

定义任务环境

在救援仿真初期，城市发生一场地震，平民被困在废墟中，建筑物发生火灾， 道路被路障阻塞，一组救援团队(FB，PF，AT)被部署在城市中，以援救更多 的市民，最大限度地控制建筑物的火势，减小城市遭受灾难的损失为目标，其中 PF可以清除路障，AT救助受伤平民，FB对建筑物进行灭火，由于在仿真初期， 各智能体没有合作过，各自能力也是未知的，所以，需要寻求一个寻找合作效率 最高的救援团队。

为了完成一个复杂的救援任务T，可以定义一个模型F，其中F(A)是这个模 型的实例，为了更好的表达在救援活动中三类移动智能体之间合作关系，可以利 用它们完成同一个任务网络的联系，制定一个加权连通图模型，顶点代表智能体， 边代表了智能体的关系，权重表示合作的协同系数d，d越小，合作的越好，成 本越低。

图2是一个基于任务关系的救援仿真全通图。但一个全通图并不能很好地捕 捉智能体合作间的传递性，比如PF和FB合作的很好，FB和AT合作的很好， 那么PF和AT合作的很好，于是将全通图2修正为一个连通图图3，把(PF， AT)移除，为了模型化智能体之间的协同系数d和它们基于任务的关系之间的 负相关性的关系，可以引入一个权重函数w：由在图中PF和FB最小距离得到 w(d(PF,FB))，w(d)≥0且w(d)和d成反比关系，作为一个简化假设，并且假设 权重是能够完全捕捉基于任务的智能体关系的。

救援仿真环境下定义加权协同图

下面对智能体在救援初始时刻的处理单个任务能力进行一个简单建模，并将 智能体合作执行某一任务的效果进行量化：F(A)，这样如果AT和FB都能与PF 很好地合作，然而PF1处理单个任务能力比PF2要好，此时F({PF，FB})>F({PF， AT})，选择(PF，FB)组合完成任务，虽然F是一个未知的分布，但它仍可以被分 解成多个子任务，每个子任务都可以当作是标准正态分布，其中单峰函数可以表 示智能体完成任务的平均表现，而对称分布又代表了智能体能力的多样性。下面 给出一个协同图的定义1：

A：智能体团队，T：接受的复杂任务，M：分解复杂任务T后的子任务，F： 2^A→X(X是具有未知分布的M维随机变量)，F代表了救援仿真中的未知 世界灾难模型，F(A)是在这个世界模型中智能体团队得到的世界模型，F(A)值和 智能体团队A处理M子任务情况有关。V：计算在基于子任务M的基础上复杂 任务T完成的整体价值。例如：$V_{\mathrm{sum}}\left(X\right)={\Sigma }_{m=1}^{M}X\left(m\right),V_{\max }\left(X\right)={\max }_{m=1}^{M}X\left(m\right),$当且仅当X(m)＞τ，有V_task(X)＝V_sum(X)，其中，若子任务M低 于设定的阈值τ，那么此任务的值为0。X(m)表示X中的第m元素。得到一个 最优智能体团队：有V(F(A^*))≥V(F(A))。

下面将协同的思想带入救援仿真环境中，在救援仿真中，用被救的平民 (civilian)数量和城市中建筑物(building)状态的组合定义一个函数V。对 于每个角色分配策略p，每个角色都需要分配一个智能体类型。同一个类型的智 能体a∈A可以被分配多个角色，比如：使得π(r_α)＝π(r_β)，这 表示了多个同样的智能体都会扮演这个角色。因此给出定义2：

有N个智能体类型(N＝6)和M个角色，为找到属于价值函数V的最佳的角 色分配策略p^*，假设角色分配策略表现为一个正态分布，每个智能体类型a_i∈A与M个正态分布{C_i,1,...,C_i,M}相关，其中C_i,a是智能体a_i在 担任角色r_a时单独处理任务的能力，为了有效地对智能体协同情况建模，引入兼 容函数φ，兼容性越高表示协同效果越好，兼容性是可以传递的——如果a₁和a₂高度兼容，a₂和a₃高度兼容，那么a₁和a₃高度兼容。定义其中 φ是一个单调递减函数，输入距离参数，输出兼容性，短距离代表了高兼容性。 如图4，PF，AT，FB三个智能体间距离代表了它们之间的兼容性，PF和FB具有 高兼容性，但是相对于自己的兼容性低，同理，由传递性可知，PF和AT的兼容 性也很高。

基于加权协同图的救援仿真模型

加权协同图模型S是一个多元数组{G,C}，其中：

G＝{V,E}是一个加权连通图；

每个a_i∈A都会用一个顶点v_i∈V表示，a_i代表一个智能体；

e＝(v_i，v_j，w_i，j)∈E是顶点v_i,v_j之间带有权重w_i,j∈Z⁺的边；

例如，每个顶点都有一个绕回自己的圈。

使得C_i＝{C_i，1，...，C_i，M其中是a_i在角色r_a中的能力。为了通过加权协同图顶点间的距离获取智能体之间的兼容性 函数φ，因此调整成对协同函数：分配给角色r_a，r_b的智能体a_i，a_j之间的成对 协同关系式：S₂(a_i，a_j，r_α，r_β)＝φ(d(v_i，v_j))·(C_i，α+C_j，β)  (1)

其中，d(v_i,v_i)＝w_i,i，而且因为i≠j，d(v_i,v_i)＝w_i,i是在加权协同图中顶点 v_i,v_j之间最短距离，设图S中的S(A)是一对协同队的平均值，也就是：

$\frac{1}{\left(\begin{array}{c}\left|A\right|\\ 2\end{array}\right)}·\underset{\{a,a^{\prime }\}\in R}{\Sigma }{S}_2(a,a^{\prime }).$如图5，图5简单救援加权协同图模型。S(A)返回一组 代表任务完成情况的正态分布，由上述定义可得：

${\mu }_{A,M}=\frac{1}{\left(\begin{array}{c}\left|A\right|\\ 2\end{array}\right)}·\underset{\{a,a^{\prime }\}\in A}{\Sigma }{w}_{a,a^{\prime }}·({\mu }_{a,m}+{\mu }_{a^{\prime },m})---\left(2\right)$

${\sigma }_{A,M}=\frac{1}{\left(\begin{array}{c}\left|A\right|\\ 2\end{array}\right)}·\underset{\{a,a^{\prime }\}\in A}{\Sigma }{w}_{a,a^{\prime }}·({\sigma }_{a,m}^2+{\sigma }_{a^{\prime },m}^2)---\left(3\right)$

其中，在智能体在处理子任务中w_a，a′＝w(d(v_a，v_a′))和 被认为是独立的。由此类推，制定一个智能体团队协同函 数：一个角色策略π：R→A分配的智能体团队协同关系为：

$S\left(\pi \right)=\frac{1}{\left(\begin{array}{c}\left|R\right|\\ 2\end{array}\right)}·\underset{r_{\alpha },r_{\beta }\in R}{\Sigma }{S}_2(\pi \left(r_{\alpha }\right),\pi \left(r_{\beta }\right),r_{\alpha },r_{\beta })---\left(4\right)$

所以协同函数返回一个正态分布，它代表了智能体团队在角色分配策略下的 表现。

利用加权协同图构建协作团队

在加权协同图基础上利用一个逼近算法获得最佳的救援团队，由于救援团队 的数量是由救援任务中外在环境所限制的，利用分区的思想假设一个任务需要智 能体的个数是固定的，且该任务的子任务所需智能体个数也是固定的，假如队伍 的人数n是未知的，可以利用该算法不断将递增的n迭代运算，返回所有适合的 n值，然后选择最优的个数，在加权协同图中，为了排列选择最优的队伍，将代 表智能体能力的正态分布转化为它们的均值，用于简化比较步骤。伪代码如下：

A＝RandomTeam(A，n)//随机生成一个队

Use S(A)to get ArrayList(N_A，1….N_A，M)then  v＝V(Evaluate(N_A，1，p)...Evaluate(N_A，M，p))//获得该 队伍智能体完成任务能力的评估值

For k＝1 to k_max do

{

A′＝RandomTeamNeighbor(A)//若在救援中没有 所需要的智能体，则利用相邻智能体代替

v′＝V(Evaluate(N_A′，1，p)，....，Evaluate(N_A′，M，p))

If p(v，v′，Temp(k，k_max))＞random()//引入 温度预测，Temp为一个温度函数

A＝A′ and v＝v′

Return  A

}

由上述算法得到了一个近似最优的团队，下面将寻求最优的角色分配策略。

建立最优协作分配策略

已知一个加权协同图S，希望使用S来估计出最优角色分配策略π^*。但是， 协同函数S返回的是一个正态分布。所以在定义估值函数，它使用一个风险因素 ρ∈(0，1)将正态分布转换为一个数：(其中 φ^-1标准正态累计分布函数倒数。当ρ＝1/2时，返回值等于分布的平均值，当 ρ＞1/2(＜1/2)时，方差递增(递减)。有了为分布分级的估值函数，通过智能体对 建筑物灭火这一任务进一步探索角色分配策略，形成估算出的最优团队。算法开 始使用一个随机分配策略，通过改变其中一个角色的智能体类型生成相邻策略。 新的策略使用Evaluate计算分数以及RCRSS提供的标准服务器RoboRescue-V1、 1的温度模拟器。

为了使用上述的加权协同图模型，必须从数据中学习一个加权协同图模型， 下面提出一种使用角色分配策略的实例学习的加权协同图学习算法。其中V是 未知的，但是可以得到V的实例T＝{(π₁，V₁)，....，(π_|T|，V_|T|)}，尽管V(π)是一个 分布函数，但在每个在T中的策略只使用一个实例，比如

$\forall ({\pi }_i,V_i),({\pi }_j,V_j)\in T,{\pi }_i\ne {\pi }_j.$

图6最优分配策略算法流程图，关于加权协同图的学习算法有两步：

1.随机生成初始加权协同图，用实例T来估计智能体的处理任务的能力；

2、智能体团队执行救援策略，其中加权协作图是多样的，这样让智能体团 队更好的探索了加权协作图的空间，基于实例的对数似然估计函数得到新的加权 协同图。

在伪代码中，利用RandomGraphStructure函数生成一个初始的加权协作图， 它生成了个顶点，并在图中随机加了任意权重的边从而让协作图连通，每个 顶点都有自循环的边。然后，在智能体进行消防灭火的时候，用 NeighborGraphStructure来探索加权协作图的空间。通过以下四种情况生成一个 相邻的图结构：

a.在小于最大权值V_max时，随机对一个边的权值增加1；

b.在大于最小权值V_mim时，随机对一个边的权值减小1；

c.在两个顶点间增加一条新边；

d.把一个不影响图连通的边消除。

因为加权协作图的边的权值时按照1为单位增减的正值，所以能探索边的 所有权值的组合，而且c、d两种情况会改变顶点的直接连接情况。如下是加权 协同图的学习算法的伪代码：

G＝RandomGraphStruture(A)//随机生成一 个加权协同图模型

C←EstimateCapabilities(G，R，T)//此时当前 协同图中智能体协作的能力

S←(G，C)，l←LogLikelihood(S，T)//对数 似然估计值

for k＝1to k_max do{

G′←NeighborGraphStructure(G)

C′←EstimateCapabilities(G′，R，T)

S′←(G′，C′)，l′←Loglikelihood(S′，T)

}//遍历k_max次，建立相邻空间的加权协同图结 构，然后探索图的空间

if P(l，l′，Temp(k，k_max))＞random()then//若 相邻空间解劝协同图有更好的消防表现

S←S′，l←l′//取代现有加权协同图

return S

智能体协作能力测试

上面提到的EstimateCapabilities方法，有N个智能体和M个角色，因此需 要估计NM个正态分布。假设在|T|＞2NM的约束条件下，加权协作图的结构 是已知的，可以计算两个顶点v_i，v_j间的距离。若v_i≠v_jv_i¹v_j，则d(v_i，v_j)是 它们之间的最小距离。若v_i＝v_j，则d(v_i，v_j)＝w_i，j，例如顶点v_i的自循环边的权 值。通过距离，φ可以计算出成对智能体兼容性。EstimateCapabilities以最大 化训练实例T的对数似然估算出正态分布。从一个单独的训练样本 (π，V(π))∈T中可形成一个等式，它包含智能体能力的均值和方差。

图7是救援智能体协作简图。图7代表了救援仿真中三种移动智能体类型和 两个角色的加权协同图的例子。假设智能体能力C_i，α是未知的，并且π＝(r₁→FB，r₂→AT)，同时它们之间的协同作用为： $S\left(\pi \right)=\phi \left(d(v_1,v_2)\right)(C_{\mathrm{1,1}}+C_{\mathrm{2,2}})=\frac{1}{2}(C_{\mathrm{1,1}}+C_{\mathrm{2,2}}),$因此V(π)的对数似然函数是：

$-\frac{1}{2}\log (2\pi ·\frac{1}{4}({\sigma }_{\mathrm{1,1}}^2+{\sigma }_{\mathrm{2,2}}^2))-\frac{{(V\left(\pi \right)-\frac{1}{2}({\mu }_{\mathrm{1,1}}+{\mu }_{2,2}))}^2}{2·\frac{1}{4}({\sigma }_{\mathrm{1,1}}^2+{\sigma }_{\mathrm{2,2}}^2)}---\left(5\right).$

T中的每个实例都与一个包含智能体能力的均值和方差的表达式相对应，为 了求得能使T的对数似然函数最大的分布函数，对数似然函数的总和也必须是 最大化的。均值最初用一个最小二乘解计算程序估算，然后方差根据提供的均值 用一个非线性解算器估计。

实验和结果

Robocup Rescue救援仿真比赛要求智能体在300个周期内相互协作，完成 救援任务，比赛结束后，根据评分V判断救援的成果，比赛的评分标准是 分数主要是由营救市民的个数，道路清理的程度，扑灭建 筑的数量来综合给出的，每个智能体在救援中体现了各自的特点和作用，它们是 相辅相成的，只有高效的协作才能更好的发挥智能体的作用并获得更高的分数， 所以评分的高低间接的体现出了智能体之间的协作能力和算法的效率。下面将从 3个方面测试评价加权协同图。

一、交互协作效率的改善

将算法用于Robocup Rescue仿真平台中，论证加权协同图能否很好地获取 动态环境下智能体的交互情况。使用在Robocup Rescue中4种智能体协作的算 法和Robocup2013比赛中的Istanbul场景，其中有46个救援智能体，为了测试 加权协同图的交互性和学习的特点，首先：对于这46个智能体，在仿真初期， 每个智能体都会随机赋予它一个算法来控制，因此在一场比赛中的协作策略将是 对46个智能体的各自协作算法的分配协作。对比赛进行多次仿真，并从中随机 取出400个警察智能体(PF)的样本，在仿真结束后，对平民(civilian)的生 命值(hp)和存活的智能体的个数，以及建筑物烧毁程度，进行一次加权求和。 首先在400个样本上进行6轮交叉学习，在数据中提取300个样本作为训练学 习组，剩余的100个样本作为测试组，由于样本的数量不足以计算出准确的加权 协同图智能体能力的方差C_i,α，可以将它设为一个常数，接着用从6轮交叉比对 中学习的加权协同图来估计最优的角色分配策略，为了得到交互情况的曲线，以 200个迭代次数为单位，每200次中随机抽取10个样本的对数似然函数值，绘 制曲线。图8测试了在样本中随机抽取50个样本的对数似然函数曲线，根据图 8可以看到加权协同图有效的模拟了测试中Robocup救援任务分配策略的交互 情况，证明了加权协同图交互学习的有效性。

二、智能体团队决策的改善

为了测试使用加权协同图后的智能体协作的改善，使用Robocup2013比赛 提供的Kobe地图进行测试，对比使用前和使用后的效果，从图9中可以看出， 未使用加权协同图时，在着火建筑物区域，只有两只消防队和一个警察智能体在 进行救援，但是附近区域的一支消防队和一个警察)没有参与该救援协作，导致 着火建筑物群火势较大，救援效果不理想。

图10是使用了加权协同图后的效果，图中可以看到，原先没有参与救援协 作的消防队和警察智能体参与到了扑灭着火建筑群的任务中来，警察有效的清理 了路障，4个消防队也迅速控制火势，将受灾面积降到了最小，由此可见，在救 援策略上，智能体之间的协作效率有了很大的改善。

三、整体效果的改善

将加权协同图与拍卖算法和一个随机协作策略进行比较。首先在Kobe地图 上进行多次对比测试，然后选择Robocup2013比赛中的地图，统计每种策略方法、 每张地图比赛得分，进行对比。图11是比赛仿真初期，图12使用拍卖算法，图 13使用加权协同图。

下面针对不同地图进行10次对比测试，如表1,比较最后所得的平均分：

表1分数统计表

测试地图(10次) VC2 Berlin2 Kobe3 Istanbul Mexico2 Eindhover Paris3 拍卖算法最高分 140.12 97.67 67.42 17.34 19.54 20.25 134.68 加权图最高分 159.22 120.45 80.55 19.23 30.1 26.43 157.11 拍卖算法最低分 125.42 89.65 60.78 12.95 13.43 14.22 110.76 加权图最低分 143.09 102.56 70.92 16.45 18.7 21.33 147.43 拍卖算法平均分 132.45 94.25 65.4 15.41 16.21 17.65 120.98 加权图平均分 155.26 108.17 73.36 18.11 21.67 24.12 153.88

将上面数据绘制成柱状图，如图14所示，进行对比后发现，引入加权协同 图后，智能体协作救援的整体效率有了很大提升，证明了利用加权协同图进行多 智能体任务分配的有效性。

实施例根据RobocupRescue仿真比赛的特点，首先定义基于角色的加权协同 图，并针对比赛中智能体的能力和协作效果进行建模，然后对比赛中的智能体协 作团队进行了定义，利用基于加权协同图的学习算法和任务分配策略进行救援仿 真比赛中的智能体消防协作。通过实验仿真测试，证明了该方法的有效性。