# Competitive Perimeter Defense in Tree Environments

Richard L. Frost1 and Shaunak D. Bopardikar2 This work was sponsored by the
Army Research Laboratory and was accomplished under Cooperative Agreement
Number W911NF-17-2-0181.1Richard L. Frost is with the Department of Computer
Science and Engineering, Michigan State University<EMAIL_ADDRESS>D.
Bopardikar is with the Department of Electrical and Computer Engineering,
Michigan State University

###### Abstract

We consider a perimeter defense problem in a rooted full tree graph
environment in which a single defending vehicle seeks to defend a set of
specified vertices, termed as the perimeter from mobile intruders that enter
the environment through the tree’s leaves. We adopt the technique of
competitive analysis to characterize the performance of an online algorithm
for the defending vehicle. We first derive fundamental limits on the
performance of any online algorithm relative to that of an optimal offline
algorithm. Specifically, we give three fundamental conditions for finite, 2,
and $\frac{3}{2}$ competitive ratios in terms of the environment parameters.
We then design and analyze three classes of online algorithms that have
provably finite competitiveness under varying environmental parameter regimes.
Finally, we give a numerical visualization of these regimes to better show the
comparative strengths and weaknesses of each algorithm.

##  I Introduction

This paper considers a perimeter defense problem in a tree environment in
which a single defending vehicle moving along the tree’s edges tries to
intercept intruders before they enter a certain region called the perimeter.
We confine ourselves to a class of trees known as full trees, which have the
greatest possible number of intruder entrances and the largest perimeter for a
given tree and perimeter depth. Tree graphs are commonly used to abstract
indoor environments, tunnels and road networks, and therefore, this scenario
arises anytime it is necessary for an autonomous surveillance vehicle to
intercept/track targets in such an environment. The full tree environment
narrows as intruders approach the perimeter region making this scenario
particularly prescient in situations where targets must converge to a finite
number of chokeholds such as insect swarms descending on a food source or
vehicles stopping at a refueling point. This perimeter defense problem is
_online_ in the sense that the defending vehicle has complete information of
an intruder only when it is present in the environment and is not aware of
when or where new intruders will enter the environment.

Perimeter defense problems have previously been studied in a variety of
environments under varying assumptions (cf. the survey [1]). These studies
tend to focus on strategies for either a small number of intruders [2] or
intruders released as per some stochastic process [3, 4, 5]. These problems
have also been extensively studied in the context of reach-avoid and pursuit-
evasion games [6, 7]. However, these works typically do not consider a worst-
case scenario in which large numbers of intruders are deployed strategically
to overwhelm the defender(s). Recognizing this, [8] and [9] utilized the
competitive analysis technique to design algorithms for worst case inputs in
continuous space (linear/planar conical) environments by using competitive
analysis. This technique [10, 11] characterizes the performance of an online
algorithm by comparing its performance to that of an optimal offline algorithm
on the same input. This value is known as the _competitive ratio_ of an online
algorithm.

Another related body of work is graph clearing in which a team of searching
agents try to capture a mobile intruder who is aware of the searcher’s
locations. Strategies for locating both mobile (or static) intruders in such a
scenario were explored for graphs by [12], and also with partial information
[13, 14]. Determining the number of searchers necessary to guarantee the
capture of the intruder is known to be NP-complete for general graphs, but can
be found in linear time for trees [15]. Similarly, determining an optimal
search strategy is NP-hard on graphs, but polynomial time for trees [16]. This
differs from the perimeter defense problem considered here in that we have
only a single defender and each intruder is locked to a fixed course.

In this paper, we consider a rooted full tree environment with edges of unit
length, total depth $d\in\mathbb{N}$, and all vertices of distance less that
$d$ from the root having $\delta\in\mathbb{N}$ children. We assume that
capture can happen anywhere along an edge and not necessarily at a vertex. All
vertices at a distance of $\rho\in\\{1,\dots,d\\}$ from the root serve as a
perimeter that every intruder released at the tree’s leaves tries to reach by
moving at a fixed speed $v<1$. A single defending vehicle moves with a maximum
speed of 1 in the tree to capture intruders before they reach the perimeter.

The primary contribution of this paper is to generalize the scope of the
algorithmic strategies and fundamental limits derived for linear [8] and
conical [9] environments to a new class of tree-based environments.
Specifically, we establish necessary conditions for the intruder velocity $v$
in terms of the tree parameters $d$, $\rho$, and $\delta$ for any online
algorithm to be $c$-competitive for a finite $c$, 2-competitive, or
$\frac{3}{2}$-competitive (Section III). We design three online algorithms
that have provable competitiveness under certain parameter regimes.
Specifically, we give an algorithm that 1-competitive, an algorithm whose
competitiveness is a function of $\delta$ and $\rho$ for the environment, and
a class of algorithms whose competitiveness varies based on a sweeping depth
parameter (Section IV). Finally, we provide a numerical visualization of the
parameter regimes in which the fundamental limits and the algorithm guarantees
apply (Section V).

##  II Problem Formulation

In this section, we formally introduce the models of the environment, the
defending vehicle and the intruder motion.

Consider a weighted, cycle-free graph $T=(V,E,w)$ rooted at some vertex $r\in
V(T)$ with $w:E(T)\rightarrow 1$. For vertices $v_{i},v_{j}\in V(T)$, we say
that $v_{i}$ is the _child_ of $v_{j}$ if $(v_{i},v_{j})\in E(T)$ and
$\textit{dist}(v_{i},r)>\textit{dist}(v_{j},r)$, where the distance
$\textit{dist}\,:V\times V\to\mathbb{R}_{\geq 0}$ denotes the shortest
distance between any two vertices measured over the edges connecting them. The
following is a formal definition of a _full tree_ , i.e., the environments
considered in this paper.

######  Definition 1 (Full Tree)

A weighted, cycle-free graph $T$ rooted at $r$ with depth $d\in\mathbb{N}$ and
branching factor $\delta\geq 2$ is a full tree if every vertex of $T$ has
exactly $\delta$ child vertices save for those of distance $d$ from $r$,
termed as the leaves, which have no child vertices.

