自利Agent追捕联盟生成算法

吕 磊, 王 浩, 林 航, 方宝富(.合肥工业大学 计算机与信息学院，安徽 合肥 30009; . 国网安徽省电力公司 信息通信分公司,安徽 合肥 3006)

自利Agent追捕联盟生成算法

吕 磊1, 王 浩1, 林 航2, 方宝富1
(1.合肥工业大学 计算机与信息学院，安徽 合肥 230009; 2. 国网安徽省电力公司 信息通信分公司,安徽 合肥 230061)

多Agent合作追捕是多Agent系统研究的经典问题,在机器人等领域具有重要的应用前景。文章提出了面向任务的自利Agent联盟生成算法,该算法能同时处理多个不同类型的逃跑Agent的任务分配问题;因为追捕Agent和逃跑Agent速度相等,追捕联盟成员位置的分布十分关键,所以提出了基于贡献度的联盟成员选择策略;同时为了较好地体现追捕Agent的自利性,定义了需求度作为自利性的度量,解决了冲突协商且有利于资源的优化配置。通过与经典拍卖算法的比较表明,该算法显著提高了追捕成功率。

追捕-逃跑问题;自利Agent;追捕联盟;贡献度;需求度

多Agent系统[1]主要任务是研究和解决单个机器人无法解决的问题。该类问题的关键是多个Agent之间的协作,只有通过协作才能合理有效地完成任务,而任务分配则是其中的关键问题之一。任务分配的主要研究方法有基于集中规划[2]、基于阈值响应[3]以及基于市场交易[4]的方法等。

追捕-逃跑问题是多Agent协作和竞争的经典问题,其中的任务分配是联盟生成问题,只有多个追捕Agent达成追捕联盟才能有效地完成追捕。关于该问题任务分配的研究有很多。文献[5]根据追捕任务的相似性,先按步骤完成任务分配,如果当前追捕任务分配能匹配历史任务集合中的元素,那么可以借鉴系统经验集进行任务匹配,进而形成当前追捕联盟;文献[6]利用Agent的自利性,提出了基于相似度的两阶段联盟选择算法,能解决不同类型任务的联盟生成问题;文献[7]从自利Agent的角度出发,让每个Agent提出一个对其最有利的方案,然后提交给中央管理者,最后由中央管理者根据VCG(Vickrey-Clarke Groves)算法给出“最优”方案;文献[8]从情感角度研究了追捕任务分配,提出了基于情感协作因子的追捕任务分配算法,该算法利用2步拍卖算法生成追捕联盟,仅适用于逃跑Agent速度较低的情况;文献[9]研究了自利、异质Agent的分布式联盟分配问题,提出了基于协作度的联盟形成机制,但是未给出自利性的具体度量,且联盟形成过程中未考虑任务的影响。

目前对追捕-逃跑问题大多研究的是逃跑Agent速度低于追捕Agent的非自利Agent追捕问题,并且不考虑逃跑Agent的类型,目标是多个追捕Agent如何有效协作以尽可能小的代价完成追捕[10]。本文研究中,追捕Agent具有自利性且与逃跑Agent速度相等,而逃跑Agent则具有不同类型[11],因此多个追捕Agent之间的协作不仅要考虑能否追捕成功和逃跑Agent类型的问题,同时还要体现Agent的自利性。

1 联盟生成中的主要问题

1.1 追捕问题基本假设

为了研究速度相等条件下自利Agent的追捕联盟生成算法,对多个多种类型的追捕问题作如下假设:

(1) 追捕区域为无界连续区域,时间可离散化并记每个追捕周期为Time。

(2) 不考虑Agent之间的通信,所有任务数据均为公共知识,包括逃跑Agent的数据、联盟分配数据和重分配数据。

(3) 逃跑Agent分为Ⅰ、Ⅱ、Ⅲ 3种不同的类型,即选择固定方向逃跑、选择随机方向逃跑和选择“最优”方向逃跑(这里的“最优”因收益函数的不同而不同),不同类型的逃跑Agent具有不同的能力值,可分别赋予C1、C2和C3。

(4) 所有追捕Agent均具有自利性(Agent会优先选择加入对自己较有利的联盟),且速度均相等。

在无界连续区域中,有m个追捕Agent和n个逃跑Agent,分别记为P={p1,p2,…,pm}和E={e1,e2,…,en}。为了叙述的方便和问题的需要,给出如下定义。

