# Target Defense against Periodically Arriving Intruders

Arman Pourghorban and Dipankar Maity The authors are with the Department of
Electrical and Computer Engineering at The University of North Carolina at
Charlotte, NC, 28223, USA. Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>This
research is supported by the ARL grant ARL DCIST CRA W911NF-17-2-0181

###### Abstract

We consider a variant of pursuit-evasion games where a single defender is
tasked to defend a static target from a sequence of periodically arriving
intruders. The intruders’ objective is to breach the boundary of a circular
target without being captured and the defender’s objective is to capture as
many intruders as possible. At the beginning of each period, a new intruder
appears at a random location on the perimeter of a fixed circle surrounding
the target and moves radially towards the target center to breach the target.
The intruders are slower in speed compared to the defender and they have their
own sensing footprint through which they can perfectly detect the defender if
it is within their sensing range. Considering the speed and sensing
limitations of the agents, we analyze the entire game by dividing it into
partial information and full information phases. We address the defender’s
capturability using the notions of engagement surface and capture circle. We
develop and analyze three efficient strategies for the defender and derive a
lower bound on the capture fraction. Finally, we conduct a series of
simulations and numerical experiments to compare and contrast the three
proposed approaches.

###### Index Terms:

Target-defense, pursuit-evasion, partial information games, multi-agent
systems.

##  I Introduction

In this paper, we study a circular target-defence game between a single
defender and a team of sequentially arriving intruders. This problem has been
found useful in multi-robot applications such as patrolling [1], area
monitoring [2], area securing [3], coastline defense [4] and has motivated a
great amount of research e.g., see [5] for a review on this topic.

Since the formulation of the Pursuit-Evasion Game (PEG) [6], several
variations of it have been proposed in the last few decades that directly
address target/area/perimeter defense type applications. For example, reach-
avoid games are a variant of PEGs where a group of agents attempt to reach a
target while avoiding some adversarial circumstances generated by the opponent
group [7, 8, 9]. Likewise, perimeter-defence problems are another variant of
PEGs wherein the defender team is tasked to capture the intruders before the
latter breach the target perimeter. Target-defence games, which are of
particular relevance for this paper, have been studied by considering the
scenario where the defenders’ movements are constrained on the perimeter of
the target [10, 11] and also where the defenders can move freely in the
environment [12],[13]. In this work we consider the second scenario where the
defenders can move freely in the environment.

Of particular relevance to this paper is the work in [14] that considered a
problem where the intruders appeared randomly according to a Poisson arrival
process at a fixed distance from the target perimeter. Several algorithms for
capturing the intruders are discussed and some performance bounds for the
capture fraction are derived. However, this work did not consider any sensing
capability for the intruders and therefore, the intruders are restricted in
terms of the evasive strategies they can deploy. Similarly, in [15] and [16]
among many others, the intruders attempting to breach a target perimeter are
tasked with simple and fixed a priori strategies. These works also do not
consider the sensing capability which enables the intruders to evade from the
defender instead of just being captured on their direct path toward the
target. To the best of our knowledge, some of the earliest works on similar
problems have been considered in [17] where a vehicle (equivalent to our
defender) is tasked to serve multiple randomly arriving customers (equivalent
of our intruders) in an optimal fashion. In contrast these works, we show in
our earlier work [18] that the sensing capability and the adversarial nature
of the arriving intruders result in a particular type of evasive maneuver
where the intruders can force the defender to pursue them and thus, the
defender ends up capturing the intruders at locations which are advantageous
for the next intruders to increase their target breaching probability.
Sensing-enabled motion tactics in the context of target defense games is one
of the key features of this paper and our earlier works [18, 19].

In [18], the arrival of the intruders were assumed to be sequential, i.e., the
next intruder appears randomly only after the current intruder breaches the
target perimeter or gets captured. As a consequence, the defender had only one
intruder to engage with at any given time. In this paper, we extend the work
of [18] and consider periodically incoming intruders. This way, depending on
the period of arrival, there might be multiple intruders available to engage
with and the defender needs to decide which intruder to engage with while
considering their sensing capabilities and the associated potential evasive
strategies deployed by these intruders. Similar to [18], we consider a partial
information game framework where, due to the sensing limitations, the agents
do not have each other’s information all the time and they must consider trade
off between sensing advantage and positional advantage while choosing their
strategies. The main contributions of this paper are: (i) We analyze a sensing
limited perimeter-defence game against periodically incoming intruders. The
intruders’ entry points are considered to be random. We analyze both finite
and infinite time (asymptotic) performances of the game. (ii) We derive the
strategies for all the agents and the discuss how to determine the
capturability of an intruder using the concepts of engagement surface and
capture circle. (iii) Based on the notion of capturability, we introduce three
strategies for the defender to determine which intruder(s) to purse and in
what manner (i.e., how to delay being sensed by that intruder to gain
positional and informational advantages), (iv) We theoretically derive a lower
bound for one of our proposed strategies. (v) We numerically validate (using
Monte-Carlo type random trials of experiments) the theoretically found lower
bound and compare it with the true performances of the three proposed
strategies for a wide range of parameters.

The rest of the paper is organized as follows: In Section II, we formulate our
problem, discuss parametric assumptions, and provide some useful definitions
and necessary background materials. The two phases (partial and full
information) are discussed in Sections III-A and III-B, respectively. We
analyze the whole game and design algorithms for the defender’s strategies in
Section IV. In section V, we analyze one of the proposed defender strategies
and compute a lower bound on this strategy’s performance. Simulations and
numerical results are discussed in Section VI. The developed algorithms were
deployed in Robotics Operating Systems (ROS) to generate experimental results.
We conclude the paper in Section VII.

Notation: All vectors are denoted with lowercase bold symbols, e.g.,
$\mathbf{x}$. $\hat{\mathbf{u}}(\theta)$ denotes the unit vector
$[\cos\theta,~{}\sin\theta]^{\intercal}$.

##  II Preliminaries

###  II-A Problem Formulation

defender$\longleftarrow$intruder$\longleftarrow$$\rho_{{}_{\rm
T}}$$\rho_{{}_{\rm A}}$$r_{{}_{\rm T}}$

Figure 1: g: Target region of radius $r_{{}_{\rm T}}$, g: intruders sensing
region of radius $\rho_{{}_{\rm A}}$, g: Target Sensing Region (TSR) of radius
$\rho_{{}_{\rm T}}$, – TSR Boundary.

We consider a target guarding problem in ${\mathbb{R}^{2}}$ where a
periodically arriving sequence of intruders is tasked to breach a circular
target region $\mathcal{R}_{\rm T}=\\{\textbf{x}\in{\mathbb{R}^{2}}\ |\
\|\textbf{x}\|\leq r_{{}_{\rm T}}\\}$, see Fig. 1. A single defender is
assigned to protect the target from the incoming sequence of intruders and, if
possible, capture the intruders before they reach the target boundary
$\partial\mathcal{R}_{\rm T}\triangleq\\{\textbf{x}\in{\mathbb{R}^{2}}\ |\
\|\textbf{x}\|=r_{{}_{\rm T}}\\}$. Given an arrival period $T$, the defender
maximizes the asymptotic intruder capture fraction
$J=\liminf_{t\to\infty}\frac{N(t)}{\lfloor\frac{t}{T}\rfloor},$ where $N(t)$
denotes the total number of intruders captured in $t$ amount of time.