An environment $\mathcal{E}(d,\delta,\rho)$ is the full tree with depth $d$
and branching factor $\delta$ rooted at some vertex $r$. Within
$\mathcal{E}(d,\delta,\rho)$ is the perimeter $\mathcal{P}(\rho)$ defined as
the induced subtree consisting of $r$ and all vertices $v$ such that
$dist(v,r)\leq\rho$ for some whole number $1\leq\rho<d$. Note that
$\mathcal{P}(\rho)$ is a full tree rooted at $r$ with depth $\rho$ and
branching factor $\delta$. We define the set of perimeter vertices for an
environment, $P(\mathcal{E})$, as the set of all vertices $v$ such that
$dist(v,r)=\rho$. Alternatively, this can be thought of as the set of all
vertices in $\mathcal{P}(\rho)$ with degree one. As $\mathcal{P}(\rho)$ is a
full tree, the number of vertices $|P(\mathcal{E})|=\delta^{\rho}$. Next, we
define the set of intruder entrances for an environment, $L(\mathcal{E})$, as
the set of all vertices $v$ such that $dist(v,r)=d$. Again there is an
alternate description of $L(\mathcal{E})$ as the set of all vertices with
degree one in $\mathcal{E}$. This gives us that $|L(\mathcal{E})|=\delta^{d}$.

#### Intruders

An intruder is a mobile agent that enters the environment at some time during
the scenario from any of vertices in $L(\mathcal{E})$. After entering the
environment, an intruder moves at a fixed speed $v\in(0,1)$ towards the
nearest vertex in $P(\mathcal{E})$. Intruders cannot change their direction or
speed.

#### Defending Vehicle

As in [8], the defense is a single vehicle with motion modeled as a first
order integrator. The defending vehicle always begins at the root vertex $r$
and can freely transverse the environment via its edges, moving at a maximum
speed of unity. We also say that the defender is aware of the intruder
velocity $v$.

#### Capture and Loss

An intruder is said to be captured if its location coincides with that of the
defender before the intruder reaches a perimeter vertex. An intruder is said
to be lost if it reaches a perimeter vertex without being captured. We give
ties in capture/loss to the defender, which is to say that an intruder may be
captured exactly on a perimeter vertex without being lost.

Since the weight function $w$ assigns unit length to each edge in the
environment, the defender can traverse an edge in 1 time unit, while an
intruder requires $\frac{1}{v}$ time units to do the same. The edges of the
environment graph do not merely represent connectivity between vertices, but
constitute continuous one dimensional spaces. Thus, at any time instant, a
vehicle (defender or intruder) may be located either at a vertex or at some
location on an edge. Consider an edge in $e$ and let $v_{i}$ and $v_{j}$ be
the vertices incident to it such that $dist(v_{i},r)<dist(v_{j},r)$. We map
the location of a vehicle on edge $e$ to the interval $[0,1]$ such that 0
corresponds to $v_{i}$ and 1 corresponds to $v_{j}$. Thus, the location of a
vehicle at time instant $t$ is given by a tuple $(e,l)$, where $e$ is an edge
and $l\in[0,1]$. We then define the set of intruder locations $\mathcal{Q}(t)$
as the location tuples of all intruders in the environment at time instant
$t$. Now consider a three-tuple of the form $(t,N(t),Z)$ where $t$ is a time
instant, $N(t)$ is the number of intruders released at time $t$, and $Z$ is a
set consisting of the intruder entrances that the $N(t)$ intruders will be
released at. An input instance $\mathcal{I}$ is the set of such tuples for all
$0\leq t\leq T$, where $T$ is some final time instant. Note that given
$\mathcal{I}$ and the intruder velocity $v$, it is possible to derive
$\mathcal{Q}(t)$ for any $t\leq T$. We can now formally define online and
offline algorithms for the defending vehicle.

Figure 1: An environment with depth $d=2$, perimeter depth $\rho=1$, and
branching factor $\delta=2$. The small purple dots represent the intruders
trying to reach perimeter vertices $p_{1}$ and $p_{2}$ after arriving from
intruder entrances $\ell_{1}$ and $\ell_{4}$. The defending vehicle is
represented by the blue triangle.

######  Definition 2 (Online Algorithm)

An online algorithm is a map
$\mathcal{A}:\mathcal{Q}(t)\rightarrow(\\{0,1\\},g\in V(\mathcal{E}))$, where
$V(\mathcal{E})$ is the vertex set of the environment. In short, $\mathcal{A}$
assigns the defender a speed of either 0 or 1 and a direction along the
shortest path between its current location and some vertex $g$ as a function
of the current locations of intruders in the environment and the intruder
velocity.

######  Definition 3 (Offline Algorithm)

An (optimal) offline algorithm is an algorithm
$\mathcal{O}:\mathcal{I}\rightarrow(\\{0,1\\},g\in V(\mathcal{E}))$ that
computes the defender’s speed and direction based on the input instance
$\mathcal{I}$. This algorithm is aware from the beginning of an instance of
all intruders that will be released, i.e., a non-causal algorithm.

######  Definition 4 (Competitive Ratio, [8, 9])

Given an environment $\mathcal{E}(d,\delta,\rho)$, an input instance
$\mathcal{I}$, an intruder velocity $v$, and an online algorithm
$\mathcal{A}$, let $\mathcal{A}(\mathcal{I})$ be the number of intruders from
$\mathcal{I}$ captured by a defender using $\mathcal{A}$. Now, let
$\mathcal{O}$ be an optimal offline algorithm that maximizes the number
$\mathcal{O}(\mathcal{I})$ of captured intruders from $\mathcal{I}$. Then, the
_competitive ratio of $\mathcal{A}$ on input instance $\mathcal{I}$_ is then
$c_{\mathcal{A}}(\mathcal{I})=\frac{\mathcal{O}(\mathcal{I})}{\mathcal{A}(\mathcal{I})}$.
The _competitive ratio of $\mathcal{A}$ for an environment $\mathcal{E}$_ is
$c_{\mathcal{A}}(\mathcal{E})=\sup_{\mathcal{I}}c_{\mathcal{A}}(\mathcal{I})$.
Finally, _the competitive ratio of an environment $\mathcal{E}$_ is
$c(\mathcal{E})=\inf_{\mathcal{A}}c_{\mathcal{A}}(\mathcal{E})$. We say that
an online algorithm $\mathcal{B}$ is _$c$ -competitive for an environment
$\mathcal{E}(d,\delta,\rho)$_ if $c_{\mathcal{B}}(\mathcal{E})\leq c$, for
some constant $c\geq 1$.

