基于Voronoi图最近邻协商的多机协同追捕方法

张云赫， 苏立晨， 董云帆， 刘瑜， 李宇萌

(1.北京航空航天大学 电子信息工程学院， 北京 100191； 2.北京航空航天大学 自动化科学与电气工程学院， 北京 100191；3.北京电子工程总体研究所， 北京 100854；4.清华大学 信息科学技术学院， 北京 100084)

随着我国低空空域持续开放，无人机“黑飞”事件频发，对公共安全、国防安全带来巨大挑战。近年来，以协同追捕为代表的柔性反制技术为复杂低空安全管控提供了新的思路。协同追捕通过控制多个装备捕获装置的追捕无人机，对“黑飞”无人机进行协同追踪并将其网捕，可更有效地消除“黑飞”无人机带来的安全隐患，具有重要理论研究意义与实际工程应用价值。

协同追捕问题的本质是一组追捕者依据协同策略与逃逸者连续交互、互相对抗、动态博弈的过程[1-3]，已受到国内外学者高度关注。对于协同追捕问题的求解，是Isaacs[4-6]提出的微分博弈方法，他从状态交互的角度建立了微分博弈方程组，实现了对双方动态对抗关系的建模与刻画。后续工作在此基础上建立了线性、非线性微分追逃博弈模型[7-15]，分别讨论并解决了在不同运动规律下的协同追捕问题。然而此类方法在求解过程中涉及的变量多、维度高，求解速度迟缓。针对这一不足，Parsons[16-17]将图论概念引入协同追捕问题，提出了离散微分博弈方法，通过在图上的离散化建模，只求解在离散时刻点上的追捕策略，时刻点间的策略通过平滑近似获取。此类方法虽然显著提高了求解速度，但考虑协同追捕问题固有的连续性，离散化表征和平滑近似必然导致精度上的损失，追捕策略在连续时间域上的整体性能难以保证。

此后，基于图决策理论的方法也被用于解决多智能体协同追捕问题，其中较为经典的是Voronoi图。由Tsiotras[18]通过Voronoi图将连续的动作空间转化为离散的图单元，极大地缩小了动作搜索空间，降低了计算复杂度，提升了计算效率。同时动态Voronoi图划分的时变特性又保证了可行解的连续性，一定程度上平衡了求解速度和计算精度，实现了对移动目标的高效追捕，然而该工作是在逃逸者的控制策略已知的前提下设计协同追捕策略，适应性较差。针对这一问题，张伟等[19-20]基于Voronoi图提出了一种分布式多对一追捕策略，并验证了在逃逸者控制策略未知情况下，该追捕策略依然能实现对逃逸者的追捕，然而以上工作均只适用于理想环境下的多对一的协同追捕问题，无法应用于存在多个逃逸者的协同追捕场景。

在多无人机协同追捕问题中，Voronoi图法通过将有界环境划分，将连续的动作空间离散化，一方面极大地减小了动作搜索空间，提高了计算效率，适合无人机进行实时决策；另一方面将各架无人机分隔开，保证了一定的安全性。由于实际城市低空环境地形地貌复杂，追捕无人机可能受到障碍物遮挡导致通信受限，然而现有工作中大多设定为无人机均可获取完备信息，无法适用于存在障碍物且机间通信受限的场景中。

因此，本文重点开展多对多协同追捕问题研究，在信息非完备和多障碍物的环境约束下建立了通信约束与可行域受限下的协同追捕模型，基于Voronoi图的划分对环境进行表征，提出了基于最近邻协商面积最小化的追捕策略求解方法，有效提升了多机协同追捕的可靠性与鲁棒性。

1 问题描述与建模

(1)

(2)

追捕者的目标是在有限时间内抓住所有逃逸者，对于第i个逃逸者来说，即至少有一个追捕者离该逃逸者的距离小于抓取半径rc：

(3)

(4)

(5)

式中tΔ表示时间步。

2 基于Voronoi图的协同追捕方法

2.1 Voronoi图的基本性质

本文以Voronoi图为基本框架，将各架无人机用质点表示，以该质点为生成元构成Voronoi图，对二维有界环境进行划分(如图1所示)，并基于Voronoi图的以下几个基本性质来定义协同追捕问题模型：

图1 Voronoi图划分场景示意Fig.1 Schematic diagram of Voronoi partition