There is a circular sensing annulus of radius $\rho_{{}_{\rm T}}$ around the
target boundary such that the defender can sense the location of any attacker
present in this region. We will refer to this annulus sensing region as the
Target Sensing Region (TSR). Each intruder appears on the TSR boundary with a
uniform random probability which is independent of the former arrivals. We
assume that the intruders do not communicate/coordinate with each other and
they each move radially toward the target center.

Let $\mathbf{x}_{\rm A}(t),\mathbf{x}_{\rm D}(t)\in\mathbb{R}^{2}$ denote the
positions of a representative intruder and the defender at time $t$. The
defender and the intruders are assumed to have first-order dynamics, i.e.,

$\displaystyle\dot{\mathbf{x}}_{\rm A}=v_{\rm A}\hat{\mathbf{u}}(\psi_{\rm
A}),\qquad\dot{\mathbf{x}}_{\rm D}=v_{\rm D}\hat{\mathbf{u}}(\psi_{\rm D}),$
(1)

where the defender (intruder) directly controls its speed and heading angle by
selecting $v_{\rm D}$ and $\psi_{\rm D}$ ($v_{\rm A}$ and $\psi_{\rm A}$),
respectively. We assume that the defender and the intruders move with speeds 1
and $\nu$, respectively, i.e., $|v_{\rm D}(t)|=1$ and $|v_{\rm A}(t)|=\nu$ for
all $t$. Furthermore, to avoid a trivial scenario we assume that $\nu<1$,
i.e., the defender is faster.

After arriving on the TSR boundary, an intruder moves radially toward the
target center until it senses the defender, similar to the setup of [14, 16,
19] among others. The defender has access to the instantaneous positions
$\mathbf{x}_{\rm A}(t)$ for all the intruders that are within the TSR. Each
intruder is equipped with a sensor and is able to sense the defender only if
the defender is within a distance of $\rho_{{}_{\rm A}}$ or less, i.e., the
intruders have a circular sensing footprint of radius $\rho_{{}_{\rm A}}$.
Using this sensing capability, an intruder is able to find the right breaching
point on the target, or able to get out of the TSR uncaptured, or is able to
evade for some time before getting captured by the defender. This evasive
maneuver is an important capability for the intruders since it forces the
defender to pursue and capture the intruder at a location that is likely to be
unfavorable for the defender to start pursuing the next intruder.

###  II-B Parametric Assumption

The overall outcome of this game depends on the game parameters $r_{{}_{\rm
T}},\rho_{{}_{\rm A}}$, $\rho_{{}_{\rm T}}$ and $\nu$. We assume that the
parameters satisfy the following condition

$\displaystyle(1+\nicefrac{{2\nu}}{{(1-\nu^{2})}})\rho_{{}_{\rm
A}}\leq\rho_{{}_{\rm T}},\quad\nu r_{{}_{\rm T}}\leq\rho_{{}_{\rm T}}.$ (2)

This assumption is required for capturing a capturable attacker inside the
TSR, as will be discussed later in much detail in III-A1. Capturing the
attacker inside the TSR is a necessity for the defender since the defender has
access to the attacker’s location only when the latter is inside the TSR.
Otherwise, there can be a deadlock situation where, if the intruder cannot
breach, it may successfully evade and keep trying indefinitely until it
successfully gets to breach or no longer has a strategy to evade. Therefore,
it is not possible to relax assumption (2) without preventing evasion of the
attacker. Furthermore, this assumption also avoids the situation where an
incoming intruder can sense the defender as soon as it appears on the TSR
boundary. Such a scenario also leads to a deadlock because the intruder can
immediately get out of the TSR if it does not have a strategy to breach. The
readers are referred to [18, Theorem 2] for more details on this assumption.
The second condition (i.e., $\nu r_{{}_{\rm T}}\leq\rho_{{}_{\rm T}}$) is
necessary to ensure that the defender can capture any intruder from the target
center. This way, when the defender has no capturable intruders, it goes
toward the target center to increase its probability to capture the next
arriving intruder.

###  II-C Apollonius Circle

Given the locations of the defender and the intruder at time $t$, the
Apollonius Circle contains all the points the intruder can reach before the
defender gets there. The set of all such points is a circular region with
center $\mathbf{x}_{\rm C}(t)$ and radius $r_{\rm C}(t)$:

$\displaystyle\mathbf{x}_{\rm C}(t)=\alpha\mathbf{x}_{\rm
A}(t)-\beta\mathbf{x}_{\rm D}(t),\quad r_{\rm C}(t)=\gamma\|\mathbf{x}_{\rm
A}(t)-\mathbf{x}_{\rm D}(t)\|,$ (3)

where $\alpha=(1-\nu^{2})^{-1},\quad\gamma=\nu\alpha,\quad\beta=\nu\gamma.$

######  Lemma 1 ([20])

The defender has a strategy to capture the intruder arbitrary close to the
Apollonius circle, regardless of any strategy that intruder chooses to escape.
$\triangle$

Apollonius circle is a critical tool for analyzing these types of games since
it specifies the regions where the agents can have winning strategies.

##  III Game Phases

Each game between the defender and any of the intruders can be divided into
two phases, namely, the Full information phase and the Partial/Asymmetric
information phase. From the time an intruder arrives on the TSR boundary to
the time it first senses the defender is referred to as the partial
information phase between that intruder and the defender. Therefore, in this
phase, only the defender can sense the intruder and not vice-versa. Defender’s
strategy against that intruder in this phase depends on whether the intruder
is capturable or not. If it is capturable, then the defender picks a location
and time to engage with the intruder by coming within the intruder’s sensing
region. Otherwise, the defender picks another intruder or movers closer to the
target center.

On the other hand, in the Full information phase, both agents can sense each
other, i.e., $\|\mathbf{x}_{\rm A}(t)\|<r_{{}_{\rm T}}+\rho_{{}_{\rm T}}$ and
$\|\mathbf{x}_{\rm A}(t)-\mathbf{x}_{\rm D}(t)\|\leq\rho_{{}_{\rm A}}$. In
this phase, the defender has a strategy to capture the intruder if the
Apollonius circle fits inside the TSR. However, if the Apollonius circle has
any intersection with the target, the intruder would have a guaranteed
strategy to breach, and if it has any intersection with the TSR boundary, then
the intruder would have a guaranteed strategy to escape before being captured
by the defender.

###  III-A Partial Information Phase

In this phase, the defender has access to the intruders’ information and not
vice-versa. The intruders move radially until it senses the defender. To
exploit this information advantage, the defender engages with the intruders in
particular configurations that guarantee capture. In [18] we show that
earliest engagement is not the optimal strategy since the intruder may survive
by evading. The defender may need to wait for a certain amount of time before
it engages with the intruder. A sub-optimal waiting strategy was first
introduced in [19] and the optimal engagement strategy was derived in [18]. We
will discuss these desirable engagement configurations and how to reach such
configurations using the notion of Engagement Surface.

####  III-A1 Engagement Surface

