基于共识主动性的群体机器人目标搜索与围捕

范衠，孙福赞，马培立，李文姬，石泽，王诏君，朱贵杰，李恪，辛斌

（1. 汕头大学 电子系，广东，汕头 515063；2. 汕头大学 广东省数字信号与图像处理技术重点实验室，广东，汕头515063；3. 北京理工大学 自动化学院，北京 100081；4. 复杂系统智能控制与决策国家重点实验室，北京 100081）

近年来，关于环境信息未知且通信受限情况下的目标搜索和围捕问题越来越受到学术界的关注.由于单体机器人处理复杂任务的能力通常被认为是有限的，而群体机器人系统可以通过局部交互的方式协作完成复杂任务[1]. 除此之外，与单体机器人系统相比，群体机器人系统具有适应性强、扩展性强、可靠性高等优点. 因此，群体机器人系统被广泛应用于灾后搜索和幸存者营救任务[2]、部署移动传感器网络任务[3]、区域覆盖及协作任务[4]、截留护送任务[5]和小型飞行器编队飞行[6]等任务中.

对于目标搜索任务而言，群体机器人系统需要解决区域覆盖的问题. 该问题的解决需要群体机器人通过自身携带的传感器来获取周围环境的信息，并与临近的机器人协同合作，寻找到目标. 例如：GIUGGIOLI等[7]提出了一种用分布式控制思想解决区域覆盖问题的方法，该方法受鸟类在领地中鸣叫的现象启发，通过定位与记忆机制来访问环境中未知的点. CALVO等[8]将生物启发式协调策略用于群体机器人环境探索，该策略采用信息素作为媒介，让群体机器人可以通过信息素的间接交流来完成任务.

对于目标围捕任务而言，群体机器人需要根据目标周围的环境自动生成合适的群体聚合形态[9]. 例如：XIE等[9]提出了一种能将磁性微型机器人重构为链状、带状、漩涡状等形态，机器人执行形态之间可逆转换的策略，从而实现协同搬运的任务. MENG等[10]受生物体形态发育过程的启发，提出了一种基于基因调控网络(gene regulatory network, GRN)的群体聚合形态形成方法. ZHANG等[11]在已有规则的基础上使用插值隐函数 (radial basis implicit function,RBIF)的方法实现了群体机器人在受限环境中对动态目标的围捕. YUAN等[12]根据领导跟随(leader-follower model)模型提出了基于追踪的分层基因调控网络(tracking-based hierarchical gene regulatory network,TH-GRN)的群体机器人行为模式，该方法将分层基因调控网络与领导跟随模型相结合，并设计了一系列动态复杂的仿真环境来验证该模型的性能. 实验结果显示TH-GRN模型在动态复杂的环境中效果显著.

然而，现有的方法在研究群体机器人目标搜索和围捕时，通常需要设置一些难以满足的假设，如无限距离的传感器[13]，理想的无障碍环境[14]，以及非常可靠的通信链路[15]等. 为了在通信受限或环境未知的条件下完成目标搜索和围捕任务，本文受蚁群觅食行为启发，提出一种基于共识主动性的群体机器人目标搜索与围捕框架. 该框架由3个阶段组成，分别为搜索阶段、跟踪阶段和围捕阶段. 具体流程如下：(1)利用改进的反蚁群算法对目标进行搜索；(2)当机器人发现目标后，机器人进入跟踪阶段并引导其他机器人向目标聚集；(3)当目标周围的机器人规模达到一定阈值后，群体机器人进入围捕阶段并利用基于信息素的分层基因调控网络模型来实现对目标的围捕. 本文主要贡献如下：

1) 提出一种基于共识主动性的群体机器人目标搜索与围捕框架. 该框架将目标搜索与围捕作为统一的任务进行研究，实现了群体机器人分布式协同控制；

2) 在传统的反蚁群算法基础上提出了一种改进的多信息素的反蚁群算法，实现了更好的区域覆盖性能；

3) 提出的基于信息素的分层基因调控网络模型将信息素作为媒介，克服了原GRN网络依赖于全局信息和原插值隐函数方法需要人为设置特征点的缺陷，完成了群体机器人在通信受限与环境信息未知场景下协同围捕目标的任务.

1 整体框架