定义1 每个追捕Agent可以用四元组pi=〈pos,cap,pref,gid〉表示,其中pos为pi的坐标;cap为pi的能力值;pref为pi的需求偏好;gid为pi的所属联盟。

定义2 每个逃跑Agent可以用四元组ej=〈pos,cap,value,type〉表示,其中pos为ej的坐标;cap为ej的能力值;value为ej的价值;type为ej的类型。

任务分配的目标是将m个追捕Agent划分为n个联盟,每个联盟负责一个逃跑Agent的围捕任务。记所有的空闲Agent为Pa(P的子集),每个追捕联盟记为Ci,n个追捕联盟可以用Mc(分配矩阵)表示,Mc=[C1C2…Cn],从而联盟生成[12]可定义如下。

定义3 联盟生成即依据任务的要求,为每个联盟寻找一个最优或近似最优且满足Agent自利需求的Pa的一个划分,最终获得分配矩阵Mc的过程。

根据追捕问题的基本假设,可知追捕联盟的选择是一个双向选择的过程,从而需要解决联盟如何选择联盟成员以及追捕Agent如何选择联盟2个主要问题。

1.2 追捕Agent贡献的度量

因为追捕Agent和逃跑Agent的速度相等,所以必须有多个追捕Agent协作进行围捕。而要想围捕逃跑Agent就必须考虑2个因素,即距离和角度。当距离较近且分布于逃跑Agent周围的多个追捕Agent结成联盟时,围捕成功率就会提高。据此本文提出了贡献度的概念来衡量一个追捕Agent对于一个联盟的贡献,从而可以依据贡献度来完成联盟成员的选择。

贡献度的定义如下。

定义4 贡献度是对追捕Agent围捕逃跑Agent贡献大小的度量,包括距离和角度2个因素,记为Rc,其计算公式为:

Rc=λKd+μKθ

(1)

其中,Kd和Kθ分别为距离系数和角度系数;λ和μ为2个因素影响因子,且λ+μ=1。

对于距离系数和角度系数,距离越近,贡献越大;角度越大,贡献越大。因此计算距离系数的公式为:

(2)

角度的计算需要先给出包围角度的概念,包围角度即追捕Agent“挡住”了逃跑Agent逃跑方向的多少,如图1所示。

图1 包围角度

如果存在多个追捕Agent,那么它们的包围角度有可能出现交叉的情况,如图2所示。

图2 有交叉包围角度

图2中追捕Agentp1(点P1处)和Agentp2(点P2处)的包围角度有交叉,即图中的α。本文假设任何包围角度有交叉的2个Agent不会影响对方另一侧的包围角度,即α小于等于∠P1EP2,而对有交叉一侧的包围角度处理如下:

(1) 如果α≤60°,那么将α看作距离逃跑Agente(点E处)较近的Agent(图2中P1处)有交叉一侧的包围角度,距离e较远的Agent则为0。

(2) 如果α>60°,那么距离e较近的Agent有交叉一侧的包围角度为60°,距离e较远的Agent则为θ-60°。

1.3 追捕Agent自利性的度量

因为Agent具有自利性,所以在满足任务基本要求下有权选择对其最有利的追捕目标,并加入追捕该目标的联盟。自利追捕Agent会选择距离近且价值高的逃跑Agent,因此可以定义需求度为到逃跑Agent的距离和价值的函数。这样追捕Agent可以得到对每个逃跑Agent的需求度,依需求度排序即可得到其偏好序列。Agent的需求度计算公式如下:

(3)

其中,Dij为pj对ej的需求度;dk为pk到ej的距离;vk为ek的价值;w1和w2为距离和价值的权值,且w1+w2=1。

1.4 信息共享机制

因为本文假设所有的任务数据为公共知识,但是追捕Agent的个人数据对其他Agent而言却是未知的,所以要实现联盟的分配,可以采用集中加分布的体系结构,即将任务数据放到决策模块统一管理,而将个人数据交由每个追捕Agent计算和更新。

联盟分配体系结构如图3所示。

图3 联盟分配体系结构

每个追捕Agentpi都可以将个人数据提交到决策模块,由决策模块进行联盟分配,分配之后将分配信息或重分配信息反馈给所有的追捕Agent,每个追捕Agent根据收到的信息计算和更新个人数据。

2 联盟生成算法

2.1 联盟成员的选择

逃跑Agent分为不同的类型,因此需要根据类型来选择追捕联盟。

