多Agent联合灭火救援协同组织研究

2014-12-31刘静，程桦

合肥工业大学学报（自然科学版） 2014年1期

刘静，程桦

（1.中国人民武装警察部队学院消防指挥系，河北廊坊 065000；2.安徽大学资源与环境工程学院，安徽合肥 230601）

多Agent系统中，Agent之间的协作是最关键、最具特色的一个环节。在多Agent系统中，单个Agent往往非独立完成某项任务，它必须通过和其他Agent相互协作，完成既定作战任务［1］。多个Agent的交互会表现为相互合作，但在此过程中也会出现冲突行为，如何消除由于交互而产生的冲突，是一个重要的研究课题［2］。对于联合灭火救援协作的假设如下：① 对于给定的任务Task，需要解决问题的能力和资源超出单个Agent所能提供的能力和资源；② 单个Agent完成某个单项任务所具备的信息、知识是不全面的。

部队作战是为了达成一定的作战目的，所有兵力（包括参战兵力装备、通信保障和后勤辅助兵力）在指挥员统一指挥下而进行的一系列军事活动，包括作战方案制定和作战计划实施2个主要过程［3］。本文的军队组织结构特指多Agent系统的协作和协调方法，目的是利用该方法建立描述作战Agent联合灭火救援的模型。

1 作战Agent的协作及联合行动

作战型Agent组织中的Agent特点如下：①Agent是利他的，这是军事指挥的一个重要特征，首先完成上级Agent命令它承担的角色，然后再追求自身的目标；②Agent的个性不同，具有不同知识和技能，如水罐编成和泡沫编成具有不同作战优势；③ 具有作战组织结构设计所需要的基本知识和技能。

1.1 联合灭火救援任务

各Agent在相互协作的过程中，实时感知救援环境；根据协同作战需要，与其他作战Agent进行适时信息交互；根据所拥有的关于参战力量的协作信息，在具体作战规则（如消防部队战斗条令、相关作战指挥知识等）指导下，制定协作决策方法，使自身在整个作战行动中能够完成与其他Agent的协作；根据制定的协作决策，调用系统的相应功能模块并执行，同时接受外界协作环境对其产生的影响，完成预期作战目标；在协作过程中，对协作决策进行动态调整，使其状态和动作能够适应复杂的联合灭火救援协同作战要求。

1.2 联合灭火救援角色功能

联合灭火救援将任务分解为7类，即成员交互类A、环境感知类B、协作群体结构类C、信息缓存类D、协作综合态势类E、动态协作类F及协作决策类G，相应的角色功能和责任见表1所列。

表1 联合灭火救援任务分解表

（1）A类角色包含6个角色，职责是进行参数测量，这6个角色具有独立性，不存在相互之间的通信和依赖。

（2）B类角色包含3个角色，相互独立，不存在任何相互关系。

（3）C类角色包含7个角色，Cl、C3、C4、C5、C6、C7之间具有独立性，但均依赖于C2。

（4）D类角色包含10个角色，相互独立，不存在任何相互关系。

（5）E类角色包含3个角色，相互独立，不存在任何相互关系。

（6）F类角色包含6个角色，相互独立，不存在任何相互关系。

（7）G类包括4个角色，相互独立，各角色对应实际协同模式中的实体。

1.3 联合灭火救援协作结构

联合灭火救援多Agent系统的协作结构，是系统中各个实体Agent相互配合、协同工作所表现出来的组织形态［4］。有什么样的协作结构就有相对应的协作机制，它决定系统自适应、协调及自治等特征形式和实现方法［5］。

Agent协作结构种类很多，最常用的是对等网络、联盟和黑板结构3种模型［6］。对等网络结构是指多Agent系统中的各成员具有相同的角色和地位，不设协调者，相互之间通过对等的通信和交互实现信息共享［7］。成员内部只有局部信息，通信和状态都是固定的［8］。黑板结构是指系统中存在多个知识源，Agent通过黑板内容的增减和修改来公布信息共享和Agent协作情况［9－11］。本文采用联盟结构确定联合灭火救援的组织协同，如图1所示。