1)每个Voronoi元胞内有一个生成元(追捕者或逃逸者所在位置)；

2)每个Voronoi元胞内的点到该生成元距离小于到其他生成元的距离；

3)Voronoi元胞边界上的点到生成此边界的生成元距离相等；

4)有共同边界的2个Voronoi元胞互为相邻元胞。

图中每架无人机根据所生成的Voronoi元胞及相邻元胞的相关信息进行决策，这极大地减小了其动作搜索空间，提高了生成决策的计算效率。

2.2 基于面积最小化的协同追捕策略

对于追捕者而言，逃逸者的具体控制策略不可获知，但逃逸者仅会在其安全到达集内运动[21]。安全到达集是指逃逸者能快于其他追捕者直线到达的点的集合，逃逸者可到达该集合区域内的任何一点，从而避免被追捕者抓取。当追捕者和逃逸者拥有相同的最大速度和动力学方程时，安全到达集也就转化为了有界环境下的Voronoi图划分，即逃逸者的Voronoi元胞表示为：

∀j∈{1,2,3,…，N}}

(6)

式中q表示Voronoi元胞内的点。

由于逃逸者只能移向自己安全到达集内的点，追捕者期望通过最小化逃逸者的安全到达集的大小，也就是最小化逃逸者所生成的Voronoi图划分区域的面积来逐渐缩小逃逸者的可行动作空间，从而最终完成对逃逸者的抓取，把这个策略称为“面积最小化”策略，该策略将会把追捕者引导至追捕者和逃逸者共同Voronoi划分边界的中点。

假设逃逸者所生成的Voronoi划分区域为Ve，其面积大小为Ae，则面积的大小可以表示为：

(7)

式中q表示逃逸者生成Voronoi区域Ve内的点，则Ae的导数为：

(8)

希望通过追捕者采取策略来持续地减小Ae，可以把上面公式的右边第2项分解为单个的减小量，如果最大化Ae的减小速度，则每个追捕者的速度为：

(9)

由此，依据面积最小化策略的思想，可以得到追捕者的控制速度。各追捕者采取这样的速度选择，Ae可以沿负梯度方向，即以最快的速度减小。

2.3 追捕策略可行性证明

本文将依据5个结论来简要证明在该策略下，追捕者可以在有限时间内完成对单个逃逸者的抓取。

(10)

结论证明：对于式(5)中定义的Ae，通过莱布尼茨积分公式，可得Ae的导数简化为：

(11)

(12)

应用结论1，将式(10)代入式(9)，可得追捕者的速度简化为：

(13)

(14)

式中Cb为追捕者xp和逃逸者xe的Voronoi图的共同边界的重心。

结论证明：对于单个追捕者和单个逃逸者的场景，Ae的导数简化为：

(15)

将追捕者速度，式(13)代入式(15)，可得：

(16)

从而得到Ae≤0，且当Ae=0时，可以得到：

(17)

根据结论2可以得到，对于逃逸者来说，能够保持其安全到达集大小的唯一策略就是移向Voronoi共同边界的重心Cb。定义d为追捕者和逃逸者之间的距离，则：

d=‖xp-xe‖2=(xp-xe)T(xp-xe)

(18)

(19)

结论证明：距离d的导数为

(20)

(21)

由于Cb在相邻2个Voronoi元胞的公共边界上，根据2.1节Voronoi图的性质(3)，可得‖Cb-xp‖=‖Cb-xe‖，因此式(21)简化为：

(22)

(23)

(24)

移项后得到：

(25)

放缩合并，得到：

(26)

(27)

E=kAe+d

(28)

结论5对于系统函数(28)，在采取策略，式(13)的情况下，如果在t0时刻前没有完成抓取，则：

E(t)

(29)

结论证明：根据结论4，得到以下的2个条件：

(30)

(31)

则系统函数的导数为：

(32)

(33)

(34)

经过一系列的推导证明，可得到追捕者的速度简化为：

(35)

由此可以看到，该追捕策略将引导追捕者移向和逃逸者共同Voronoi边界的重心，在二维环境中，也就是移向共同边界的中点。

通过以上推导，给出了多无人机的协同追捕策略，证明了在有界凸环境内，无论逃逸者采取何种控制策略，追捕者均可确保在有限时间内完成对其的抓取，在这一前提下，通过设定逃逸者以“move-to-centroid”策略[22]尽可能保持其安全到达集的大小以及所覆盖区域的均匀划分：