(1) 第1类型逃跑方向固定,因此只需选择1个合适的追捕Agent从其逃跑方向去围堵即可。为了尽可能围堵到该类型逃跑Agent,必须选择在与逃跑方向夹角小于45°范围内的追捕Agent,然后选择其中距离逃跑Agent最近的C1个追捕Agent作为该类型的追捕联盟。

(2) 第2类型逃跑方向随机选择,因此选择距离该类型逃跑Agent最近的C2个追捕Agent作为该类型的追捕联盟。

(3) 第3类型选择的是最优方向,因此必须选择足够多的追捕Agent进行围捕,需要C3个均匀分布在其周围的追捕Agent。为了选取合适的追捕Agent,可依据1.2节中给出的贡献度来选择,先计算每个追捕Agent对该类型Agent的贡献度,然后选择C3个贡献度最大的追捕Agent作为该类型的追捕联盟。

依据上述策略为所有逃跑Agent选择追捕联盟后,可能存在冲突,因此各追捕Agent之间需要协商,协商之后可能有不满足条件的联盟,再依据联盟选择策略选择,再协商,如此反复直到满足联盟条件并且没有冲突。

2.2 自利Agent联盟生成算法

上述联盟选择然后协商解决冲突的过程称作第1轮协商,之后可能还存在空闲的追捕Agent；因为空闲追捕Agent的影响,第1轮协商得到的追捕联盟并不是最优的,所以还需要再进行第2轮协商,对联盟成员做最后的筛选。结合Agent的自利性,本文提出了基于贡献度的自利Agent联盟生成算法,具体步骤如下:

(1) 初始化各追捕Agent的数据和任务数据。

(2) 根据公共空间中的数据和各追捕Agent的数据计算每个追捕到所有逃跑Agent的距离,记为Mdis(距离矩阵);然后追捕Agentpi根据公共空间中的数据和Mdis计算其偏好序列pref。

(3) 计算空闲追捕Agent集合Pa对第3种类型的逃跑Agent的贡献度,记为Mrcon(贡献度矩阵)。

(4) 根据逃跑Agent的类型,为所有联盟未分配完成的逃跑Agent从Pa中选择满足条件的追捕Agent,得到追捕联盟,记为分配矩阵Mc。

(5) 依据Mc统计出存在任务冲突的追捕Agent集合Sc和无冲突的追捕Agent集合Sd。对于Sd中的Agent若满足联盟条件,则作为该联盟的成员;否则将其放入Pa中并从Mc中移除。对于Sc中的Agent可依据自身的偏好选择一个联盟,若满足联盟条件,则作为该联盟的成员;否则将其放入Pa中并从Mc中移除。

(6) 判断所有联盟是否已分配完成以及Pa是否非空。若存在联盟未分配完成并且Pa非空,则转到步骤(3),否则继续第2轮协商。

(7) 经过第1轮协商,得到了初步的分配矩阵Mc,若Pa为空,则联盟分配完成,该Mc即为最终的分配矩阵,转到步骤(9);若Pa非空,则继续下面的步骤。

(8) 对于第3类型的联盟,遍历Pa中的所有Agent,将每个Agent加入到联盟中,然后重新计算该联盟成员对该联盟的贡献度,若加入的Agent的贡献度并非为最差的,则将其加入到该联盟,而把贡献度最差的Agent放入Pa中;若加入的Agent的贡献度为最差的,则遍历下一个Pa中的Agent。

(9) 将得到的最终分配矩阵Mc发给每个pi,更新pi所属的联盟。

上述步骤即为自利Agent的联盟生成算法,协作主要体现在2轮协商和贡献度上。第1轮协商是在分配过程中,主要针对逃跑Agent的类型来对有限追捕Agent的联盟分配;第2轮协商是在分配之后,主要追捕第3类型的联盟做分配优化;而贡献度则为第3类型的逃跑Agent选择追捕协作Agent提供依据。

2.3 重分配机制

因为追捕状态会随着追捕的进行而不断变化,所以联盟也应做出相应的变化[13]。为了适应不断变化的追捕状态,本文提出了2个重分配的策略:① 每过3个周期执行1次重分配;② 当有逃跑Agent被追捕到时执行重分配。

2.4 追逃策略

当追捕联盟生成之后,追捕团队需要采用一定的追捕策略完成追捕任务,而除第1类型和第2类型的逃跑Agent的逃跑策略已知外,第3类型的逃跑Agent的逃跑策略是可变的。本文假设在追捕环境中存在一种虚拟力场,所有追捕Agent对逃跑Agent产生斥力,而逃跑Agent对其联盟成员产生引力。在此仅研究力的大小,引力Fp和斥力Fe的定义如下:

