基于多种群协同进化的多逃逸者围捕任务分配

高子璇,张国富,2,3,4,苏兆品,2,3,4,李 磊

(1.合肥工业大学 计算机与信息学院,安徽 合肥 230601;2.大数据知识工程教育部重点实验室(合肥工业大学),安徽 合肥 230601;3.智能互联系统安徽省实验室(合肥工业大学),安徽 合肥 230009;4.工业安全应急技术安徽省重点实验室(合肥工业大学),安徽 合肥 230601)

0 引 言

随着机器人在军事、工业领域中的应用,机器人追逃问题[1-2]已成为人工智能和机器人领域中的研究热点之一,其研究类型主要分为对单逃逸者的追逃问题和对多逃逸者的追逃问题。自Isaacs[3]为两个参与者制定追逃策略以来,对单追捕-单逃逸者之间的博弈进行了详细的研究。单追捕-单逃逸者的情况是一个零和博弈,可以用著名的贝尔曼方程[4]的扩展来解决。Jia等[5]提出用连续时间马尔可夫决策过程(CTMDP)来解决一个追击者和一个逃逸者的追逃问题中的不确定性。Pan等[6]提出了一种基于区域的中继追击方案,在追捕的过程中可以更换主动追击者,来使追击时间缩短。Kokolakis等[7]提出了一种基于关键强化学习(RL)的算法用于在线学习,并在有限时间内学习追击策略,从而实现对逃逸者的有限时间捕获。

在多追捕-单逃逸者的追逃问题中,Lin等[8]研究了一类线性二次多追捕-单逃逸者微分对策,逃逸者实施传统的反馈纳什策略,而追捕者基于最佳可实现性能指标的新概念实施纳什策略。Kumkov等[9]为对象组的冲突互动制定了特殊的公式和方法来解决对象太多时相位向量的维数很高时带来的困难。

近年来,现代交互多智能体系统推动了对多追捕-多逃逸者追逃问题的研究,该研究涉及到围捕任务的分配,主要解决如何分配若干个机器人进行协同围捕逃逸者的问题。围捕机器人在障碍物环境下的实时移动大多采用人工势场法[10]等来确定。在多追捕-多逃逸者的追逃问题的研究中,Stipanovic等[11]通过将水平集函数定义为玩家的目标来确定确保捕获或规避的条件,提供了一种在具有多个参与者的追逃游戏中设计保证捕获或保证规避策略的方法。胡俊和朱庆保[12]为围捕任务的分配设计了一种“协商分配法”,李瑞珍[13]沿用了“协商分配法”并应用于全方位的围捕系统中,但并没有在逃逸机器人数量较多的情境下进行更深入的实验与研究。徐望宝等[14-15]提出了一种基于人工力矩的自组织围捕方法,并设计了一种围捕机器人吸引点基于局部信息的确定与调整方法;文献[16]提出了一种链阵方法,计算复杂度高,围捕团队数目可以不相同并且可以随时加入或退出,在围捕者改变围捕目标后,围捕效率不够理想。高晓阳[17]提出了一种分配原则,使围捕机器人依次选择离自己最近的围捕点,丧失了对所有机器人一视同仁的公平性。张红强等[18]提出了一种基于围捕者面对多目标中心方向180度范围内的两最近邻进行任务分配的分配方法,减少运动距离和能量消耗。

Lopez等[19]设计了一种规则,围捕者先选择距离自己最近的围捕点,如果两个围捕者有相同的最接近的逃逸者,将距离最短的围捕者的目标更改为其第二个最近的逃逸者,可以解决任务分配冲突的问题。陈铭治和朱大奇[20]将每个围捕者到逃逸者的预估时间编为矩阵,根据围捕一个逃逸者所需围捕者的数目计算该逃逸者被围捕所需的最短总时间,围捕者优先围捕具有最小预估时间的逃逸者。

需要指出的是,上述已有研究大都采用距离优先分配的策略,在逃逸者数量较多的情况下,难以实现围捕任务的均衡分配,降低了系统围捕的效率。为此,该文在总结和分析前人工作的基础上,构建了一种全方向的群机器人逃逸围捕任务分配数学模型,然后基于遗传算法和多种群协同进化提出了一种多逃逸者围捕任务分配算法,设计了相应的编码方式、交叉和变异策略。最后,在开发的群机器人逃逸围捕仿真平台上测试了算法的有效性。

1 问题描述