本文提出了一种基于共识主动性的群体机器人目标搜索与围捕框架. 该框架的具体流程如图1所示. 在图1中，该框架分为3个阶段，分别为探索阶段、跟踪阶段和围捕阶段. 在探索阶段中，群体机器人利用改进的反蚁群算法来搜索目标. 在该阶段，群体机器人依照邻域网格上的信息素浓度计算转移概率并进行移动，在移动的同时释放搜索信息素，并通过构建一个栅格化的信息素地图以帮助各个机器人尽可能高效地覆盖未探索的区域. 此外，当机器人在地图上运动期间遇见障碍物的时候，将释放对应的障碍物信息素进行标识. 当某个机器人首先发现目标后，该机器人将进入跟踪阶段，通过在移动的时候留下特定的跟踪信息素，从而引导其他未发现目标的机器人沿着信息素聚集到目标周围. 最后，当目标周围的机器人规模达到一定阈值后，围捕阶段被激活. 更具体地说，在围捕阶段，群体机器人通过读取周围信息素浓度，利用基于插值隐函数的分层基因调控网络模型来实现对目标的围捕. 图1给出了对该框架的详细描述.

图1 基于共识主动性的群体机器人多目标搜索与围捕算法框架流程图Fig. 1 A flowchart of the stigmergy-based swarm robots for targets searching and trapping

1.1 探索阶段

针对未知环境下的目标围捕任务，群体机器人对目标的快速搜索将是该任务中不可或缺的部分.在本框架的第一阶段，群体机器人使用其携带的传感器来探测周围未知环境，群体机器人在探索目标的同时也会在沿途留下信息素. 机器人会根据其他机器人沿途留下的信息素并结合改进的反蚁群算法(improved inverse ant colony system, IIACS)来指导自身的运动, 以更高效地对未知环境进行探索.

传统的蚁群算法[16]使机器人偏向于选择信息素浓度较高的路径，与传统的蚁群算法不同的是，反蚁群算法[17]则倾向于使机器人选择信息素浓度低的路径，从而避开已经探索过的区域，获得更高效的全局搜索能力. 但反蚁群算法在帮助群体机器人完成对地图的探索后，由于机器人此时已经分散开，往往无法很快组织起来对目标进行有效的围捕. 因此，本文对反蚁群探索算法进行了改进，提出了两种新的信息素(障碍信息素和目标信息素)来帮助群体机器人进行更加高效的协作探索与围捕. 该运动策略可以通过如下公式表示.

在实际场景中，本方法会每隔一段距离就放置一个RFID传感器. 当机器人移动时，会读取地图上RFID传感器中信息素的浓度信息，并通过公式(1)和公式(2)选择下一个转移节点并更新该节点的信息素浓度，其公式如下.

式中的stage1和stage2分别表示探索阶段和跟踪阶段.从式(4)可以看出，机器人在移动过程中会释放3种类型的信息素，即探索信息素、避障信息素以及跟踪信息素. 这3类信息素对应3个变量τ1，τ2，τ3，并都初始化为0. 这3类信息素各自代表的意义不同，τ1用于引导探索，τ2用于避障，τ3则是跟踪，即发现目标后引导聚集(以方便进行围捕). 机器人可以根据自身携带的RFID设备来对信息素进行处理，并根据公式(4)和(5)来更新规则. 即在不同的情况(如探索到障碍或目标)下，机器人将会释放不同类型的信息素，用来处理机器人探索、发现障碍物以及发现目标后引导聚集3种不同情况.

此外，机器人产生的信息素会随着时间的推移而蒸发，如公式(5)所示.

式中，ρ代表了信息素蒸发系数. 针对不同的情况、机器人将会设计不同的蒸发系数. 如果机器人处于探索或跟踪目标状态，蒸发系数ρ设置为0.1，其目的是让探索和跟踪信息素浓度随着时间降低. 如果机器人检测到障碍物，蒸发系数ρ需要设置为0，来保证障碍物信息素浓度不随着时间推移而降低. 值得注意的是，由于本文障碍物信息素浓度不随着时间推移而降低，所以缺省认为障碍物是静止的. 以下为改进的反蚁群算法(IIACS)的伪代码.

算法1：基于多信息素的反蚁群算法

在算法1中，第4行表示群体机器人首先需要确定自己是否处于探索阶段(在初始化的时候，每个机器人都是处于探索阶段)，并通过自身携带的RFID(radio frequency identification) 传感器读写地图中的信息素浓度. 在第5行中，如果机器人处于探索阶段，会根据式(1)选择下一个转移节点. 在第6行中，如果机器人在移动过程中发现了障碍物，就会释放障碍信息素(Pherob)来标示障碍物的位置，以便后续机器人可以根据信息素来提前避开障碍物. 第7行则表示机器人发现目标或者检测到其他机器人释放的跟踪信息素(Phertr)时，它就会进入跟踪阶段，否则将继续处在探索阶段，直到检测到一个目标. 第9行与第10行则表示更新信息素浓度地图.

