基于二分图的群体追逃博弈任务分配算法

Task Allocation Algorithm for Group Pursuit-Evasion Game Based on Bipartite Graph

摘要: 本文考察群体追逃博弈中追逐者的任务分配问题。通过构建二分图，设计全新算法对追逐者进行任务分配，将群体追逃博弈转化成多个多追一博弈。在多追一情形下给出了追逐者及逃避者的最优策略。运用本文所建立的算法，在考虑扰动因素的情形下，原本冗余的追逐者有可能转化为积极的追逐者。数值算例验证了任务分配的可行性及稳定性。

Abstract: This paper examines the task assignment of chasers in a group pursuit-evasion game. By constructing a bipartite graph, a new algorithm is designed to assign tasks to the chasers, and the group pursuit-evasion game is transformed into a game of multiple chases. In the case of chasing more than one, the optimal strategies of chasers and evaders are given. Using the algorithm established in this paper, under the condition of considering disturbance factors, the original redundant chasers may be transformed into active chasers. Numerical examples verify the feasibility and stability of task assignment.

1. 引言

追逃博弈(Pursuit-Evasion Games)是一类特殊的零和博弈，其中追逐者(Pursuer)致力于在最短的时间内将状态引导到一个给定的目标，而他的对手逃避者(Evader)则希望尽力延迟被捕获。文献 [1] 总结追逃博弈的近期研究成果，包括一追一博弈、多追一博弈和多追多博弈等。涉及多个追逐者和逃避者的群体追逃问题(MPNE)是目前应用最广泛的领域之一，军事上无人机集群的作战、自然界动物间的捕食猎杀都可作为群体追逃博弈的例子。文献 [2] 研究追逐者与逃避者最大速度相等情形下的多追一博弈，分别给出追逐者保证捕获和逃避者保证逃跑的条件。文献 [3] [4] 研究逃避者具有速度优势的多追一博弈，文献 [3] 考察追逐者与逃避者的最优策略，文献 [4] 关注捕获发生的条件。文献 [5] 运用几何方法研究时间最优的多追一博弈，并给出求解追逃双方最优策略的算法。文献 [6] 给出时间最优的多追一博弈的全局Stackelberg解(Global Stackelberg Solution)，并证明解的鲁棒性。

近年来，群体追逃博弈的主要解决方法是把复杂的多追多博弈转化成多个一追一(1P1E)或多追一(MP1E)博弈，这必然涉及到追逐者的任务分配问题。文献 [7] [8] [9] [10] 使用Voronoi图解决任务分配问题。文献 [7] 提出一种在整个空间上构建追逐者的Voronoi图的算法，把多追一博弈转化为地区分配问题加以解决。文献 [8] 使用动态Voronoi图研究接力追逃博弈，给出追逐者的任务分配方案。文献 [9] 以 [8] 为基础研究动态流场环境下的接力追逃博弈，给出追逐者的任务分配，同时保证任务分配随时间动态更新。文献 [10] 研究三维动态流场环境下的群体追逃博弈，并基于Voronoi图设计算法对追逐者进行任务分配。文献 [11] 通过构建追逐者与逃避者之间的通讯图(Communication Graphs)对追逐者进行任务分配，求解零和情形下的最大最小策略，并给出非合作情形下群体追逃博弈的纳什均衡。文献 [12] 运用Apollonius圆作为工具求解具有边界限制的追逃博弈，给出一追一博弈追逃双方的最优策略，并把结论推广到多追一、多追多博弈。文献 [13] 研究追逐者策略集受限制情形下的任务分配问题，并提出将“积极(Active)”与“冗余(Redundant)”的概念应用到分配问题中。

文献 [12] 中的最优策略在多追一博弈中被证明是有效的，但把结论扩展到多追多博弈中时，空间的维度和局中人的数目增加导致计算难度增大。此时一种可行的方法是将群体追逃博弈转化为多个一追一或多追一子博弈，在每个时刻为每个追逐者分配一个逃避者作为目标。即使这种方法只会得到局部最优解(Sub-optimal Solution)，在追逐者和逃避者规模较大时这是可接受的。本文的主要目的是针对实际应用场景，考虑到追逐者可能发生机械故障等意外情况，为最小化这种情况产生的影响，提出一种任务分配算法，并在考察扰动因素的情形下验证冗余的追逐者在使用该算法的情形下有可能会转化为积极的追逐者。

本文的其余部分安排如下：第2节对多追多博弈进行描述；第3节定义预计捕获时间，给出多追一博弈中追逐者与逃避者的最优策略；第4节中以预计捕获时间为指标，利用Kuhn-Munkres算法为每个追逐者分配一个逃避者作为目标，将群体追逃博弈划分为多个一追一或多追一子博弈；第5节使用数值算例验证了任务分配的可行性，并在有扰动因素的情形下验证了冗余的追逐者有可能会转化为积极的追逐者；第6节对全文进行总结并提出后续研究方向。

