基于有限状态机的多机器人围捕策略研究

张奇松，胡玉兰

（沈阳理工大学 信息科学与工程学院，辽宁 沈阳 110168）

在机器人协调协作中，多机器人围捕任务可以看作多机器人队形控制的另一种形式。在传统队形控制中，有跟随领航者法（Leader-follower）、基于行为法（Behavior-based）、虚拟结构法（Virtual structure）。其中跟随领航者法即基于Leaderollower法和虚拟结构法的队形控制方法，侧重于传统的控制理论，可以利用动态系统理论对编队系统的稳定性进行分析，但是缺乏基于行为控制方法中的队形反馈信息。为了增加基于Leader-follower方法在进行编队控制时的实用性，这里提出一种基于有限状态机的多机器人围捕方案，引入队形条件反馈信息，建立基于条件反馈机制和Leader-follower相结合的多机器人队形控制模型实现了多机器人系统的队形控制，并给出有限状态机原理，定义围捕各阶段的不同状态。

1 改进式Leader-follower队形控制

1.1 Leader-follower基本思想

基于Leader-follower法是由Leader给定Follower的运行参数，具体的运动控制由Follower自行计算，该方法具有很好的系统可扩展性、运动策略灵活性和计算并行性。但是Leader与 Follower相对独立，Leader不容易得到 Follower的跟踪误差，如果Leader运动过快可能导致落后的机器人离队，而且整个系统对Leader机器人依赖性较大，如果Leader机器人发生故障会导致整个系统瘫痪。针对上述缺点，一些文献提出相应的解决办法。文献[1]利用反馈线性化得到非完整约束机器人的轨迹跟踪控制法则；文献[2]平滑时变反馈控制法则构成一个开环链式的队形；文献[3]引入合作方法，即Follower的运动不仅由自身决定，还受到其他机器人的影响。

在利用传统的Leader-follower方法控制队形过程中，为了在避障和保持队形之间进行协调，常常引入“虚拟机器人”概念，并将机器人的运行状态分为正常运行模式和避障模式。当某个机器人处于避障模式时，其他机器人参考替代它的“虚拟机器人”以保证正常的运行，但如果Leader根据队形反馈进行的调节过于频繁，会导致整体运动不顺畅，甚至可能当多个Follower同时处于避障状态，由于Leader队形反馈停止运动，导致系统处于死锁状态。对此，这里引入了队形的条件反馈机制，如图1所示。

图1 队形条件反馈的Leader-follower控制结构Fig.1 Leader-follower control structure of formation conditions feedback

1.2 条件反馈队形控制的基本原理

条件队形反馈的基本原理为：

1）初始时Leader接受任务T，然后根据环境信息E进行运动规划。

2）Leader将自身的运行状态 S=（XL，YL，VL，WL）和任务信息 T 通过公共变量区通知 Robot i（i=1，2，...，n）。

3）每个follower根据任务T计算自己在队形中的期望位置 Pdi=（xdi，ydi）（i=1，2，...，n），结合环境信息 E，根据控制策略产生控制量，即（υi，wi）。 队形信息 P=（P1，P2，...，Pn）被反馈给Leader，其中P1为Follower1当前位置。在正常运动时Leader不将队形反馈信息作为自己运动的依据，依靠Follower自行调整速度来提高队形保持率。

4）如果当个别机器人处于通信范围边缘时，Leader降低运动速度，使得落后机器人能够赶上，防止Follower掉队。在特殊情况下（等待较长时间而最远的Follower与Leader之间的距离没有缩短），Leader会放弃故障机器人，重新进行队形调整。

2 多机器人围捕策略设计

2.1 开阔队形侦查策略

在机器人行进过程中，为了保证系统具有强的防御性能，获得详细的环境信息和保持近距离的通信，选择具有向心性的队形（像圆形、菱形）。线形队形（纵队和横队）中机器人位置非常开阔，侦查范围广、重复侦查区域少，所以这里使用线形队形作为侦查队形。