Note that it is preferable for an online algorithm to have a low competitive
ratio, as this corresponds to it having similar performance to what is
optimal. For instance, a 1-competitive algorithm matches the performance of an
optimal offline algorithm for all inputs. Under these definitions, determining
the competitive ratio of online algorithms is commonly done by considering
inputs that offer some clear advantage to an optimal offline that is not
available to an online defender.

_Problem Statement:_ The goal is to derive fundamental limits on the
competitiveness of any online algorithm and to design online algorithms for
the defender on the full tree environment and characterize their
competitiveness.

##  III Fundamental Limits

We give three fundamental limits on the competitiveness of any online
algorithm in terms of the environment’s parameters. First, we adapt the
results of [8] to the tree environment by finding optimal linear environments
embedded within the full trees to show bounds on finite and 2-competitiveness.
We then give a limit that is fully unique to the tree environment that bounds
where online algorithms can do better than $\frac{3}{2}$-competitive. We first
define some relevant concepts.

######  Definition 5 (Descendant Vertices)

For $v_{i},v_{j}\in V(\mathcal{E})$, if there exists a path from the root $r$
to some $\ell\in L(\mathcal{E})$ that includes both $v_{i}$ and $v_{j}$, we
say that $v_{i}$ is the descendant of $v_{j}$ if
$\textit{dist}(v_{i},r)>\textit{dist}(v_{j},r)$.

######  Definition 6 (Branch of a Tree Graph)

For a vertex $v\in V(\mathcal{E})$, the _branch of $\mathcal{E}$_ rooted at
$v$, denoted by $B(v)$, is the induced subgraph of $\mathcal{E}$ consisting of
$v$ and all descendants of $v$. Note that $B(v)$ is a full tree with branching
factor $\delta$ and depth $d-dist(r,v)$.

######  Definition 7 (Branch Entrances)

For a branch $B(v)$, the _Branch Entrances_ are $ent(B(v))=L(\mathcal{E})\cap
V(B(v))$.

###### Theorem III.1

For any environment $\mathcal{E}=(d,\delta,\rho)$, if the intruder velocity
$v>\frac{d-\rho}{2\rho}$, then there does not exist a $c$-competitive
algorithm.

This first result, whose proof is presented in the Appendix, characterizes
parameter regimes for which no online algorithm can be finitely competitive.
The ratio corresponds to the time for the defender to move between perimeter
vertices exceeding the time it takes a newly released intruder to be lost.
This next result shows when an online algorithm can not do better than 2
competitive. Notably, the proof technique for this result is unique to the
tree, as it relies on having multiple intruder entrances under each perimeter
vertex.

###### Theorem III.2

For an environment $\mathcal{E}=(d,\delta,\rho)$, if
$v\geq\frac{d-\rho}{d+\rho}$, then $c(\mathcal{E})\geq 2$.

###### Proof.

We first select two perimeter vertices, $p_{i}$ and $p_{j}$ such that
$dist(p_{i},p_{j})=2\rho$. We then show that for two input instances of two
intruders each, we can guarantee that only a single intruder can be captured
by an online algorithm, while an optimal offline can always capture both. Let
$\ell_{i}\in ent(B(p_{i}))$ and $\ell_{j}\in ent(B(p_{j}))$.

We first show the result when $v=\frac{d-\rho}{d+\rho}$. Consider an input
where a single intruder is released at each of $\ell_{i}$ and $\ell_{j}$ at
time $d$. The only possible method to capture both intruders in this input is
for the defender to be located at either of $\ell_{i}$ or $\ell_{j}$ at time
$d$ (capturing one intruder right away) and then moving immediately to either
$p_{j}$ (if it first captured the intruder at $\ell_{i}$) or $p_{i}$ (if it
first captured the intruder at $\ell_{j}$). Since it takes $d$ times units to
reach either of $\ell_{i}$ or $\ell_{j}$ from $r$, any algorithm that does not
immediately begin moving to either $\ell_{i}$ or $\ell_{j}$ at the start of
the scenario can be at best 2-competitive. However, since an online algorithm
cannot know which of the intruder entrances will be $\ell_{i}$ and which will
be $\ell_{j}$, there always exists an alternate input instance when the
location it arrives at is incorrect. Meanwhile, an optimal offline algorithm
is aware of the correct vertex to move to and can always capture both
intruders.

For the case when $v>\frac{d-\rho}{d+\rho}$, we can use a similar input where
an intruder is released at $\ell_{i}$ at time $d$ and a second intruder is
released at $\ell_{j}$ at time $2d+\rho-\frac{d-\rho}{v}$. The only method to
capture this input is to arrive at $\ell_{i}$ at time $d$ (capturing the first
intruder) and then immediately moving to $p_{j}$ to capture the second
intruder. Once again, an online algorithm’s lack of knowledge on which
intruder entrance will be $\ell_{i}$ means that there always exists an input
where any given algorithm loses an intruder.

In summary, we have described two classes of inputs such that, without prior
knowledge of where the intruders will be deployed, no single online algorithm
can capture both intruders. Since there exist offline algorithms that capture
all intruders in these inputs, no online algorithm can be better than
2-competitive, and the result follows. ∎

The next result, proven in the Appendix, shows regions where no online
algorithm can do better than $\frac{3}{2}$-competitive.

###### Theorem III.3

For an environment $\mathcal{E}(d,\delta,\rho)$ such that $\delta\geq 3$, if
the following two conditions hold:

$\frac{d-\rho}{d+3\rho}\leq v<\frac{d-\rho}{d+\rho},\text{ and }$ (1)
$d+\rho+2(d-\rho)\frac{1-v}{1+v}-\frac{2\epsilon v}{1+v}>\frac{d-\rho}{v},$
(2)

for $\epsilon=d+3\rho-\frac{d-\rho}{v}$. Then,
$c(\mathcal{E})\geq\frac{3}{2}$.

Although this result shows only $\frac{3}{2}$-competitiveness, it bounds the
competitiveness of online algorithms in a region that has not previously been
explored, by using inputs that are unique to the tree environment.

##  IV Algorithms

We now present online algorithms for the defending vehicle and analyze their
competitiveness.

###  IV-A Sweeping Algorithm