1.2 跟踪阶段

当机器人通过自身的传感器探测到目标后，机器人将由探索阶段转入到跟踪阶段并开始释放跟踪信息素. 在该阶段，机器人通过检测目标在过去一段时间内的位移变化情况来自适应调整其运动速度和方向，从而保证对目标的实时跟踪，如式(6)所示.

式中：j代表下一个转移节点；Δt表示传感器的检测间隔； (xt,yt)表 示在t时刻下机器人位置； φ(s)代表了转移节点与当前节点的相对角度. 以下为跟踪阶段的伪代码，如算法2所示.

此外，若处于探索阶段的机器人检测到其余机器人留下的跟踪信息素，则会沿着该信息素的方法进行移动，从而聚集到目标周围，具体移动节点计算公式如下.

在算法2中，第4行主要用来判断机器人是否处于跟踪阶段. 如伪代码所示，如果机器人自身含有目标信息并且运行时间小于预设值，则机器人处于跟踪阶段. 第4行到第6行为算法判断目标是否在机器人的感知范围内. 如果目标不在感知范围内，d1将被设置为无穷大，并且机器人会根据跟踪信息素(Phertr)浓度选择移动方向. 否则，算法将计算出机器人到目标的距离d1，并根据式(6)来对运动方向进行选择. 在第7行，每个围捕机器人都会检测自身周围的邻域机器人密度，当围捕机器人检测到邻域机器人密度均达到一定阈值后，群体机器人会从跟踪阶段进入围捕阶段.

1.3 围捕阶段

在未知环境下完成目标的围捕任务，这需要群体机器人系统充分考虑自身与目标、障碍以及其余围捕机器人之间的信息. 为此，在文献[11]的基础上，本文结合信息素的机制提出了一种基于插值隐函数的分层基因调控网络模型. 与传统的分层基因调控网络(hierarchical gene regulatory network, H-GRN)模型[14]相比，本文将基于信息素输入的插值隐函数模型嵌入到H-GRN模型中，并将其命名为(pheromone based hierarchical gene regulatory network, PH-GRN)，如图2所示.

图2 PH-GRN模型图Fig. 2 The model of PH-GRN

该方法能将插值隐函数所需的3类特征点通过前面在探索和跟踪阶段生成的信息素浓度地图自动生成，并计算出合适的群体聚合形态. 这3类特征点分别为内点I、边界点B和 外点E. 其中，内点I表示了所要包围目标的特征点；B为边界特征点，由聚集在目标周围的其余围捕机器人提供；外点E则是环境地图中的障碍物，所生成的聚合形态需要避开环境中的障碍物.

为了提高群体机器人在移动中的避碰能力，下层PH-GRN模型提出了一种基于局部环境信息方向向量的机器人运动方法，具体如下.

如图3所示，橙色粗箭头表示了每个机器人根据式(10)计算出的最终方向向量.

图3 Fi矢 量的生成过程(橙色箭头为最终方向向量)Fig. 3 The generation process of the Fi vector (the orange arrow is the final direction vector)

Di作为邻域形态密度因子，用于引导机器人移动到低密度区域，从而实现在包围圈上群体机器人的均匀分布，如式(11)所示.

式中：nei表 示位于i节点的机器人检测到的邻域机器人个数；µe为 邻域机器人e的二维坐标.