Given an intruder location $\mathbf{x}_{\rm A}(t)$ in the partial information
phase, we can accurately predict its path since it is moving in a straight
line toward the target center with maximum velocity. Let $\mathbf{x}_{\rm
A}(t_{1})$ be the location of the intruder at time $t_{1}>t$. To start the
engagement with the intruder exactly at time $t_{1}$, the defender must be at
point on the intruder’s sensing boundary, i.e., $\mathbf{x}_{\rm
D}(t_{1})=\mathbf{x}_{\rm A}(t_{1})+\rho_{{}_{\rm
A}}\hat{\mathbf{u}}({\theta})$ for some $\theta\in[0,2\pi)$. The choice of
$\theta$ (equivalently, the choice of $\mathbf{x}_{\rm D}(t_{1})$) will
determine the Apollonius circle, and the final outcome (i.e.,
capture/evade/breach) of the engagement. We defined the notion of engagement
surface to represent this concept in [18].

######  Definition 1 (Engagement Surface)

Given an intruder location $\mathbf{x}_{\rm A}(t_{0})$ at time $t_{0}$, the
engagement surface for this intruder, denoted as $S_{\rm
engage}(\mathbf{x}_{\rm A}(t_{0}))$, is the locus of the points
$\mathbf{x}_{\rm D}\triangleq\mathbf{x}_{\rm A}(t_{0}+t_{\rm
eng})+\rho_{{}_{\rm A}}\hat{\mathbf{u}}(\theta_{\rm eng})$, where $(t_{\rm
eng},\theta_{\rm eng})$ satisfies

$\sin^{2}\bigg{(}\frac{\theta_{\rm eng}-\theta_{\rm
A}}{2}\bigg{)}=\frac{(r_{{}_{\rm T}}+\gamma\rho_{{}_{\rm A}})^{2}-(r_{\rm
A}-t_{\rm eng}\nu-\beta\rho_{{}_{\rm A}})^{2}}{4\beta\rho_{{}_{\rm A}}(r_{\rm
A}-t_{\rm eng}\nu)},$ (4)

where $(r_{\rm A},\theta_{\rm A})$ is the polar coordinate representation of
the intruder’s given location $\mathbf{x}_{\rm A}(t_{0})$. $\triangle$

Note that $t_{\rm eng}$ represents the time spent before the intruder senses
the defender and the full information phase starts and $\theta_{\rm eng}$
denotes the angle on the intruder’s sensing boundary the defender will engage.
Since the pair $(t_{\rm eng},\theta_{\rm eng})$ uniquely defines a spatio-
temporal engagement point for a given intruder location $\mathbf{x}_{\rm
A}(t_{0})$, we will simply consider $(t_{\rm eng},\theta_{\rm eng})$
satisfying (4) to be the elements of the set $S_{\rm engage}(\mathbf{x}_{\rm
A}(t_{0}))$. A representative engagement surface is shown in Fig. 2.

$\mathbf{x}_{\rm A}(t_{0}\\!+\\!t_{\rm eng})$$\theta_{\rm
eng}$$x_{1}$$D_{1}$$D_{2}$$x_{2}$$r$$r_{\rm eng}$$\mathbf{x}_{\rm
A}(t_{0}\\!+\\!t_{\rm eng}^{*})$$\theta_{\rm eng}^{*}$$\phi_{\rm
eng}$$\theta_{\max}$$\textbf{x}_{\rm eng}$

Figure 2:  (Left) The cyan oval-shaped curve represents the locus of the
engagement points $\mathbf{x}_{\rm A}(t_{0}+t_{\rm eng})+\rho_{{}_{\rm
A}}\hat{\mathbf{u}}(\theta_{\rm eng})$. We demonstrate a configuration where a
defender $D_{1}$ starts the full information phase by engaging at the point
$x_{1}$ when the intruder is at $\mathbf{x}_{\rm A}(t_{0}+t_{\rm eng})$.
(Right) The engagement configuration with the intruder at time $t_{0}+t_{\rm
eng}^{*}$ where $\medbullet$ and $\Diamondblack$ denote the locations of the
intruder and the defender, respectively. The hollow blue circle denotes the
initial location of the defender.

Starting the full information phase from any of the points on this engagement
surface guarantees capture of the intruder since the Apollonius circles
generated from these engagement configurations do not have any intersection
with the target perimeter or the TSR boundary. This can be verified by
constructing the Apollonius circle as per (3) and using Assumption (2). Given
that the capture is guaranteed if engagement is started from this surface, the
intruder’s objective in this case is to get captured the farthest from the
target center. This will increase the breach probability for the other
intruders as discussed in [18, Corollary 1]. Furthermore, it has been shown in
[18] that the farthest capture point will be at a radial location of
$r_{{}_{\rm T}}+2\gamma\rho_{{}_{\rm A}}$ since the radius of Apollonius
circle will be $\gamma\rho_{{}_{\rm A}}$ and the center will at a distance of
$r_{{}_{\rm T}}+\gamma\rho_{{}_{\rm A}}$ from the target center. The circle
with radius $r_{{}_{\rm T}}+2\gamma\rho_{{}_{\rm A}}$ and concentric with the
target is referred to as the Capture Circle, since all the captures of the
intruders will happen on this circle, see [18] for details.

####  III-A2 Capturability of an Intruder

Let the defender be located at a point $r\hat{\mathbf{u}}({\theta_{\rm D}})$
at the time the intruder appears on the TSR boundary. In [18, Theorem 1], we
proved the condition on $r$ and $\theta_{\rm D}$ that ensures capturing an
incoming intruder utilizing the Engagement Surface. This theorem provides the
maximum allowed initial angular separation $\theta_{\max}$ between the
intruder and the defender to ensure capture by starting the engagement at
$(t_{\rm eng},\theta_{\rm eng})\in S_{\rm engage}(\mathbf{x}_{\rm A}(t_{0}))$:

$\displaystyle\theta_{\max}(t_{\rm eng},\theta_{\rm
eng},r)=\cos^{-1}\bigg{(}\frac{r_{\rm eng}^{2}+r^{2}-t_{\rm eng}^{2}}{2r_{\rm
eng}r}\bigg{)}+\phi_{\rm eng},$ (5a) $\displaystyle\phi_{\rm
eng}=\sin^{-1}\bigg{(}\frac{\rho_{{}_{\rm A}}\sin(\theta_{\rm eng})}{r_{\rm
eng}}\bigg{)},$ (5b) $\displaystyle\begin{split}&r_{\rm
eng}=\Big{(}(r_{{}_{\rm T}}+\rho_{{}_{\rm T}}-t_{\rm
eng}\nu)^{2}+\rho_{{}_{\rm A}}^{2}\\\ &\qquad\quad+2(r_{{}_{\rm
T}}+\rho_{{}_{\rm T}}-t_{\rm eng}\nu)\rho_{{}_{\rm A}}\cos(\theta_{\rm
eng})\Big{)}^{1/2}.\qquad\end{split}$ (5c)

We notice that $\theta_{\max}$ depends on the choice of $t_{\rm eng}$ and
$\theta_{\rm eng}$. By maximizing over $(t_{\rm eng},\theta_{\rm eng})$ with
the constraint (4), we obtain the pair $(t_{\rm eng}^{*},\theta_{\rm
eng}^{*})$.

###### Remark 1