群机器人多逃逸者围捕问题设定在二维受限环境,有m个围捕机器人,用Q={q1,q2,…,qm}表示;有n个逃逸机器人,用P={p1,p2,…,pn}表示。对每个逃逸机器人pi(i=1,2,…,n),存在一个以逃逸者当前位置为中心,感知距离r为半径建立的安全域,如图1所示。在安全域边界上设定e个均匀分布的围捕点,每个围捕点由一个围捕机器人完成,当该逃逸机器人周围的所有围捕点均被围捕机器人占领时,认为该逃逸机器人被围捕成功,所有逃逸机器人均被围捕成功时,停止追逃行为,判定群机器人围捕系统围捕成功。

图1 安全域及Fk示意图

将每一个逃逸机器人看作一个围捕任务,则共有n个任务,设任务集为S={S1,S2,…,Sn},由图1可知,每个任务由e个围捕者共同完成。则围捕点的集合为{Si1,Si2,…,Sie},即任务Si对应围捕点集合{Si1,Si2,…,Sie}。

假设围捕机器人qk(k=1,2,…,m)所对应的围捕点为Sij(i=1,2,…,n;j=1,2,…,e),qk到Sij的距离Fk如图1所示,并表示为公式1。

(1)

其中,(xk,yk),(xij,yij)分别为围捕机器人qk和对应围捕点Sij在地图中对应的坐标。

2 基于多种群协同进化的多逃逸者围捕任务分配策略求解

该文设计了一种基于多种群协同进化遗传算法来求解群机器人多逃逸者围捕任务的分配问题。为了保持种群的多样性,先初始化生成D个不同的编码组合,在每个组合里再将任务集合S进行合适的分组,一组代表一个种群,通过多种群协同进化的方式得到最终的分配方案,算法流程如图2所示。

图2 基于多种群协同进化的任务分配算法流程

多种群协同进化遗传算法的过程如下:

(1)随机生成D个不同的编码组合,在这些组合里,任务集顺序保持一致,围捕者集合的顺序随机生成。

(2)将每一个组合中的编码按同样的分组方式对编码进行划分分组,来保持合适的编码长度。

(3)分组后的每一组为一个独立的种群,每个种群同时进行各自的初始化和交叉、变异、选择等操作。

(4)将每个种群选择的最优解按分组顺序进行组合,得到最终解。

(5)每个组合均可得到一个最终解,再选择D个组合中的最优解作为文中算法所得到的分配方案。该分配方案的适应度函数值的大小即为本次算法最终得到的目标函数值。

2.1 个体编码

第h(h=1,2,…,L)组的个体编码如图3所示,每一个编码表示种群中的一个个体。第一行表示任务Sha(a=1,2,…,w),第二行表示围捕者qhb(b=1,2,…,ew)。

图3 第h组个体编码示意图

Sha(a=1,2,…,w)为任务集S中按顺序排序分配到各组中的任务,qhb(b=1,2,…,ew)为围捕者集合Q中随机选取的不重复围捕者。所有组的任务组合起来为一个完整的任务集S,所有组的围捕者组合起来为一个完整的围捕者集合Q,如公式2所示。

(2)

每一组的任务和围捕者均不会重复,即对L组中任意的两组h1和h2,都有如下约束条件:

∀h1,h2∈{1,2,…,L}{Sh11,Sh12,…,Sh1w}∩{Sh21,Sh22,…,Sh2w}=∅

∀h1,h2∈{1,2,…,L}{qh11,qh12,…,qh1ew}∩{qh21,qh22,…,qh2ew}=∅

(3)

L个种群相互独立,各自进行交叉变异选择的过程,互不干扰。

2.2 种群初始化

为了保持种群个体多样性,首先生成D个不同的组合,其中第一行编码为任务集S的顺序排列,第二行编码为围捕者集合Q的随机乱序排列。将生成的长序列划分为L个任务组,一组代表一个种群,每个种群由第二行编码的染色体信息形成Z个不同的个体,表示围捕任务的第一行编码初始化后保持不变。

2.3 适应度函数

围捕机器人完成全部围捕任务所耗费的步长往往由距离围捕点最远的围捕机器人所决定,对于群机器人多逃逸者围捕的任务而言,任务分配的目标是使该距离越小越好,因此设定适应度函数Fit为该编码个体中Fk的最大值。

Fit=max(Fk),k=1,2,…,ew

(4)

适应度函数越小,围捕效果越好,在选择过程中选择适应度函数值更小的个体来进行下一次的交叉和变异。

2.4 交叉算子