(4)

(5)

以每个逃跑Agent的位置为圆心,画1个单位圆,在圆周上取H个等分点,连接圆心和这H个点得到H个方向向量,逃跑Agent的运动方向即从这H个方向向量中选取。预先计算逃跑Agent到达这H个点所受的斥力Fe,然后选取Fe最小的方向作为逃跑方向。追捕Agent使用同样的方法选取引力Fp最大的方向作为追捕方向。

3 仿真试验

3.1 仿真环境参数与对比试验

试验中3种类型逃跑Agent的能力值C1、C2、C3分别取1、2、4,代表每种类型至少需要的追捕Agent个数,同时根据追捕的难易程度分别赋予3种类型的逃跑Agent的价值为1、2、3,所有追捕Agent的能力值均视为1。贡献度2个因素的影响因子为λ和μ,因为需要执行的是围堵策略,角度的影响较大,所以λ=0.2,μ=0.8；而自利Agent需求度的计算需要2个权值,这里取w1=w2=0.5;Agent逃跑方向的个数H=36。

为了分析和说明本文提出的联盟生成算法,选取文献[8]中的任务分配算法进行对比试验。该算法采用的是拍卖算法且机器人具有情感,其中情感对联盟生成的影响体现为协作因子,只有协作因子满足条件的机器人才参与任务分配,因此假设所有的追捕Agent均愿意参与任务分配,其他条件与本文的算法一致。

3.2 仿真试验

(1) 试验1。为了说明本文基于贡献度的自利Agent联盟生成算法,本试验选取了3个多追多的追捕试验,分别为10追1、10追2和10追3的追捕试验,如图4所示。

根据试验1和追捕问题的基本假设,可知本文算法具有3个特点:① 能依据逃跑Agent的不同类型为其选择合适的追捕联盟；② 随着追捕的进行,能及时进行重分配；如图4b中的1号追捕Agent，在将其联盟的逃跑Agent追捕到后接着去围堵向其逃跑过来的另一个逃跑Agent;又如图4c中5号和9号追捕Agent，会在追捕过程中及时调整其追捕联盟；③ 在满足任务要求的情况下同时考虑了Agent的自利性；如图4c中的5号追捕Agent,一开始适合追捕第1类型的2号逃跑Agent,但是因为第3类型的3号逃跑Agent距其较近且价值也更高,于是对3号逃跑Agent的需求度高于2号逃跑Agent的需求度,所以选择了第3个追捕联盟,随着追捕的进行,其对2号逃跑Agent的需求度逐渐增大,在重分配过程中又选择了第2个追捕联盟。

图4 不同类型和数量逃跑Agent的追捕试验

(2) 试验2。文献[8]的拍卖算法是逃跑Agent速度小于追捕Agent速度的场景,于是在100×100的区域内随机选取100组数据,以10追3为例,由本文算法和拍卖算法得到的对比结果如图5所示。

图5 逃跑Agent速度较小时的对比试验

从图5a可以看出,2个算法的追捕时间相差不大,只是本文算法偶尔会出现较坏的情况,这是由于本文是针对不同逃跑Agent的类型做任务分配,当追捕Agent位置特殊时,可能存在有的联盟没有满足条件的追捕Agent,不能及时追捕,从而出现追捕时间较坏的情况；从图5b可以看出,2个算法的总代价相差不大。

(3) 试验3。在速度相等的情况下本文算法与拍卖算法进行了3组对比试验,分别为10追3、11追3、12追3,每组各做100次,得到的试验数据见表1所列。

分析表1中的数据可知:① 随着追捕Agent个数的增加,2个算法的成功率均有所增加；② 拍卖算法的成功率明显较低,主要原因是该拍卖算法适用于逃跑Agent速度小于追捕Agent速度的追逃问题,而不能很好地解决速度相等的追逃问题；③ 本文算法的成功率较高,适用于逃跑Agent的速度和追捕Agent速度相等的追逃问题，即便如此,仍然存在追不到的情况,这是由开始时追捕Agent和逃跑Agent位置所决定的,对此需要采用更好的追捕算法才能解决。

表1 追捕成功率对比

4 结 论