The importance of finding $\theta_{\max}(t_{\rm eng}^{*},\theta_{\rm
eng}^{*})$ is that, if the angular separation between an intruder and the
defender is more than $\theta_{\max}(t_{\rm eng}^{*},\theta_{\rm eng}^{*})$ at
the time the intruder arrived on the TSR boundary, then it is ensured that the
defender is not able to capture this intruder. Therefore, the defender can
simply ignore this intruder from the game and focus on the rest. If the
angular separation is exactly $\theta_{\max}(t_{\rm eng}^{*},\theta_{\rm
eng}^{*})$, then $(t_{\rm eng}^{*},\theta_{\rm eng}^{*})$ is the unique point
where the defender needs to start the engagement. Otherwise, if the angular
separation is less, the defender has multiple engagement points and it will be
able to start engagement sooner than $t_{\rm eng}^{*}$. Thus, $t_{\rm
eng}^{*}$ is a tight upper bound on the amount of time spent before the
engagement starts. $\triangle$

Equation (5) is computed for an intruder that just arrived on the TSR
boundary. We now generalize this concept to find the maximum angular
separation to be able capture an intruder located at an arbitrary radial
location of $r_{\rm A}$. That is, given a defender located at
$r\hat{\mathbf{u}}(\theta_{\rm D})$, it is able to capture an intruder
currently located at $r_{\rm A}\hat{\mathbf{u}}(\theta_{\rm A})$ by starting
the full information phase $t_{\rm eng}$ amount of time from now, if
$|\theta_{\rm D}-\theta_{\rm A}|\leq\theta_{\max}(t_{\rm eng},\theta_{\rm
eng},r,r_{\rm A})$, where $\theta_{\max}(t_{\rm eng},\theta_{\rm eng},r,r_{\rm
A})$ has the same expression as in (5) with $r_{\rm eng}$ being

$\displaystyle r_{\rm eng}=\big{(}(r_{\rm A}-t_{\rm eng}\nu)^{2}+\rho_{{}_{\rm
A}}^{2}+2(r_{\rm A}-t_{\rm eng}\nu)\rho_{{}_{\rm A}}\cos(\theta_{\rm
eng})\big{)}^{1/2}.$

By maximizing over $(t_{\rm eng},\theta_{\rm eng})$ with the constraint (4),
we find $\theta_{\max}(t_{\rm eng}^{o},\theta_{\rm eng}^{o},r,r_{\rm A})$ that
provides the capturability condition for an intruder located at a radial
distance of $r_{\rm A}$. Using $\theta_{\max}(t_{\rm eng}^{o},\theta_{\rm
eng}^{o},r,r_{\rm A})$, we define the capturable set $\Omega_{\rm cap}$ for a
given defender location $r\hat{\mathbf{u}}(\theta_{\rm D})$ as follows

$\displaystyle\Omega_{\rm cap}(r,\theta_{\rm D})=\\{(r_{\rm A},\theta_{\rm
A})~{}:|\theta_{\rm A}\\!-\\!\theta_{\rm D}|\leq\theta_{\max}\\!(t_{\rm
eng}^{o},\theta_{\rm eng}^{o},r,r_{\rm A}\\!)\\}.$ (6)

If an intruder is located at $r_{\rm A}\hat{\mathbf{u}}(\theta_{\rm A})$ such
that $(r_{\rm A},\theta_{\rm A})\in\Omega_{\rm cap}(r,\theta_{\rm D})$, then
that intruder is capturable. Thus, by computing this region $\Omega_{\rm
cap}(r,\theta_{\rm D})$, the defender can easily check which intruders are
capturable and which are not. In Fig. 3, we illustrate this region.

$o_{1}$$o_{2}$$o_{k}$

Figure 3: The cyan region represents $\Omega_{\rm cap}$ for a defender where
$\medbullet$ denotes its location.The blue curves represent the intersection
of each orbit $o_{i}$ with the region $\Omega_{\rm cap}$ which form the
capturable arcs, as discussed in Section V. The purple and the pink angular
sectors represent the angles ($\varphi_{1}$ and $\varphi_{k}$, respectively)
formed by the first and the last orbits.

###### Remark 2

$\Omega_{\rm cap}(r,\theta_{\rm D})$ is symmetric about $\theta_{\rm D}$ and
furthermore, due to the circular symmetry, $\Omega_{\rm cap}(r,\theta_{\rm
D})$ obtained by rotating $\Omega_{\rm cap}(r,0)$ by angle $\theta_{\rm D}$,
for every $r$. $\triangle$

###### Remark 3

Let the defender be located at a point $r\hat{\mathbf{u}}({\theta_{\rm D}})$.
For any intruder located at $r_{\rm A}\hat{\mathbf{u}}(\theta_{\rm A})$, the
defender is able capture this intruder if $(r_{\rm A},\theta_{\rm
A})\in\Omega_{\rm cap}(r,\theta_{\rm D})$. Furthermore, the full information
phase will start no later than $t_{\rm eng}^{o}$. Note that $t_{\rm eng}^{o}$
is only a function of the radial locations of the intruder ($r_{\rm A}$) and
the defender ($r$). Furthermore, for all $r_{\rm A}<\rho_{{}_{\rm
T}}+r_{{}_{\rm T}}$, it can be verified that $t_{\rm
eng}^{o}<\nicefrac{{\rho_{{}_{\rm A}}}}{{(1+\nu)}}+\nicefrac{{(r_{\rm
A}-r_{{}_{\rm T}})}}{{\nu}}$. $\triangle$

###  III-B Full Information Phase

In this phase of the game, both agents can sense each other. As soon as the
intruder senses the defender it computes the instantaneous Apollonius circle
and checks whether this configuration leads to a capture or breach by checking
whether this circle intersects with the target or the TSR boundary,
respectively.

Let the intruder and defender locations at the start of the engagement phase
be $\mathbf{x}_{\rm A}$ and $\mathbf{x}_{\rm D}=\mathbf{x}_{\rm
A}+\rho_{{}_{\rm A}}\hat{\mathbf{u}}(\theta_{\rm eng})$, respectively.
Therefore, the Apollonius circle center will be at $\mathbf{x}_{\rm
C}=\alpha\mathbf{x}_{\rm A}-\beta\mathbf{x}_{\rm D}=\mathbf{x}_{\rm
A}-\beta\rho_{{}_{\rm A}}\hat{\mathbf{u}}(\theta_{\rm eng})$. Let us denote
$\mathbf{x}_{\rm A}\equiv r_{\rm A}\hat{\mathbf{u}}(\theta_{\rm A})$ and
$\mathbf{x}_{\rm C}\equiv r_{\rm C}\hat{\mathbf{u}}(\theta_{\rm C})$, and
consequently,

$\displaystyle\theta_{\rm C}=\tan^{-1}\bigg{(}\frac{r_{\rm A}\sin(\theta_{\rm
A})-\beta\rho_{{}_{\rm A}}\sin({\theta_{\rm eng}})}{r_{\rm A}\cos(\theta_{\rm
A})-\beta\rho_{{}_{\rm A}}\cos({\theta_{\rm eng}})}\bigg{)}.$ (7)

Therefore, the point $\textbf{x}_{p}$ on the Apollonius circle that is
farthest from the target center will be at

$\displaystyle\textbf{x}_{p}=\mathbf{x}_{\rm C}+\gamma\rho_{{}_{\rm
A}}\hat{\mathbf{u}}(\theta_{\rm C}),$ (8)

since the radius of the Apollonius circle is $\gamma\rho_{{}_{\rm A}}$.