图1 多Agent联合灭火救援的协作结构模型

处于组织层的指挥Agent等对其下属的控制具有强制性，作战Agent和指挥Agent都是彼此独立的，他们按照系统要求，接受并执行各自的任务。可见多Agent联合灭火救援3层协作结构本质上是一种动态自组织结构，这也是多Agent系统特点的集中体现。该结构明确了联合灭火救援中作战Agent和指挥Agent相互间的控制关系，使复杂系统在结构上更为简化，而各层在控制上更具灵活性和可靠性。该结构能使联合灭火救援作战实现全局最优，在联合灭火救援作战指挥领域具有一定的通用性。

2 动态任务分配协作算法

2.1 合同网协议

文献［12－13］提出合同网协议，主要用于研究分布式问题求解，其基本思想是利用招标－投标－中标这一机制，将系统任务进行分配，通过招标方和投标方的双向选择，相互协商，避免资源和知识等发生冲突，提高系统完成任务的质量，降低系统代价［14－15］。

2.2 作战Agent分配原则

（1）火场主要方面原则。首先将兵力分配给火场主要方面，并且优先分配给作战能力最强的Agent。

（2）到达救援现场时间最少原则。按照消防部队执勤战斗条令要求和消防部队5个“第一”要求，组织实施灭火与应急救援行动。

（3）救援人员安全第一原则。尽量避免灭火救援人员和装备受到高温、辐射、爆炸、倒塌及中毒伤害。

（4）多种因素兼顾原则。在前3条原则无法同时满足的情况下，应兼顾各原则，这是多目标优化问题。

（5）战勤人员决策优先原则。无论何时，保证战勤人员的决策比计算机优先级高，战勤人员可以随时干预与更改计算机给出的火力分配方案。

2.3 术语和约定

（1）A为m个作战Agent集合，A＝｛a1，a2，…，am｝。

（2）T为需要完成的子任务集合，T＝｛t1，t2，…，tn｝，T0＝T∪ Ø。其中，Ø 为虚拟任务集，表示任务队列中的开始节点或终止节点。由于虚拟任务集Ø没有执行过程，因此开始执行时间为0，占用时间也为0。

（3）Ai为符合任务ti要求备选的作战Agent集合，ti∈T，Ai⊆A。

（4）Cji表示任务Agentaj（aj∈A，1≤j≤m）完成任务ti所付出的代价。

（6）Nsj（t）表示Agentaj在t时刻所具有的作战能力。

（7）Hjα为子任务组合效益权重；Wij为对应任务的权重。

（8）Qik、Lj为潜在任务分配组和正式组。

（9）sj为共同占用作战组，S为共同占用作战组集。

要保证联合灭火救援任务分配使整个部队付出的代价最小，目标函数为：

在能够完成上级Agent分配任务的前提下，要争取最大收益，付出最小代价，即

（2）式使某一作战任务只能执行一次，即作战任务具有不可再现性，一旦任务分配给某个作战Agent或者一组作战Agent并执行，这个任务即宣告结束，无需进行再次分配。当任务执行结束后，后续任务只能有一个，该后续任务可以是虚拟任务；（3）式确保作战Agent的任务队列中的起始节点唯一；（4）式确保作战Agent的任务队列中任务执行时间不会重叠，前任任务和后续任务与当前任务ti共同占用作战Agentsj。

要确保任务执行能力和资源需求，当作战Agentsj在t时刻开始执行任务时，其作战能力和资源要大于、等于该任务所要求的力量总数，否则任务将无法完成，即

2.4 任务优化分配算法

上级Agent分配任务的原则是在能够完成任务的前提下，以最小的作战代价和消耗获取最大的作战效果。

（1）作战Agentaj（aj∈A，1≤j≤m）向上一级指挥Agentc公布所能完成的任务集Tj，Tj⊆T。