In this algorithm, the defending vehicle continuously transverses every edge
in the tree in a fixed order. Finding such a walk is analogous to finding the
shortest length closed walk with starting vertex $r$ that incorporates every
edge of the tree in question. For a tree, this walk can be found easily by
following the path induced by a _depth-first-search_ on the tree beginning at
$r$. We will assume that a Sweeping algorithm follows the path of a depth-
first-search that chooses the left-most unvisited vertex when it must make a
decision.

###### Lemma 1

The length of one iteration of a Sweeping algorithm on an environment with
depth $d$ and branching factor $\delta$ is
$2((\frac{\delta^{d+1}-1}{\delta-1})-1)$.

This result follows from the fact that each edge in the tree must be traversed
exactly twice, and yields the following.

###### Theorem IV.1

A Sweeping algorithm is 1-competitive if

$v\leq\frac{d-\rho}{2((\frac{\delta^{d+1}-1}{\delta-1})-1)-(d-\rho)}$ (3)

Otherwise, it is not $c$-competitive for any finite $c$.

###### Remark 1

This result characterizes the fact that all intruders in an input can
certainly be captured, even in an online setting, if the intruder velocity is
sufficiently small.

###  IV-B Stay At Perimeter Algorithm

We next give an adaptation of an algorithm first presented in [9] that allows
for a significantly more permissive parameter regime at the cost of an
exponential competitive ratio, Stay at Perimeter (SaP). This algorithm breaks
up time into epochs of duration in the interval $[2\rho v,4\rho v]$. During
each epoch, the defending vehicle either waits at one of the perimeter
vertices of the environment, capturing any intruders that are headed toward
that location or travels to a new perimeter vertex and waits there. The
algorithm breaks up the each of the subtrees rooted at every perimeter vertex
into three regions that represent the trade off for moving to a new perimeter
vertex from the current one.

The SaP algorithm is detailed in Algorithm 1. We provide a brief overview of
the terminology necessary to understand the algorithm. Let
$p_{1},\dots,p_{\delta^{\rho}}$ be the perimeter vertices the environment, and
let $P_{1},\dots P_{\delta^{\rho}}$ be the subtrees given by
$B(p_{1}),\dots,B(p_{\delta^{\rho}})$. For a subtree $P_{k}$, the regions
$S^{1}_{k}$, $S^{2}_{k}$, and $S^{3}_{k}$ are defined as all locations in
$P_{k}$ whose distance from $p_{k}$ are in the intervals $[0,2\rho v]$,
$[2\rho v,4\rho v]$, and $[4\rho v,6\rho v]$ respectively. We denote the
number of intruders present in each of these regions as $|S^{h}_{k}|$ for
$h\in\\{1,2,3\\}$. Suppose, the defender is located at some perimeter vertex
$p_{j}$ at the beginning of an epoch. The algorithm finds the value
$\eta_{j}^{k}$ for each subtree $P_{k}$.

$\eta_{j}^{k}:=\begin{cases}|S_{k}^{2}|+|S_{k}^{3}|&\text{if }k\neq j\\\
|S_{j}^{1}|+|S_{j}^{2}|+|S_{j}^{3}|&\text{if }k=j\end{cases}$

Using these values of $\eta_{i}^{k}$, the algorithm decides if it should
remain at its current location $p_{j}$ in which case the epoch will be of
duration $2\rho v$, or if it should move to a different perimeter vertex and
wait there in which case the epoch will be of length $4\rho v$. This decision
takes into account that by leaving its current location to wait at some
different perimeter vertex $p_{n}$, the defender will lose all intruders in
$S_{j}^{1}$ and possibly all intruders in $S_{n}^{1}$.

Algorithm 1 Stay at Perimeter

1: Defender is at vertex $r$ and waits until time $2\rho$

2: $k^{*}$ =
$\operatorname*{arg\,max}_{k\in\\{1,\dots,\delta^{\rho}\\}}\\{\eta^{1}_{i},\dots,\eta^{\delta^{\rho}}_{i}\\}$,
set $P_{i}=P_{k^{*}}$

3: Move to vertex $p_{k^{*}}$ and wait until time $6\rho$

4: for  _each_ epoch do

5: $k^{*}$ =
$\operatorname*{arg\,max}_{k\in\\{1,\dots,\delta^{\rho}\\}}\\{\eta^{1}_{i},\dots,\eta^{\delta^{\rho}}_{i}\\}$

6: $P_{n}=P_{k^{*}}$

7: if $P_{n}\neq P_{i}$ and $|S_{o}^{2}|\geq|S_{i}^{1}|$ then

8: Move to vertex $p_{k^{*}}$

9: Wait for $2\rho v$ time units, capturing $|S_{o}^{2}|$

10: $P_{i}=P_{n}$

11: else

12: Remain at current vertex

13: Wait for $2\rho v$ time units, capturing $|S_{i}^{1}|$

14: end if

15: end for

Figure 2: Breakdown of an environment as perceived by the Stay at Perimeter
(SaP) algorithm. Here SaP considers the two branches rooted at $p_{1}$ and
$p_{2}$. The regions of the subtrees considered in each epoch are highlighted.
As long as the defender is located at $p_{1}$ all intruders from the left
subtree will be captured.

###### Theorem IV.2

For any environment that satisfies $v\leq\frac{d-\rho}{6\rho}$, Stay at
Perimeter is $\frac{3\cdot\delta^{\rho}-1}{2}$-competitive.

###### Proof.

To prove this result, we will establish a one to one correspondence between
the Stay at Perimeter (SaP) algorithm and the Stay Near Perimeter (SNP)
algorithm from [9] with the following modifications to its parameters. The
$n_{s}$ resting points of SNP become the $\delta^{\rho}$ perimeter vertices of
the full tree environment for SaP. The effect of positioning the defender at a
perimeter vertex in the full tree setting is equivalent to positioning a
defender at a resting point in the conical setting as it prevents the loss of
any intruder from the branch rooted at that vertex so long as the defender is
there. The need for a capture radius around the defender is eliminated in the
tree environment as the defender needs to only occupy a single point-like
location to block off that section of the perimeter from losses rather than a
region like in the cone. The sectors considered by SNP then become the
branches rooted at each perimeter vertex for SaP. The distance $D$ seen in the
description of SNP is equal to $2\rho$ in the full tree. This is because if
$p_{i}$ and $p_{j}$ are the perimeter vertices in a full tree environment
$2\leq dist(p_{i},p_{j})\leq 2\rho$. For this reason, the time intervals of
duration $Dv$ for the conical environment are equivalent to the the $2\rho v$
time intervals described above. Finally, as the full tree environments
considered here are of some whole number depth $d$ rather than the radius of 1
used in [9], our constraint for the existence of the intervals becomes
$\frac{d-\rho}{v}\leq 6\rho$.