此外，Obi作为根据障碍物信息素得到的远离障碍物因子，其计算公{式如下.

算法3为围捕阶段的伪代码. 具体描述如下：第3行判断机器人是否处于围捕阶段. 第4行到第5行为机器人通过读取地图上的信息素生成内点I、边界点B和 外点E，并结合插值隐函数(RBIF)生成合适的包围形状，在第6行，机器人使用基于插值隐函数的分层基因调控网络模型来控制自身与其余机器人协作形成特定的包围形状.

算法3：基于多信息素地图的群体机器人围捕方法

2 实验仿真与分析

本文将通过一组仿真实验来评估上述基于共识主动性的多目标搜索和围捕框架. 首先，为了验证所提出的方法的可行性，本文针对动态目标设计了搜索和围捕的仿真实验. 表1列出了一些重要的仿真参数. 此外，在该模型中，本文主要考虑了如下几个合理的约束.

表1 仿真参数设置Tab. 1 Parameters setting of simulation

(1) 探索和跟踪阶段不允许围捕机器人之间存在直接通信，只有在围捕阶段允许机器人有最小的通信距离，即只允许和一定范围内的邻域机器人通信；

(2) 群体机器人的移动速度大于目标的移动速度；

(3) 机器人在网格地图中只允许上下左右进行运动，且机器人一次只能移动一个网格；

(4) 实验环境是有界的.

2.1 仿真配置与实验要求

针对目标搜索与围捕任务，群体机器人系统需要完成以下要求：

1) 群体机器人能探索环境并实现对目标的跟踪和围捕功能；

2) 当群体机器人发现目标后，机器人需要引导其余机器人对目标进行围捕；

3) 在围捕目标过程中，群体机器人不能碰撞障碍物，机器人之间也不允许碰撞.

本文提出以下实验假设：

1) 仿真环境为2 m×2 m的场地(经网格化后为20×20的网格地图)，每个网格都会部署一个可以读写信息素浓度信息的RFID标签；

2) RFID标签的读写范围与机器人的传感器范围都是10 cm，机器人对目标的感知范围为40 cm；

3) 机器人需要与邻域机器人和目标机器人保持10 cm及以上的安全距离；

4) 机器人的速度设置为10 cm/s，目标速度设置为5 cm/s.

2.2 动态单目标搜索和围捕

为了验证所提出方法的可行性，本文在含有障碍物的环境中对动态单目标进行了搜索和围捕的仿真实验. 在仿真中，目标用“★”表示，群体机器人用不同颜色的“●”表示. 障碍物设置为两个灰色区域.需要注意的是，障碍物和目标的位置是未知的，需要被群体机器人协同搜索得到.

图4展示了群体机器人利用本文提出的框架对动态目标的搜索和围捕过程. 具体流程如下，图4(a)～(b)展示了群体机器人依次从左下角基地出发，并利用改进的反蚁群算法开始对环境进行探索，并留下信息素来帮助其余围捕机器人向不同方向进行探索.图4(c)展示了在t=120 s时，部分机器人检测到目标，并进入跟踪阶段. 值得注意的是，如图4(d)所示，由于目标是运动的，检测到目标的机器人会跟着目标一起移动，并释放跟踪信息素用来引导其他机器人到达目标周围. 图4(e)和(f)展示了群体机器人利用基于插值隐函数的分层基因调控网络模型对目标进行包围. 可以看到，当目标运动时，在含有障碍物的环境下，群体机器人也能很好对动态目标进行围捕.

图4 群体机器人利用该框架对动态单目标进行搜索和围捕Fig. 4 The framework is used by swarm robots to search and entrap dynamic single target

2.3 动态多目标搜索和围捕

为了验证所提出的方法对复杂围捕任务的可行性，本文进一步设置了一个更具有挑战性的场景. 具体如下，群体机器人需要先在受限环境下围捕多个目标，然后多个目标将会向四周逃逸，群体机器人需要在受限环境下对多目标进行重新进行分配和围捕.在该场景下，目标用“★”表示，群体机器人用不同颜色的“●”表示，灰色区域为障碍物.

图5展示了群体机器人利用本文提出的框架在该环境下对动态多目标进行围捕的过程. 图5(a)～(c)展示了群体机器人利用反蚁群算法对未知多目标进行搜索和围捕的过程. 图5(d)展示了当t=206 s时，目标开始向不同方向逃逸的场景，由于群体机器人的躲避策略使得群体机器人被“推”离目标，此时群体机器人跟踪阶段再次激活. 随着目标向四周逃逸，如图5(e)～(f)所示，群体机器人被分为3个子群体，分别对3个方向的目标再次进行了围捕.

图5 群体机器人利用该框架对动态多目标进行搜索和围捕Fig. 5 The framework is used by swarm robots to search and entrap dynamic multi-targets

2.4 评价指标与实验分析

首先，针对目标搜索与围捕问题，本文讨论了2.2节实验场景下不同群体机器人数量对区域覆盖率Cr的影响. 如图6所示，在目标搜索与围捕过程中，区域覆盖率随时间不断上升，且参与任务的机器人数量越多，整体的区域覆盖率越大.