2. 问题描述

本节考察M个追逐者和N个逃避者参与的追逃微分博弈，记为 $\Gamma \left(M,N\right)$，博弈发生在2维欧式空间上且无边界。本文假设追逐者知道逃避者的最优策略，所考察的模型事实上成为Stackelberg博弈。追逃双方均具有简单运动的性质，即能够无约束地瞬时改变前进方向。其中追逐者的目的是捕获所有逃避者，捕获的方式为点捕获，即某个追逐者与逃避者的位置重合；与之相反，逃避者的目的是尽可能防止被捕获。记第i个追逐者为 $P_i$，第j个逃避者为 $E_j$。

追逐者与逃避者的状态方程如下：

$\begin{array}{l}{\stackrel{\dot{}}{x}}_i^p\left(t\right)=v_p\cos {\varphi }_i\left(t\right),x_i^p\left(t_0\right)=x_{i0}^p,\\ {\stackrel{\dot{}}{y}}_i^p\left(t\right)=v_p\sin {\varphi }_i\left(t\right),y_i^p\left(t_0\right)=y_{i0}^p,i=1,\cdots ,M,\\ {\stackrel{\dot{}}{x}}_j^e\left(t\right)=v_e\cos {\psi }_j\left(t\right),x_j^e\left(t_0\right)=x_{j0}^e,\\ {\stackrel{\dot{}}{y}}_j^e\left(t\right)=v_e\sin {\psi }_j\left(t\right),y_j^e\left(t_0\right)=y_{j0}^e,j=1,\cdots ,N,\end{array}$ (1)

其中 $p_i\left(t\right)=\left(x_i^p\left(t\right),y_i^p\left(t\right)\right)\in R^2$， $e_j\left(t\right)=\left(x_j^e\left(t\right),y_j^e\left(t\right)\right)\in R^2$ 分别表示追逐者 $P_i$，逃避者 $E_j$ 在t时刻的位置， $p_i\left(t_0\right)=\left(x_i^p\left(t_0\right),y_i^p\left(t_0\right)\right)\in R^2$， $e_j\left(t_0\right)=\left(x_j^e\left(t_0\right),y_j^e\left(t_0\right)\right)\in R^2$ 分别为追逐者 $P_i$，逃避者 $E_j$ 在初始时刻 $t_0$ 的位置。 ${\varphi }_i\left(t\right)$， ${\psi }_j\left(t\right)\in \left[-\pi ,\pi \right)$ 分别表示追逐者 $P_i$，逃避者 $E_j$ 的输入控制，追逃双方通过在每个时刻选择策略控制前进方向。常量 $v_p$， $v_e$ 是追逐者与逃避者的线速度，本文假设 $v_p>v_e$，以保证点捕获一定会在有限时间内发生。记捕获逃避者 $E_j$ 所用时间为

$T_j=\min \left\{t|\exists i\in \left\{1,\cdots ,M\right\},\rho \left(p_i\left(t\right),e_j\left(t\right)\right)=0\right\},$ (2)

其中 $\rho \left(p_i\left(t\right),e_j\left(t\right)\right)=\sqrt{{\left(x_j^e\left(t\right)-x_i^p\left(t\right)\right)}^2+{\left(y_j^e\left(t\right)-y_i^p\left(t\right)\right)}^2}$ 表示 $P_i$ 与 $E_j$ 在t时刻的距离。

所有逃避者均被捕获时博弈终止，终止时刻

$T=\max \left\{T_j\right\},j=1,\cdots ,N.$ (3)

定义 $\Gamma \left(M,N\right)$ 的值函数

$V=\underset{{\varphi }_i\left(t\right)}{\min }\underset{{\psi }_j\left(t\right)}{\max }{\displaystyle \underset{j=1}{\overset{N}{\sum }}{T}_j},i=1,2,\cdots ,M;j=1,2,\cdots ,N.$ (4)

对于较大的 $M,N$，直接求解(4)式得到追逃双方的最优策略在实际应用中是不可行的，本文通过如下步骤求解追逃双方的局部最优策略(Sub-optimal Strategy)：

步骤1 在 $\Gamma \left(M,N\right)\left(M\ge N>1\right)$ 中，为每个追逐者分配一个逃避者作为目标，将 $\Gamma \left(M,N\right)$ 划分为N个一追一或多追一子博弈。

步骤2 在 $\Gamma \left(M,1\right)\left(M>1\right)$ 中，考察追逐者知道逃避者的最优策略的情形，给出追逐者和逃避者的最优策略。

3. 多追一博弈

3.1. 追逃双方的最优控制求解

