# Cooperative Evasion by Translating Targets with Variable Speeds

Shivam Bajaj  Eloy Garcia  Shaunak D. Bopardikar Shivam Bajaj and Shaunak D.
Bopardikar are with the Department of Electrical and Computer Engineering,
Michigan State University. email<EMAIL_ADDRESS><EMAIL_ADDRESS>Eloy
Garcia is with the Wright-Patterson Air Force Research Laboratory, Dayton OH.
email<EMAIL_ADDRESS>
###### Abstract

We consider a problem of cooperative evasion between a single pursuer and
multiple evaders in which the evaders are constrained to move in the positive
$Y$ direction. The evaders are slower than the vehicle and can choose their
speeds from a bounded interval. The pursuer aims to intercept all evaders in a
given sequence by executing a Manhattan pursuit strategy of moving parallel to
the $X$ axis, followed by moving parallel to the $Y$ axis. The aim of the
evaders is to cooperatively pick their individual speeds so that the total
time to intercept all evaders is maximized. We first obtain conditions under
which evaders should cooperate in order to maximize the total time to
intercept as opposed to each moving greedily to optimize its own intercept
time. Then, we propose and analyze an algorithm that assigns evasive
strategies to the evaders in two iterations as opposed to performing an
exponential search over the choice of evader speeds. We also characterize a
fundamental limit on the total time taken by the pursuer to capture all
evaders when the number of evaders is large. Finally, we provide numerical
comparisons against random sampling heuristics.

##  I Introduction

We consider a single pursuer multi-evader pursuit evasion problem in which the
aim of the pursuer is to intercept all of the evaders in a fixed given
sequence. The evaders are constrained to move along the positive $Y$
direction. The pursuer follows the Manhattan distance, i.e., moving parallel
to the $X$-axis followed by moving parallel to the $Y$-axis. The aim of the
evaders is to cooperatively maximize the total time to intercept all evaders.
Such a set-up arises in riot control or border protection scenarios in which a
ground or air vehicle would like to optimally visit mobile locations headed
toward a boundary/asset, or in UAV monitoring of vehicles along a highway.
This setup is also applicable in multiple robotic decoy deployment [1].

###  I-A Related work

Since the seminal work by Isaacs in [2], much has been done in the field of
pursuit evasion with a lot of focus on multi-agent pursuit evasion [3, 4, 5].
The case of a single pursuer and 2 evaders has been extensively analyzed [6],
[7]. Protector-Prey-Predator [8] and Target-Attacker-Defender differential
game [9] are some examples of this scenario. With more than two evaders, the
complexity of the problem grows exponentially with number of evaders. The
problem of successive pursuit with cooperative multiple evaders is considered
in [10, 11, 12] and [13]. Our problem differs as the evaders are constrained
to move in a fixed direction and can choose their individual speeds from a
bounded interval to maximize the total intercept time. Thus, the evasive
strategies are based on the range of evader speeds.

###  I-B Contributions

We consider an optimal evasion problem between a single pursuer and $n$
evaders. The pursuer moves with unit speed. The evaders are constrained to
move in the positive $Y$ direction such that their speeds
$v_{i},i\in\\{1,\dots,n\\}$, lie in the interval
$[{u}_{\textup{min}},{u}_{\textup{max}}]$ with
$0<{u}_{\textup{min}}<{u}_{\textup{max}}<1$. The evaders need to choose their
speeds in order to maximize the total intercept time. We first present a
complete solution to the optimal evasion problem for $n\leq 2$. We then show,
for general $n$, that the optimal choice of the speed for each evader is one
of the extremes, i.e., ${u}_{\textup{min}}$ or ${u}_{\textup{max}}$. We
further show that, by enforcing cooperation among evaders, they are able to
maximize the total intercept time. In order to implement the cooperative
strategies, it is important to determine the conditions under which
cooperation is optimal. Such conditions are also provided in this paper. We
present an algorithm which assigns the evasive strategies to the evaders in
two iterations as opposed to performing an exponential search over the choice
of evader speeds. For sufficiently large $n$, for which the global optimum is
difficult to compute, we establish a fundamental upper bound to the total
intercept time taken by the pursuer to capture all evaders. Finally, we
provide comparisons through numerical results.

###  I-C Organization

The paper is organized as follows. Section II comprises the formal problem
definition. In section III, we derive an evasive strategy for multiple evaders
and provide a Sequential-Greedy-Cooperation algorithm. Section IV establishes
a fundamental upper bound on the total time to intercept all evaders. Section
V presents the numerical simulations. Finally, section VI summarizes this
paper and outlines directions for future work.

##  II Problem formulation

We consider an optimal evasion problem played between a single pursuer with
simple motion and $n$ mobile evaders. We denote the pursuer as $P$ and evaders
as $E_{i}$ with $i\in\\{1,\dots,n\\}$. The pursuer with initial location at
$(X,Y)$ is assumed to be moving with unit speed either along the $X$ or the
$Y$ axis. We term this pursuit strategy as _Manhattan pursuit_ , and is
formally defined as follows.

######  Definition 1 (Simple Manhattan pursuit)

Given initial locations $(x_{i},y_{i})$ and $(X,Y)$ of an evader $E_{i}$ and
the pursuer $P$ respectively, the pursuer

  1. 1.

moves with unit speed along the positive or negative $X$ direction until
$X(t)=x_{i}$ and then,

  2. 2.

moves with unit speed along positive or negative $Y$ axis to intercept the
evader.

The evaders, initially located at $\\{(x_{1},y_{1}),\dots,(x_{n},y_{n})\\}$,
are constrained to move along the positive $Y$ direction with simple motion
such that their instantaneous speeds $v_{i}$, $i\in\\{1,\dots,n\\}$, lie in
the interval $[{u}_{\textup{min}},{u}_{\textup{max}}]$ with
$0<{u}_{\textup{min}}<{u}_{\textup{max}}<1$ (Fig. 1). The pursuer is said to
intercept the $i^{th}$ target when its location coincides with that of the
$i^{th}$ target. The game terminates when the pursuer intercepts the last
evader. A _strategy_ for an evader $E_{i}$ is a measurable function, defined
as
$v_{i}(\\{X(t),Y(t)\\},\\{x_{i}(t),y_{i}(t)\\}_{i=1}^{n})\to[{u}_{\textup{min}},{u}_{\textup{max}}]$,
where the notation $\\{X(t),Y(t)\\}$ denotes the set of all locations
$(X(\tau),Y(\tau)),\forall\tau\in[0,t]$.

Figure 1: Problem setup. The triangle represents the pursuer and the blue dots
represent the evaders. The red dashed line represents the path taken by the
pursuer to intercept the evaders. The cross represents the intercept
locations.

The goal is to solve the following problem.

######  Problem II.1 (Optimal evasion)

Given that the pursuer follows a fixed order to intercept the evaders,
determine strategies $v_{1}^{*},v_{2}^{*},\dots,v_{n}^{*}$ for the evaders
that maximizes the total time $T_{n}$ taken by the pursuer to intercept all
$n$ evaders.

##  III Evasive Strategy

We begin with the case of a single evader followed by two evaders, and then
present the more general case. We start by defining the following simple
Manhattan pursuit strategy.

###  III-A Single Evader

In this section, we first consider the case of a single evader and a pursuer,
located at $(x_{1},y_{1})$ and $(X,Y)$ respectively. We first present a result
on the time taken to intercept a single evader. This will be used in deriving
the optimal strategy for the evader. We denote $\Delta
x_{i}^{i-1}:=|{x_{i-1}-x_{i}}|$, where $x_{0}=X$ and $T_{i}^{i-1}(v_{i})$ as
the time taken by the pursuer to intercept evader $i$ moving with speed
$v_{i}$ after intercepting evader $i-1$. Specifically, $T_{1}^{0}(v)$ is the
time taken to intercept the first evader moving with speed $v$. For brevity,
we omit the proofs for the single evader case as they can be derived by
following the steps in the proof of the general case presented later.

######  Lemma III.1 (Time to intercept a single evader)

The time $T_{1}^{0}$ taken by $P$ to intercept $E_{1}$ is