Since the engagement point is chosen to be on the engagement surface, one may
verify that $\|\textbf{x}_{p}\|=r_{{}_{\rm T}}+2\gamma\rho_{{}_{\rm A}}$. That
is every capture will occur on a circle of radius $r_{{}_{\rm
T}}+2\gamma\rho_{{}_{\rm A}}$. This helps us analyzing the game since, after
capturing an intruder, the defender always starts it next pursuit from this
circle. Therefore, the defender can precompute the capturability region
$\Omega_{\rm cap}(r_{{}_{\rm T}}+2\gamma\rho_{{}_{\rm A}},0)$ and using Remark
2 can compute its instantaneous capturable region for any $\theta_{\rm D}$.

###### Remark 4

Although $\textbf{x}_{p}$ is the point that is furthest from the target, the
intruder still may chose to not move towards $\textbf{x}_{p}$ and get captured
at a different point on the Apollonius circle. Based on Lemma 1, we can
construct a pursuit strategy for the defender which will ensure that the
intruder cannot get out of the Apollonius circle. For the subsequent analysis,
we will assume that the intruder gets captured at $\textbf{x}_{p}$.
$\triangle$

During this phase, an intruder (say intruder $i$) might sense the defender
while the defender is pursuing another intruder. At this moment, intruder $i$
constructs the Apollonius circle and checks whether it can breach. If it
cannot breach but escape is possible, then this intruder confirms that the
defender has targeted another intruder since a rational defender will not
waste time by engaging with an intruder that can escape. If neither breach nor
evasion is possible, the intruder moves toward the point $\textbf{x}_{p}$ for
an infinitesimal amount of time and checks whether the defender has also moved
toward $\textbf{x}_{p}$. If the defender did not move toward $\textbf{x}_{p}$,
the intruder concludes that the defender is pursuing another intruder and
hence intruder $i$ resumes moving radially toward the target. Otherwise, they
continue their motion toward $\textbf{x}_{p}$ and capture happens.

##  IV Defender Strategy

The game begins with the defender being located at the center of the target.
The first intruder appears on the TSR boundary at time $t=0$. Since this
intruder is guaranteed to be captured due to Assumption (2), the defender
moves to the closest engagement point and waits until the intruder senses the
defender. As soon as the intruder senses the defender, the full information
phase starts and capture would take place on the Capture Circle as discussed
in Section III-B. One may also verify that this intruder will be captured at
time $t=(\nicefrac{{\rho_{{}_{\rm T}}}}{{\nu}})+2\gamma\rho_{{}_{\rm A}}$. New
intruders will appear randomly on the TSR boundary at every $T$ amount of
time, where $T$ is the arrival period. By the time the first intruder is
captured, $\lfloor\nicefrac{{(\nicefrac{{\rho_{{}_{\rm
T}}}}{{\nu}}+2\gamma\rho_{{}_{\rm A}})}}{{T}}\rfloor$ new intruders would have
appeared and, depending on the game parameters, some of them may even have
breached while the defender was pursuing the first one, e.g., if
$2\gamma\rho_{{}_{\rm A}}<T$, then the second intruder would have breached.
After the first capture, the defender is located on the capture circle and
makes a decision on how and which intruder to pursue. In this paper we propose
three strategies for the defender to decide which intruder to pursue, namely:
Nearest Agent, Earliest Breach, and Weighted Distance strategy.

###  IV-A Nearest Agent Strategy

In this strategy, the defender considers the intruder nearest to it to pursue.
If the nearest intruder was capturable – which can be easily decided by
checking whether that intruder lies within $\Omega_{\rm cap}$ – the defender
will find the earliest engagement point $(t_{\rm eng},\theta_{\rm eng})$ that
lies on the engagement surface of this intruder and reachable by this
defender, i.e., given $\mathbf{x}_{\rm A}(t_{0})$, the defender solves the
following optimization problem

$\displaystyle\begin{split}\min\nolimits_{t_{\rm eng},~{}\theta_{\rm
eng}}~{}~{}~{}&t_{\rm eng}\\\ \text{subject to }~{}~{}&(t_{\rm
eng},\theta_{\rm eng})\in S_{\rm engage}(\mathbf{x}_{\rm A}(t_{0})),\\\
&\|\mathbf{x}_{\rm A}(t_{0}+t_{\rm eng})+\rho_{{}_{\rm
A}}\hat{\mathbf{u}}(\theta_{\rm eng})-\mathbf{x}_{\rm D}(t_{0})\|\leq t_{\rm
eng}.\end{split}$ (9)

The defender start the full information phase at this earliest possible
engagement location. In this way, the defender minimizes the time to start the
engagement phase so that it has more time pursue the other intruders. If the
nearest intruder is not capturable, it checks whether the second nearest one
is capturable, and so on. If none of the available intruders in the TSR is
capturable, i.e., none of the intruders are within $\Omega_{\rm cap}$, the
defender moves radially toward the center of the target until a new intruder
appears on the TSR boundary and then the defender checks the capturability of
this newly arrived intruder. If this intruder is not capturable then the
defender keeps moving toward the target center and will check capturability of
the next intruders appearing on the TSR boundary. This process repeats until
an intruder arrives that is capturable, or the defender is less than
$(\nicefrac{{\rho_{{}_{\rm T}}}}{{\nu}})-r_{{}_{\rm T}}$ distance away from
the target center, in which case it is guaranteed to capture any incoming
intruder [18, Lemma 2]. For any capturable intruder, the defender picks the
earliest reachable engagement point, since minimizing the capture time gives
the defender more time to pursue other intruders.

###### Remark 5

The duration of the game between the defender and an intruder is comprised of
two components: the time ($t_{\rm eng}$) spent in the partial information
phase and the time to capture the intruder once the full information phase
starts. When capture occurs at $\textbf{x}_{p}$ defined in (8), the capture
time only depends on the choice of $\theta_{\rm eng}$, and given by the
expression $t_{\rm cap}\triangleq\alpha\rho_{{}_{\rm
A}}\\!\sqrt{1+\nu^{2}+2\nu\cos(\theta_{\rm eng}\\!-\\!\theta_{\rm C})}$, where
$\theta_{\rm C}$ is defined in (7). Therefore, one could consider $t_{\rm
eng}+t_{\rm cap}$ in (9) to minimize the total game duration instead of
minimizing the duration of the partial information phase ($t_{\rm eng}$).
$\triangle$

The optimization problem in (9) is solved numerically via exhaustive search in
this paper. Efficient techniques can be developed that leverages the geometry
of the engagement surface and left as a potential future work.

###  IV-B Earliest Breach Strategy

This strategy considers the intruders’ distances from the center of the
target. The objective is to prioritize the intruder that is the closest to
breach, which is analogous to the concept of Earliest Deadline First for
dynamic priority scheduling algorithms in real-time systems. In this approach,
the defender first computes the region $\Omega_{\rm cap}$ and considers the
intruder in this region that is closest to the target center. Similar to the
Nearest Agent Strategy, the defender’s objective here is also to minimize the
capture time, therefore, it picks the earliest engagement point. If
$\Omega_{\rm cap}$ does not contain any intruder, the defender moves toward
the target center until the next intruder appears on the TSR boundary.

Notice that the major difference between the Nearest Neighbor and Earliest
Breach strategies is how the defender prioritizes the intruders within
$\Omega_{\rm cap}$. If $\Omega_{\rm cap}$ is does not contain any intruder,
then both the algorithms will behave exactly the same.

Algorithm 1 Initialization $\&$ Intruder Arrival