本节考察由M个追逐者和1个逃避者参与的博弈 $\Gamma \left(M,1\right)$。不失一般性，记逃避者为 $E_1$，距离最近的追逐者为 $P_I\left(I\in \left\{1,\cdots ,M\right\}\right)$，追逃双方从初始时刻开始，每经过一次时间步长为 $\Delta t$ 的迭代需要输入一次控制。由于 $v_p$， $v_e$ 是常量，求解最短捕获时间的控制等价于求解距离下降最快的控制。故逃避者 $E_1$ 的目的是在已知状态 $p_I=p_I\left(t\right)$， $p_i=p_i\left(t\right)\left(i=1,\cdots ,M,i\ne I\right)$， $e_1=e_1\left(t\right)$ 和步长 $\Delta t$ 情形下选择策略 ${\psi }_1={\psi }_1\left(t\right)$ 使得自身尽可能远离最近的追逐者，即逃避者 $E_1$ 的值函数可设为

$V_{e1}\left(p_I,e_1;{\psi }_1\right)=\underset{{\psi }_1}{\max }\rho \left(p_I,e_1\left(t+\Delta t\right)\right),$ (5)

其中

$\rho \left(p_I,e_1\left(t+\Delta t\right)\right)=\sqrt{{\left(x_1^e+\Delta t{v}_e\cos {\psi }_1-x_I^p\right)}^2+{\left(y_1^e+\Delta t{v}_e\sin {\psi }_1-y_I^p\right)}^2}.$

下面寻找使逃避者值函数最大化的策略，令 $\rho$ 对 ${\psi }_1$ 求偏导等于0，得

$\begin{array}{l}\frac{\partial \rho }{\partial {\psi }_1}=\frac{2\left(x_1^e+\Delta t{v}_e\cos {\psi }_1-x_I^p\right)\times \left(-\Delta t{v}_e\sin {\psi }_1\right)}{2\rho \left(p_I,e_1\left(t+\Delta t\right)\right)}\\ +\frac{2\left(y_1^e+\Delta t{v}_e\sin {\psi }_1-y_I^p\right)\times \Delta t{v}_e\cos {\psi }_1}{2\rho \left(p_I,e_1\left(t+\Delta t\right)\right)}=0,\end{array}$ (6)

即

$\frac{\sin {\psi }_1^{*}}{\cos {\psi }_1^{*}}=\frac{y_1^e-y_I^p}{x_1^e-x_I^p}.$ (7)

解上式可得

${\psi }_1^{*}=\text{arctan2}\frac{y_1^e-y_I^p}{x_1^e-x_I^p}.$ (8)

由(8)式可知，逃避者的最优策略跟自身位置 $e_1$ 及距其最近的追逐者的位置 $p_I$ 有关。

追逐者 $P_i\left(i=1,\cdots ,M\right)$ 的目的是在已知状态 $p_I=p_I\left(t\right)$， $p_i=p_i\left(t\right)\left(i=1,\cdots ,M,i\ne I\right)$， $e_1\left(t\right)$，步长 $\Delta t$ 和逃避者的最优策略 ${\psi }_1^{*}$ 的情形下选择策略 ${\varphi }_i$ 使自身尽可能接近逃避者 $E_1$，即追逐者 $P_i\left(i=1,\cdots ,M\right)$ 的值函数可设为

$V_{pi}\left(p_i,e_1;{\varphi }_i\right)=\underset{{\varphi }_i}{\min }\rho \left(p_i\left(t+\Delta t\right),e_1\left(t+\Delta t\right)\right),$ (9)

其中

$\rho \left(p_i\left(t+\Delta t\right),e_1\left(t+\Delta t\right)\right)=\sqrt{{\left(x_1^e+\Delta t{v}_e\cos {\psi }_1^{*}-x_I^p-\Delta t{v}_p\cos {\varphi }_i\right)}^2+{\left(y_1^e+\Delta t{v}_e\sin {\psi }_1^{*}-y_I^p-\Delta t{v}_p\sin {\varphi }_i\right)}^2}.$

寻找使追逐者值函数最小化的策略，令 $\rho$ 对 ${\varphi }_i$ 求偏导等于零，得

$\begin{array}{l}\frac{\partial \rho }{\partial {\varphi }_i}=\frac{2\left(x_1^e+\Delta t{v}_e\cos {\psi }_1^{*}-x_I^p-\Delta t{v}_p\cos {\varphi }_i\right)\times \Delta t{v}_p\sin {\varphi }_i}{2\rho \left(p_i\left(t+\Delta t\right),e_1\left(t+\Delta t\right)\right)}\\ +\frac{2\left(y_1^e+\Delta t{v}_e\sin {\psi }_1^{*}-y_I^p-\Delta t{v}_p\sin {\varphi }_i\right)\times \left(-\Delta t{v}_p\cos {\varphi }_i\right)}{2\rho \left(p_i\left(t+\Delta t\right),e_1\left(t+\Delta t\right)\right)}=0,\end{array}$ (10)