$\displaystyle T_{1}^{0}(v)=\begin{cases}\frac{\Delta
x_{1}^{0}+y_{1}-Y}{1-v},\text{ if }\Delta x_{1}^{0}>(Y-y_{1})/v,\\\
\frac{\Delta x_{1}^{0}+Y-y_{1}}{1+v},\text{ otherwise.}\end{cases}$

######  Lemma III.2 (Monotonicity of time to intercept)

The time $T_{1}^{0}(v)$ is a monotonically increasing function of $v$ if
$\Delta x^{0}_{1}>\frac{Y-y_{1}}{v}$. Otherwise, $T_{1}^{0}(v)$ is a
monotonically decreasing function of $v$.

###### Remark 1

The time to intercept is monotonic even when the pursuer follows a Euclidean
strategy, i.e., given the initial locations of $E_{1}$ and $P$, as
$(x_{1},y_{1})$ and $(X,Y)$ respectively, the vehicle moves towards
$(x_{1},y_{1}+vT_{1}^{0})$, where $T_{1}^{0}$ is

$\displaystyle\frac{(y_{1}-Y)v}{1-v^{2}}+\sqrt{\frac{(X-x_{1})^{2}}{1-v^{2}}+\frac{(Y-y_{1})^{2}}{(1-v^{2})^{2}}}.$

Lemma III.2 characterizes the monotonic nature of $T_{1}^{0}(v)$. This only
means that the maximum is achieved at one of the extremes. The next theorem
characterizes the evader’s optimal choice of speed.

######  Theorem III.3 (Single evader optimal strategy)

Given the initial locations $(x_{1},y_{1})$ and $(X,Y)$ of the evader and the
pursuer respectively, the optimal strategy $v^{*}$ for the evader is

$\displaystyle v^{*}=\begin{cases}{u}_{\textup{min}},\text{ if }y_{1}<Y-\Delta
x_{1}^{0}(\frac{{u}_{\textup{min}}+{u}_{\textup{max}}}{2+{u}_{\textup{min}}-{u}_{\textup{max}}})\\\
{u}_{\textup{max}},\text{ otherwise. }\end{cases}$

###### Proof.

We provide only an outline. We find a location $(x_{1},y^{\prime})$ such that
$T_{1}^{0}({u}_{\textup{min}})=T_{1}^{0}({u}_{\textup{max}})$, where
$T_{1}^{0}({u}_{\textup{min}})$ (resp. $T_{1}^{0}({u}_{\textup{max}})$) is the
time to intercept when evader moves with ${u}_{\textup{min}}$ (resp.
${u}_{\textup{max}}$). From Lemma III.1,
$T_{1}^{0}({u}_{\textup{min}})=T_{1}^{0}({u}_{\textup{max}})\Rightarrow
y^{\prime}=Y-\Delta
x_{1}^{0}\big{(}\frac{{u}_{\textup{min}}+{u}_{\textup{max}}}{2+{u}_{\textup{min}}-{u}_{\textup{max}}}\big{)}$.
This means that if $y_{1}=y^{\prime}$, then from Lemma III.2, it would not
matter if the evader moves with ${u}_{\textup{min}}$ or ${u}_{\textup{min}}$
as $T_{1}^{0}({u}_{\textup{min}})=T_{1}^{0}({u}_{\textup{max}})$, and
$T_{1}^{0}$ will be maximum at both ${u}_{\textup{min}}$ and
${u}_{\textup{max}}$. If $y_{1}<y^{\prime}$, then, from Lemma III.2, either
$T_{1}^{0}({u}_{\textup{min}})<T_{1}^{0}({u}_{\textup{max}})$ or
$T_{1}^{0}({u}_{\textup{min}})>T_{1}^{0}({u}_{\textup{max}})$. Assuming
$T_{1}^{0}({u}_{\textup{min}})<T_{1}^{0}({u}_{\textup{max}})\Rightarrow
y_{1}>y^{\prime}$ and thus, by contradiction, we get the result. The second
case is analogous and we get the result. ∎

We now consider the case of two evaders and derive the optimal evasion
strategies for both evaders. We say that an evader $E_{i}$ moves _greedy_ if
it moves with speed that maximizes its own intercept time. An evader
_cooperates_ if it moves with a speed that maximizes the total intercept time.
We denote the greedy strategy of evader $i$ as $v_{i_{g}}^{*}$ and the
cooperative strategy as $v_{i_{c}}^{*}$.

###  III-B Two evaders

Similar to previous section, we first derive an expression for the time taken
to intercept the evaders followed by the optimal strategy for both evaders.

Let the first evader $E_{1}$ be located at $(x_{1},y_{1})$ and move with speed
$v_{1}$ and the second evader $E_{2}$ be located at $(x_{2},y_{2})$ and move
with speed $v_{2}$. Then, the following result summarizes the time to
intercept $E_{2}$ after intercepting $E_{1}$. For ease of reference, we
introduce the following condition:

$\Delta x_{2}^{1}>\frac{y_{1}-y_{2}+(v_{1}-v_{2})T_{1}^{0}(v_{1})}{v_{2}}.$
(1)

######  Lemma III.4 (Time to intercept $E_{2}$)

The time $T_{2}^{1}(v_{1},v_{2})$ taken by $P$ to intercept $E_{2}$ after
intercepting $E_{1}$ is

$\displaystyle T_{2}^{1}(v_{1},v_{2})=\begin{cases}\frac{\Delta
x_{2}^{1}+y_{2}-y_{1}+(v_{2}-v_{1})T_{1}^{0}(v_{1})}{1-v_{2}},\text{ if
\eqref{eq:2evader-condition} holds,}\\\ \frac{\Delta
x_{2}^{1}+y_{1}-y_{2}+(v_{1}-v_{2})T_{1}^{0}(v_{1})}{1+v_{2}},\text{
otherwise.}\end{cases}$

###### Proof.

Consider the case when condition (1) holds, after the intercept of $E_{1}$.
This means that after the completion of stage (1) for the pursuit of $E_{2}$,
the evader’s $Y$-coordinate strictly exceeds $Y=y_{1}+v_{1}T_{1}^{0}(v_{1})$.
The additional time to intercept the second evader is

$\frac{y_{2}+v_{2}T_{1}^{0}(v_{1})-y_{1}-v_{1}T_{1}^{0}(v_{1})+v_{2}\Delta
x_{2}^{1}}{1-v_{2}}.$

Thus, total time to intercept $E_{2}$ after intercepting $E_{1}$ is

$\displaystyle T_{2}^{1}(v_{1},v_{2})=\frac{\Delta
x_{2}^{1}+y_{2}-y_{1}+(v_{2}-v_{1})T_{1}^{0}(v_{1})}{1-v_{2}}.$

The second case can be derived analogously and this concludes the proof. ∎

######  Lemma III.5 (Monotonicity of time to intercept $E_{2}$)

Given that $E_{1}$ moves with $v_{1}$, the time $T_{2}^{1}(v_{1},v_{2})$ is
monotonically increasing function of $v_{2}$ if condition (1) holds.
Otherwise, $T_{2}^{1}(v_{1},v_{2})$ is a monotonically decreasing function of
$v_{2}$.

###### Proof.

From Lemma III.4, $\frac{dT_{2}^{1}(v_{1},v_{2})}{dv_{2}}>0$ if condition (1)
holds and $\frac{dT_{2}^{1}(v_{1},v_{2})}{dv_{2}}<0$, otherwise. ∎

We now characterize an optimal greedy strategy for $E_{2}$. In what follows,
we denote
$V:=\frac{{u}_{\textup{min}}+{u}_{\textup{max}}}{2+{u}_{\textup{min}}-{u}_{\textup{max}}}$.

######  Lemma III.6 ($E_{2}$’s greedy strategy)

The greedy strategy $v_{2g}^{*}$ for $E_{2}$ for a greedy $E_{1}$ moving with
$v_{1g}^{*}$ is

$\displaystyle v_{2g}^{*}=\begin{cases}{u}_{\textup{max}},\text{ if }y_{2}\geq
y_{1}-\Delta x_{2}^{1}V+(v_{1g}^{*}-V)T_{1}^{0}(v_{1g}^{*}),\\\
{u}_{\textup{min}},\text{ otherwise.}\end{cases}$

###### Proof.