With these modifications, the results of Lemmas IV.5 and IV.6 from [9] also
become applicable to SaP. This is because these results do not rely on any
specific property of the conical environment. Instead, they only depend on the
distance $D$, the number of sectors/resting points $n_{s}$, and the
comparisons made by SNP. As SaP has an equivalent notion of $D$ and $N_{s}$
and makes the same decisions as SNP based on these notions, we can carry
forward these results to our analysis. This gives us that: every two
consecutive intervals captured by SaP account for $3(\delta^{\rho}-1)$ lost
intervals, and every interval lost by SaP is accounted for by some captured
interval. Given that these results hold, we have that Stay at Perimeter is
$\frac{3\cdot\delta^{\rho}-1}{2}$-competitive when
$v\leq\frac{d-\rho}{6\rho}$. ∎

The parameter regimes under which the SaP algorithm can perform do not depend
on the branching factor $\delta$ of the environment, instead it only requires
that the previously mentioned regions are well formed. However, this is traded
for a competitive ratio dependent on the number of perimeter vertices in the
environment which does depend exponentially on $\delta$. In the next
algorithm, we will examine a strategy that seeks to strike a balance between
sweeping the entire tree and only waiting at the perimeter vertices.

###  IV-C Compare and Subtree Sweep Algorithm

We now present a new algorithm that sweeps only a portion of the environment,
allowing for a more permissive parameter regime. The Compare and Subtree Sweep
(CaSS) takes a single additional parameter, an integer sweeping depth $1\leq
s\leq\rho$, which determines both the competitiveness of the algorithm along
with the parameter regime under which that competitiveness can be achieved.
The algorithm breaks up time into epochs; during each epoch one of the
$\delta^{s}$ subtrees rooted at a vertex of distance $s$ from the root is
swept using the previously described sweeping method.

Compare and Subtree Sweep is defined in Algorithm 2 and is summarized as
follows. Let $a_{1},\dots a_{\delta^{s}}$ be the set of vertices of distance
$s$ from the root vertex $r$. Now consider the subtrees rooted at each of
these vertices. Each of these subtrees contain an equal, positive number of
perimeter vertices. For each vertex $a_{k}$, the capture region $A_{k}$ is
defined as all locations in the subtree rooted at $a_{k}$ whose distance below
a perimeter vertex is at least $\frac{1}{2}(d-\rho)$. We denote the number of
intruders present in $A_{k}$ as $|A_{k}|$. At the beginning of each epoch, the
defending vehicle is located at vertex $r$, where it identifies the capture
region with the greatest number of intruders $A_{*}$ (breaking any ties by
choosing the left most region). The defender then moves to the root vertex of
the subtree containing $A_{*}$, denoted $a_{*}$ and carries out the Sweeping
algorithm on the subtree starting at vertex $a_{*}$. The vehicle then returns
to $r$, and the next epoch begins.

Figure 3: The Compare and Subtree Sweep algorithm will follow the path in
purple when $s=1$ and $|A_{1}|>|A_{2}|$ (shown in blue). As $\rho=1$ in this
environment, there is only a single valid value for for $s$.

###### Lemma 2

For any environment such that,

$4v\left(s+\frac{\delta^{d-s+1}}{\delta-1}-1\right)\leq d-\rho,$

  * •

Every intruder that lies in $A_{*}$ at the beginning of an epoch $k$ is
captured by Compare and Subtree Sweep with sweeping depth $s$, and

  * •

Any intruder that enters the environment during the course of an epoch $k$ is
either captured during epoch $k$ or is located in a capture region during
epoch $k+1$.

###### Proof.

We begin by considering the length of time taken by the defending vehicle to
complete a single epoch. The vehicle must first travel from $r$ to the root of
the subtree containing $A_{*}$ taking time $s$. The defender must then
complete a single iteration of the Sweeping algorithm on the subtree. Since
the subtree in question is of depth $d-s$ and the defending vehicle moves with
unit speed, Lemma 1 gives us that this takes time
$2(\frac{\delta^{d-s+1}-1}{\delta-1}-1)$. Finally, the vehicle must return to
the root taking another $s$ time units. Thus a single epoch takes a total of
$2(s+\frac{\delta^{d-s+1}-1}{\delta-1}-1)$ time units. This means that an
intruder in $A_{*}$ can move at most distance
$2v(s+\frac{\delta^{d-s+1}-1}{\delta-1}-1)$ during an epoch. Even assuming
that the intruder is as close to a perimeter vertex as possible, while being
within $A_{*}$ and is moving at the maximum velocity permitted by the
constraint above, it can only travel at most distance $\frac{1}{2}(d-\rho)$.
However, during this time the entire subtree containing $A_{*}$ has been
traversed by the defender and the defender has returned to the root, implying
that that the intruder in question has been captured. The first result
follows.

For the second result, we first consider the case that an intruder enters the
environment in a different subtree than $A_{*}$ for epoch $k$. Suppose that it
enters in the subtree containing capture region $A_{j}$. We first note that
the region $A_{j}$ includes the intruder entrances for the subtree and thus
the intruder begins in the capture region $A_{j}$. By the same analysis as
above, the furthest an intruder can travel in an epoch is
$\frac{1}{2}(d-\rho)$. Thus, even given the maximum travel time within epoch
$k$ (which would occur when the intruder enters just as epoch $k$ begins), the
intruder still lies within the capture region as epoch $k+1$ begins and the
result follows. We now consider the case that an intruder enters the
environment in the same subtree as $A_{*}$ for epoch $k$. There exist time
intervals within epoch $k$ such that intruders arriving in those intervals
will be captured in epoch $k$ and thus will not be located in a capture region
during epoch $k+1$. The most obvious of these intervals is the first $s$ time
units of epoch $k$, where the defending vehicle is moving to vertex $a_{*}$.
Intruders entering during this interval will be within the subtree rooted at
$a_{*}$ at the beginning of the sweep and will be captured during it. The
other intervals arise from the order in which the Sweeping algorithm visits
intruder entrances in $A_{*}$. First note that the Sweeping algorithm visits
every intruder entrance in $A_{*}$ exactly once from left to right. Intruders
that enter during the course of epoch $k$ at an intruder entrance that has not
yet been visited during the sweep will be captured in epoch $k$ as they are
still in the path of the sweep. Meanwhile, intruders that enter at an intruder
entrance that has been already been visited during epoch $l$ will still be in
the capture region during epoch $k+1$ by the same token as in the previous
case. This concludes the proof of the second result. ∎