1:Initialize $\mathbf{x}_{\rm D}\leftarrow[0,0]^{\intercal}$, $N_{\rm
capture}\leftarrow 0$, $n\leftarrow 1$, $\tilde{\rho}_{{}_{\rm
T}}\leftarrow(r_{{}_{\rm T}}+\rho_{{}_{\rm T}})$, and $N,T$ $\triangleright$
$N$ = total no. of arrivals

2:for $t=0:T:NT$ do

3: $\theta_{\rm A}(n)\sim{\mathcal{U}}(-\pi,\pi)$ $\triangleright$ Uniform
random arrival

4: $\mathbf{x}_{\rm A}(n)\leftarrow\tilde{\rho}_{{}_{\rm
T}}\hat{\mathbf{u}}(\theta_{\rm A}(n))$

5: $n\leftarrow n+1$

6:end for

Algorithm 2 Defender’s strategy

1:Initialize the weight $w\in[0,1]$ and the arrival process (Algorithm 1)

2:$t_{0}\leftarrow$ current time,

3:dist $\leftarrow\emptyset$ $\triangleright$ List of capturable intruders

4:for $n=1:m$ do $\triangleright$ $m$ = No. of intruders within TSR

5: if $\mathbf{x}_{\rm A}{{}_{,\,n}}(t_{0})\in\Omega_{\rm cap}(\mathbf{x}_{\rm
D}(t_{0}))$ then $\triangleright$ capturability test

6: dist${}_{n}\leftarrow w\|\mathbf{x}_{\rm
A}{{}_{,\,n}}(t_{0})\|+(1-w)\|\mathbf{x}_{\rm
A}{{}_{,\,n}}(t_{0})-\mathbf{x}_{\rm D}(t_{0})\|$

7: end if

8:end for

9:if dist$\neq\emptyset$ then

10: $\displaystyle i^{*}\leftarrow\arg\\!\\!\min_{n=1:m}{\tt dist}_{n}$
$\triangleright$ Pick the ‘closest’ intruder

11: $(t_{\rm eng},\theta_{\rm eng})\leftarrow$ Solution from (9) for
$\mathbf{x}_{\rm A}{{}_{,\,i^{*}}}$

12: Defender goes to ${\textbf{x}}_{\rm eng}$ $\triangleright$ Full Info.
phase starts

13: $N_{\rm capture}\leftarrow N_{\rm capture}+1$ $\triangleright$ capture
happens

14: $\mathbf{x}_{\rm D}\leftarrow\textbf{x}_{p}$ $\triangleright$
$\mathbf{x}_{\rm D}$ after capture

15:else

16: Defender gets closer to the target center until the next intruder appears
on the TSR boundary

17:end if

18:Repeat from Step 2

###  IV-C Weighted Distance Strategy

In this strategy, we propose a hybrid between the Nearest Agent and the
Earliest Breach strategies. In this approach, the defender instead of checking
the intruders’ distances from the target or from itself, it considers a convex
combination of these distances and picks the intruder within $\Omega_{\rm
cap}$ that has the lowest weighed distance. This weighted distance approach is
a generalized method that contains the previous two strategies as special
cases by appropriately choosing the weight. By adaptively changing the
weights, the defender will be able to efficiently adjust its behavior for more
complicated scenarios such as where the arrival is aperiodic. The pseudocode
is presented in Algorithms 1 and 2.

###### Remark 6

Note that all the algorithms have the same computational complexity since they
only differ in the weight $w$ used in line 6 of Algorithm 2.

##  V Performance Guarantee on Earliest Breach strategy

We measure the performance of the proposed strategies by their capture
fraction. Capture fraction is the ratio of the number of intruders captured
and the number of intruders arrived. In this section, we compute a lower bound
on this capture fraction for the Earliest Breach strategy.

Recall from our previous discussion that the defender minimizes the engagement
time, which depends on the location of the intruder. Therefore, the actual
engagement time is a random variable due to the random arrival points of the
intruder. The probability distribution of the earliest engagement time is
analytically and computationally intractable. To analytically compute a lower
bound on the capture fraction, we use an upper bound on this random variable.
We further assume that, after each capture, the defender waits for a new
intruder to appear on the TSR boundary before it checks whether $\Omega_{\rm
cap}$ contains any intruder or not. By this way, we are ensured that the
intruders will be located on a group of fixed circular orbits
$o_{1},o_{2},...,o_{k}$ with $T\nu$ distance from each other and the first
orbit being the TSR boundary itself. As shown in Fig. 3, for a given defender
location, just an arc on each orbit is capturable. These arcs are the
intersections between the orbits and the set $\Omega_{\rm cap}$.

Let $\varphi_{i}$ be the angle made by the arc associated with orbit $o_{i}$;
see Fig. 3. Therefore,

$\varphi_{i}=\theta_{\max}(t_{\rm eng}^{o},\theta_{\rm eng}^{o},r,r_{\rm
A})\big{|}_{r=r_{{}_{\rm T}}+2\gamma\rho_{{}_{\rm A}},~{}r_{\rm A}=r_{{}_{\rm
T}}+\rho_{{}_{\rm T}}-(i-1)T\nu}.$

The probability an intruder being located on that arc of orbit $o_{i}$ is
$\nicefrac{{\varphi_{i}}}{{2\pi}}$, since the intruders appear uniformly
randomly on the TSR boundary and move toward the target center radially
afterwards. Let $p_{{}_{\Omega}}$ denote the probability that there is at
least one intruder on one of these arcs. Therefore,

$p_{\Omega}=1-\prod\nolimits_{i=1}^{k}(1-q_{i}),$

where $k=\lceil\nicefrac{{\rho_{{}_{\rm T}}}}{{(T\nu)}}\rceil$ is the total
number of orbits.

With $1-p_{{}_{\Omega}}$ probability, there will not be any intruder within
$\Omega_{\rm cap}$ and therefore, the defender will move toward the target
center and check capturability of the next arriving intruder after $T$ amount
of time. The defender keeps moving toward the target center and keeps checking
capturability as soon as new intruder arrives. Let $p_{i}$ denote the
probability that the defender has been unsuccessful to find a capturable
intruder $i$ times in a row. Therefore, the defender will be at a radial
location of $r_{{}_{\rm T}}+2\gamma\rho_{{}_{\rm A}}-iT$. Note that, this
probability only depends on the intruder arriving on the TSR boundary, and
therefore is computed based on the maximum angular separation formula (5),
i.e., $p_{i}=\nicefrac{{\theta_{\max}(t_{\rm eng}^{*},\theta_{\rm
eng}^{*},~{}r_{{}_{\rm T}}+2\gamma\rho_{{}_{\rm A}}-iT)}}{{2\pi}}$. We now
present the lower bound of the Earliest Breach strategy in the following
lemma.

###### Lemma 2

For a given arrival period $T$, a lower bound on the capture fraction of the
Earliest Breach strategy is

$\displaystyle c_{\infty}\triangleq\frac{T(1-\nu)}{\rho_{{}_{\rm
A}}+(1-\nu)\tau_{\rm avg}},$ (10)

where $\tau_{\rm avg}$ is derived in Lemma 3. $\triangle$

###### Proof:

Let us consider that the defender just captured its $n$-th intruder and has
consumed $T_{n}$ amount of time, which is a random variable. The total time
consumed after capturing the $n+1$-th intruder is therefore

$\displaystyle T_{n+1}=T_{n}+\tau_{{\rm eng},\,\,(n+1)}+\tau_{{\rm
cap},\,\,(n+1)},$