From Lemma III.5, $T_{2}^{1}(v_{1g}^{*},v_{2})$ is maximized at either
$v_{2}={u}_{\textup{min}}$ or $v_{2}={u}_{\textup{max}}$. The aim is to find
the critical location $y_{2}^{\prime}$ such that if $E_{2}$ was located at
$(x_{2},y_{2}^{\prime})$, then the time
$T_{2}^{1}(v_{1g}^{*},{u}_{\textup{max}})$=
$T_{2}^{1}(v_{1g}^{*},{u}_{\textup{min}})$. Note that this is possible only if
condition (1) holds for $v_{2}={u}_{\textup{max}}$ and does not hold for
$v_{2}={u}_{\textup{min}}$. From Lemma III.4, we get
$y_{2}^{\prime}=y_{1}-\Delta x_{2}^{1}V+(v_{1g}^{*}-V)T_{1}^{0}(v_{1g}^{*})$.
This means that if $y_{2}=y_{2}^{\prime}$, then irrespective of $E_{2}$’s
choice of ${u}_{\textup{min}}$ or ${u}_{\textup{max}}$, the time to intercept
$E_{2}$ will be the same and from Lemma III.5, the time to intercept $E_{2}$
will be maximum at both ${u}_{\textup{min}}$ and ${u}_{\textup{max}}$, given
that $E_{1}$ moves greedy. Now, consider that the initial location of $E_{2}$
is such that $y_{2}<y_{2}^{\prime}$. From Lemma III.5, the time to intercept
will be maximized only at either ${u}_{\textup{min}}$ or ${u}_{\textup{max}}$
and so assume that $T_{2}^{1}$ is maximized at ${u}_{\textup{max}}$, i.e.,
$T_{2}^{1}(v_{1g}^{*},{u}_{\textup{max}})>T_{2}^{1}(v_{1g}^{*},{u}_{\textup{min}})$.
This implies $y_{2}>y_{2}^{\prime}$. This is a contradiction as
$y_{2}<y_{2}^{\prime}$. This means that $T_{2}^{1}$ will be maximized if
$E_{2}$ moves at ${u}_{\textup{min}}$. Similarly, when $y_{2}\geq
y_{2}^{\prime}$ it can be shown that $T_{2}^{1}$ will be maximized if $E_{2}$
moves at ${u}_{\textup{max}}$ and has been omitted for brevity. In the case
when condition (1) does not hold for $v_{2}={u}_{\textup{max}}$ or holds for
$v_{2}={u}_{\textup{min}}$, then it implies that $y_{2}<y_{2}^{\prime}$ and
$y_{2}\geq y_{2}^{\prime}$ respectively. This concludes the proof. ∎

Lemma III.6 yields a _greedy_ strategy for $E_{2}$ when $E_{1}$ and $E_{2}$
both move greedily. However, it might be better for the evaders to cooperate
to maximize the total intercept time. We now characterize the conditions on
cooperation between the two evaders.

Figure 2: Cases for cooperation. (a) The time (solid line) taken by the
pursuer to intercept $E_{2}$ directly from $(X,Y)$ and time (dashed line)
taken by the pursuer to intercept $E_{1}$ first then $E_{2}$ are the same. (b)
$E_{1}$ and $E_{2}$ cooperate by moving at ${u}_{\textup{min}}$ and
${u}_{\textup{max}}$ respectively (c) $E_{1}$ and $E_{2}$ cooperate by moving
at ${u}_{\textup{max}}$ and ${u}_{\textup{min}}$ respectively.

We define that a point $A$, located at $(x_{A},y_{A})$, is _above_ point $B$,
located at $(x_{B},y_{B})$, if $y_{A}>y_{B}$ and we define point $A$ is
_below_ point $B$ if $y_{A}<y_{B}$.

######  Lemma III.7 (Conditions on cooperation)

Given the initial locations of $E_{1}$, $E_{2}$, and $P$ as $(x_{1},y_{1})$,
$(x_{2},y_{2})$, and $(X,Y)$ respectively, $E_{1}$ cooperates with $E_{2}$ if

(i) Case 1:

$\displaystyle Y-\Delta x_{1}^{0}V\leq y_{1}\leq Y-\Delta
x_{1}^{0}{u}_{\textup{min}},\text{ and}$ $\begin{split}&y_{2}>y_{1}-\Delta
x_{2}^{1}V+\big{(}v_{1g}^{*}-V)T_{1}^{0}(v_{1g}^{*})+\\\
&2\big{(}\frac{{u}_{\textup{min}}\Delta
x_{1}^{0}+y_{1}-Y}{2+{u}_{\textup{min}}-{u}_{\textup{max}}}\big{)},\end{split}$
(2)

(ii) Case 2:

$\displaystyle Y-\Delta x_{1}^{0}{u}_{\textup{max}}\leq y_{1}\leq Y-\Delta
x_{1}^{0}V,\text{ and}$ $\begin{split}&y_{2}\leq y_{1}-\Delta
x_{2}^{1}V+(v_{1g}^{*}-V)T_{1}^{0}(v_{1g}^{*})+\\\
&2\big{(}\frac{{u}_{\textup{max}}\Delta
x_{1}^{0}+y_{1}-Y}{2+{u}_{\textup{min}}-{u}_{\textup{max}}}\big{)}.\end{split}$
(3)

###### Proof.

Let the initial location of $E_{1}$ satisfy $y_{1}\geq Y-\Delta x_{1}^{0}V$
and initial location of $E_{2}$ satisfy $y_{2}\geq y_{1}-\Delta
x_{2}^{1}V+(v_{1g}^{*}-V)T_{1}^{0}(v_{1g}^{*})$. Then, from Theorem III.3, to
maximize its own intercept time, $T_{1}^{0}(v_{1g}^{*})$, $E_{1}$ moves with
${u}_{\textup{max}}$. Also, from Lemma III.6, $E_{2}$ moves with
${u}_{\textup{max}}$ in order to maximize its own intercept time
$T_{2}^{1}(v_{1g}^{*},v_{2})$. As the pursuer follows the Manhattan pursuit
strategy, the time taken to cover the path in the y-direction to intercept
$E_{1}$ and then $E_{2}$ is the same as the time taken to cover the path in
y-direction to intercept only $E_{2}$ from the initial pursuer location
$(X,Y)$ (see Fig.2 (a)). Mathematically,

$\displaystyle
T_{1}^{0}({u}_{\textup{max}})+T_{2}^{1}({u}_{\textup{max}},{u}_{\textup{max}})=\frac{\Delta
x_{1}^{0}+\Delta x_{2}^{1}+y_{2}-Y}{1-{u}_{\textup{max}}}.$

Thus, in order to increase the total time to intercept, $E_{1}$ and $E_{2}$
need to cooperate. One way to cooperate is that $E_{1}$ moves with a speed
$v_{1}$ such that $E_{1}$ is intercepted below the pursuer, i.e., $\Delta
x_{1}^{0}<(Y-y_{1})/v_{1}$ and $E_{2}$ moves greedily, i.e., with
${u}_{\textup{max}}$ (see Fig 2 (b)). This is only possible if

$\displaystyle\Delta x_{1}^{0}<(Y-y_{1})/{u}_{\textup{min}}$
$\displaystyle\Rightarrow y_{1}<Y-\Delta x_{1}^{0}{u}_{\textup{min}}.$

If $y_{1}>Y-\Delta x_{1}^{0}{u}_{\textup{min}}$, then for any speed
$v_{1}\in[{u}_{\textup{min}},{u}_{\textup{max}}]$ for $E_{1}$, $\Delta
x_{1}^{0}>(Y-y_{1})/v_{1}$, and so the total distance covered in the
y-direction to intercept $E_{1}$ and $E_{2}$ will be the same as the total
distance covered in the y-direction to intercept $E_{2}$, from the pursuer’s
initial location $(X,Y)$, irrespective of $E_{1}$’s choice. The only other way
in which $E_{1}$ and $E_{2}$ can cooperate in order to increase the total
intercept time is when $E_{1}$ moves greedily, i.e., with ${u}_{\textup{max}}$
and $E_{2}$ with speed $v_{2}$ such that $y_{2}<y_{1}-\Delta
x_{2}^{1}v_{2}+(v_{1g}^{*}-v_{2})T_{1}^{0}(v_{1g}^{*})$ such that intercept of
$E_{2}$ is below the intercept location of $E_{1}$ (see Fig. 2 (c)). Thus, to
determine which of the two scenarios yield the greater time to intercept, we
arrive at a condition
$T_{1}^{0}({u}_{\textup{min}})+T_{2}^{1}({u}_{\textup{min}},{u}_{\textup{max}})>T_{1}^{0}({u}_{\textup{max}})+T_{2}^{1}({u}_{\textup{max}},{u}_{\textup{min}})$.