即

$\frac{\sin {\varphi }_i^{*}}{\cos {\varphi }_i^{*}}=\frac{y_1^e+v_e\sin {\psi }_1^{*}-y_I^p}{x_1^e+v_e\cos {\psi }_1^{*}-x_I^p}.$ (11)

解上式可得

${\varphi }_i^{*}=\arctan 2\frac{y_1^e+v_e\sin {\psi }_1^{*}-y_I^p}{x_1^e+v_e\cos {\psi }_1^{*}-x_I^p}.$ (12)

由(12)式可知，追逐者 $P_i$ 的最优策略跟自身位置 $p_i$ 及逃避者的位置 $e_1$ 和逃避者的最优策略 ${\psi }_1^{*}$ 有关。

3.2. 最优控制的几何解释

本节使用Apollonius圆 [14] 来描述(12)式。Apollonius圆是一组到两定点距离满足给定比值的点集。设追逐者 $P_i$ 和逃避者 $E_j$ 的位置为 $p_i\left(t\right)=\left(x_i^p\left(t\right),y_i^p\left(t\right)\right)$， $e_j\left(t\right)=\left(x_j^e\left(t\right),y_j^e\left(t\right)\right)$，记追逐者 $P_i$ 和逃避者 $E_j$ 对应的Apollonius圆为 $A_{ij}\left(t\right)$，圆心位于 $O_{ij}\left(t\right)=\left(\frac{x_j^e-{\alpha }^2{x}_i^p}{1-{\alpha }^2},\frac{y_j^e-{\alpha }^2{y}_i^p}{1-{\alpha }^2}\right)$，半径为 $r_{ij}\left(t\right)=\frac{\alpha }{1-{\alpha }^2}\rho \left(p_i,e_j\right)$。 $u\left(t\right)$ 是Apollonius圆 $A_{ij}\left(t\right)$ 上的某一点，常量 $\alpha =\frac{\rho \left(u,e_j\right)}{\rho \left(u,p_i\right)}=\frac{v_e}{v_p}<1$。假设 $E_j$ 在t时刻选择沿方向 ${\stackrel{\to }{\psi }}_1\left(t\right)$ 逃跑， $P_i$ 都有一个对应的方向 ${\stackrel{\to }{\varphi }}_i\left({\stackrel{\to }{\psi }}_1\left(t\right)\right)$ 保证其在Apollonius圆 $A_{ij}\left(t\right)$ 上的某一点 $p_i\left(T_{j_i}\right)$ 处捕获 $E_j$。

定义预计捕获时间 $T_{j_i}$ 为追逐者 $P_i$ 预计捕获逃避者 $E_j$ 的时刻，则有 $T_j=\min \left\{T_{j_i}\right\},i=1,\cdots ,M$。其中 $T_{j_i}$ 满足

$\rho \left(p_i\left(T_{j_i}\right),e_j\left(T_{j_i}\right)\right)=0,\frac{\rho \left(e_j\left(T_{j_i}\right),e_j\right)}{\rho \left(p_i\left(T_{j_i}\right),p_i\right)}=\frac{v_e}{v_p},$ (13)

可得

$T_{j_i}=\frac{\rho \left(p_i\left(T_{j_i}\right),p_i\right)}{v_p}.$ (14)

对于上式，可以通过联立Apollonius圆的方程与逃避者的速度方向所在直线方程，求得两个交点，

并选取使 $T_{j_i}$ 值较大的点作为 $p_i\left(T_{j_i}\right)$，进而可以求得 $T_{j_i}$ 的值。因此可以将追逐者 $P_i$ 的最优策略改写为

${\varphi }_i{}^{*}=\text{arctan}\frac{x_i^p\left(T_{j_i}\right)-x_i^p}{y_i^p\left(T_{j_i}\right)-y_i^p},i=1,\cdots ,M.$ (15)

至此本节完成 $\Gamma \left(M,1\right)$ 追逃双方最优策略的求解：考察由M个追逐者和1个逃避者参与的博弈 $\Gamma \left(M,1\right)$，给定任意 $t\in \left[t_0,T_1\right]$ 时刻所有局中人的位置，假设逃避者 $E_1$ 和追逐者 $P_i$ 的值函数分别为(5)和(9)式，则逃避者 $E_1$ 在t时刻的最优策略为(8)式，追逐者 $P_i$ 在t时刻的最优策略为(15)式。

图1直观地描述了博弈 $\Gamma \left(2,1\right)$，可以看出 $e_1\left(t_0\right)$， $p_1\left(T_{1_1}\right)$ 和 $p_2\left(T_{1_2}\right)$ 三点共线，由于 $p_2\left(T_{1_2}\right)$ 距离 $e_1\left(t_0\right)$ 更近，假设所有人均不改变速度方向，追逐者 $P_2$ 将在 $p_2\left(T_{1_2}\right)$ 处捕获逃避者，捕获时间为 $T_{1_2}$。