如图4所示,对每一个种群中所有个体各进行下述操作:

图4 交叉示意图

相邻两个父代个体两两为一组进行交叉,每个父代个体均选择头部作为交叉点;

设定Cr∈[0,1]为交叉概率,c←rand(0,1),若满足c≤Cr,则在其中的一个父代个体中随机选中一段基因位,然后插入到另一个父代个体的头部,另一个父代个体也选择相同位置的相同长度的基因段进行相同的操作;

按照所需的基因位长度ew从前到后对重复或多余的基因进行剔除。

在文中的编码方式下,每个个体的基因位都是唯一且不可随意缺失的,只可移动位置。仅用普通的交叉算法使两个父代个体相互交换产生新个体,会导致个体中基因位的缺失或重复,因此采用上述交叉模式既可以保证这一编码特性,又可为种群提供不同的基因位置组合。

2.5 变异算子

对每个父代个体和交叉产生的子代个体进行变异操作。以个体C为例,Cu和Cv分别表示个体C的第u个和第v个基因位,u为个体中除v以外的随机位置,Gr←rand(0,1),g∈[0,1]为变异概率。若满足g≤Gr,则互换Cu和Cv:

(5)

2.6 选择操作

将初始种群与交叉变异后的进化种群组合在一起,按照适应度函数值由小到大进行排序,选取Z个最佳个体组成新的初始种群继续进化,达到所设定的迭代次数G时停止进化。这样,每一代都保留了种群中的优良个体,促使种群持续探索更好的解。

3 机器人围捕方法和仿真平台

3.1 围捕方法

机器人围捕过程如下:

step1:构建围捕地图环境,随机生成障碍物和各机器人,相互之间不重合,并获取位置坐标。

step2:根据逃逸者的坐标生成期望围捕点。

step3:用多种群协同进化遗传算法选择最优任务分配策略。

step4:各围捕机器人通过人工势场法确定运动方向。

step5:每行走一步,更新各机器人位置信息。

step6:判断所有围捕机器人是否到达对应的围捕点,若是,则围捕成功,围捕结束;若否,则继续进行围捕。

3.2 仿真平台

基于Java语言在Windows 10环境下开发了一个群机器人多逃逸者围捕仿真平台,如图5所示。所有机器人在二维平面内运动,撞到边界则更换运动方向,目标机器人的运动方向设为随机。目标安全域半径r设为20,设定6个围捕机器人围捕1个逃逸机器人。在受限的地图环境中,因为逃逸者永远逃离不出地图边界,因此将围捕者速度设为和逃逸者速度相等,设置所有机器人的运动步长t为4。在设定好机器人的初始位置和障碍物的位置后,打开仿真平台会在界面上显示每个个体的位置,其中小圆形表示围捕者,小三角形表示逃逸者,障碍物用大圆形和大三角形表示。然后各机器人开始运动,待围捕完成时,整个平台所有个体暂停运动,结束围捕。

图5 仿真平台中围捕过程示意图

以8个逃逸者为例,来演示仿真平台从初始化生成到全部围捕任务结束的过程,即n=8,m=48。障碍物个数设为10,随机生成在地图中,并不与机器人位置重合。其中圆形障碍物5个,三角形障碍物5个。当所有逃逸机器人均被围住时,所有机器人才停止运动,围捕结束,围捕过程如图5所示。

4 仿真实验与分析

为了验证所提算法的有效性,结合第三节中的仿真平台,首先给出初始参数设置,然后对比分析所提算法在目标函数上的优势,最后将设计的多种群协同优化遗传算法与算法1和算法2进行深入的对比分析。

4.1 参数设置

对于多种群协同优化算法而言,不同参数的选取对其效果有着至关重要的影响。选取逃逸者数量n为16,且每组实验都保证除所要探求的参数不同,其他完全相同,每组均做30组实验求取目标函数平均值。表1表示每组任务数w、种群个体数Z和初始化时生成的编码组合数D对实验结果的影响,表2表示交叉概率Cr、变异概率Gr对实验结果的影响。

表1 不同参数下的目标函数均值

表2 不同交叉、变异概率下的目标函数均值

种群个体数和编码组合数过多也会增加算法计算量和复杂度,综合考虑,每组的任务数目w设为4,种群个体数Z设为100,编码组合数D设为10,交叉概率Cr设为0.9,变异概率Gr设为0.3较为合适。

图6表示在逃逸者数量n为16时,执行一次多种群协同优化算法的收敛曲线,在迭代次数达到200时算法进入非常稳定的状态,因此将遗传算法的最大迭代次数G设为200。