图6 不同数量下群体机器人区域覆盖率随时间变化的曲线Fig. 6 The curves of the area coverage rate over time for different numbers of robots.

第2个评价指标设定为围捕成功覆盖率Dr. 在实际应用中，为了保证围捕目标的效果，通常要求目标多个方向都存在相应的围捕机器人. 因此，本文以目标为中心进行角度六等分，统计各角度的围捕机器人数量并以此计算围捕成功覆盖率Dr，具体计算公式如下：

式中：M表示目标数量；Trap(m,l)表 示目标m在l·60°方向上是否存在围捕机器人，若是，则返回1， 否则为0.

图7统计了不同机器人数量阈值下围捕成功覆盖率Dr的情况，实验场景与2.2节和2.3节保持一致，最大运行时间T=300 s. 由图7可见，动态单目标场景下，围捕成功覆盖率随着机器人数量的增大而增大，且在机器人数量为6的时候达到最大值. 同时，在动态多目标场景下，围捕成功覆盖率在机器人数量为12的时候为最大值. 值得一提的是，在机器人数量为14时，围捕成功覆盖率反而出现了下降，这是因为当机器人数量达到一定值的时候，场景障碍物以及机器人之间的避碰措施反而会影响机器人围捕目标的效率，以至于在到达最大运行时间的时候部分机器人未能实现对目标的围捕.

图7 不同数量下群体机器人围捕成功覆盖率随机器人数量变化的柱状图Fig. 7 The histograms of the entrapment success coverage rate for different numbers of robots.

第3个评价指标为平均围捕距离Ed，用来表示所有机器人距离目标的平均距离，通过观察过程中Ed数值的变化，可以反映出围捕的完成程度. 在保持与目标安全距离的前提下，一般认为Ed越小越好.Ed的计算公式如下：

式中：nr表 示执行任务的机器人数量；Dis(i)表示机器人和目标之间的距离.

针对目标搜索与围捕问题，本文将所提框架IIACS-PH-GRN与前人所提的反蚁群系统算法(inverse ant system-based surveillance system, IAS-SS)[17]进行了对比. IAS-SS算法的实验参数与文章[17]保持一致，也和H-GRN模型进行融合以获得围捕功能，具体参数和本文中提出的IIACS-PH-GRN模型中用到的H-GRN模型的参数保持一致. 机器人数量分别设定为6个和12个. 实验场景与2.2节和2.3节保持一致，独立运行了20次，统计平均围捕距离Ed的数值并取平均值，实验结果如图8所示.

图8 不同场景下应用两种算法时平均围捕距离随时间变化的曲线Fig. 8 The curves of the average distance versus time when the two algorithms are applied in different scenarios

由图8可知，在整个实验过程中平均围捕距离随着时间逐渐减小，本文所提的IIACS-PH-GRN框架较IAS-SS-H-GRN算法可以获得更小的平均围捕距离. 这主要是由于我们提出的方案中多类信息素的加入可以帮助群体机器人更早地实现聚集，并开始围捕目标. 此外，在多目标场景中平均围捕距离Ed的突然增大是目标们的突然“逃逸”所导致的.

此外，IIACS-PH-GRN和IAS-SS-H-GRN在第2个评价指标围捕成功覆盖率Dr上的表现如图9所示.IIACS-PH-GRN较IAS-SS-H-GRN具有更高的围捕成功覆盖率，且在两个场景中均能更快地完成围捕任务.

图9 不同场景下应用两种算法时围捕成功覆盖率随时间变化的柱状图Fig. 9 The histogram of the success coverage rate of entrapment over time when the two algorithms are applied in different scenarios

综上所述，本文所提出的群体机器人目标搜索和围捕框架相较于传统算法具有更好的性能.

3 结 论

本文研究了在环境未知和通信受限的条件下，群体机器人对目标的搜索和围捕问题. 为此，本文提出了基于共识主动性的群体机器人目标搜索与围捕框架，该框架融合了反蚁群算法和基于信息素的分层基因调控网络模型. 实验结果表明，该框架能够很好地解决上述问题，获得了比传统算法更加优越的性能，对未来研究在各种复杂环境下的群体机器人目标搜索及围捕打下了良好的基础. 本文的后续研究将针对性地设计更加全面的仿真场景，并侧重于研究在不同场景下模型参数的自适应调节策略，同时根据真实的通信受限环境进一步考虑更有效的行为映射机制，以获得更加贴合实际场景的可以用于实机实验的目标搜索与围捕模型.