我们提出了一种分布式算法，用于在有界凸环境中使用多个追踪者（pursuer）共同追捕多个逃避者（evader）。该算法适用于拦截受保护空域中的非法无人机，以及其他应用。追踪者不知道逃避者的策略，但通过使用基于Voronoi图对环境进行的全局“区域最小化”策略，我们保证了在有限时间内捕获所有逃避者。我们提出了一种适用于二维（2-D）和三维（3-D）环境的分布式策略，并在多个仿真中显示出其优于其他分布式的多追踪者启发式方法。通过使用自主和人工控制的机器人进行实验，以展示该方法的实用性。人工控制的逃避者无法避免被使用该算法的追踪者捕获。

由于论文证明比较多，本文只介绍文章的主要内容，对详细证明过程感兴趣的同学可以自行查阅。

Pursuers和evaders均使用使用单积分模型，即
x ˙ e i = u e i , ∥ u e ( t ) ∥ ≤ v max ⁡ x ˙ p j = u p j , ∥ u p ( t ) ∥ ≤ v max ⁡ \begin{aligned}\dot{x}_e^i&=u_e^i,\quad\|u_e(t)\|\leq v_{\max}\\\dot{x}_p^j&=u_p^j,\quad\|u_p(t)\|\leq v_{\max}\end{aligned} x˙ei​x˙pj​​=uei​,∥ue​(t)∥≤vmax​=upj​,∥up​(t)∥≤vmax​​
不失一般性，文章将速度约束条件设置为 v m a x = 1 v_{max}=1 vmax​=1。

pursuers的目标是抓捕环境中的所有evaders，每个evader被捕捉成功的条件表示为：
min ⁡ j ∈ n p ∥ x e i ( t c ) − x p j ( t c ) ∥ < r c \min_{j\in n_{p}}\|x_{e}^{i}(t_{c})-x_{p}^{j}(t_{c})\|<r_{c} j∈np​min​∥xei​(tc​)−xpj​(tc​)∥<rc​
其中 n p n_p np​为pursuer的数量， r c r_c rc​为捕捉半径。

对于本文中的agent，它的Voronoi图定义如下：
V i = { q ∈ Q ∣ ∥ q − x i ∥ ≤ ∥ q − x j ∥ , ∀ j ≠ i , i , j ≤ n } V_i=\{q\in Q|\|q-x^i\|\leq\|q-x^j\|,\forall j\neq i,i,j\leq n\} Vi​={q∈Q∣∥q−xi∥≤∥q−xj∥,∀j=i,i,j≤n}
Voronoi图中，某一cell的相邻的cell使用集合 N i \mathcal{N}_i Ni​表示。
论文在该部分部分没有提及"in a bounded convex environment"时Voronoi图的表示，在实际的代码实施部分需要自行进行修改Voronoi图的求解

对于evader所在的cell V e V_e Ve​，其面积可以表示为：
A e = ∫ V e d q A_{e}=\int_{V_{e}}dq Ae​=∫Ve​​dq
A e A_e Ae​的变化可以用以下的微分方程进行描述
A ˙ e = ∂ A e ∂ x e x ˙ e + ∑ j = 1 n p ∂ A e ∂ x p j x ˙ p j \dot{A}_e=\frac{\partial A_e}{\partial x_e}\dot{x}_e+\sum_{j=1}^{n_p}\frac{\partial A_e}{\partial x_p^j}\dot{x}_p^j A˙e​=∂xe​∂Ae​​x˙e​+j=1∑np​​∂xpj​∂Ae​​x˙pj​

经过推导可知，上式中出现的偏导数可以改写成如下形式：
∂ A e ∂ x p j = L j ∥ x p j − x e ∥ ( x p j − C b j ) \frac{\partial A_e}{\partial x_p^j}=\frac{L_j}{\|x_p^j-x_e\|}\left(x_p^j-C_{b_j}\right) ∂xpj​∂Ae​​=∥xpj​−xe​∥Lj​​(xpj​−Cbj​​)

其中 b j b_j bj​是evader和pursuer j的Voronoi边界， L j L_j Lj​是边界的面积（如果是二维情形，就是边界的长度， C b j C_{b_j} Cbj​​是边界的质心。

进一步可以得到pursuer的控制律：
u p j = − ∂ A e ∂ x p j ∥ ∂ A e ∂ x p j ∥ = ( C b j − x p j ) ∥ C b j − x p j ∥ \begin{aligned} u_p^j&=-\frac{\frac{\partial A_e}{\partial x_p^j}}{\|\frac{\partial A_e}{\partial x_p^j}\|} \\ &=\frac{(C_{b_j}-x_p^j)}{\|C_{b_j}-x_p^j\|} \end{aligned} upj​​=−∥∂xpj​∂Ae​​∥∂xpj​∂Ae​​​=∥Cbj​​−xpj​∥(Cbj​​−xpj​)​​

本部分首先证明了在单-单情形下，采用上文所述的pursuer控制律，能够保证 A ˙ e ≤ 0 \dot A_e \leq 0 A˙e​≤0对任意的evader控制律都成立，并且等于零的情形只出现在evader控制律如下的情形：
u e ∗ = ( C b − x e ) ∥ C b − x e ∥ u_e^*=\frac{(C_b-x_e)}{\|C_b-x_e\|} ue∗​=∥Cb​−xe​∥(Cb​−xe​)​

然后文章证明了单-单情形下，若 A ˙ e = 0 \dot A_e = 0 A˙e​=0，则evader与pursuer之间的距离的平方 z z z会不断减小。