注1 需要特别说明的是，双方的最优策略是具有反馈性质的，当某个时刻距离最小的追逐者与上个时刻不同时，追逃双方通过重新计算(8)和(15)式动态更新最优策略。

注2 当某个t时刻有多个追逐者与逃避者 $E_1$ 的距离同为最小值时，值函数 $V_{e1}$ 不满足连续可微，故 $E_1$ 在t时刻选择随机方向前进。追逐者 $P_i\left(i=1,\cdots ,M\right)$ 在t时刻无法知道 $E_1$ 的最优策略，故 $P_i\left(i=1,\cdots ,M\right)$ 选择

${\varphi }_i^{*}=\arctan 2\frac{y_1^e-y_i^p}{x_1^e-x_i^p}.$ (16)

作为(15)式的替代。在t时刻双方都不是最优策略，但是当步长 $\Delta t\to 0$ 时，双方的策略对捕获时间 $T_1$ 的影响可以忽略。

注3 在逃避者 $E_1$ 选择最优策略的情形下，每个时刻只有距离最近的追逐者 $P_I$ 和预计捕获时间 $T_{j_i}$ 最短的追逐者 $P_i$ 会对捕获时间 $T_1$ 产生影响。

Figure 1. The optimal strategy of chasing and fleeing in game $\Gamma \left(2,1\right)$

图1. 博弈 $\Gamma \left(2,1\right)$ 中追逃双方的最优策略

4. 群体追逃博弈任务分配

本节考察由M个追逐者和N个逃避者参与的博弈 $\Gamma \left(M,N\right)\left(M\ge N>1\right)$，主要研究追逐者的任务分配问题。

4.1. 二分图的构建

构建 $\Gamma \left(M,N\right)$ 对应的二分图 [15] $G=\left(V,E,A\right)$，其中顶点集 $V=\left\{V_{p1},\cdots ,V_{pM},V_{e1},\cdots ,V_{eN}\right\}$ 表示M个追逐者和N个逃避者的顶点集合，它可以分为两个子集 $V_1=\left\{V_{p1},\cdots ,V_{pM}\right\}$ 和 $V_2=\left\{V_{e1},\cdots ,V_{eN}\right\}$，记顶点 $V_{pi}$ 与 $V_{ej}$ 之间有边 $E_{ij}$，故边集 $E=\left\{E_{ij}|i=1,\cdots ,M;j=1,\cdots ,N\right\}$，同时边 $E_{ij}$ 上有权值 $a_{ij}$，权矩阵 $A=\left\{a_{ij}|i=1,\cdots ,M;j=1,\cdots ,N\right\}$。

构建 $\Gamma \left(M,N\right)$ 对应的任务分配矩阵 ${\mu }^{M\times N}=\left\{{\mu }_{ij}|i=1,\cdots ,M;j=1,\cdots ,N\right\}$，如果将逃避者 $E_j$ 分配给追逐者 $P_i$，则 ${\mu }_{ij}=1$，否则 ${\mu }_{ij}=0$。这里规定一个追逐者只能选择一个逃避者作为目标，即

${\displaystyle \underset{j=1}{\overset{N}{\sum }}{\mu }_{ij}}\le 1,i=1,2,\cdots ,M.$

4.2. 基于扰动因素的冗余追逐者的任务分配策略

由注3得到，在逃避者选择最优策略的情形下， $\Gamma \left(M,1\right)\left(M>1\right)$ 中至多有 $M-1$ 个追逐者可以认为是冗余的，他们对捕获时间没有影响。

下面考察具有扰动因素的群体追逃博弈 $\tilde{\Gamma }\left(M,N\right)\left(M\ge N\right)$。假设每个追逐者在博弈开始后均有概率发生故障，导致其无法继续参与博弈。

任务分配 $K=\left(k_1,k_2,\cdots ,k_N\right)$ 是一个N维向量，其中 $k_j$ 表示分配给逃避者 $E_j$ 的追逐者的个数， $j=1,\cdots ,N$。分配给逃避者 $E_j$ 的追逐者发生故障的个数可以视为离散随机变量 $X_j$。假设 $X_j$ 服从参数为 $k_j$ 和 $\epsilon$ 的二项分布，记为 $X_j~B\left(k_j,\epsilon \right)$，其中 $\epsilon$ 为每个追逐者发生故障的概率。

定义事件Z：每个逃避者在博弈开始后至少分配到1个追逐者进行追逐，则