本文利用追逃问题对自利Agent的联盟生成算法进行了研究,由于是面向任务(任务的类型不同)的联盟分配,本文提出了2轮协商机制,结合需求度和贡献度,给出了追逃问题的自利Agent的联盟生成算法。该算法能解决不同逃跑Agent的联盟生成问题,同时能较好地解决逃跑Agent均匀分布于追捕Agent周围时两者速度相等的追逃问题。

[1] ARAI T，PAGELLO E，Parker L E.Editorial：advances in multi-robot systems[J]. IEEE Transactions on Robotics and automation，2002，18(5)：655-661.

[2] LIEMHETCHARAT S，VELOSO M.Modeling and learning synergy for team formation with heterogeneous agents[C]//Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1. Richland：International Foundation for Autonomous Agents and Multiagent Systems，2012：365-374.

[3] KOES M，NOURBAKHSH I，SYCARA K.Constraint optimization coordination architecture for search and rescue robotics[C]//Proceedings 2006 IEEE International Conference on Robotics and Automation.[S.l.]:IEEE，2006：3977-3982.

[4] 闫路平.多机器人合作追捕目标问题研究[D].哈尔滨:哈尔滨工业大学，2008.

[5] LIU H，CHEN J F.Task matching & scheduling algorithm of hybrid avator team in collaborative virtual environments[C]//International Conference on Machine Learning and Cybernetics.[S.l.]：IEEE，2008：2384-2389.

[6] GENIN T，AKNINE S.Coalition formation strategies for self-interested agents in task oriented domains[C]//2010 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology.[S.l.]：IEEE，2010，2：205-212.

[7] NISSIM R，BRAFMAN R I.Cost-optimal planning by self-interested agents[C]//Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence.Washington,D.C.:Bellevue,2013:732-738.

[8] FANG B，CHEN L，WANG H，et al. Research on multirobot pursuit task allocation algorithm based on emotional cooperation factor[J]. The Scientific World Journal，2014(4):864180.

[9] 胡军，张振兴，邹立.基于协作度的分布式自动协商联盟形成机制[J].计算机研究与发展，2015，52(5)：1080-1090.

[10] WANG H，LUO C，FANG B.An alliance generation algorithm based on modified particle swarm optimization for multiple emotional robots pursuit-evader problem[C]//11th International Conference on Fuzzy Systems and Knowledge Discovery.[S.l.]：IEEE，2014：886-891.

[11] 柳林，季秀才，郑志强. 基于市场法及能力分类的多机器人任务分配方法[J]. 机器人，2006，28(3)：337-343.

[12] 王浩，丁磊，方宝富，等.多机器人追逃问题中的追捕联盟生成算法[J]. 机器人，2013，35(2)：142-150.

[13] CAI Z S，SUN L N，GAO H B，et al.Multi-robot cooperative pursuit based on task bundle auctions[C]//HUANG X Y，XIONG Y，LIU H.Intelligent Robotics and Applications-First International Conference. Berlin：Springer Verlag，2008：235-244.

(责任编辑 胡亚敏)

Self-interested Agent pursuit alliance generation algorithm

(1.School of Computer and Information， Hefei University of Technology， Hefei 230009， China; 2.Information and Telecommunication Branch of State Grid Anhui Electric Power Company， Hefei 230061, China)

Multi-Agent cooperative pursuit is a classic problem of multi-Agent systems， which has important applications in the field of robotics. The alliance generation algorithm of task-oriented self-interested Agent is proposed. The algorithm can handle the task allocation problem of many different types of escape Agents. For the pursuit Agent and escape Agent have equal speed, the position distribution of alliance members is critical. Therefore, an alliance member selection strategy based on contribution degree is put forward. In order to better reflect the self-interest of pursuit Agent， need degree is defined as a measure of self-interest， which can deal with the conflict negotiation and promote the most optimum allocation of resources. Compared with the classic auction algorithm， the proposed algorithm significantly improves the success rate of the pursuit.

pursuit-evasion problem; self-interested Agent; pursuit alliance; contribution degree; need degree

2016-02-01；

2016-04-29

国家高技术研究发展计划(863计划)资助项目(2012AA011005);国家自然科学基金资助项目(61175051;61175033;61203360);安徽省自然科学基金资助项目(1308085QF108)和合肥工业大学博士学位人员专项基金资助项目(JZ2014HGBZ0014)

吕 磊(1991-),男,云南宣威人,合肥工业大学硕士生; 王 浩(1962-),男,江苏泰州人,博士,合肥工业大学教授,博士生导师.

10.3969/j.issn.1003-5060.2017.06.010

TP242.6

A

1003-5060(2017)06-0769-07