###### Theorem IV.3

Compare and Subtree Sweep with sweeping depth $s$ is $\delta^{s}$-competitive
in environments where

$4v\left(s+\frac{\delta^{d-s+1}}{\delta-1}-1\right)\leq d-\rho$

###### Proof.

From Lemma 2, we ensure that Compare and Subtree Sweep captures
$\frac{1}{\delta^{s}}$ of all intruders entering the environment in every
epoch. The result follows. ∎

Algorithm 2 Compare and Subtree Sweep

1: Defender is at vertex $r$ and waits for
$2(s+\frac{\delta^{d-s+1}}{\delta-1}-1)$ time units after the arrival of the
first intruder

2: for each epoch do

3: $A_{*}$ = $\operatorname*{arg\,max}\\{|A_{1}|,\dots,|A_{\delta^{s}}|\\}$

4: $a_{*}$ = root vertex of subtree containing $A_{*}$

5: Move to $a_{*}$ and perform a Sweep on $A_{*}$

6: Move to $r$

7: end for

Figure 4: Parameter regimes for fundamental limits, Sweeping algorithm, and
Stay Near Perimeter Algorithm for varying values of $\rho$ on a full tree with
depth $d=20$ and branching factor $\delta=3$.

##  V Numerical Visualizations

We give a numerical visualization of the bounds derived for the full tree
environment. Figure 4 shows the $(\frac{\rho}{d},v)$ parameter regimes for a
fixed value of $d=20$ and $\delta=3$ and a varying value of $\rho$. Each point
in the figure represents one of the possible integer values of $\rho$ for the
environment.

Values of $v$ above the points corresponding to Theorem III.1 and Theorem
III.2 correspond to velocities where there exist no $c$-competitive or no
algorithm whose performance is better better than 2-competitive, respectively.
The space between the points corresponding to Theorem III.3 and Theorem III.2
give intruder velocities for which no algorithm can do better than
$\frac{3}{2}$-competitive. Interestingly, this region only exists for
environments where $\frac{\rho}{d}<0.5$. This is due to the extra constraint
on the environment parameters required by Theorem III.3.

It is unsurprising that the bound for the Sweeping algorithm is close to zero
for all values of $\rho$ as the bound is exponential with respect to the
environment depth $d$. While the bound for the SaP Algorithm, is significantly
more permissive, it comes at the cost of exponential competitiveness with
respect to $\rho$. This may be an acceptable trade-off when $\rho$ is small.
However, a Sweeping strategy gives significantly better competitiveness for
only a slightly more strict speed requirement as $\rho$ approaches $d$.

Figure 5 shows the parameter regimes for which the Compare and Subtree Sweep
algorithm is effective for several different sweeping depths. We see that for
$d=5$ and $\delta=2$, CaSS offers a larger effective area than the Sweeping
algorithm for values of $s$ that exceed 1. Thus, it is not preferred to deploy
CaSS with $s=1$ for this combination of $d$ and $\delta$, as it offers a worse
competitive ratio at a stricter velocity requirement. This is not always the
case, however. For instance, setting $\delta=3$ causes CaSS to always eclipse
the parameter regime of the Sweeping algorithm.

Figure 5: Parameter regimes for Compare and Subtree Sweep Algorithm and
Sweeping Algorithm for all values of $\rho$ on a full tree with depth $d=5$
and branching factor $\delta=2$.

##  VI Conclusions and Future Directions

This paper analyzed a scenario in which a single defending vehicle must defend
a perimeter in a full tree environment from intruders that may enter at any
time. We gave and analyzed three algorithms for the defending vehicle each
with a provably finite competitive ratio. Specifically, the Sweeping algorithm
is 1-competitive, i.e. it matches the performance of an optimal offline, but
requires an exponentially scaling constraint on the intruder’s velocity. The
Compare and Subtree Sweep algorithm offers a slight improvement on this
constraint, and gives a range of competitiveness based on an externally chosen
sweeping depth. Finally, the Stay at Perimeter algorithm is very permissive in
terms of its constraint on the intruder velocity. However, this is at the cost
of an competitive ratio that scales exponentially with the perimeter depth
$\rho$, making it most effective when the perimeter size is small. We also
derived three fundamental limits on the competitiveness of any online
algorithm.

The work presented here suggests that there is a trade-off for online
algorithms between exponential competitiveness and exponentially low intruder
velocities. However, the exponential competitiveness results are based on the
implicit assumption that an optimal offline algorithm can capture all
intruders. To this end, future directions will include an improved worst-case
analysis for the optimal offline. Additionally, we plan to expand the current
analysis to trees that are not full, and create strategies for multiple
defenders.

###  -A Proof of Theorem III.1

Inspired by the idea from [8], we will construct an input instance for
$\mathcal{E}$ consisting of two parts: a stream and a burst. We first select
two perimeter vertices $p_{i},p_{j}\in P(\mathcal{E})$ such that
$dist(p_{i},p_{j})=2\rho$. Since $\mathcal{E}$ is a full tree and $\delta>1$,
there is always such a pair of vertices. Now select $\ell_{i}$ and $\ell_{j}$
arbitrarily from $ent(B(p_{i}))$ and $ent(B(p_{j}))$ respectively. Note that
intruders arriving at $\ell_{i}$ (resp. $\ell_{j}$) will be lost when they
arrive at $p_{i}$ (resp. $p_{j}$).

Let a burst of intruders, $burst(\ell,n)$, be the simultaneous arrival of $n$
intruders into the environment at intruder entrance $\ell\in L$. Further, let
a stream of intruders, $stream(\ell,t)$, be the repeated arrival of a single
intruder into the environment at intruder entrance $\ell\in L$ with a delay of
$t$ time units between arrivals. The first part of the input is a burst,
$burst(\ell_{j},c+1)$, that arrives at the earliest time that any online
algorithm arrives at $p_{i}$. The second part of the input consists of a
stream, $stream(\ell_{i},2d)$, beginning at time $d$ and terminating as soon
as the burst is released.