$\frac{\Delta
x_{2}^{1}+y_{2}-y_{1}+(1-{u}_{\textup{min}})T_{1}^{0}({u}_{\textup{min}})}{1-{u}_{\textup{max}}}>\\\
\frac{\Delta
x_{2}^{1}+y_{1}-y_{2}+(1+{u}_{\textup{max}})T_{1}^{0}({u}_{\textup{max}})}{1+{u}_{\textup{min}}}\\\
\Rightarrow y_{2}>y_{1}-\Delta
x_{2}^{1}V+(v_{1g}^{*}-V)T_{1}^{0}(v_{1g}^{*})+\\\
\frac{2({u}_{\textup{min}}\Delta
x_{1}^{0}+y_{1}-Y)}{2+{u}_{\textup{min}}-{u}_{\textup{max}}}.$

Note that as $T_{1}^{0}(v_{1})$ and $T_{2}^{1}(v_{1},v_{2})$ are monotonic in
$v_{1}$ and $v_{2}$ respectively, so the above condition is checked only at
the extreme values, i.e., ${u}_{\textup{min}}$ and ${u}_{\textup{max}}$. Thus,
this means that $E_{1}$ should cooperate only if equation (2) holds.
Furthermore, if the initial location of $E_{1}$ was such that $y_{1}\leq
Y-\Delta x_{1}^{0}V$, then from Lemma III.3, $E_{1}$ moves greedily, i.e.,
with speed ${u}_{\textup{min}}$. Since, this will already ensure that $\Delta
x_{1}^{0}<(Y-y_{1})/{u}_{\textup{min}}$ and so, there is no need for
cooperation. Case 2 is analogous. This concludes our proof. ∎

######  Theorem III.8 (Optimal cooperative strategy for $E_{1}$)

Given the initial locations $(x_{1},y_{1})$, $(x_{2},y_{2})$, and $(X,Y)$ of
$E_{1}$, $E_{2}$ and $P$, respectively, if the conditions for cooperation in
Lemma III.7 hold, then the optimal cooperative strategy $v_{1c}^{*}$ for
evader $E_{1}$ is

$v_{1c}^{*}=\begin{cases}{u}_{\textup{min}},\text{ for case 1 from Lemma
\ref{lem:coop_2E_MD} or,}\\\ {u}_{\textup{max}},\text{ for case 2 from Lemma
\ref{lem:coop_2E_MD}.}\end{cases}$

###### Proof.

Consider that case 1 of Lemma III.7 holds. Then $E_{1}$ moves with speed
$v_{1}$ such that $\Delta x_{1}^{0}<(Y-y_{1})/v_{1}$. We know from Lemma III.7
that the conditions on cooperation ensure that the total time to intercept
during cooperation is higher than the greedy choice. Since $T_{1}^{0}(v_{1})$
is monotonic in $v_{1}$, from Lemma III.2, $v_{1c}^{*}={u}_{\textup{min}}$.
The second case is derived analogously. This concludes the proof. ∎

In this subsection, we analyzed the case of 2 evaders, primarily to highlight
the underlying problem structure. Next, we will consider the case of $n$
evaders. Similar to the two evader case, we will first present a result on the
time taken to intercept the $k^{th}$ evader after intercepting the $k-1^{th}$
evader. Then we will present results on the greedy and cooperative strategies
between $E_{k}$ and $E_{k-1}$.

###  III-C $n$ Evaders

For ease of presentation, we will denote $(y_{i}-y_{j})$ as $\Delta y_{j}^{i}$
for some $i,j$ and for brevity, we denote $T_{i}^{i-1}(v_{1},\dots,v_{i})$ as
$T_{i}^{i-1}(v_{-i},v_{i})$. We present the following condition for ease of
reference.

$\Delta x_{k}^{k-1}>\frac{\Delta
y_{k}^{k-1}+(v_{k-1}-v_{k})\sum_{i=1}^{k-1}T_{i}^{i-1}}{v_{k}}.$ (4)

######  Lemma III.9 (Time to intercept $E_{k}$)

The time $T_{k}^{k-1}(v_{-k},v_{k})$ taken by $P$ to intercept $E_{k}$, moving
with $v_{k}$, after intercepting $E_{k-1}$, moving with $v_{k-1}$, is

$\displaystyle T_{k}^{k-1}=\begin{cases}\frac{\Delta x_{k}^{k-1}+\Delta
y_{k-1}^{k}+(v_{k}-v_{k-1})\sum_{i=1}^{k-1}T_{i}^{i-1}}{1-v_{k}},\text{ if
\eqref{eq:greed_n} holds,}\\\ \frac{\Delta x_{k}^{k-1}+\Delta
y_{k}^{k-1}+(v_{k-1}-v_{k})\sum_{i=1}^{k-1}T_{i}^{i-1}}{1+v_{k}},\text{otherwise.}\end{cases}$

###### Proof.

We establish this result using mathematical induction. Lemma III.4 yields the
base of induction for $k=2$. Assume that for some $k=\bar{k}$, the result
holds. Consider that the initial location of the next evader, $E_{\bar{k}+1}$,
is such that $\Delta
x_{\bar{k}+1}^{\bar{k}}>(y_{\bar{k}}-y_{\bar{k}+1}+(v_{\bar{k}}-v_{\bar{k}+1})\sum_{i=1}^{\bar{k}}T_{i}^{i-1})/v_{\bar{k}+1}$.
This means that after the completion of stage (1) of simple pursuit of
$E_{\bar{k}+1}$, the X-coordinate of the pursuer equals $x_{\bar{k}+1}$ and at
the same time, the evader’s y-coordinate strictly exceeds the pursuers
y-coordinate $(=y_{\bar{k}}+v_{\bar{k}}\sum_{i=1}^{\bar{k}}T_{i}^{i-1})$.
Thus, the time to intercept $E_{\bar{k}+1}$ after intercepting $E_{\bar{k}}$
will be

$\displaystyle\frac{\Delta
x_{\bar{k}+1}^{\bar{k}}+y_{\bar{k}+1}-y_{\bar{k}}+(v_{\bar{k}+1}-v_{\bar{k}})\sum_{i=1}^{\bar{k}}T_{i}^{i-1}}{1-v_{\bar{k}+1}}.$

Thus, by induction the result holds for any value of $\bar{k}$. The other case
is derived analogously. ∎

######  Lemma III.10 (Monotonicity of time to intercept)

Given that each $E_{i}$, $i\in{1,\dots,k-1}$ moves with $v_{i}$, the time
$T_{k}^{k-1}$ is monotonically increasing function of $v_{k}$ if condition (4)
holds. Otherwise, $T_{k}^{k-1}$ is a monotonically decreasing function of
$v_{2}$.

###### Proof.

We only provide an outline. We use induction to establish the result. Lemma
III.5 yields the base of the induction. Assuming that the result holds for
some $k=\bar{k}$, it can be checked that
$\frac{dT_{\bar{k}+1}^{\bar{k}}}{dv_{k}}>0$ if condition (4) holds. Otherwise,
$\frac{dT_{\bar{k}+1}^{\bar{k}}}{dv_{k}}<0$. This concludes the proof. ∎

Since Lemma III.10 establishes that the time to intercept a $k^{th}$ evader is
maximized at either ${u}_{\textup{min}}$ or ${u}_{\textup{max}}$, finding an
optimal strategy for all evaders would require analyzing all $2^{n}$
possibilities in the worst case.

We now present an algorithm that assigns respective strategies to the evaders
in just two iterations. The algorithm, summarized in Algorithm 1, first
assigns the greedy strategies to all evaders. Then, it assigns cooperative
strategies by considering two sequentially paired evaders at a time.
Now, we will present the results that the algorithm uses in assigning the
strategies.