除此之外，文章还考虑了一种情况，即 A e A_e Ae​减小，但是 z z z在增大并保持在区间 [ r c 2 , l max ⁡ 2 ] [r_c^2, l_{\max}^2] [rc2​,lmax2​]中，其中 l max ⁡ 2 l_{\max}^2 lmax2​为有界凸区域中任意两点的最大距离，在这种情形下，evader永远不会被抓住。文章证明了这一情况不可能出现。（这里它提到的情况我想了很久也没想明白是怎么出现的，小伙伴们可以把自己的理解发到评论区）

随后，论文定义了一个“cost-to-capture”函数，由两部分组成：
E = k A e + z E = kA_e +z E=kAe​+z
此处的 k k k使用了上一部分证明中的公式，并且证明了这个函数在evader被抓到之前是单调递减的。

多evaders情形下，用 A e A_e Ae​表示所有evader的cell面积（三维情形下为体积），则其变化可以用下式表示：
A ˙ e = ∑ i = 1 n e ∂ A e i ∂ x e i x ˙ e i + ∑ i = 1 n e ∑ k ∈ N e i ∂ A e i ∂ x e k x ˙ e k + ∑ j = 1 n p ∑ i ∈ N p j ∂ A e i ∂ x p j x ˙ p j \begin{aligned}\dot{A}_{e}=\sum_{i=1}^{n_{e}}\frac{\partial A_{e_{i}}}{\partial x_{e}^{i}}\dot{x}_{e}^{i}+\sum_{i=1}^{n_{e}}\sum_{k\in\mathcal{N}_{e_i}}\frac{\partial A_{e_{i}}}{\partial x_{e}^{k}}\dot{x}_{e}^{k}+\sum_{j=1}^{n_{p}}\sum_{i\in\mathcal{N}_{p_{j}}}\frac{\partial A_{e_{i}}}{\partial x_{p}^{j}}\dot{x}_{p}^{j}\end{aligned} A˙e​=i=1∑ne​​∂xei​∂Aei​​​x˙ei​+i=1∑ne​​k∈Nei​​∑​∂xek​∂Aei​​​x˙ek​+j=1∑np​​i∈Npj​​∑​∂xpj​∂Aei​​​x˙pj​​

如果此时直接将单evader中的pursuer控制律推广成如下形式：
u p j = − ∑ i ∈ N p j ∂ A e i ∂ x p j u_p^j=-\sum_{i\in\mathcal{N}_{p_j}}\frac{\partial A_{e_i}}{\partial x_p^j} upj​=−i∈Npj​​∑​∂xpj​∂Aei​​​
则可能会出现由于邻接的evaders具有对称的分布而导致各个偏导数之和为零，从而陷入对称陷阱（symmetry trap）。论文提出了只追踪距离最近的evader从而避免这一问题。此时，记追踪同一个evader κ \kappa κ的pursuer集合为 P κ P_\kappa Pκ​， κ \kappa κ与追踪它的pursuers的Voronoi剖分定义为：
V ˉ κ = { q ∣ ∥ x e κ − q ∥ ≤ ∥ x p j − q ∥ , j ∈ P κ } \bar{V}_\kappa=\{q|\|x_e^\kappa-q\|\leq\|x_p^j-q\|,j\in P_\kappa\} Vˉκ​={q∣∥xeκ​−q∥≤∥xpj​−q∥,j∈Pκ​}
类比单evader情形，pursuers的控制律可以表示为：
u p j = ( C b ˉ κ j − x p j ) ∥ C b ˉ κ j − x p j ∥ u_p^j=\frac{\left(C_{\bar{b}_{\kappa j}}-x_p^j\right)}{\|C_{\bar{b}_{\kappa j}}-x_p^j\|} upj​=∥Cbˉκj​​−xpj​∥(Cbˉκj​​−xpj​)​
其中 b ˉ κ j \bar b_{\kappa j} bˉκj​是 x e κ x_e^\kappa xeκ​和 x p j x_p^j xpj​在 V ˉ κ \bar{V}_\kappa Vˉκ​中共享的边， C b ˉ κ j C_{\bar{b}_{\kappa j}} Cbˉκj​​是 b ˉ κ j \bar b_{\kappa j} bˉκj​的质心。
在初始时刻，可能会出现部分evader没有pursuer追踪，但是部分evader有多个pursuer追踪的情形。对此，论文证明了使用这种全局策略仍然能够保证有限时间内抓捕所有evaders。
值得注意的是，本部分所提的global policy不能保证最优性，只能确保有限时间内抓捕。目前唯一能够找到最优解的方法是求解HJI方程，但是基于HJI的方法对于大规模的MAS是难以实现的。

仿真中evader使用的策略是“move-to-centroid”，即向所在cell的质心移动，表示为：
u e i = ( C V i − x e i ) ∥ C V i − x e i ∥ u_e^i=\frac{\left(C_{V_i}-x_e^i\right)}{\left\|C_{V_i}-x_e^i\right\|} uei​=∥CVi​​−xei​∥(CVi​​−xei​)​
evader有全局信息，通过所有的agents的位置来计算 V i V_i Vi​，采用这种控制策略有两个理由：

1. 如果evader只是远离pursuer，则会导致最终被围堵在边界位置
2. 如果evader希望扩大 A e A_e Ae​，则其需要向pursuer前进，显然会被抓捕（在2.2.2节的 u e ∗ u_e^* ue∗​中已经证明了这一点）

这也说明了这篇论文提出的算法只对pursuer有益。

论文结果复现的结果见本人B站视频：