$P\left(Z\right)={\displaystyle \underset{j=1}{\overset{N}{\prod }}P\left(X_j\le k_j-1\right)}={\displaystyle \underset{j=1}{\overset{N}{\prod }}\left(1-{\epsilon }^{k_j}\right)}.$ (17)

下面寻找使事件Z发生概率最大的分配K，即求解非线性规划问题

$\begin{array}{l}\underset{k_j}{\max }P\left(Z\right),\\ \text{s}\text{.t}\text{.}{k}_1+k_2+\cdots +k_N=M,\\ k_j\ge 1,j=1,\cdots ,N.\end{array}$ (18)

由(17)式得

$\ln P\left(Z\right)={\displaystyle \underset{j=1}{\overset{N}{\sum }}\ln \left(1-{\epsilon }^{k_j}\right)}.$ (19)

设 $f\left(x\right)=1-{\epsilon }^x$，由 $f^{″}\left(x\right)<0$ 得 $f\left(x\right)$ 是上凸函数，可得 $\ln f\left(x\right)$ 也是上凸函数，那么有

$\frac{{\displaystyle \underset{j=1}{\overset{N}{\sum }}\ln f\left(k_j\right)}}{N}\le \ln f\left(\frac{{\displaystyle \underset{j=1}{\overset{N}{\sum }}{k}_j}}{N}\right)=\ln f\left(\frac{M}{N}\right)$ (20)

当且仅当 $k_1=k_2=\cdots =k_N=\frac{M}{N}$ 时等号成立，此时 $P\left(Z\right)$ 取最大值，因此在进行任务分配时应尽可能平均分配追逐者。

4.3. 基于二分图的任务分配

设追逐者 $P_i$ 预计捕获逃避者 $E_j$ 的时间为 $T_{j_i}$，给出任意时刻所有追逐者和逃避者的位置，求解所有 $T_{j_i}$，并作为权值记录到二分图G中。不断调用Kuhn-Munkres算法 [15]，从未分配的追逐者中选择预计捕获时间总和最小的N个追逐者分别分配给对应的逃避者，将已分配的追逐者和与之相关的边从二分图G中删去，直到任务分配结束为止。

本文建立BGBTA (Bipartite Graph Based Target Assignment)，尝试刻画整个追逃博弈及其相应的动态任务分配过程。

BGBTA

Input 追逐者与逃避者的数目 $M,N$，初始状态 $p_i\left(t_0\right),e_j\left(t_0\right),i=1,\cdots ,M;j=1,\cdots ,N$，迭代步长 $\Delta t$

Step 1 为每个逃避者 $E_j$ 计算最近的追逐者 $P_I^j$。

Step 2 根据初始状态计算所有预计捕获时间 $T_{j_i}$。

Step 3 构建二分图G。

Step 4 调用Kuhn-Munkres算法，从未分配追逐者集合中选出最多N个追逐者，为每个逃避者分配一个追逐者，将已分配的追逐者和与之相关的边从图上删去，更新二分图G，直到所有追逐者均已分配。

Step 5 每个逃避者选择(8)式作为策略，每个追逐者选择(15)式作为策略。直到某个时刻存在某个逃避者的最近的追逐者与上个时刻不同或博弈终止。

Step 6 如果博弈终止，则算法终止；否则转Step 1。

事实上，只需要将追逐者与逃避者的数目 $M,N$，初始状态 $p_i\left(t_0\right),e_j\left(t_0\right),i=1,\cdots ,M;j=1,\cdots ,N$，迭代步长 $\Delta t$ 输入BGBTA，它能将 $\Gamma \left(M,N\right)$ 按照逃避者划分为N个多追一子博弈，并使事件Z发生的概率最大。每个子博弈中追逃双方使用第3节给出的最优策略，进而得到一个MPNE问题的局部最优解，且最优策略在迭代过程中实现动态更新。

5. 数值算例

本节给出追逐者与逃避者数目分别为 $M=N$ 、 $N=2N$ 、 $M=5N$ 的数值算例，并考虑扰动因素。求解所有预计捕获时间 $T_{j_i}$，作为权值记录到二分图G。依次给出任务分配的二分图、任务分配矩阵、追逃双方的运动轨迹，计算全部逃避者被捕获的时间总和T。设追逐者速度为 $\alpha =1\text{m}/\text{s}$，逃避者速度为 $\beta =0.6\text{m}/\text{s}$，迭代步长 $\Delta t=0.1\text{s}$。

5.1. $M=N$ 情形

追逐者数量 $M=3$，逃避者数量 $N=3$。追逐者与逃避者的初始状态分别为

$\begin{array}{l}{p}_1\left(t_0\right)=\left(4,28\right),p_2\left(t_0\right)=\left(19,3\right),p_3\left(t_0\right)=\left(25,5\right),\\ e_1\left(t_0\right)=\left(22,1\right),e_2\left(t_0\right)=\left(9,2\right),e_3\left(t_0\right)=\left(3,25\right).\end{array}$