1 Assign greedy speeds to all evaders

2 if  _$E_{i}$ and $E_{i+1}$ can cooperate, $\forall\text{ }1<i<n$,_ then

3 Assign optimal cooperative strategy

4else

5 Assign optimal greedy strategy.

6

7 end if

8Repeat from step 2.

Algorithm 1 Seq-GreC Algorithm

######  Lemma III.11 (Evader k’s greedy strategy)

The greedy strategy $v_{kg}^{*}$ for $E_{k}$, when each $E_{i}$,
$i\in\\{1,\dots,k-1\\}$ moves with $v_{1g}^{*}$ is

$\displaystyle v_{kg}^{*}=\begin{cases}{u}_{\textup{max}},\text{ if }y_{k}\geq
y_{k-1}-\Delta x_{k}^{k-1}V+\\\
(v_{(k-1)g}^{*}-V)\sum_{i=1}^{k-1}T_{i}^{i-1},\\\ {u}_{\textup{min}},\text{
otherwise.}\end{cases}$

###### Proof.

Suppose the result holds for some $k=\bar{k}$. Consider the next evader,
$E_{\bar{k}+1}$. Similar to the proof of Lemma III.6, we find
$y_{\bar{k}+1}^{\prime}=y_{\bar{k}}-\Delta
x_{\bar{k}+1}^{\bar{k}}V+(v_{\bar{k}g}^{*}-V)\sum_{i=1}^{\bar{k}}T_{i}^{i-1}$.
If $y_{\bar{k}+1}<y_{\bar{k}+1}^{\prime}$, then, from Lemma III.10, the time
will be maximized at either ${u}_{\textup{min}}$ or ${u}_{\textup{max}}$.
Thus, assuming
$T_{k}^{k-1}(v_{1g}^{*},\dots,v_{(k-1)g}^{*},{u}_{\textup{max}})>T_{k}^{k-1}(v_{1g}^{*},\dots,v_{(k-1)g}^{*},{u}_{\textup{min}})$
yields $y_{\bar{k}+1}>y_{\bar{k}+1}^{\prime}$ which is a contradiction and so
$v_{kg}^{*}={u}_{\textup{min}}$. Moreover, by induction, the result holds for
any value of $\bar{k}$. Case 2 is proved analogously. This concludes our
proof. ∎

The previous lemma presented a result on the greedy strategy of any evader
$E_{k}$. This result is the first step of the Algorithm 1. As the second step
of Algorithm 1 requires to check the conditions of cooperation between two
consecutive evaders, we will now present a result on the conditions if two
evaders should cooperate or not. We introduce the notation,
$U:=\frac{2}{2+{u}_{\textup{min}}-{u}_{\textup{max}}}$.

######  Lemma III.12 (Cooperation conditions for $E_{k-1}$)

Given the initial locations of $E_{k-1}$, $E_{k}$, and $P$ as
$(x_{k-1},y_{k-1})$, $(x_{k},y_{k})$, and $(X,Y)$ respectively, then $E_{k-1}$
will cooperate with $E_{k}$ if
(i) Case 1:

$\displaystyle y_{k-2}+(v_{(k-2)a}^{*}-V)\sum_{i=1}^{k-2}T_{i}^{i-1}-\Delta
x_{k-1}^{k-2}V\leq y_{k-1}$ $\displaystyle\leq
y_{k-2}+(v_{(k-2)a}^{*}-{u}_{\textup{min}})\sum_{i=1}^{k-2}T_{i}^{i-1}-\Delta
x_{k-1}^{k-2}{u}_{\textup{min}}$

and

$\displaystyle\Delta y_{k}^{k-1}>-\Delta
x_{k-1}^{k}V+(v_{(k-1)g}^{*}-V)\sum_{i=1}^{k}T_{i}^{i-1}+$ $\displaystyle
U\big{(}{u}_{\textup{min}}\Delta x_{k-1}^{k-2}+\Delta
y_{k-2}^{k-1}-(v_{(k-2)a}^{*}-{u}_{\textup{min}})\sum_{i=1}^{k-2}T_{i}^{i-1}\big{)}$
(5)

(ii) Case 2:

$\displaystyle
y_{k-2}+(v_{(k-2)a}^{*}-{u}_{\textup{max}})\sum_{i=1}^{k-2}T_{i}^{i-1}-\Delta
x_{k-1}^{k-2}{u}_{\textup{max}}$ $\displaystyle\leq y_{k-1}\leq
y_{k-2}+(v_{(k-2)a}^{*}-V)\sum_{i=1}^{k-2}T_{i}^{i-1}-\Delta x_{k-1}^{k-2}V$

and

$\begin{split}&\Delta y_{k-1}^{k}<-\Delta
x_{k}^{k-1}V+(v_{(k-1)g}^{*}-V)\sum_{i=1}^{k}T_{i}^{i-1}+\\\
&U\big{(}{u}_{\textup{max}}\Delta x_{k-1}^{k-2}+\Delta
y_{k-2}^{k-1}-(v_{(k-2)a}^{*}-{u}_{\textup{max}})\sum_{i=1}^{k-2}T_{i}^{i-1}\big{)},\end{split}$
(6)

where $v_{(k-2)a}^{*}$ determined by Algorithm 1.

###### Proof.

Let us assume that this result holds for some $k=\bar{k}-1$. The idea is to
prove this result using induction by deriving the conditions for cooperation
between $E_{\bar{k}}$ and $E_{\bar{k}+1}$. For brevity, we will reuse Figure 2
with the two evaders $E_{1}$ and $E_{2}$ in the figure corresponding to
$E_{\bar{k}}$ and $E_{\bar{k}+1}$ respectively. Suppose that the initial
location of $E_{\bar{k}}$ satisfies $y_{\bar{k}}\geq
y_{\bar{k}-1}+(v_{(\bar{k}-1)a}^{*}-V)\sum_{i=1}^{\bar{k}-1}T_{i}^{i-1}-\Delta
x_{\bar{k}}^{\bar{k}-1}V$ and the location of $E_{\bar{k}+1}$ satisfies
$y_{\bar{k}+1}>y_{\bar{k}}-\Delta
x_{\bar{k}+1}^{\bar{k}}V+(v_{\bar{k}g}^{*}-V)\sum_{i=1}^{\bar{k}}T_{i}^{i-1}$.
Then, from Lemma III.11, $E_{\bar{k}}$ moves with ${u}_{\textup{max}}$ to
maximize the component $T_{\bar{k}}^{\bar{k}-1}$ out of its intercept time and
$E_{\bar{k}+1}$ moves with ${u}_{\textup{max}}$ to maximize
$T_{\bar{k}+1}^{\bar{k}}$. This implies that when $P$ completes stage 1 for
the pursuit of $E_{\bar{k}}$, $P$ is below $E_{\bar{k}}$. As the pursuer
follows the Manhattan pursuit strategy, the time taken to cover the path in
the y-direction to intercept $E_{\bar{k}}$ and then $E_{\bar{k}+1}$ equals the
time taken to cover the path in the y-direction to intercept only
$E_{{\bar{k}}+1}$ from the pursuer’s location (2 (a)). Note that the pursuer
is located at the intercept location of $E_{\bar{k}-1}$. So, to increase the
total time to intercept, $E_{\bar{k}}$ and $E_{\bar{k}+1}$ need to cooperate
which can occur in only two ways.