Suppose the defender adopts an algorithm that never moves to $p_{i}$. In this
case, the stream will not terminate and all released intruders will be lost.
Since an offline algorithm can move to $p_{i}$ before any intruders in the
stream are even released, it can capture all intruders in the stream. Thus,
the result holds for this class of online algorithms.

We now consider online algorithms that do eventually move to $p_{i}$ and show
that the result still holds. Suppose the online defender arrives at $p_{i}$ at
time $t$. At this time $t$, the burst will be released at $\ell_{j}$. Since
$v>\frac{d-\rho}{2\rho}$, the defender cannot reach $p_{j}$ before the burst
is lost. However, since an optimal offline algorithm is aware of the timing of
the burst’s release, it can always arrive at $p_{j}$ in time to capture it.

As there is no way for an online algorithm to capture any of the $c+1$
intruders in the burst, we must consider how many intruders from the stream
can be captured in order to find the competitive ratio. If $t<d$, then the
stream never begins and the online defender captures no intruders. Here, an
optimal offline can simply move to $p_{j}$ by time $t+\frac{d-\rho}{v}$, which
it can always do as $t\geq\rho$. Thus the competitive ratio is infinite for
this scenario. If $t=d$, then a single intruder from the stream has been
released when the burst is released. An online algorithm cannot capture the
burst but can capture the single stream intruder by just waiting at $p_{i}$.
Meanwhile, an optimal offline defender can once again ignore the single stream
intruder and capture the burst. As the offline algorithm captures $c+1$
intruders and the online captures only a single intruder, this class of online
algorithms is $c+1$-competitive. Finally, when $t>d$, we have at least the
same competitiveness result as when $t=d$. As the delay between stream
intruder releases is $2d$ there is only ever a single stream intruder present
in the environment at any given time. Thus the online defender can only ever
capture a single intruder from the stream. Again the offline defender can
always guarantee the capture of the burst guaranteeing $c+1$-competitiveness.
Indeed, if $t$ is sufficiently larger than $d$, then the offline defender can
capture some of the intruders from the stream before moving to capture the
burst giving an even higher competitive ratio.

###  -B Proof of Theorem III.3

To show this result, we describe a class of inputs that consist of 3 intruders
deployed according to a specific schedule. First, we select 3 distinct
perimeter vertices $p_{1}$, $p_{2}$, and $p_{3}$ such that the distance
between every pair $p_{i}$, $p_{j}$ is $2\rho$. We then select $\ell_{1}$,
$\ell_{2}$, and $\ell_{3}$ from $ent(B(p_{1}))$, $ent(B(p_{2}))$, and
$ent(B(p_{3}))$ respectively.

We first consider the case when $v=\frac{d-\rho}{d+3\rho}$. Consider the
following input. The intruder released at $\ell_{1}$ is released at time
$d+3\rho$, the intruder released at $\ell_{2}$ is released at time $d+\rho$,
and the intruder released at $\ell_{3}$ is released at time $d+3\rho$. We will
refer to these intruders as $A$, $B$, and $C$ respectively. As none of $A$,
$B$, or $C$ will be lost at the same perimeter vertex, there is no method to
capture any of these intruders simultaneously. Therefore, in any strategy that
captures all intruders there must be an intruder that is captured first,
second, and then the last one. To begin, we will show that there exist two
solutions that capture all intruders with capture orders $A,B,C$ and $C,B,A$
respectively. We will then show that these are the only such solutions that
capture $A$ or $C$ first.

A possible capture solution with capture order $A,B,C$ is as follows. At time
$d+3\rho$ the defending vehicle arrives at $\ell_{1}$, capturing $A$
instantaneously as it enters the environment. The defending vehicle then moves
to capture $B$ at $p_{2}$. As $p_{2}$ is distance $d+\rho$ away from
$\ell_{1}$, the defending vehicle arrives at $p_{2}$ at time $2d+5\rho$, just
in time to capture $B$. Finally, the defending vehicle moves to $p_{3}$ to
capture $C$. As $p_{3}$ is at a distance of $2\rho$ from $p_{2}$, the
defending vehicle has just enough time to do this. Notice that the captures of
$B$ and $C$ occur at the latest time possible, with any deviation from the
described route resulting in the loss of at least one of the intruders. This
implies that any delay in capturing $A$ would also result in the loss of an
intruder. Therefore, any algorithm that hopes to capture all intruders and
capture $A$ first must follow exactly the path described above, meaning that
there is only a single capture solution with capture order $A,B,C$. Also, note
that $A,C,B$ is not a valid capture solution as even just the travel time for
the defender from $\ell_{1}$ (where it captures $A$) to $p_{3}$ (where it must
reach to capture $C$) causes the loss of $B$. Therefore, the only solution for
capturing all three intruders in the input that begins with capturing $A$ is
the one described above. As $A$ and $C$ are released simultaneously, there
exists a symmetric capture solution where the defending vehicle arrives at
$\ell_{3}$ at time $d+3\rho$ capturing $C$, then captures $B$ at $p_{2}$, and
finally moves to $p_{1}$ to capture $A$. Reasoning as before, it follows that
there is only a single method for capturing all intruders in this input that
captures $C$ first.