由BGBTA得到 $t_0$ 时刻追逐者任务分配的二分图及其相应的任务分配矩阵如图2所示，追逐者和逃避者的运动轨迹如图3所示。

${\mu }^{3\times 3}={\left(\begin{array}{ccc}0& 0& 1\\ 0& 1& 0\\ 1& 0& 0\end{array}\right)}^{\text{T}}$

Figure 2. Bipartite graph of task assignments of chasers in $\Gamma \left(3,3\right)$ and their task assignment matrix

图2. $\Gamma \left(3,3\right)$ 中追逐者任务分配的二分图及其任务分配矩阵

Figure 3. The trajectory of the chasing and fleeing parties in $\Gamma \left(3,3\right)$

图3. $\Gamma \left(3,3\right)$ 中追逃双方的运动轨迹

5.2. $M=2N$ 情形

追逐者数量 $M=6$，逃避者数量 $N=3$。追逐者与逃避者的初始状态分别为

$\begin{array}{l}{p}_1\left(t_0\right)=\left(4,28\right),p_2\left(t_0\right)=\left(19,3\right),p_3\left(t_0\right)=\left(25,5\right),\\ p_4\left(t_0\right)=\left(9,17\right),p_5\left(t_0\right)=\left(5,30\right),p_6\left(t_0\right)=\left(20,6\right),\\ e_1\left(t_0\right)=\left(22,1\right),e_2\left(t_0\right)=\left(9,2\right),e_3\left(t_0\right)=\left(3,25\right).\end{array}$

由BGBTA得到 $t_0$ 时刻追逐者任务分配的二分图及其相应的任务分配矩阵如图4所示，追逐者和逃避者的运动轨迹如图5所示。

${\mu }^{6\times 3}={\left(\begin{array}{cccccc}0& 0& 1& 0& 0& 1\\ 0& 1& 0& 1& 0& 0\\ 1& 0& 0& 0& 1& 0\end{array}\right)}^{\text{T}}$

Figure 4. Bipartite graph of task assignments of chasers in $\Gamma \left(6,3\right)$ and their task assignment matrix

图4. $\Gamma \left(6,3\right)$ 中追逐者任务分配的二分图及其任务分配矩阵

Figure 5. The trajectory of the chasing and fleeing parties in $\Gamma \left(6,3\right)$

图5. $\Gamma \left(6,3\right)$ 中追逃双方的运动轨迹

5.3. $M=5N$ 情形

追逐者数量 $M=15$，逃避者数量 $N=3$。追逐者与逃避者的初始状态分别为

$\begin{array}{l}{p}_1\left(t_0\right)=\left(25,28\right),p_2\left(t_0\right)=\left(4,28\right),p_3\left(t_0\right)=\left(19,3\right),\\ p_4\left(t_0\right)=\left(9,17\right),p_5\left(t_0\right)=\left(29,29\right),p_6\left(t_0\right)=\left(5,30\right),\\ p_7\left(t_0\right)=\left(29,15\right),p_8\left(t_0\right)=\left(25,5\right),p_9\left(t_0\right)=\left(13,28\right),\\ p_{10}\left(t_0\right)=\left(24,29\right),p_{11}\left(t_0\right)=\left(30,3\right),p_{12}\left(t_0\right)=\left(12,29\right),\\ p_{13}\left(t_0\right)=\left(21,23\right),p_{14}\left(t_0\right)=\left(23,12\right),p_{15}\left(t_0\right)=\left(20,6\right),\\ e_1\left(t_0\right)=\left(22,1\right),e_2\left(t_0\right)=\left(9,2\right),e_3\left(t_0\right)=\left(3,25\right).\end{array}$

由BGBTA得到 $t_0$ 时刻追逐者任务分配的二分图及其相应的任务分配矩阵如图6所示，追逐者和逃避者的运动轨迹如图7所示。

${\mu }^{15\times 3}={\left(\begin{array}{ccccccccccccccc}0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 1& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 1& 0\end{array}\right)}^{\text{T}}$

Figure 6. The bipartite graph of the task assignment of the chaser in $\Gamma \left(15,3\right)$ and its task assignment matrix

图6. $\Gamma \left(15,3\right)$ 中追逐者任务分配的二分图及其任务分配矩阵

Figure 7. The trajectory of the pursuit and escape in $\Gamma \left(15,3\right)$

图7. $\Gamma \left(15,3\right)$ 中追逃双方的运动轨迹

5.4. 加入扰动因素情形

下面考察具有扰动因素的群体追逃博弈，假设追逐者 $P_8$ 在3 s时发生故障，无法继续参与博弈。由BGBTA得到 $\tilde{\Gamma }\left(6,3\right)$ 与 $\tilde{\Gamma }\left(15,3\right)$ 追逐者和逃避者的运动轨迹分别如图8、图9所示。其中追逐者任务分配的二分图及其任务分配矩阵与不加入扰动因素时相同。