The first is that $E_{\bar{k}}$ moves with speed $v_{\bar{k}}$ satisfying
$\Delta
x_{\bar{k}}^{\bar{k}-1}<(y_{\bar{k}-1}-y_{\bar{k}}+(v_{(\bar{k}-1)a}^{*}-v_{\bar{k}})\sum_{i=1}^{\bar{k}-1}T_{i}^{i-1})/v_{\bar{k}}$,
which means that $P$ intercepts $E_{\bar{k}}$ below the intercept point of
$E_{\bar{k}-1}$ and $E_{\bar{k}+1}$ moves greedily, i.e., with
${u}_{\textup{max}}$ (Fig. 2 (b)). This is possible only if $\Delta
y_{\bar{k}-1}^{\bar{k}}\leq(v_{(\bar{k}-1)a}^{*}-{u}_{\textup{min}})\sum_{i=1}^{\bar{k}-1}T_{i}^{i-1}-\Delta
x_{\bar{k}}^{\bar{k}-1}{u}_{\textup{min}}$ holds. If $\Delta
y_{\bar{k}-1}^{\bar{k}}>(v_{(\bar{k}-1a)}^{*}-{u}_{\textup{min}})\sum_{i=1}^{\bar{k}-1}T_{i}^{i-1}-\Delta
x_{\bar{k}}^{\bar{k}-1}{u}_{\textup{min}}$, then for any speed $v_{\bar{k}}$
for $E_{\bar{k}}$, the total distance covered in the $Y$-direction to
intercept $E_{\bar{k}}$ and $E_{\bar{k}+1}$ will be the same as the total
distance covered to intercept $E_{\bar{k}+1}$ from the pursuer’s location,
irrespective of $E_{\bar{k}}$’s choice.

The second case in which $E_{\bar{k}}$ and $E_{\bar{k}+1}$ cooperate is if
$E_{\bar{k}}$ moves greedily with ${u}_{\textup{max}}$ and $E_{k+1}$ moves
with speed $v_{\bar{k}+1}$ such that $y_{\bar{k}+1}<y_{\bar{k}}-\Delta
x_{\bar{k}+1}^{\bar{k}}v_{\bar{k}+1}+(v_{\bar{k}g}^{*}-v_{\bar{k}+1})\sum_{i=1}^{\bar{k}}T_{i}^{i-1}$,
i.e., the intercept location of $E_{\bar{k}+1}$ is below the intercept
location of $E_{\bar{k}}$ (Fig. 2 (c)). To determine which of the two
scenarios yield greater intercept time, we arrive at the condition

$\displaystyle\sum_{i=1}^{k}T_{i}^{i-1}+T_{\bar{k}+1}^{\bar{k}}({u}_{\textup{max}})>\sum_{i=1}^{k}T_{i}^{i-1}+T_{\bar{k}+1}^{\bar{k}}({u}_{\textup{min}})$

which yields the conclusion that $E_{\bar{k}}$ should cooperate with
$E_{\bar{k}+1}$ only if equation (III.12) holds. This concludes our proof for
case 1. Case 2 can be proved by following the steps for Case 1 and has been
omitted for brevity. ∎

Lemma III.12 establishes the conditions for cooperation between any two
consecutive evaders. The next result characterizes the cooperative strategies
of the evaders.

######  Theorem III.13 (Cooperative strategy for $E_{k-1}$)

If the conditions on cooperation in Lemma III.12 hold, then the optimal
strategy $v_{(k-1)c}^{*}$ for $E_{k-1}$ during cooperation with $E_{k}$ is

$v_{(k-1)c}^{*}=\begin{cases}{u}_{\textup{min}},\text{ for case 1 of Lemma
\ref{lem:coop_nE_MD} },\\\ {u}_{\textup{max}},\text{ for case 2 of Lemma
\ref{lem:coop_nE_MD}. }\end{cases}$

###### Proof.

Assume that the result holds for $k=\bar{k}-1$. The idea is to prove this
result by induction by deriving this result for $E_{\bar{k}}$. Suppose case 1
from Lemma III.12 holds for $E_{\bar{k}}$ and $E_{\bar{k}+1}$. From Lemma
III.12, we know in order to cooperate with $E_{\bar{k}+1}$, $E_{\bar{k}}$
moves with a speed $v_{\bar{k}}$ such that $\Delta
x_{\bar{k}}^{\bar{k}-1}<(y_{\bar{k}-1}-y_{\bar{k}}+(v_{\bar{k}-1}^{*}-v_{\bar{k}})\sum_{i=1}^{\bar{k}-1}T_{i}^{i-1})/v_{\bar{k}}$,
i.e., $E_{\bar{k}}$ is intercepted below the pursuer’s location. We also know
from the same lemma that these conditions on cooperation ensure that the total
time to intercept while cooperation is higher than total time to intercept
when the evaders move greedy. Now, since $T_{\bar{k}}^{\bar{k}-1}$ is
monotonic in $v_{\bar{k}}$, $v_{\bar{k}c}^{*}={u}_{\textup{min}}$. Similar
steps can be followed for case 2. ∎

######  Remark 2 (Sandwiched evader)

For some $i\in\\{1,\dots,n\\}$, if Lemma III.12 holds for evader $E_{i-1}$ and
$E_{i}$ as well as $E_{i}$ and $E_{i+1}$, then evader $E_{i}$ moves greedy.

##  IV Fundamental Limit

In the previous sections, we considered that the pursuer followed a fixed
strategy to capture all evaders. We now establish a fundamental upper bound,
for _a large number of evaders_ , on the total time taken to intercept all
evaders by the pursuer following _any_ strategy. We first provide some
existing results that will be useful in establishing the bound.

Given a set of $m$ points, a _Euclidean minimum Hamiltonian path_ (EMHP) is
the shortest path through $m$ points such that each point is visited exactly
once. When the points are translating with some constant speed $v\in(0,1)$,
then the shortest tour though the points is called _Translational minimum
Hamiltonian path_ (TMHP) [18].

######  Lemma IV.1 (Length of EMHP tour)

Given $m$ points in a $l\times h$ rectangle in the plane, where
$h\in\mathbb{R}_{>0}$ and $l\in\mathbb{R}_{>0}$, there exists a path that
starts from a unit length edge of the rectangle, passes through each of the
$m$ points exactly once, and terminates on the opposite unit length edge, with
length upper bounded by $\sqrt{2lhm}+h+2.5$

###### Proof.

The proof is similar to the proof provided in [19] for a $1\times h$ rectangle
and thus, has been omitted. ∎

To calculate the EMHP tour through translating points $s,s_{1},\dots,s_{f},f$
that move with speed $v$, the points are scaled by defining a conversion map
$C_{v}:\mathbb{R}^{2}\to\mathbb{R}^{2}$ such that
$C_{v}(x,y)=(\frac{x}{\sqrt{(1-v^{2})}},\frac{y}{1-v^{2}})$ [18].

######  Lemma IV.2 (Length of TMHP tour [18])

Let the initial and final point be denoted as $s=(x_{s},y_{s})$ and
$f=(x_{f},y_{f})$ respectively, and $v\in(0,1)$ denote a constant speed of all
evaders, then the length of the TMHP tour is
$\frac{v(y_{f}-y_{s})}{1-v^{2}}+\mathcal{L}_{E}(C_{v}(s),{C_{v}(s_{1}),\dots,C_{v}(s_{f})},C_{v}(f))$
where, $\mathcal{L}_{E}(C_{v}(s),{C_{v}(s_{1}),\dots,C_{v}(s_{f})},C_{v}(f))$
denotes the length of the EMHP starting with point $s$, moving through points
${s_{1},\dots,s_{f}}$ and ending at point $f$.

The optimal order followed by the vehicle in the TMHP solution is the same as
the optimal order followed by the vehicle in the EMHP solution.

Denote ${n}_{\textup{max}}\in\mathbb{Z}_{0}^{+}$ as the total number of
evaders that move with ${u}_{\textup{max}}$ and
${n}_{\textup{min}}=n-{n}_{\textup{max}}$ as the total number of evaders that
move with ${u}_{\textup{min}}$. Let $\mathcal{{A}_{\textup{max}}}$ and
$\mathcal{{A}_{\textup{min}}}$ denote the area of the smallest enclosing
rectangular environment that the ${n}_{\textup{max}}$ and ${n}_{\textup{min}}$
evaders occupy initially. We assume that all of the evaders are initially
located within a rectangular environment of area $\mathcal{A}$. The pursuer’s
strategy is to capture all the ${n}_{\textup{max}}$ evaders first, followed by
capturing all the evaders moving with ${u}_{\textup{min}}$. This is because if
the pursuer captures the ${n}_{\textup{min}}$ evaders first then naturally,
the evaders moving with ${u}_{\textup{max}}$ will be further away from the
pursuer.