（3）aj给出Tj中完成所有子任务所付出的代价，即Cjk（1≤k≤l，l＝｜Tj｜，tk∈Tj），将结果返回给上一级Agentc，这里Cjk就是sj完成任务tk需要的作战能力。此处的作战能力是任务tk在Tj中某一位置，aj完成任务所付出的代价。虽然作战任务相同，例如同是火情侦察，但由于在不同的作战阶段，或者在同一作战阶段，但侦察范围不同，完成此项侦察任务需要的力量和付出的代价也不同。因此，作战任务tk在不同任务序列或同一任务序列不同位置时，在时间环境等约束条件下，aj完成任务付出的代价可能是不一样的。

（5）将潜在任务组集合表示为Qj＝｛qj1，qj2，…，qjα｝，其中，1≤α≤2｜Tj｜－1，则作战付出的代价值表为SCj＝｛scj1，scj2，…，scjα，｝，对qjα中的任务是按Tj中任务执行时间顺序递增排列的。

（6）将各作战Agent给出的代价值Cjk（aj∈A，1≤j≤m）发送给指挥Agentc，指挥Agentc得到每一子任务的最小代价值为ek（1≤k≤n），构成最小代价值表为E＝｛e1，e2，…ek，…，en｝，并返回给T的回应者。其中，ek＝min｛apjα｜tk∈qjα；1≤α≤2｜Tj｜－1；1≤j≤m｝，k＝1，2，…，n。

（8）经过计算得出潜在任务组完成任务的权重集合，比较找出权重最大的潜在任务组qjk，即qjk满足如下条件：（Hjk／scjk）≥（Hjα／scjα），1≤α≤｜Qj｜，并将qjk及对应的权重Wjk／scjk反馈给Agentc。此时，出现权重最大的任务组可能有2个或者2个以上，表明具备完成此任务的作战Agent可能有多个，则进一步选择实际开始执行时间st最早的任务组，即选择能尽快到达指定救援现场或者救援阵地的作战Agent。

例如，假设得到权重最大任务组有和由于任务组中任务是按原Tj中任务执行时间顺序递增排列的，即Tj＝｛t1，t2，t3，…，tl｝，l＝｜Tj｜。因此，确定由哪个任务组最终完成作战任务，取决于任务组中开始执行的时间，对2个任务组中的第1个任务进行比较，此时都为t1，实际开始执行时间一样，继而对第2个任务进行比较，对应为t2和t3。在Tj中，st2＞st3，故选择以此类推，直到找出权重最大并开始执行时间最早的任务组，即为所选任务组，这个任务组既有较强的作战能力，同时又会以较快的速度到达救援现场，体现了消防部队准确迅速的作战原则。

（9）指挥Agentc计算得到权重最大的潜在任务组qj′k，即qj′k满足条件：（Hj′k／scj′k）≥（Hjα／scjα），sj∈S，1≤j≤m，将向所有作战 Agent发出通告，qj′k为作战 Agentaj′的长期任务组。

（10）aj′同样也会收到该通告，之后将qj′k添加到其长期任务组列表Lj′，对于其他的作战Agent，在收到qj′k为作战 Agentaj′的长期任务组通告后，将把任务组qjα从Qj中删除，即对∀j，α，qjα∩qj′k≠Ø时，删除权重Hjα／scjα，返回步骤（8），进行循环计算，这时潜在任务组为删除qjα之后剩余的任务队列，同理找出最大权值，直到Qj＝Ø。

3 算法在火场进攻中的应用

某次作战行动中，设任务T对某一火点进行强攻，分解为4个独立的子任务t1、t2、t3、t4，采用强行破拆、正面进攻、侧翼进攻及后方供水，有3个作战Agent完成此任务。

（1）作战Agent完成作战任务的能力为：

完成作战任务矩阵为：

（3）aj给出作战子任务集Tj中所有完成作战子任务时付出代价值Cjk（1≤k≤l，l＝｜Tj｜，tk∈Tj），并反馈给上级指挥Agent。其中