2.2 半圆形队形预包围策略

在开阔地带执行围捕任务时，圆形包围队形难以直接形成，因为当invader发现围捕机器人后会改变运动轨迹，多机器人系统预先分配的包围点便失去了作用。为此，将最后的围捕分为两个阶段。

第1阶段为扇形展开半圆形预包围圈，如图2所示。在围捕任务中，机器人一般具有略强于Invader的侦查能力，所以机器人会先于Invader发现对方。最早发现Invader的机器人自动成为围捕阶段的Leader，然后其根据拟合出的Invader轨迹确定出预包围点，并根据机器人之间的位置关系分配半圆形预包围队形的队形点。因为此时重要的不再是机器人到达队形点的先后时间，而是能够有效地堵截Invader的逃脱方向。当Invader发现机器人后会首选转向逃脱，此时机器人若能够将其正前方180°的路径全部封堵，则Invader只能反向逃脱，这样可以为接下来圆形包围队形的形成争取有利条件。

图2 扇形展开半圆形预包围队形Fig.2 Sector semicircle beforehand surrounded formation

第2阶段为收缩队形并形成圆形包围圈。为了防止Invader过早发现机器人，本文将预包围队形的半径设的比较大，如果直接形成运行圆形包围队形，早会造成相邻机器人之间的空隙过大，Invader可以从空隙中逃脱，导致围捕的失败。所以，本文设计机器人预包围队形首先向Invader方向收缩，然后形成圆形包围队形。

2.3 围捕任务退出策略

在动态围捕任务中，因为不能确保机器人每一次都能侦查到动态目标，所以设定两种退出方式：1）按照侦查队形前进N步没有发现目标，则系统退出围捕任务；2）发现目标后，在围捕过程中，以要求队形包围Invader，并且Invader静止，则围捕任务完成。

3 基于有限状态机的多机器人围捕

3.1 围捕有限状态机设计

设定有限状态机为一个三元组M=（E，Qst，φ），各变量具体含义如下：Qst={q1，q2，...，qm}为离散状态的有限集合；E={e1，e2，...，en}为Leader指令的有限集合；φ为从一个状态到另一个状态的映射，可表达为 φ（qs，E）=qk∈Qst。

在系统模型中 Qst包含6种状态：初始化（q1）、保持队形运行（q2）、侦查（q3）、半圆队形预围捕（q4）、圆形队形捕捉（q5）和退出（q6），其中在 q1、q3、q4状态的初始时刻要完成新队形点的分配及Leader更换。

初始时刻，机器人群体处于无序排列的状态，Leader机器人发出启动指令（e1），机器人首先组成指定队形，然后向指定区域运动。在保持队形运动过程，机器人主要任务是快速运动，此外要低频率的进行Invader侦查。如果发现环境复杂，机器人会自行进行蛇形队形的转换。如果在这个阶段发现Invader（e2），机器人则直接进入捕捉状态。机器人到达指定区域（e3）后，开始转换为比较开阔的侦查队形。由于环境的限制，本文将捕捉结果分为 2种：1）发现 Invader（e2），则机器人进行围捕，捕捉到 Invader后退出（e8）；2）到达侦查限制（e6）而没有发现Invader，则系统直接退出（e8）。在围捕的过程中可能发生Invader逃脱（e5）的情况，这是多机器人系统重新进入侦查状态。在机器人进行捕捉过程中，最先发现Invader的机器人自动成为新的Leader，整个捕捉过程由新Leader控制。为了加快捕捉任务完成的速度，系统首先组成半圆形队形（e4）进行预捕捉。Leader根据Invader的运动方向和运动速度预测出捕捉点，然后以捕捉点为圆心，在Invader的运动方向上形成较大半径的半圆形包围队形，从而阻挡住Invader的逃脱，而且能够较晚被Invader发现。形成半圆包围队形后，Leader发出圆形包围指令（e7）。首先收缩队形，各机器人向Invader的位置移动，Invader会选择逃脱方向，这时各机器人在Invader周围形成圆形包围圈，从而彻底阻挡住Invader的逃脱路线，围捕任务完成。