where $\tau_{{\rm eng},\,\,(n+1)}$ is the time spent before the $n+1$-th full
information phase starts and $\tau_{{\rm{{cap}}},\,\,(n+1)}$ is the time to
capture the intruder as soon as both agents engage (i.e., the duration of the
full information phase). The latter is upper bounded by
$\nicefrac{{\rho_{{}_{\rm A}}}}{{1-\nu}}$. Therefore we may write

$\displaystyle T_{n+1}$ $\displaystyle\leq T_{n}+\tau_{{\rm
eng},\,\,(n+1)}+\frac{\rho_{{}_{\rm A}}}{1-\nu}\leq T_{1}+n\frac{\rho_{{}_{\rm
A}}}{1-\nu}+\sum\nolimits_{i=2}^{n+1}\tau_{{\rm eng},\,i}.$

We notice that the time consumed for capturing the first intruder is a
deterministic quantity $T_{1}=\frac{\rho_{{}_{\rm
T}}}{\nu}-\frac{\rho_{{}_{\rm A}}}{1+\nu}$.

The number of arrived intruders by time $T_{n+1}$ is
$\lfloor\frac{T_{n+1}}{T}\rfloor$. Therefore, the expected capture fraction
after capturing the $(n+1)$-th one can be written as

$\displaystyle
c_{n+1}=\mathbb{E}\Biggl{[}\frac{n+1}{\lfloor\frac{T_{n+1}}{T}\rfloor}\Biggr{]},$
(11)

which can be further simplified to

$\displaystyle
c_{n+1}\geq\mathbb{E}\Biggl{[}\frac{n+1}{\frac{T_{1}}{T}+\frac{n}{T}\frac{\rho_{{}_{\rm
A}}}{1-\nu}+\frac{1}{T}\sum\nolimits_{i=2}^{n+1}\tau_{{\rm
eng},\,i}-\frac{\epsilon}{T}}\Biggr{]},$

where $\epsilon\in[0,T)$ is a random variable such that
$\nicefrac{{(T_{n+1}-\epsilon)}}{{T}}$ is an integer. Using Jensen’s
inequality, we may write

$\displaystyle c_{n+1}$
$\displaystyle\geq\Biggl{[}\frac{n+1}{\frac{T_{1}}{T}+\frac{n}{T}\frac{\rho_{{}_{\rm
A}}}{1-\nu}+\frac{1}{T}\sum\nolimits_{i=2}^{n+1}\mathbb{E}[\tau_{{\rm
eng},\,i}]-\frac{\mathbb{E}[\epsilon]}{T}}\Biggr{]}$
$\displaystyle\geq\Biggl{[}\frac{n+1}{\frac{T_{1}}{T}+\frac{n}{T}\frac{\rho_{{}_{\rm
A}}}{1-\nu}+\frac{n}{T}\tau_{\rm
avg}-\frac{\mathbb{E}[\epsilon]}{T}}\Biggr{]},$ (12)

where $\tau_{\rm avg}$ is an upper bound to $\mathbb{E}[\tau_{{\rm
eng},\,i}]$, which is given in Lemma 3. Taking the limit $n\to\infty$, we
obtain

$\displaystyle\lim_{n\to\infty}c_{n+1}\geq\frac{T(1-\nu)}{\rho_{{}_{\rm
A}}+(1-\nu)\tau_{\rm avg}}=c_{\infty}.$

∎

###### Remark 7

Lemma 2 provides a lower bound for both finite $n$ as well as when
$n\to\infty$. As seen from (12), the effects of $T_{1}$ and $\epsilon$ become
negligible as $n$ increases. This behavior will also be noticed in the
simulation (see Fig. 4) where the capture fraction has a transient behavior
that stabilizes as the game progresses. $\triangle$

The following lemma provides the upper bound $\tau_{\rm avg}$.

###### Lemma 3

$\mathbb{E}\big{[}\tau_{{\rm eng},\,i}\big{]}$ is upper bounded by $\tau_{\rm
avg}$, where

$\displaystyle\tau_{\rm avg}=$ $\displaystyle p_{{}_{\Omega}}t_{\rm
eng}^{*}+(1-p_{{}_{\Omega}})\sum\nolimits_{j=1}^{\ell}\prod\nolimits_{i=1}^{j-1}(1-p_{i})p_{j}(t_{\rm
eng}^{*}+jT)$

where $\ell=\Big{\lceil}\frac{2r_{{}_{\rm T}}+2\gamma\rho_{{}_{\rm
A}}-\frac{\rho_{{}_{\rm T}}}{\nu}}{T}\Big{\rceil}$ and $\prod_{i=1}^{0}\equiv
1$. $\triangle$

###### Proof:

A detailed proof of this lemma has been omitted due to page limitations. A
sketch proof is provided below. If there is an intruder within $\Omega_{\rm
cap}$ then the maximum time to start the engagement phase is $t_{\rm
eng}^{*}$. Otherwise, the defender move toward the target center and try again
when a new intruder arrives $T$ amount of time later and so on until the
defender reaches a radial location of $(\nicefrac{{\rho_{{}_{\rm
T}}}}{{\nu}})-r_{{}_{\rm T}}$ or less, from where it is guaranteed to capture
any intruder appearing on the TSR boundary. ∎

##  VI Simulation Results

We simulate the game with the following parameters $r_{{}_{\rm T}}=4$,
$\rho_{{}_{\rm A}}=1,~{}\rho_{{}_{\rm T}}=5$, and $\nu=0.75$. Under this
parametric choice we conducted $100$ random trials of the game. In each trial
of this Monte-Carlo experiment, we considered a game duration of $10^{4}$
units with a period of $T=2$. The abscissa of Fig. 4 denotes the game duration
and the ordinate denotes the capture fraction up to that time. We have
compared our three proposed strategies where recall that $w=0$ corresponds to
the Earliest Breach strategy and $w=1$ for the Nearest Agent strategy. We have
considered $w=0.25,0.5$, and $0.75$ and simulated the Weighted Distance
strategy. For a short game duration ($<10^{2}$), it is observed form Fig. 4
that the defender performs the best under a Weighted Distance strategy with
weight $w=0.25$ and for a longer duration, we observe that the defender
performs better with the Earliest Breach strategy, although the difference in
performance is small. Although one might be tempted to conclude that a lower
value of $w$ is preferable, we also notice that $w=1$ performs reasonably well
for both short and long horizons and outperforms $w=0$ for shorter horizons.

Figure 4: Capture fraction versus Game duration for $10^{4}$ unit time of the
game. Cyan curve presented by $w=0$ is the Earliest Breach strategy and the
red curve presented by $w=1$ is the  Nearest Agent strategy.Weighted Distance
strategy with three coefficients $w=0.25,0.5,0.75$ are shown with green,
yellow and black curves respectively.

Keeping all the other parameters the same, we now vary the period $T$ and
compare the performances of the proposed algorithms, as shown in Fig. 5. In
addition, the lower bound on on the Earliest Breach strategy, as derived in
Lemma 10, is also plotted in this figure. For small (integer) periods starting
from 1 to 4, the defender captured more utilizing the Earliest Breach
strategy. For $T=5$, the Weighted Distance strategy with $w=0.75$ has the
highest capture fraction and for $T=6,7$ and $8$ the defender captured more
using the Nearest Agent strategy. From the period $T=9$ the capture fraction
utilizing any of the algorithms converged to a same number. For $T\geq 13$ the
defender is able to capture all the arriving intruders and hence the capture
fraction became 1.