（4）对子任务的可能性完全组合，可得潜在作战子任务集为：

（5）a1、a2、a3对应潜在作战子任务的代价值为：SC1＝｛2，3.2，4｝，SC2＝｛1.8，3.5，4｝，SC3＝｛1.8，2，3｝。

（6）给出最小代价指标E为：

（7）对所有Qj中潜在任务组，计算各权重Hjα／scjα，即H11／sc11＝ 1，H12／sc12＝ 0.75，H13／sc13＝1.10，H21／sc21＝1，H22／sc22＝0.60，H23／sc23＝1.23，H31／sc31＝ 1，H32／sc32＝ 1，H33／sc33＝1.26。

（8）作战Agent向指挥Agent反馈其最大权重为：

（9）找出最大权s3：W33／sc33，并向其他作战Agent宣布q33为长期任务组。

（10）s3将q33＝｛0.6t3，t4｝从Q3中取出，加入到L1。a3将满足q32∩q33≠Ø 的q31、q32，q33删除，H31／sc31、H32／sc32和H33／sc33也被删除，删除后的｜Q3｜＝Ø；同理，其他作战Agent也采用此过程，将满足qj2∩q33≠Ø（j≠1）中的qjα和其权重删除，返回步骤（8），对删除后的潜在子任务集进行新一轮计算，从中比较筛选出最大权值。此时，由于最大权重H23／sc23＝1.23，删除后，｜Q1｜＝｜Q2｜，所以，对潜在作战子任务重新进行计算，L2为｛0.6t2，0.4t3｝，L3为｛t1，0.4t2｝，经过3次循环，∀Qj＝Ø，结束。

由所有作战子任务分配可知，由Agent1独立完成作战任务t1，Agent2独立完成作战任务t4，作战任务t2由Agent1和Agent2协作完成，作战任务t3由Agent2和Agent3协作完成，整个作战任务分配完成。

4 结束语

本文在分析联合灭火救援组织机制基础上，结合军事指挥特点，研究了作战型Agent的特点。根据多Agent联合灭火救援组织特点，采用物理分解和功能分解相结合的方法，对系统任务进行分解。利用联盟协作结构，基于角色协作模型，与指挥层次相对应。给出了动态任务分配协作算法、指挥Agent与作战Agent动态任务处理流程和指挥Agent与作战Agent的协作算法，并结合战例分析算法在火场进攻中的应用，以证明该算法对解决实际作战问题的能力。

［1］李建华，康青春，商靠定，等.灭火战术［M］.北京：群众出版社，2004：15－27.

［2］公安部政治部.灭火应用战术［M］.北京：警官教育出版社，1998：215－218.

［3］公安部消防局.中国消防手册：第9卷.［M］.上海：上海科学技术出版社，2006：371.

［4］莫于川.中华人民共和国突发事件应对法释义［M］.北京：中国法制出版社，2007：26－31.

［5］季慎强.法国灭火救援的组织指挥［J］.浙江消防，2000（2）：36－38.

［6］张羽.论联合战斗［M］.北京：国防大学出版社，2003：18－23.

［7］司光亚.战略决策综合集成研讨与模拟环境研究与实现［D］.长沙：国防科技大学，2000.

［8］薛宏涛.基于协进化机制的多智能体系统体系结构及多智能体协作方法研究［D］.长沙：国防科技大学，2002.

［9］胡晓峰.战争模拟引论［M］.北京：国防大学出版社，2004：7－11.

［10］史越东.指挥决策学［M］.北京：解放军出版社，2005：40－46.

［11］纵恒，王文伟，陈阳娟.大型石油化工储罐区消防安全系统设计［J］.合肥工业大学学报：自然科学版，2012，35（9）：1259－1263.

［12］杨瑞平，郭齐胜，赵宏绪，等.C3I系统建模与仿真［M］.北京：国防工业出版社，2006：17－22.