We now show that there is no method to capture all three intruders that begins
by capturing $B$. To do this, we will show that even if the defender captures
$B$ as early as possible (giving it the most time to capture $A$ and $C$) and
moves optimally to capture $A$ and $C$ (even if they have not yet been
released) it still cannot capture all three intruders. The earliest point in
time that $B$ can be captured is just as it has been released at time
$d+\rho$. At this time, neither of $A$ or $C$ have been released (nor will
they be for another $2\rho$ time units). However, let us assume that the
algorithm for the defender causes it to begin moving to towards $p_{1}$ or
$p_{3}$ which would minimize the distance it must travel to capture $A$ or $C$
respectively. As $A$ and $C$ are released simultaneously (and thus lost
simultaneously), we will assume without loss of generality that the defending
vehicle moves towards $\ell_{1}$ to capture $A$. Now the soonest that the
defending vehicle can reach $p_{1}$ is at time $2d+2\rho$. As $d>\rho$,
$2d+2\rho>d+3\rho$, meaning that at the moment the defending vehicle arrives
at $p_{1}$, $A$ and $C$ have been in the environment for $d-\rho$ time units.
Thus, $A$ and $C$ are at a distance of $(d-\rho)(1-v)$ from $p_{1}$ and
$p_{3}$, respectively. Starting from $p_{1}$, it will take the defending
vehicle a minimum of $2(d-\rho)\frac{1-v}{1+v}$ time units to capture $A$ and
return to $p_{1}$. It will then require an additional $2\rho$ time units to
reach $p_{3}$, which it must do before $C$ is lost at time
$d+3\rho+\frac{d-\rho}{v}$. This means that in order to capture all intruders,
we must have the following:
$(d+\rho)+(d+\rho)+2(d-\rho)\frac{1-v}{1+v}+2\rho\leq
d+3\rho+\frac{d-\rho}{v}$. However, this relation is a direct contraction to
condition (2), as $\epsilon=0$ when $v=\frac{d-\rho}{d+3\rho}$. Therefore, all
three intruders can not be captured in strategies where $B$ is captured
immediately. It can be easily shown that not capturing $B$ immediately does
not offer any improvement.

In summary, when $v=\frac{d-\rho}{d+3\rho}$, the only method to capture all
intruders in the described input is for the defending vehicle to either arrive
at $p_{1}$ or $p_{3}$ exactly at time $d+3\rho$. However, algorithms that
arrive at $p_{1}$ by this time, can only capture at most two intruders in an
input that releases intruders at $p_{2}$ and $p_{3}$ at time $d+3\rho$ and at
$p_{1}$ at time $d+\rho$. Similarly, algorithms that arrive at $p_{3}$ by this
time, can only capture at most two intruders in an input that releases
intruders at $p_{1}$ and $p_{2}$ at time $d+3\rho$ and at $p_{3}$ at time
$d+\rho$. Therefore, without prior (offline) knowledge of where intruder $A$
or $C$ will be released and which vertices are $\ell_{1}$, $\ell_{2}$, and
$\ell_{3}$ no algorithm can capture all three intruders. Therefore,
$c(\mathcal{E})\geq\frac{3}{2}$ when $v=\frac{d-\rho}{d+3\rho}$.

The case of when $v>\frac{d-\rho}{d+3\rho}$ follows a similar argument.
However the input changes to: $A$ is released at time $d+3\rho$ at $\ell_{1}$,
$B$ is released at time $d+\rho+\epsilon$ at $\ell_{2}$, where
$\epsilon=d+3\rho-\frac{d-\rho}{v}$, and $C$ is released at time
$d+3\rho+\epsilon$ for the same $\epsilon$ at $\ell_{3}$. For this input, the
only valid capture order is $A$, $B$, $C$ and the result follows by a simlar
argument to before.

## References

  * [1] D. Shishika and V. Kumar, “A review of multi agent perimeter defense games,” in Decision and Game Theory for Security: 11th International Conference, GameSec 2020, College Park, MD, USA, October 28–30, 2020, Proceedings 11, pp. 472–485, Springer, 2020.
  * [2] A. Von Moll, E. Garcia, D. Casbeer, M. Suresh, and S. C. Swar, “Multiple-pursuer, single-evader border defense differential game,” Jour. of Aerospace Info. Systems, vol. 17, no. 8, pp. 407–416, 2020.
  * [3] D. G. Macharet, A. K. Chen, D. Shishika, G. J. Pappas, and V. Kumar, “Adaptive partitioning for coordinated multi-agent perimeter defense,” in 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 7971–7977, IEEE, 2020.
  * [4] S. L. Smith, S. D. Bopardikar, and F. Bullo, “A dynamic boundary guarding problem with translating targets,” in Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pp. 8543–8548, IEEE, 2009.
  * [5] F. Bullo, E. Frazzoli, M. Pavone, K. Savla, and S. L. Smith, “Dynamic vehicle routing for robotic systems,” Proceedings of the IEEE, vol. 99, no. 9, pp. 1482–1504, 2011.
  * [6] G. Das and D. Shishika, “Guarding a translating line with an attached defender,” in 2022 American Control Conference (ACC), pp. 4436–4442, IEEE, 2022.
  * [7] A. Pourghorban, M. Dorothy, D. Shishika, A. Von Moll, and D. Maity, “Target defense against sequentially arriving intruders,” in IEEE Intern. Conf. on Decision and Control (CDC), pp. 6594–6601, 2022.
  * [8] S. Bajaj, E. Torng, and S. D. Bopardikar, “Competitive perimeter defense on a line,” in 2021 American Control Conference (ACC), pp. 3196–3201, IEEE, 2021.
  * [9] S. Bajaj, E. Torng, S. D. Bopardikar, A. Von Moll, I. Weintraub, E. Garcia, and D. W. Casbeer, “Competitive perimeter defense of conical environments,” in 2022 IEEE 61st Conference on Decision and Control (CDC), pp. 6586–6593, IEEE, 2022.
  * [10] D. D. Sleator and R. E. Tarjan, “Amortized efficiency of list update and paging rules,” Communications of the ACM, vol. 28, no. 2, pp. 202–208, 1985.
  * [11] S. Gutiérrez, S. O. Krumke, N. Megow, and T. Vredeveld, “How to whack moles,” Theoretical computer science, vol. 361, no. 2-3, pp. 329–341, 2006.
  * [12] D. Borra, F. Pasqualetti, and F. Bullo, “Continuous graph partitioning for camera network surveillance,” Automatica, vol. 52, pp. 227–231, 2015.
  * [13] K. Kalyanam, D. W. Casbeer, and M. Pachter, “Pursuit of a moving target with known constant speed on a directed acyclic graph under partial information,” SIAM Journal on Control and Optimization, vol. 54, no. 5, pp. 2259–2273, 2016.
  * [14] S. Sundaram, K. Kalyanam, and D. W. Casbeer, “Pursuit on a graph under partial information from sensors,” in 2017 American Control Conference (ACC), pp. 4279–4284, IEEE, 2017.
  * [15] N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou, “The complexity of searching a graph,” Journal of the ACM (JACM), vol. 35, no. 1, pp. 18–44, 1988.
  * [16] A. Kolling and S. Carpin, “Pursuit-evasion on trees by robot teams,” IEEE Transactions on Robotics, vol. 26, no. 1, pp. 32–47, 2009.