###  VI-A Robotic Operating System Experiments

We conducted a simulation in the Robotics Operating System (ROS) for $10$
incoming intruders for a game duration of $20$ unit. The arrival period $T$
was chosen to be $2$. To compare our two strategies (Earliest Breach and
Nearest Agent), we considered the exact scenario including the arrival points
of the intruders. The defender performed differently for the two strategies.
The first intruder is captured the first by both the strategies. Afterwards,
the Earliest Breach strategy picked the fifth intruder, which was captured
next. Next, that strategy picked the ninth intruder but the capture was not
completed within the game duration or 20 time unit. For the Nearest Agent
strategy, defender was able to capture both the sixth and eighth arriving
intruders. Then the algorithm picked the tenth one, however, before the
defender could make noticeable progress, the game duration ended. The
trajectories of the defender for the Nearest Agent strategy and the Earliest
Breach strategy are demonstrated in Fig. 6.111 A short simulation video is
available at
https://drive.google.com/drive/folders/1Gz6L53BLB6qwfLYzvQDr5LeQEoXwsEya?usp=sharing.

Figure 5: The capture fraction is plotted against the intruder arrival period
$T$. The cyan (dashed) line represents the case $w=0$, i.e., the Earliest
Breach strategy and the magenta one represents $w=1$, i.e., the Nearest Agent
strategy. The Weighted Distance strategy with three coefficients $w=0.25,0.5$
and $0.75$ are shown with green, yellow, and black dashed lines respectively.
The derived lower bound on the capture fraction is shown in the blue dashed
line. Figure 6:  (Left) Nearest Agent, (Right) Earliest Breach. The sequence
of incoming intruders is enumerated with colored numbers from 1 to 10. The
trajectory of the defender is shown with blue lines. The gray arc is the
capture circle on which all the intruders get captured.

##  VII Conclusions

In this paper, we formulated a target defense game against a sequence of
periodically incoming intruders. Intruders move radially toward the target
center to breach the target boundary while the defender is tasked to capture
as many intruders as possible. Based on the available information to the
defender, it computes the capturability of an intruder using the notion of
Engagement Surface, and all of the captures occur on the perimeter of a fixed
circle called the Capture Circle. We proposed a generalized distance-based
strategy for the defender to prioritize the intruders to pursue and
analytically computed a lower bound on the capture fraction. Numerical studies
are presented to compare and contrast the performance over different arrival
periods.

A natural extension of this work would be to consider different arrival
patterns for the intruders (e.g. non-uniform probability of arrival locations,
multiple simultaneous arrivals). Furthermore, one may also consider a
heterogeneous team for the intruders where different intruders may have
different speed and sensing capabilities. In addition to these, extensions of
this work to arbitrary shaped target would be of extremely useful for real-
world applications.

## References

  * [1] C. Yan and T. Zhang, “Multi-robot patrol: A distributed algorithm based on expected idleness,” _International Journal of Advanced Robotic Systems_ , vol. 13, no. 6, 2016.
  * [2] T. Alam and L. Bobadilla, “Multi-robot coverage and persistent monitoring in sensing-constrained environments,” _Robotics_ , vol. 9, no. 2, 2020.
  * [3] Y. Lee and E. Bakolas, “Guarding a convex target set from an attacker in Euclidean spaces,” _IEEE Control Systems Letters_ , vol. 6, no. 6, 2022\.
  * [4] E. García, A. Von Moll, D. Casbeer, and M. Pachter, “Strategies for defending a coastline against multiple attackers,” in _58th IEEE Conference on Decision and Control_ , 2019, pp. 7319–7324.
  * [5] D. Shishika and V. Kumar, “A review of multi agent perimeter defense games,” in _Decision and Game Theory for Security: 11th International Conference, Proceedings_ , 2020, pp. 472–485.
  * [6] R. Isaacs, _Differential games: a mathematical theory with applications to warfare and pursuit, control and optimization_. Courier Corporation, 1999.
  * [7] Z. Zhou, R. Takei, H. Huang, and C. J. Tomlin, “A general, open-loop formulation for reach-avoid games,” in _51st IEEE Conference on Decision and Control_ , 2012, pp. 6501–6506.
  * [8] J. F. Fisac, M. Chen, C. J. Tomlin, and S. S. Sastry, “Reach-avoid problems with time-varying dynamics, targets and constraints,” 2014. [Online]. Available: https://arxiv.org/abs/1410.6445
  * [9] E. Garcia, D. W. Casbeer, and M. Pachter, “Optimal strategies for a class of multi-player reach-avoid differential games in 3D space,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 3, pp. 4257–4264, 2020\.
  * [10] L. Guerrero-Bonilla, C. Nieto-Granda, and M. Egerstedt, “Robust perimeter defense using control barrier functions,” in _International Symposium on Multi-Robot and Multi-Agent Systems_ , 2021, pp. 164–172.
  * [11] E. S. Lee, D. Shishika, G. Loianno, and V. Kumar, “Defending a perimeter from a ground intruder using an aerial defender: Theory and practice,” 2021. [Online]. Available: https://arxiv.org/abs/2109.02852
  * [12] S. Bajaj, E. Torng, S. D. Bopardikar, A. Von Moll, I. Weintraub, E. Garcia, and D. W. Casbeer, “Competitive perimeter defense of conical environments,” 2021\. [Online]. Available: https://arxiv.org/abs/2110.04667
  * [13] R. Yan, Z. Shi, and Y. Zhong, “Reach-avoid games with two defenders and one attacker: An analytical approach,” _IEEE Transactions on Cybernetics_ , vol. 49, no. 3, pp. 1035–1046, 2019.
  * [14] S. Bajaj and S. D. Bopardikar, “Dynamic boundary guarding against radially incoming targets,” in _58th IEEE Conference on Decision and Control_ , 2019, pp. 4804–4809.
  * [15] A. Adler, O. Mickelin, R. K. Ramachandran, G. S. Sukhatme, and S. Karaman, “The role of heterogeneity in autonomous perimeter defense problems,” 2022. [Online]. Available: https://arxiv.org/abs/2202.10433
  * [16] D. G. Macharet, A. K. Chen, D. Shishika, G. J. Pappas, and V. Kumar, “Adaptive partitioning for coordinated multi-agent perimeter defense,” in _International Conference on Intelligent Robots and Systems_ , 2020, pp. 7971–7977.
  * [17] D. J. Bertsimas and G. van Ryzin, “Stochastic and dynamic vehicle routing in the Euclidean plane with multiple capacitated vehicles,” _Operations Research_ , vol. 41, no. 1, pp. 60–76, 1993.
  * [18] A. Pourghorban, M. Dorothy, D. Shishika, A. Von Moll, and D. Maity, “Target defense against sequentially arriving intruders,” in _IEEE 61st Conference on Decision and Control_ , 2022, pp. 6594–6601.
  * [19] D. Shishika, D. Maity, and M. Dorothy, “Partial information target defense game,” in _IEEE International Conference on Robotics and Automation_ , 2021, pp. 8111–8117.
  * [20] M. Dorothy, D. Maity, D. Shishika, and A. Von Moll, “One Apollonius circle is enough for many pursuit-evasion games,” 2021. [Online]. Available: https://arxiv.org/abs/2111.09205