图6 收敛曲线

4.2 目标函数对比

为了保证实验的合理性,在不同的逃逸机器人数量下,分别做10组不同的机器人初始坐标下的实验,记录目标函数的值,每组记录30组数据,比较3种算法的效果。表3给出了3种算法在不同测试实例下的目标函数值(均值±标准差)。

表3 不同分配算法下的目标函数值(均值±标准差)

可以看出,在不同逃逸者数量的9个实例上,文中算法相比其他算法均获得了更小的目标函数值,可见文中算法能极大地缩短围捕机器人到对应围捕点的移动距离。标准差的大小随着n的增加逐渐降低,是因为随着逃逸者数目的增加,在有限的地图环境里各个机器人的分布逐渐密集,在每个区域内的机器人数量逐渐均衡,每种算法对不同初始坐标下的机器人所产生的目标函数越来越接近。

算法2整体差于算法1与文中算法,在逃逸机器人数量为2时,算法1与文中算法形成的分配策略的目标函数差异不明显。随着n的增加,文中算法的优势逐渐体现出来,在逃逸者数目较多的情况下,文中算法能生成一个更优的分配策略,其对应的目标函数值相比于其他两个算法均较小。

4.3 围捕步数对比

以捕获所有逃逸者时围捕者的移动步数为指标,对于组建追捕团队采取文中算法和算法1、算法2来测试3种策略对围捕结果的影响。

4.3.1 障碍物对围捕步数的影响

设置逃逸者数量为8,进行两组实验,一组是固定障碍物数量为10,在障碍物位置越来越拥堵的情况下进行10次实验,结果如图7(a)所示;另一组是障碍物数量从6增加到16,进行10次实验,结果如图7(b)所示。每次实验的围捕步数由30次不同机器人初始坐标下的实验结果取均值来获得。

图7 障碍物对围捕步数的影响

实验结果表明,在障碍物更拥堵的情况下,在某些机器人行走到该障碍物区域时,机器人的避障行为增多,机器人移动的步数会略微增加,但障碍物的位置对实验结果并不会造成很大的影响,文中算法仍占优势。随着障碍物数量的增加,3种算法下围捕机器人的移动步数均会略微增加,是因为障碍物数量越多,机器人进行的绕行就越多,会增加机器人的移动步数。

4.3.2 不同逃逸者数量下的围捕步数对比

对不同逃逸者数量n,在相同障碍物数量和位置下,采取人工势场法[10]避障,分别做10组不同机器人初始坐标下的围捕实验,每组运行30次求均值,记录围捕机器人的最大移动步数。图8给出了对应的结果。

图8 采用人工势场法,不同测试实例下的围捕步数

文中算法在逃逸者数量从4增加到14的情况下,能够有效缩短围捕机器人系统的最大围捕步数。算法1和算法2在本质上都是一种贪婪算法,其主要通过最小化围捕机器人与目标的距离来实现分配。贪婪行为机制使其行为选择是为了使自己的利益获得最大,团队成员之间没有协作,这样形成的分配策略非常不均衡。文中的任务分配策略通过遗传算法综合判断和选择不同团队可能性,形成合理的追捕团队,并考虑团队成员之间相互协调,提高捕获效率。相比算法1和算法2,文中算法考虑了团队协作,避免了分配策略不均衡导致整体围捕效率降低的问题,表现更优。

以上仿真实验证明,文中算法在不同初始化环境和不同障碍物势态下均有优势,完成同样的围捕任务下,与算法1相比围捕步数差最高可达约60步,与算法2相比围捕步数差最高可达约90步,有效地提高了围捕效率。在完成围捕任务所耗费的步数上比算法1最多降低了约15%,围捕效率最大提高了约18%;比算法2最多降低了约20%,围捕效率最大提高了约25%。

5 结束语

该文研究群机器人协同围捕多逃逸者问题,提出了一种基于多种群协同进化的多逃逸者围捕任务分配算法,根据该算法对目标函数进行优化,在理论上通过计算目标函数值来证明该算法的有效性,在仿真实验中通过对围捕步数的比较证明该算法的可行性,并在不同的仿真环境中进行实验,证明该算法的通用性。该算法实现了围捕任务的均衡分配,提高了整个群机器人围捕系统的围捕效率。在今后的研究工作中,如果障碍物不是静止而是处于运动状态,该如何避障进行路径规划,这将是下一步研究的重点内容。