(36)

式中CV表示逃逸者生成Voronoi划分区域的形心。由此可知，该策略将逃逸者引向生成Voronoi划分区域的形心。

2.4 通信受限下的协同追捕策略

由于低空运行环境复杂、约束多元，通信链路可能受到地形遮挡，导致追捕无人机不能实时地和较远处的无人机进行协商，从而共享目标。

因此，本节针对通信受限条件，提出了一种基于最近邻协商面积最小化的追捕策略，该策略假设每个追捕者和相邻的追捕者及逃逸者可进行通信，以获取相邻Voronoi元胞的相关信息，通过依次协同最小化相邻逃逸者的Voronoi元胞面积，实现对逃逸者的追捕。由此，每个追捕者锁定距离最近的相邻逃逸者为目标，速度则指向与该逃逸者的Voronoi元胞公共边的中点，如果追捕者相邻元胞没有逃逸者，速度则指向距离最近的逃逸者，对于逃逸者而言，为了尽可能保证各自安全到达集的大小，其速度指向各自生成Voronoi单元的形心。相比面积最小化策略，具有以下优势：

1)每个追捕者只需要通过和相邻追捕者，逃逸者进行通信，获取相邻Voronoi元胞的相关信息，可适用于信息不完备条件；

2)追捕者在过程中可以更换目标，不需要与其他追捕者进行协商共同目标，可适用于通信受限条件。

(37)

对于逃逸者，其控制策略为移向Voronoi元胞的形心：

(38)

式中：Vi是第i个逃逸者根据所有无人机位置所生成的Voronoi元胞；CVi为该Voronoi元胞的形心。

2.5 可行域受限下的追捕策略

本节针对存在多元障碍物的场景，在基于最近邻协商的面积最小化策略的基础上，加入了紧急避障机制，提出了可行域受限下的协同追捕策略，具体如下：

1)计算有界环境Voronoi图划分过程中，需要把障碍物中心当作静态智能体处理，参与Voronoi图构建，同时在更新Voronoi元胞信息时，需要给障碍物生成的Voronoi元胞进行特殊标记，追捕者可以根据该特殊标记识别障碍物元胞；

2)为了防止追捕者与障碍物相撞，追捕者实时地记录离附近障碍物的距离，当该距离即将小于设定的安全半径时，追捕者立即采取紧急避障机制，即上述“move-to-centroid”策略，当距离大于安全距离后，恢复到之前的控制策略。

2.6 算法仿真流程

算法流程主要分为场景定义，循环控制两个部分。场景定义主要包括追捕者和逃逸者的数量，速度大小，位置，存活状态，时间步长，边界大小以及抓取半径等参数的初始化。

算法流程图如图2所示，循环控制主要包含计算各智能体有界环境下的Voronoi图划分，计算追捕者和逃逸者的速度方向，追捕者逃逸者的位置更新以及计算是否触发抓取条件等几个部分。

图2 算法流程Fig.2 Algorithm flowchart

3 仿真实现与结果分析

根据前文提出的追捕逃逸策略进行场景仿真，场景为100 m×100 m的二维有界凸环境(本节以下仿真效果图中1个单位表示100 m)，无障碍物，有4个追捕者和8个逃逸者，场景示意图如图3所示。

图3 仿真场景示意Fig.3 Schematic diagram of simulation scenarios

图中“o”为追捕者，“*”为逃逸者,不存在障碍物。

3.1 通信受限下的多对多追捕仿真结果

场景为100 m×100 m的二维有界凸环境，存在障碍物，有4个追捕者和8个逃逸者。其中追捕者，逃逸者和障碍物的初始位置均为随机生成，时间步长设置为1 s，抓取半径设置为5 m，仿真效果如图4所示。

图4 协同追捕效果Fig.4 Schematic diagram of cooperative pursuit

由图4可以看到，随着时间的演化，4个追捕者最终完成了对所有逃逸者的追捕。在图4(a)中，由于追捕者之间的通信受限，每个追捕者只能获取相邻Voronoi元胞的信息，比如追捕者X1仅能根据X4、X8、X12的信息进行决策，其目标为相邻最近的逃逸者，在图4(b)中，4个追捕者开始逐渐包围在角落里“无处可走”的逃逸者X8、X11，最终，如图4(d)所示，多个追捕者最终依次完成了对多个逃逸者的协同追捕。