Figure 8. The trajectories of the chasing and fleeing parties in Game $\tilde{\Gamma }\left(6,3\right)$ with disturbance factors

图8. 具有扰动因素的博弈 $\tilde{\Gamma }\left(6,3\right)$ 中追逃双方运动轨迹

Figure 9. The trajectories of chasing and fleeing parties in Game $\tilde{\Gamma }\left(15,3\right)$ with disturbance factors

图9. 具有扰动因素的博弈 $\tilde{\Gamma }\left(15,3\right)$ 中追逃双方运动轨迹

5.5. 结果分析

表1给出五种情形下的捕获时间，表2给出五种情形下的任务分配。由表2， $\Gamma \left(15,3\right)$ 使用BGBTA时最先分配的3个追逐者与 $\Gamma \left(3,3\right)$ 相同， $\Gamma \left(15,3\right)$ 使用BGBTA时最先分配的6个追逐者与 $\Gamma \left(6,3\right)$ 相同。根据表1和表2，分配2个追逐者捕获 $E_1$ 的时间小于分配1个追逐者捕获 $E_1$ 的时间，而分配5个追逐者捕获 $E_1$ 的时间和分配2个追逐者相同，这说明 $P_8$ 和 $P_{15}$ 是积极的， $P_{11}$， $P_{13}$ 和 $P_{10}$ 是冗余的。

类似地，对于 $E_2$，分配2个追逐者捕获 $E_1$ 的时间小于分配1个追逐者捕获 $E_1$ 的时间，而分配5个追逐者捕获 $E_1$ 的时间和分配2个追逐者相同，这说明 $P_3$， $P_4$ 是积极的， $P_5$， $P_7$ 和 $P_1$ 是冗余的。对于 $E_3$，分配1个追逐者和5个追逐者捕获时间没有差别，这同样说明 $P_2$ 是积极的， $P_6$， $P_9$， $P_{12}$ 和 $P_{14}$ 是冗余的。综上，在 $\Gamma \left(15,3\right)$ 中15个追逐者只有 $P_2$， $P_3$， $P_4$， $P_8$ 和 $P_{15}$ 是积极的，其余10个追逐者是冗余的。

针对具有扰动因素的情形， $\tilde{\Gamma }\left(6,3\right)$ 中3s后由 $P_8$， $P_{15}$ 等2个追逐者追逐 $E_1$ 变为 $P_{15}$ 独自追逐，最后捕获 $E_1$ 的时间大于 $\Gamma \left(6,3\right)$，但小于 $\Gamma \left(3,3\right)$，这说明 $P_8$ 和 $P_{15}$ 是积极的。但是，在 $\tilde{\Gamma }\left(15,3\right)$ 中3 s后由 $P_8$， $P_{15}$ 等5个追逐者追逐 $E_1$ 变为 $P_{15}$ 等4个追逐者追逐，最后捕获 $E_1$ 的时间大于 $\Gamma \left(6,3\right)$，但小于 $\tilde{\Gamma }\left(6,3\right)$，这说明在 $\Gamma \left(15,3\right)$ 中冗余的 $P_{11}$ 在 $\tilde{\Gamma }\left(15,3\right)$ 中转化为了积极的追逐者。

Table 1. Capture time of the group pursuit-evasion game in five scenarios

表1. 五种情形下的群体追逃博弈的捕获时间

Table 2. Task assignment of the group pursuit-evasion game in five scenarios

表2. 五种情形下的群体追逃博弈的任务分配

6. 结论

本文的主要贡献是针对追逐者已知逃避者最优策略情形下的群体追逃博弈，在构建二分图的基础上，设计算法对追逐者进行任务分配，进而将群体追逃博弈转化成多个一追一或多追一子博弈。在多追一子博弈中借助Apollonius圆给出追逐者及逃避者在任意时刻的最优策略，进而得到群体追逃博弈的一个局部最优解。由数值算例分析可得，在群体追逃博弈 $\Gamma \left(M,N\right)$ 中，若博弈双方均采取最优策略，最多能有 $M-N$ 个追逐者可以视为冗余的。针对实际应用场景，考虑到追逐者可能发生机械故障等意外情况，为最小化这种情况产生的影响，本文为所有追逐者都分配了目标。本文所建立算法的优越性在于，在考虑扰动因素的情形下，原本冗余的追逐者有可能转化为积极的追逐者。

后续的研究工作包括以下几个方向：一是研究空间中具有障碍情形下的群体追逃博弈；二是研究追逐者和/或逃避者速度不一致情形下的群体追逃博弈；三是在高维空间中研究考察上述情形。