Let $T_{{n}_{\textup{max}}}$ be the time taken by the vehicle to capture all
of the ${n}_{\textup{max}}$ evaders and
$T_{{n}_{\textup{min}}}^{{n}_{\textup{max}}}$ be the time taken to intercept
the last evader that moves with ${u}_{\textup{max}}$ and the first evader that
moves with ${u}_{\textup{min}}$ after capturing all of the
${n}_{\textup{max}}$ evaders respectively. Let $T_{{n}_{\textup{min}}}$ be the
total time taken by the vehicle to capture all of the remaining
${n}_{\textup{min}}-1$ evaders. The next result characterizes an upper bound
on the time taken by the pursuer to capture all evaders following any
strategy.

######  Theorem IV.3 (Upper bound on intercept time)

Let $\Delta y$ and $\Delta x$ be the difference between the initial $y$ and
$x$-coordinate of the last evader captured moving with ${u}_{\textup{max}}$
and the first evader that is captured moving with ${u}_{\textup{min}}$. Then,
from Lemma IV.1 and Lemma IV.2, the total time taken by the pursuer to capture
all evaders is
$T=T_{{n}_{\textup{max}}}+T_{{n}_{\textup{min}}}^{{n}_{\textup{max}}}+T_{{n}_{\textup{min}}}$
where,

$\displaystyle
T_{{n}_{\textup{max}}}=\sqrt{\frac{2\mathcal{{A}_{\textup{max}}}{n}_{\textup{max}}}{(1-{u}_{\textup{max}}^{2})^{3/2}}},\text{
}T_{{n}_{\textup{min}}}=\sqrt{\frac{2\mathcal{{A}_{\textup{min}}}({n}_{\textup{min}}-1)}{(1-{u}_{\textup{min}}^{2})^{3/2}}}$
$\displaystyle
T_{{n}_{\textup{min}}}^{{n}_{\textup{max}}}=\frac{{u}_{\textup{min}}}{1-{u}_{\textup{min}}^{2}}(\Delta
y+({u}_{\textup{min}}-{u}_{\textup{max}})T_{{n}_{\textup{max}}})+$
$\displaystyle\sqrt{\frac{\Delta
x^{2}}{1-{u}_{\textup{min}}^{2}}+\frac{(\Delta
y+({u}_{\textup{min}}-{u}_{\textup{max}})T_{{n}_{\textup{max}}})^{2}}{(1-{u}_{\textup{min}}^{2})^{2}}}.$

Moreover, for large $n$, $T$ is maximum for

$\displaystyle{n}_{\textup{max}}^{*}=\bigg{\lfloor}\frac{({u}_{\textup{min}}-{u}_{\textup{max}})^{2}n}{(1-{u}_{\textup{min}}^{2})^{\frac{1}{2}}(1-{u}_{\textup{max}}^{2})^{\frac{3}{2}}+({u}_{\textup{min}}-{u}_{\textup{max}})^{2}}\bigg{\rceil},$

where $\lfloor x\rceil$ denotes the integer nearest to $x$.

###### Proof.

The outline of the proof is as follows. The expression for
$T_{{n}_{\textup{max}}}$ and $T_{{n}_{\textup{min}}}$ follows directly from
Lemma IV.1 and noting that $n$ is large. The expression for
$T_{{n}_{\textup{min}}}^{{n}_{\textup{max}}}$ follows from [18]. Consider that
the vehicle has just finished capturing all ${n}_{\textup{max}}$ evaders.
Then, all the evaders moving with ${u}_{\textup{min}}$ would have translated
${u}_{\textup{min}}T_{{n}_{\textup{max}}}$ in the $y$ direction. Note that the
area $\mathcal{{A}_{\textup{min}}}$ will remain the same as it was initially.
Since $T_{{n}_{\textup{max}}}$ is large for large ${n}_{\textup{max}}$, the
distance between the vehicle after capturing the last evader moving with
${u}_{\textup{max}}$ and the first evader moving with ${u}_{\textup{min}}$
will be large. Furthermore, since ${u}_{\textup{max}}>{u}_{\textup{min}}$ and
$T_{{n}_{\textup{max}}}$ is large, the pursuer will always be above all
evaders moving with ${u}_{\textup{min}}$ after capturing ${n}_{\textup{max}}$
evaders and thus, we get the expression for
$T_{{n}_{\textup{min}}}^{{n}_{\textup{max}}}$. The evaders can select
${n}_{\textup{max}}$ such that the total time $T$ is maximized.
Mathematically,
${n}_{\textup{max}}^{*}=\operatorname*{arg\,max}_{{n}_{\textup{max}}}T({n}_{\textup{max}})$.
If we relax the requirement of ${n}_{\textup{max}}$ to be a real number then
the function $T:\mathbb{R}\to\mathbb{R}$ is concave with global maximum in the
domain $[0,n]$. This follows as $\frac{dT^{2}}{d{n}_{\textup{max}}^{2}}<0$.
Thus, to find the maximizer, we use the first derivative test, i.e.,
$\frac{dT}{d{n}_{\textup{max}}}=0$ and then find the closest integer value
that maximizes $T$. By taking the derivative of $T$ with respect to
${n}_{\textup{max}}$, we get
$\frac{dT_{{n}_{\textup{max}}}}{d{n}_{\textup{max}}}+\frac{dT_{{n}_{\textup{min}}}^{{n}_{\textup{max}}}}{d{n}_{\textup{max}}}+\frac{dT_{{n}_{\textup{min}}}}{d{n}_{\textup{max}}}$,
where,

$\displaystyle\frac{dT_{{n}_{\textup{max}}}}{d{n}_{\textup{max}}}=\frac{\sqrt{\mathcal{{A}_{\textup{max}}}}}{(1-{u}_{\textup{max}}^{2})^{3/4}\sqrt{2{n}_{\textup{max}}}},$
$\displaystyle\frac{dT_{{n}_{\textup{min}}}}{d{n}_{\textup{max}}}=-\frac{\sqrt{\mathcal{{A}_{\textup{min}}}}}{(1-{u}_{\textup{min}}^{2})^{3/4}\sqrt{2(n-{n}_{\textup{max}}-1)}},$
$\displaystyle\frac{dT_{{n}_{\textup{min}}}^{{n}_{\textup{max}}}}{d{n}_{\textup{max}}}=\frac{{u}_{\textup{min}}}{1-{u}_{\textup{min}}^{2}}({u}_{\textup{min}}-{u}_{\textup{max}})\frac{dT_{{n}_{\textup{max}}}}{d{n}_{\textup{max}}}+$
$\displaystyle\frac{(\Delta
y+({u}_{\textup{min}}-{u}_{\textup{max}})T_{{n}_{\textup{max}}})({u}_{\textup{min}}-{u}_{\textup{max}})\frac{dT_{{n}_{\textup{max}}}}{d{n}_{\textup{max}}}}{(1-{u}_{\textup{min}}^{2})^{2}\sqrt{\frac{\Delta
x^{2}}{1-{u}_{\textup{min}}^{2}}+\frac{(\Delta
y+({u}_{\textup{min}}-{u}_{\textup{max}})T_{{n}_{\textup{max}}})^{2}}{(1-{u}_{\textup{min}}^{2})^{2}}}}.$

In the worst case, the evader initial locations will cover the area
$\mathcal{A}$ completely, i.e.,
$\mathcal{{A}_{\textup{max}}}=\mathcal{{A}_{\textup{min}}}=\mathcal{A}$.
Adding and equating to zero, and noting that $T_{{n}_{\textup{max}}}$ is
large, $\Delta
y\ll({u}_{\textup{min}}-{u}_{\textup{max}})T_{{n}_{\textup{max}}}$ and
$1-{u}_{\textup{min}}{u}_{\textup{max}}\ll\frac{\Delta
y+({u}_{\textup{min}}-{u}_{\textup{max}})T_{{n}_{\textup{max}}}}{(1-{u}_{\textup{min}}^{2})\sqrt{\frac{\Delta
x^{2}}{1-{u}_{\textup{min}}^{2}}+\frac{(\Delta
y^{2}+({u}_{\textup{min}}-{u}_{\textup{max}})T_{{n}_{\textup{max}}})^{2}}{(1-{u}_{\textup{min}}^{2})^{2}}}}$
yields