3.2 可行域受限下的多对多追捕仿真结果

本节采用的场景为100 m×100 m的二维有界凸环境，存在障碍物，有4个追捕者，4个逃逸者和4个障碍物。其中追捕者，逃逸者和障碍物的初始位置均随机生成，圆形区域表示障碍物，所有追捕者不能进入障碍物区域。仿真的时间步长设置为1 s，抓取半径和障碍物半径均设定为5 m，障碍物半径设定为3 m。一次试验过程中的几帧图像，仿真效果如图5所示。

图5 障碍物场景下追捕效果Fig.5 Schematic diagram of cooperative pursuit under obstacle scenarios

由图5可以看到，随着时间的演化，4个追捕者在规避障碍物的同时完成了对所有逃逸者的追捕。在图5(a)中，通过障碍物参与Voronoi图划分，将追捕者与障碍物分隔开，使其可以在追捕过程中有效地规避障碍物。

3.3 基线策略对比分析

上述仿真结果表示，提出的策略可以在通信受限和可行域受限的约束下实现对所有逃逸者的协同追捕，本节将和基线策略对比所有逃逸者被抓取的完成时间来分析多无人机协同追捕策略的效率。

首先给出基线策略：对于追捕者，不进行Voronoi图划分，追捕者的速度直接指向距离最近的逃逸者；对于逃逸者而言，为了使其在设定的有界环境内运动，其速度指向生成Voronoi元胞的形心。然后在不同追捕者—逃逸者数量比的情况下，分别仿真试验20次，记录基线策略和基于Voronoi图划分提出的协同追捕策略下的抓取时间，对比分析所提出协同追捕策略的效率。图6给出了2种策略在不同追捕者—逃逸者数量比的情况下多次仿真试验中抓取时间的最大值，最小值和平均值。上图中Am策略是本文提出的基于Voronoi图最近邻协商的多对多协同追捕策略。

图6 不同策略抓取时间对比Fig.6 Comparison of capturing durations under different strategies

如图6所示，当追捕者的数量多于逃逸者数量时，Am策略抓取时间的平均值比基线策略要短，这说明相比基线策略，Am策略效率更高；当逃逸者数量与追捕者数量持平甚至高于追捕者数量时，Am策略的优势则逐渐减小，这说明Am策略相比于基线策略不太适用于大量逃逸者的情况。但由于民航空管的管控，在实际的多无人机协同追捕“黑飞”无人机问题中，一般均为多个无人机抓取较少数量的“黑飞”无人机，不会出现大批量的“黑飞现象”，因此本文所提出的策略适用于实际多无人机协同追捕“黑飞”无人机问题。

此外，可以发现，对于不同的追捕者，逃逸者数量比，基线策略的抓取时间均呈现出较大的波动，其最大值和最小值差值较大，这是由于每次试验中追捕者和逃逸者的初始位置是随机的，不同的初始位置对基线策略的表现影响很大，这表明基线策略的追捕效率具有一定的不稳定性。相比而言，本文所提出策略相应的抓取时间的波动相比基线策略要小，这表明该策略的稳定性更强。

4 结论

1)采用Voronoi图对有界环境进行表征，对于多无人机协同追捕问题，提出了一种面积最小化策略，实现了多个追捕者对多个逃逸者的高效协同追捕。

2)证明了所提出的面积最小化策略可以在有限时间内完成对逃逸者的协同追捕。

3)针对城市低空复杂环境下的多元障碍和通信受限约束，提出了基于最近邻协商的协同追捕策略，仿真结果表明，在环境障碍、信息非完备的约束下，所提出的策略可以实现对多个逃逸者的高效协同追捕。

本文提出的追捕策略具有一定的有效性和鲁棒性，为多无人机协同追捕提供了理论与技术支撑。

由于在探讨多无人机协同追捕问题中，是把无人机当作质点考虑的，没有考虑无人机的大小尺寸以及相关动力学约束，另外仿真场景都是基于二维有界环境，一定程度上限制了方法对于实体无人机和实际问题的适用性。因此考虑如何添加动力学约束，在三维场景下完成多无人机的协同追捕任务是未来研究的一个重要方向。

> >