根据上述描述，机器人状态转换如下：φ（q1，e1）=q2，φ（q2，e2）=q4，φ（q2，e3）=q3，φ（q3，e2）=q4，φ（q4，e7）=q5，φ（q4，e6）=q6，φ（q4，e5）=q3，φ（q5，e5）=q3。

3.2 程序流程

图3为机器人动态，围捕程序流程图。

从该流程图可以看出，机器人的运行场景定为不同的状态，在每种状态中，机器人的功能模块的组合顺序和获得的参数存在差别，通过有限状态机来决定行为的映射规则。执行层由执行机构和探测模块组成，执行机构的主要功能是将行为层的控制参数转化为实际的物理控制量并通过硬件实施，探测模块的主要功能是利用各种传感器探测周围环境并将环境信息转化为信息处理模块可使用的信息量。

4 仿真实例

图3 动态围捕流程图Fig.3 Flow chart of dynamic seizing

仿真系统采用Visual C++语言开发，在仿真中机器人的半径为2 cm，步长为0.5 cm，间隔时间为100 ms，本文规定队形中Follower的位置误差为2 cm。图4给出了围捕实验中7种仿真图。

在围捕实验中，Invader采用跟围捕机器人相同的功能设置，只是在传感器感知范围上略微存在差别。当没有探测到任何障碍物时，Invader为直线运动；否则，它朝向安全的方向运动。

图4 7种仿真图Fig.4 Seven kinds of simulation diagrams

从以上仿真图可以看出本文根据有限状态机原理将机器人分为 6种状态，其中图 4（a）～图 4（f）分别对应初始化，保持队形初始化、保持队形运行、侦查、半圆队形预围捕、圆形队形捕捉和退出。而图4（g）为追捕机器人将入侵机器人围在其中心，根据避碰原则（即入侵机器人将其他机器人视为动态障碍物）入侵机器人没有躲避的空间，不能再移动，根据退出条件，围捕成功，系统结束运作。

5 结 论

本文主要研究了多机器人的协作围捕问题。为了实现围捕任务，提出了一种基于条件反馈机制的Leader－followers队形控制方法，同时采用有限状态机在不同状态之间进行切换。每种状态的具体实现过程，都是由队形形成和队形保持组成，通过这种状态转换带动队形转换的形式，将协调编队与围捕任务有效地结合在一起。最后通过仿真验证了算法的有效性。

[1]Desai J P， Ostrowski J， Kumar V.Controlling formations of multiple mobile robots[C]//IEEE International conference on Robotics and Automation Belgium，1998:2864－2869.

[2]Yamaguchi H，Burdick J W.Asymptotic stabilization of multiple nonholonomic mobile robots forming group formations［C］//IEEE Int Conf on Robotics and Automation，Belgium，1998：3573－3580.

[3]Pereira G A S，Das A K，Kumar V，et a1.Formation control with configuration space constraints[C]//Proc of the IEEE/RJS Int Conf on Intelligent Robots attd Systems，Las Vegas，2003：2755－2760.

[4]程磊.多移动机器人协调控制系统的研究与实现 [D].武汉：华中理工大学，2005：37－42.

[5]刘海波，顾国昌，张国印.智能机器人体系结构分类研究[J].哈尔滨工程大学学报， 2003， 24 （6）:57－60.LIU Hai-bo，GU Guo-chang，ZHANG Guo-yin.Intelligent robot structure system classification research[J].Journal of Habin Engineering University，2003，24（6）:57－60.

[6]谭民，王硕，曹志强.多机器人系统[M].北京：清华大学出版社，2005.