$\displaystyle{n}_{\textup{max}}^{*}=\frac{2\Delta
u^{4}\mathcal{A}n-(1-{u}_{\textup{min}}^{2})^{3/2}\Delta
x^{2}(1-{u}_{\textup{max}}^{2})^{3}}{2\Delta
u^{2}\mathcal{A}((1-{u}_{\textup{min}}^{2})^{\frac{1}{2}}(1-{u}_{\textup{max}}^{2})^{\frac{3}{2}}+\Delta
u^{2})},$

where $\Delta u={u}_{\textup{min}}-{u}_{\textup{max}}$. Since, $2\Delta
u^{4}\mathcal{A}n\gg(1-{u}_{\textup{min}}^{2})^{\frac{3}{2}}\Delta
x^{2}(1-{u}_{\textup{max}})^{3}$, we get the result. Furthermore, since
$\frac{d^{2}T}{d{n}_{\textup{max}}^{2}}<0$ at the critical point
${n}_{\textup{max}}^{*}$, ${n}_{\textup{max}}^{*}$ is indeed the point of
maximum. This concludes the proof. ∎

##  V Simulation Results

We first present the numerical results for Algorithm 1. We compare the mean of
the total time to intercept all evaders using Algorithm 1 to the mean of the
total time to intercept all evaders by randomly sampling over the evader
speeds of either ${u}_{\textup{min}}$ or ${u}_{\textup{max}}$ (see Figure 3).
For each value of $n$, we randomly generate the initial locations of the
evaders and the pursuer and we consider 50 Monte Carlo trials. To select the
best evader speeds, we choose $10nln(2/\delta)$ samples uniformly randomly
over the set, which guarantees that the violation probability is less than a
small quantity $\delta$ [20], where $\delta=0.1$. We compute the maximum over
the samples and then report the mean value in Figure 3. We observe that
Algorithm 1 outperforms random sampling.

Figure 4 shows a comparison when ${n}_{\textup{max}}$ is selected uniformly
randomly to the upper bound obtained by ${n}_{\textup{max}}^{*}$ for given
initial locations. To obtain the EMHP tour required for the time to intercept
evaders, the linkern111The TSP solver linkern is freely available for academic
research use at http://www.math.uwaterloo.ca/tsp/concorde/. solver was used.
We consider 50 Monte Carlo trials for each value of $n$ and report the mean
and standard deviation. It is observed that the total time to intercept all
evaders by randomly selecting ${n}_{\textup{max}}$ is well below the upper
bound obtained from ${n}_{\textup{max}}^{*}$. Thus, by performing an
additional optimization to select ${n}_{\textup{max}}$ the evaders can reach
the upper bound on time to intercept. This means that a strategy that only
depends on ${n}_{\textup{max}}$ may be sub-optimal for the evaders.

Figure 3: Comparison of Seq-Grec with Random Sampling. The blue circles
represent the mean of the total time to intercept of Seq-Grec Algorithm. The
orange star represents the mean over the samples of Random Sampling Figure 4:
Comparison of the total time to intercept when ${n}_{\textup{max}}$ is
randomly uniformly selected to that of the upper bound obtained from
${n}_{\textup{max}}^{*}$.

##  VI Conclusions and Future Work

An optimal evasion problem between single a pursuer and multiple evaders was
addressed. It is shown that by enforcing cooperation among evaders, they are
able to maximize the total interception time. Conditions where cooperation is
optimal are also presented which are crucial to implement the cooperative
strategies. An upper bound on the total time to intercept all evaders is also
presented.

In subsequent work, a generalized setup of multiple pursuers and evaders will
be considered. Constant factor approximations for both, the evaders and the
pursuers will also be addressed. Identifying which evaders should move with
${u}_{\textup{max}}$ is another possible extension.

## References

  * [1] R. Ragesh, A. Ratnoo, and D. Ghose, “Analysis of evader survivability enhancement by decoy deployment,” in _2014 American Control Conference_. IEEE, 2014, pp. 4735–4740.
  * [2] R. Isaacs, _Differential games: a mathematical theory with applications to warfare and pursuit, control and optimization_. Courier Corporation, 1999.
  * [3] V. R. Makkapati and P. Tsiotras, “Optimal evading strategies and task allocation in multi-player pursuit–evasion problems,” _Dynamic Games and Applications_ , vol. 9, no. 4, pp. 1168–1187, 2019.
  * [4] A. R. Girard and P. T. Kabamba, “Proportional navigation: optimal homing and optimal evasion,” _SIAM Review_ , vol. 57, no. 4, pp. 611–624, 2015.
  * [5] J. Selvakumar and E. Bakolas, “Evasion from a group of pursuers with a prescribed target set for the evader,” in _2016 American Control Conference (ACC)_. IEEE, 2016, pp. 155–160.
  * [6] Z. E. Fuchs, P. P. Khargonekar, and J. Evers, “Cooperative defense within a single-pursuer, two-evader pursuit evasion differential game,” in _49th IEEE Conference on Decision and Control (CDC)_. IEEE, 2010, pp. 3091–3097.
  * [7] K. Zemskov and A. Pashkow, “Construction of optimal position strategies in a differential pursuit-evasion game with one pursuer and two evaders,” _Journal of applied mathematics and mechanics_ , vol. 61, no. 3, pp. 391–399, 1997.
  * [8] D. W. Oyler, P. T. Kabamba, and A. R. Girard, “Pursuit–evasion games in the presence of obstacles,” _Automatica_ , vol. 65, pp. 1–11, 2016.
  * [9] E. Garcia, D. W. Casbeer, K. Pham, and M. Pachter, “Cooperative aircraft defense from an attacking missile,” in _53rd IEEE Conference on Decision and Control_. IEEE, 2014, pp. 2926–2931.
  * [10] A. A. Chikrii and S. Kalashnikova, “Pursuit of a group of evaders by a single controlled object,” _Cybernetics and Systems Analysis_ , vol. 23, no. 4, pp. 437–445, 1987.
  * [11] I. Shevchenko, “Guaranteed approach with the farthest of the runaways,” _Automation and Remote Control_ , vol. 69, no. 5, pp. 828–844, 2008.
  * [12] A. Belousov, Y. I. Berdyshev, A. Chentsov, and A. Chikrii, “Solving the dynamic traveling salesman game problem,” _Cybernetics and Systems Analysis_ , vol. 46, no. 5, pp. 718–723, 2010.
  * [13] S.-Y. Liu, Z. Zhou, C. Tomlin, and K. Hedrick, “Evasion as a team against a faster pursuer,” in _2013 American Control Conference_. IEEE, 2013, pp. 5368–5373.
  * [14] W. L. Scott and N. E. Leonard, “Optimal evasive strategies for multiple interacting agents with motion constraints,” _Automatica_ , vol. 94, pp. 26–34, 2018.
  * [15] K. Krishnamoorthy, S. Darbha, P. P. Khargonekar, D. Casbeer, P. Chandler, and M. Pachter, “Optimal minimax pursuit evasion on a Manhattan grid,” in _2013 American Control Conference_. IEEE, 2013, pp. 3421–3428.
  * [16] K. Kalyanam, S. Darbha, P. Khargonekar, M. Pachter, and P. R. Chandler, “Optimal cooperative pursuit on a Manhattan grid,” in _AIAA Guidance, Navigation, and Control (GNC) Conference_ , 2013, p. 4633.
  * [17] A. Alexopoulos, T. Schmidt, and E. Badreddin, “Cooperative pursue in pursuit-evasion games with unmanned aerial vehicles,” in _2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2015, pp. 4538–4543.
  * [18] M. Hammar and B. J. Nilsson, “Approximation results for kinetic variants of TSP,” in _International Colloquium on Automata, Languages, and Programming_. Springer, 1999, pp. 392–401.
  * [19] S. D. Bopardikar, S. L. Smith, F. Bullo, and J. P. Hespanha, “Dynamic vehicle routing for translating demands: Stability analysis and receding-horizon policies,” _IEEE Transactions on Automatic Control_ , vol. 55, no. 11, pp. 2554–2569, 2010.
  * [20] T. Alamo, R. Tempo, and A. Luque, “On the sample complexity of randomized approaches to the analysis and design under uncertainty,” in _Proceedings of the 2010 American Control Conference_. IEEE, 2010, pp. 4671–4676.