# Competitive Perimeter Defense on a Line

Shivam Bajaj1 Eric Torng2 Shaunak D. Bopardikar1 1Shivam Bajaj and Shaunak D.
Bopardikar are with the Department of Electrical and Computer Engineering,
Michigan State University. email<EMAIL_ADDRESS>2Eric Torng is with the
Department of Computer Science and Engineering, Michigan State UniversityThis
work has been supported in part by NSF Award ECCS-2030556.

###### Abstract

We consider a perimeter defense problem in which a single vehicle seeks to
defend a compact region from intruders in a one-dimensional environment
parameterized by the perimeter size and the intruder-to-vehicle speed ratio.
The intruders move inward with fixed speed and direction to reach the
perimeter. We provide both positive and negative _worst-case_ performance
results over the parameter space using competitive analysis. We first
establish fundamental limits by identifying the most difficult parameter
combinations that admit no $c$-competitive algorithms for any constant $c\geq
1$ and slightly easier parameter combinations in which every algorithm is at
best $2$-competitive. We then design three classes of algorithms and prove
they are 1, 2, and 4-competitive, respectively, for increasingly difficult
parameter combinations. Finally, we present numerical studies that provide
insights into the performance of these algorithms against stochastically
generated intruders.

##  I INTRODUCTION

This paper addresses a perimeter defense problem, which is a class of vehicle
routing problems, in which a vehicle seeks to intercept mobile intruders
before they reach a specified region. In our problem, a robotic vehicle must
defend a subset of a line segment from intruders that are generated at the
endpoints of the line segment and move towards the subset, with a fixed speed.
The robotic defender moves with maximum unit speed with the goal of
_capturing_ the maximum number of intruders. This perimeter defense problem is
an _online_ problem in that the input, consisting of the arrival of intruders
at specified times and locations, is only revealed gradually over time.

While perimeter defense problems have been well-studied, most prior work has
focused on determining an optimal strategy for a small number of intruders or
assuming that the input instance is generated by some stochastic process.
While these results provide valuable insights into the average-case
performance of defense strategies, they essentially ignore the worst-case
where intruders may coordinate their actions to overwhelm the defense.

To understand how algorithms that specify vehicle motion perform in the worst-
case, we adopt a competitive analysis technique [1]. In competitive analysis,
we measure the performance of an online algorithm $A$ using the concept of
_competitive ratio_ , i.e., the ratio of an optimal offline algorithm’s
performance divided by algorithm $A$’s performance for a worst-case input
instance. Algorithm $A$ is $c$-competitive if its competitive ratio is no
larger than $c$ which means its performance is guaranteed to be within a
factor $c$ of the optimal for all input instances.

The primary application for our work is defending a perimeter from intruders
such as missiles or locusts. Additional applications include gathering
information on mobile entities in surveillance or traffic scenarios.

Perimeter defense problems were first introduced for a single vehicle and a
single intruder in [2]. Since then, perimeter defense has been mostly
formulated as a pursuit-evasion game. The multiplayer setting for the same has
been studied extensively as a reach-avoid game in which the aim is to design
control policies for the intruders and the defenders [3, 4]. A typical
approach requires computing solutions to the Hamilton-Jacobi-Bellman-Isaacs
equation which is suitable for low dimensional state spaces and in simple
environments [5, 6]. Recent works include [7], which proposes a receding
horizon strategy based on maximum matching, and [8], which considers a
scenario where the defenders are constrained to be on the perimeter.

In vehicle routing problems, inputs become available over time. Introduced on
graphs in [9], a typical approach requires that the vehicle routes be re-
planned as new information is revealed over time [10]. The inputs may have
multiple levels of priorities [11] or can be randomly recalled [12]. We refer
the reader to [13] for a review of this literature. A common way to analyze
the performance of online algorithms is competitive analysis [14, 15, 16].

Another area of related work is the class of Moving Target Travelling Salesman
Problem (MTTSP) on a single line [17, 18]. Several variants of this problem
are discussed in [19]. Specifically, the authors provide an
$\mathcal{O}(n^{2})$ algorithm to capture $n$ intruders on a line in minimum
time.

Earlier, we introduced a perimeter defense problem for a circular and
rectangular environment with stochastically generated input [20, 21]. The key
distinction of the current work from these past works is the characterization
of _competitiveness_ of the algorithms for worst case inputs.

Our general contribution is the following: we introduce a perimeter defense
problem against mobile intruders using competitive analysis to derive worst-
case performance guarantees. Specifically, we consider an environment
comprising a line segment $[-1,1]$ in which the intruders arrive as per an
arbitrary sequence at the endpoints. After arrival, the intruders move toward
the origin, with fixed speed $v<1$, with the objective of reaching the region
$[-\rho,\rho]$ called the _perimeter_ , for a given $0<\rho<1$. A vehicle,
modelled as a first-order integrator with a maximum speed of unity, seeks to
capture (become coincident with) the intruders before they reach the
perimeter. Our specific contributions are as follows. We first characterize a
most difficult parameter regime in $v-\rho$ space in which no control
algorithm (either online or offline) for the vehicle can be $c$-competitive
for any constant $c$ and a second, slightly easier, parameter regime in which
no algorithm is better than 2-competitive. We also show that a class of simple
algorithms, such as the First-Come-First-Served, are not $c$-competitive, even
for parameter regimes in which other algorithms are. Next, we design and
analyze three algorithms establishing $1$, $2$, and $4$-competitiveness,
respectively, for increasingly difficult parameter regimes. We numerically
characterize their performance when the intruders are generated as per a
stochastic process. We observe that the algorithms capture at least half the
intruders generated even for parameter settings beyond their respective
parameter regime.

The paper is organized as follows. In Section II, we formally define our
problem and the competitive ratio. We derive fundamental limits on how
competitive any algorithm can be for difficult parameter regimes in Section
III. In Section IV, we design and analyze three algorithms. Section V presents
numerical simulations. In Section VI, we present a summary and possible
directions for future work.

##  II Problem Formulation

Consider an environment
$\mathcal{E}(\rho)=\\{y\in\mathbb{R}\,:\,\rho\leq|{y}|\leq 1\\}$ and let
$\bar{\mathcal{E}}:=[-1,1]$. Intruders arrive over time at either location
$-1$ or $1$ and move, with fixed speed $v<1$, towards the nearest point in
$\bar{\mathcal{E}}$ out of $-\rho$ or $\rho$. The defense consists of a single
vehicle with motion modeled as a first order integrator. The vehicle can move
with a maximum speed of unity. The vehicle is said to _capture_ an intruder
when the vehicle’s location coincides with it. An intruder is said to be
_lost_ if the intruder reaches the perimeter without being captured. Let
$n(t)$ denote the number of intruders arrived at time instant $t$. An input
instance $I$ is a tuple comprising the time instants, the corresponding number
of intruders generated at those instants and their corresponding initial
locations, is defined as $I=\\{t,n(t),\\{-1,1\\}^{n(t)}\\}_{t=0}^{T}$.

An online algorithm determines the velocity for the vehicle as a function of
the location of the intruders that have arrived in the environment up to the
current time instant $t$. Let $\mathcal{Q}(t,I)$ denote the set of
instantaneous locations of all intruders in the environment at time $t$ from
the input instance $I$. An intruder is removed from $\mathcal{Q}(t,I)$ if it
is captured or lost. We now formally define an online algorithm as follows.

Online Algorithm: An online algorithm for a vehicle is a map
$\mathcal{A}:\bar{\mathcal{E}}\times\mathbb{F}\to[-1,1]$, where
$\mathbb{F}(\mathcal{E})$ is the set of finite subsets of $\mathcal{E}$,
assigning a commanded velocity to the vehicle as a function of the position of
the vehicle, denoted as $x(t)$, and the location of the intruders, yielding
the kinematic model, $\dot{x}(t)=\mathcal{A}(x(t),\mathcal{Q}(t,I)).$

An optimal _offline algorithm_ is a non-causal algorithm having complete
information of the input instance $I$ at any time $t\leq T$ and thus, the
velocity of the vehicle is a function of current and future locations of the
intruders.

######  Definition 1 (Competitive Ratio)

Given an $\mathcal{E}(\rho)$, an input instance $I$ for $\mathcal{E}(\rho)$,
and a given online algorithm $\mathcal{A}$, let $n_{\mathcal{A}}(I)$ denote
the number of intruders captured by the vehicle when following algorithm
$\mathcal{A}$ on input instance $I$. Let $OPT$ denote the optimal algorithm
that maximizes the number of intruders captured out of input instance $I$.
Then, the competitive ratio of $\mathcal{A}$ on $I$ is defined as
$c_{\mathcal{A}}(I)=n_{OPT}(I)/n_{\mathcal{A}}(I)\geq 1$, and the competitive
ratio of $\mathcal{A}$ for environment $\mathcal{E}$ is
$c_{\mathcal{A}}(\mathcal{E})=\sup_{I}c_{\mathcal{A}}(I)$. Finally, the
competitive ratio for environment $\mathcal{E}$ is
$c(\mathcal{E})=\inf_{\mathcal{A}}c_{\mathcal{A}}(\mathcal{E})$. We say that
an algorithm is $c$-competitive for $\mathcal{E}$ if
$c_{\mathcal{A}}(\mathcal{E})\leq c$.

We assume that all of the input instances are non-adaptive where the arrival
of intruders is not based on the movement of the vehicle.

Problem Statement: The aim of this paper is to design $c$-competitive
algorithms for the vehicle with minimum $c$.

##  III Fundamental Limits

We begin by characterizing a property of an _extreme speed algorithm_ , i.e.,
$\mathcal{A}^{\prime}:\bar{\mathcal{E}}\times\mathbb{F}\to\\{-1,0,1\\}$, which
either moves the vehicle with unit speed or keeps it stationary.

######  Lemma 1 (Extreme speed algorithms)

For non-adaptive input instances where the arrival of intruders is not based
on the movement of the vehicle, extreme speed algorithms are as powerful as
general algorithms which can move with any speed in the range $0\leq V\leq 1$.

###### Proof.

Let $\mathcal{A}$ denote an arbitrary general speed algorithm and $I$ denote
an arbitrary non-adaptive input instance where there are $n$ distinct time
points where $\mathcal{A}$ captures at least one intruder of $I$. We define
the _capture profile_ of $\mathcal{A}$’s execution on $I$ as the set of pairs
$(x_{i},k_{i})$ for $1\leq i\leq n$ where $k_{i}$ is the time of the $i$th
capture and $x_{i}$ is the point where the $i$th capture occurred. Let
$I(x_{i},k_{i})$ denote the intruders in $I$ captured by $\mathcal{A}$ at
location $x_{i}$ at time $k_{i}$. We add to this capture profile the pair
$(x_{0},k_{0})$ which denotes the starting location for the vehicle and the
starting time instant.

Our goal is to show that there exists an extreme speed algorithm
$\mathcal{A^{\prime}}$ that can match $\mathcal{A}$’s capture profile for $I$:
namely having the vehicle at location $x_{i}$ at time $k_{i}$ for $0\leq i\leq
n$. If we can show this, then because $I$ is non-adaptive,
$\mathcal{A^{\prime}}$ will capture the intruders in $I(x_{i},k_{i})$ for
$1\leq i\leq n$ at $x_{i}$ at time $k_{i}$ and the result follows. Note that
$\mathcal{A^{\prime}}$ may capture the intruders in $I(x_{i},k_{i})$ at an
earlier time than $k_{i}$ because $\mathcal{A^{\prime}}$ may move differently
than $\mathcal{A}$; the crucial point is that $\mathcal{A^{\prime}}$ captures
every intruder captured by $\mathcal{A}$.

We now show that there exists an $\mathcal{A^{\prime}}$ that can match
$\mathcal{A}$’s capture profile for $I$. We prove this by induction on $i$;
namely, that there exists an $\mathcal{A^{\prime}}$ that will have the vehicle
at point $x_{j}$ at exactly time $k_{j}$ for $0\leq j\leq i$ for $0\leq i\leq
n$. The base case where $i=0$ is trivial since the vehicle starts at location
$x_{0}$ at time $k_{0}$ for both algorithms. We now show that if this is true
up to $i$, then it also holds for $i+1$. Given the induction hypothesis, we
know that there exists an $\mathcal{A^{\prime}}$ that will have the vehicle at
point $x_{j}$ at exactly time $k_{j}$ for $0\leq j\leq i$. We extend that
$\mathcal{A^{\prime}}$ by showing it can also have the vehicle at $x_{i+1}$ at
time $k_{i+1}$.

At time $k_{i}$, we have $\mathcal{A^{\prime}}$ move the vehicle from $x_{i}$
to $x_{i+1}$ arriving at $x_{i+1}$ no later than $k_{i+1}$ since the the
maximum speed of $\mathcal{A}$’s vehicle is 1, just like
$\mathcal{A^{\prime}}$’s vehicle. We then have $\mathcal{A^{\prime}}$ keep the
vehicle at $x_{i+1}$ until time $k_{i+1}$. This completes the inductive step
and, in turn, completes the proof. ∎

In light of Lemma 1, we can restrict our attention to algorithms that either
move the vehicle with maximum speed or keep the vehicle at rest.

We now present the fundamental limits. We first present a fundamental limit on
achieving a $c$-competitive ratio for any constant $c$ followed by a
fundamental limit on achieving a $2$-competitive ratio.

###### Theorem III.1

For any environment $\mathcal{E}$ such that $v>\frac{1-\rho}{2\rho}$,

  1. i.

there does not exist a $c$-competitive algorithm and

  2. ii.

no algorithm (online/offline) can capture all intruders.

###### Proof.

Assume that the vehicle starts at the origin. The input instance consists of
two phases: a stream of intruders that arrive at the endpoint $1$, $2$ time
units apart starting at time $1$, and a burst of $c+1$ intruders who arrive at
the endpoint $-1$ at time $t$ that corresponds to the first time the vehicle
moves to $\rho$ according to any online algorithm. Note that if the vehicle
never moves to location $\rho$, the stream never ends, and the burst never
arrives, so the algorithm will not be $c$-competitive for any constant $c$,
and the first result follows. Let $i$ be the number of stream intruders
released up to and including time $t$; note that $i$ might be 0 if the vehicle
reaches $\rho$ before time 1 when the first stream intruder is released. We
first observe that the vehicle will capture at most intruder $i$. In
particular, because the stream intruders are released $2$ time units apart and
$v>\frac{1-\rho}{2\rho}$, all stream intruders before $i$ have reached $\rho$
before time $t$. Two cases arise: $i=0$ and $i>0$.
Case 1: If $i=0$, this means the vehicle reached location $\rho$ before time
$1$, so $t<1$. Since $v>\frac{1-\rho}{2\rho}$, the vehicle will not be able to
capture the burst of $c+1$ intruders that arrive at time $t$. The optimal
offline algorithm, however, can move the vehicle to location $-\rho$ by time
$t$ and will thus capture all $c+1$ burst intruders.
Case 2: If $i>0$, this means the vehicle reached location $\rho$ no earlier
than time 1, so $1\leq t$. In this case, the optimal algorithm can capture the
first $i-1$ stream intruders immediately upon arrival by moving the vehicle to
endpoint $1$ at time $1$ and staying there until the first $i-1$ stream
intruders have been captured. The algorithm then moves the vehicle to $-\rho$
before the burst intruders have been released since the stream intruders
arrive $2$ time units apart. If $i=1$, the algorithm moves the vehicle
immediately to $-\rho$.
In either case, we show that the optimal offline algorithm can capture all the
burst intruders and at least all but the last stream intruder whereas the
online algorithm will capture at most 1 stream intruder, and the first result
follows.
The second result follows by observing there are choices for $t$ including
$t=1$ such that no algorithm can capture all $i$ stream intruders and all
$c+1$ burst intruders. ∎

The following theorem provides a fundamental limit on achieving a
$2$-competitive ratio for any environment.

###### Theorem III.2

For the environment $\mathcal{E}$ such that $v\geq\frac{1-\rho}{1+\rho}$,
$c(\mathcal{E})\geq 2$.

###### Proof.

In this proof, all of our input instances consist of two intruders, $a$ and
$b$, where $a$ arrives at endpoint $-1$ and $b$ arrives at endpoint $1$ and we
assume that the vehicle starts at the origin at time $0$. We first consider
the case where $v=\frac{1-\rho}{1+\rho}$. Consider the following input
instance $I_{1}$ where both $a$ and $b$ arrive at time $1$. For input instance
$I_{1}$, there are two symmetric solutions to capture both intruders; we
describe one below. At time $0$, the vehicle moves toward endpoint $1$
capturing intruder $b$ at endpoint $1$ at exactly time $1$. The vehicle then
moves to $-\rho$ to capture intruder $a$ at $-\rho$ at exactly time $2+\rho$.
The vehicle has just enough time to do this given the condition that
$v=\frac{1-\rho}{1+\rho}$. Thus, any algorithm that hopes to be better than
$2$-competitive for such an $\mathcal{E}$ must capture both intruders in
$I_{1}$, and the only way to do so is to move immediately to $-1$ or $1$
arriving at the destination point at exactly time $1$.

Now consider input instances $I_{2}$ and $I_{3}$ which also consists of two
intruders. In $I_{2}$, intruder $a$ arrives at time $1$ and intruder $b$
arrives at time $1+\epsilon$ where $\epsilon<2\rho v$. In $I_{3}$, intruder
$b$ arrives at time 1 and intruder $a$ arrives at time $1+\epsilon$ for same
$\epsilon$. Algorithms which have the vehicle arriving at endpoint $1$ at time
$1$ can capture at most one of the two intruders in input instance $I_{2}$.
This follows since the vehicle can only capture intruder $a$ if it moves
immediately to arrive at $-\rho$ at time $2+\rho$. However, as $\epsilon<2\rho
v$ and $v=\frac{1-\rho}{1+\rho}$, the vehicle cannot capture intruder $b$
before $b$ passes $\rho$. Similarly, algorithms which have the vehicle arrive
at $-1$ at time $1$ can capture at most one of the two intruders in input
instance $I_{3}$. At the same time, there exists an offline algorithm which
captures both intruders in input instance $I_{2}$ and another algorithm which
captures both intruders in $I_{3}$ which is to simply move to the correct
location at time $1$ and then capture the other intruder before it reaches
$\rho$ or $-\rho$.
We now consider the case where $v>\frac{1-\rho}{1+\rho}$. Now we only need two
input instances $I_{4}$ and $I_{5}$. In $I_{4}$, intruder $a$ arrives at time
$1$ and intruder $b$ arrives at time $1+\epsilon$ where
$\epsilon=1+\rho-\frac{1-\rho}{v}$. In $I_{5}$, intruder $b$ arrives at time
$1$ and intruder $a$ arrives at time $1+\epsilon$ for same $\epsilon$. As
$v>\frac{1-\rho}{1+\rho}$, $\epsilon>0$, using similar arguments as for
$I_{2}$ and $I_{3}$, it follows that no single online algorithm can capture
both intruders in $I_{4}$ and $I_{5}$.

In summary, even restricting the set of possible input instances to
$\\{I_{1},I_{2},I_{3},I_{4},I_{5}\\}$, no single algorithm can capture both
intruders from all five input instances, but since there exist algorithms
which capture both intruders for all five input instances, it follows that
$c(\mathcal{E})\geq 2$. ∎

We now show that a natural algorithm, _First-Come-First-Served_ (FCFS), is not
an effective algorithm for this problem. We define FCFS as the algorithm which
sends the vehicle at speed $1$ towards the earliest intruder to arrive that is
not lost or already captured breaking ties arbitrarily.

###### Lemma 2

For any $\mathcal{E}$ where $\frac{2}{v+1}+\rho>\frac{1-\rho}{v}+\epsilon$ for
some small $\epsilon>0$, FCFS is not $c$-competitive for any constant $c$.

###### Proof.

We prove this result by constructing a worst case input instance against FCFS.
Consider the following input instance $I(c)$. Let the first intruder be
released at time $0$ at $1$. Let $c+1$ intruders be released at time
$\epsilon$ at $-1$. FCFS will move the vehicle immediately towards the first
intruder and intercept it at $\frac{1}{v+1}$ at time $\frac{1}{v+1}$. Because
of the condition $\frac{2}{v+1}+\rho>\frac{1-\rho}{v}+\epsilon$, FCFS cannot
get the vehicle to $-\rho$ before the $c+1$ intruders released at time
$\epsilon$ reach $-\rho$. It follows that $FCFS(I(c))=1$. On the other hand,
if the vehicle had moved toward $-\rho$ immediately, it would capture those
$c+1$ intruders. Thus, $OPT(I(c))=c+1$, and the result follows. This result
generalizes to any variation of FCFS which services the first arriving
intruder, if possible, before any later arriving intruder. ∎

We now turn our attention to the design of algorithms with provable guarantees
on the competitive ratio. In the following section, we describe and analyze
three algorithms, characterizing parameter regimes with provably finite
competitive ratios.

##  IV Algorithms

We now propose three main algorithms for the vehicle that are provably $1$,
$2$, and $4$ competitive. As the competitive ratio increases, the parameter
regime that can be handled also increases.

###  IV-A Sweeping algorithm

We define the Sweeping algorithm (Sweep) as follows. At time 0, the vehicle
moves with unit speed toward endpoint $+1$. From this point on, the vehicle
only changes direction when it reaches an endpoint $+1$ or $-1$, at which time
it moves with unit speed towards the opposite endpoint. Sweep is an _open-
loop_ algorithm; that is, it ignores all information about intruders. One
logical variant is to stop moving in a given direction if there are no
intruders in that direction. We show this variant achieves the same
performance guarantee.

###### Theorem IV.1

For environment $\mathcal{E}$, Sweep is 1-competitive if
$v\leq\frac{1-\rho}{3+\rho}$. If not, it is not $c$-competitive for any
constant $c$.

###### Proof.

Suppose that $v\leq\frac{1-\rho}{3+\rho}$ holds. We show Sweep captures all
intruders. Any intruder $i$ will take $\frac{1-\rho}{v}$ time to get from its
arrival location, which we now assume to be $1$ without loss of generality, to
$\rho$. In the worst case for Sweep, which is that it has left $1$ just before
intruder $i$ arrived, it will take $3+\rho$ time to get to $\rho$ moving
towards intruder $i$. If $3+\rho\leq\frac{1-\rho}{v}$, then Sweep’s vehicle
will get to $\rho$ first and intruder $i$ will be captured, and the first
result follows.

For $v>\frac{1-\rho}{3+\rho}$ there is an input instance where intruders only
arrive at $1$ just after the vehicle has left $1$. As
$v>\frac{1-\rho}{3+\rho}$, all intruders will be lost and the second result
follows. ∎

We observe that the upper bound in the proof holds for the Sweep variant where
it stops moving in a given direction if there are no intruders in that
direction. The lower bound requires introducing some intruders at $-1$ to
ensure that the modified Sweep will move the vehicle towards $-1$. These
intruders might be captured, but the lower bound still holds by increasing the
number of intruders which arrive at $1$.

###  IV-B Compare and Capture (CaC) algorithm

We now present a Compare and Capture (CaC) algorithm that is provably
$2$-competitive beyond the parameter regime of the Sweep algorithm. CaC is not
open-loop but is _memoryless_ , i.e., its actions depend only on the present
state of the vehicle and the intruders.

We begin with some notation and definitions. An epoch $k$ for the CaC
algorithm is the time interval when the vehicle moves from location $x_{k}$ to
location $x_{k+1}$ and is about to move from $x_{k+1}$, capturing some
intruders along the way. Location $x_{k}$ is always either $\rho$ or $-\rho$.
We denote the start of epoch $k$ using the notation $k_{S}$. For epoch $k$, we
define ${S}_{\textup{same}}^{k}$ as the set of intruders on the same side as
the vehicle at time $k_{S}$, and ${S}_{\textup{opp}}^{k}$ as the set of
intruders on the opposite side of the vehicle that are between $\rho+2\rho v$
and $\rho+2v\rho+\frac{2v(1-\rho)}{1+v}$ away from the origin at time $k_{S}$.
Specifically, if the vehicle is located at $x_{k}=\rho$, then
${S}_{\textup{opp}}^{k}$ is defined as the set of intruders contained in
$[-(\rho+2\rho v+\frac{2v(1-\rho)}{1+v}),-(\rho+2\rho v)]$.

The CaC algorithm, summarized in Algorithm 1, works as follows: At epoch $k$,
for any $k\geq 1$, the algorithm computes the number of intruders located in
${S}_{\textup{same}}^{k}$ and ${S}_{\textup{opp}}^{k}$. If the total number of
intruders in ${S}_{\textup{same}}^{k}$ is greater than the total number of
intruders in ${S}_{\textup{opp}}^{k}$, then the vehicle moves away from the
origin for at most $\frac{1-\rho}{1+v}$ time to capture all intruders from the
set ${S}_{\textup{same}}^{k}$ and then returns to $x_{k+1}=x_{k}$. Otherwise,
the vehicle moves for at most $2\rho+\frac{4v(1-\rho)}{(1+v)^{2}}$ time to
capture all intruders located in ${S}_{\textup{opp}}^{k}$ and then returns to
$x_{k+1}=-x_{k}$.

At time $0$, we assume the vehicle starts at the origin. CaC waits at the
origin until the first intruder that arrives in the environment is $3\rho
v+\rho$ distance away from the origin, i.e., the vehicle does not move until
$\frac{1-\rho-3\rho v}{v}$ time units after the first intruder arrives. If the
total number of intruders located in $[\rho+3\rho v,1]$ is greater than the
total number of intruders located in $[-1,-(\rho+3\rho v)]$, then the vehicle
moves to $x_{1}=\rho$. If not, the vehicle moves to $x_{1}=-\rho$. The first
epoch begins when the vehicle reaches $x_{1}$.

To prove $2$-competitiveness of CaC, we first prove that any intruder not
belonging to ${S}_{\textup{same}}^{k}$ or ${S}_{\textup{opp}}^{k}$ in an epoch
$k$ will not be lost during epoch $k$.

1 Vehicle is at center and waits for $\frac{1-\rho-3\rho v}{v}$ time units

2 if  _intruders in $[\rho+3\rho v,1]\leq\text{ intruders in }[-1,-(\rho+3\rho
v)]$_ then

3 Move to $-\rho$

4else

5 Move to $\rho$.

6

7 end if

8for  _each epoch $k\geq 1$_ do

9 if  _at epoch $k$, $|{S}_{\textup{same}}^{k}|\leq|{S}_{\textup{opp}}^{k}|$_
then

10 Move to capture all intruders located in ${S}_{\textup{opp}}^{k}$

11 Move to $x_{k+1}=-x_{k}$

12 else

13 Move to capture intruders located in ${S}_{\textup{same}}^{k}$.

14 Move to $x_{k+1}=x_{k}$

15

16 end if

17

18 end for

Algorithm 1 Compare-and-Capture Algorithm

###### Lemma 3

In every epoch $k$, any intruder that lies outside of the set
${S}_{\textup{same}}^{k}$ and ${S}_{\textup{opp}}^{k}$ is not lost if
$\frac{\rho v}{1-\rho}+\frac{v^{2}}{(1+v)^{2}}\leq\frac{1}{4}.$

###### Proof.

Assume that the vehicle is located at $x_{k}=\rho$ at time $k_{S}$. Two cases
arise:

_Case 1: $|{S}_{\textup{same}}^{k}|>|{S}_{\textup{opp}}^{k}|$:_ In this case,
the vehicle moves away from the origin to capture intruders located in
${S}_{\textup{same}}^{k}$. The vehicle takes at most $\frac{1-\rho}{1+v}$ time
to capture these intruders. The total time taken by the vehicle to capture the
intruders and return to $x_{k+1}=x_{k}$ in epoch $k$ is at most
$\frac{2(1-\rho)}{1+v}$. Since the intruders in ${S}_{\textup{opp}}^{k}$ are
located in $[-(\rho+2\rho v+\frac{2v(1-\rho)}{1+v}),-(\rho+2\rho v)]$, any
intruder in the opposite side which did not belong to ${S}_{\textup{opp}}^{k}$
will be at least $2\rho v$ distance away from $\rho$ and thus, will be
contained in ${S}_{\textup{opp}}^{k+1}$.

_Case 2: $|{S}_{\textup{same}}^{k}|\leq|{S}_{\textup{opp}}^{k}|$:_ The total
time taken by the vehicle to capture intruders located in
${S}_{\textup{opp}}^{k}$ and return back to $x_{k+1}=-x_{k}$ is at most
$2\rho+\frac{4v(1-\rho)}{(1+v)^{2}}$. In order to ensure that any intruder
that did not belong to ${S}_{\textup{same}}^{k}$ is at least $\rho+2\rho v$
distance away from the origin at the end of epoch $k$, we require
$2\rho+\frac{4v(1-\rho)}{(1+v)^{2}}\leq\frac{1-\rho-2\rho
v}{v}\Rightarrow\frac{\rho v}{1-\rho}+\frac{v^{2}}{(1+v)^{2}}\leq\frac{1}{4}.$
This concludes the proof. ∎

###### Lemma 4

In every epoch $k$ of the CaC, ${S}_{\textup{opp}}^{k}$ is well defined if
$\rho+2\rho v+\frac{2v(1-\rho)}{1+v}\leq 1.$

###### Proof.

In order to ensure that ${S}_{\textup{opp}}^{k}$ is well defined, we require
that ${S}_{\textup{opp}}^{k}$ is contained in the environment. Mathematically,
this corresponds to $\rho+2\rho v+\frac{2v(1-\rho)}{1+v}\leq 1$, and the
result follows. ∎

###### Theorem IV.2

Algorithm 1 captures at least half of all intruders and is 2-competitive in
parameter regimes for which Lemma 3 and Lemma 4 both hold.

###### Proof.

Based on Lemma 4, ${S}_{\textup{opp}}^{k}$ is well-defined in every epoch $k$.
This implies that Algorithm 1 is well-defined. Lemma 3 ensures that every
intruder will belong to ${S}_{\textup{same}}^{k}$ or ${S}_{\textup{opp}}^{k}$
for some epoch $k$. Because of the comparison in line 9 of Algorithm 1, in
every epoch, the number of intruders captured is at least the number of
intruders lost. Note that an intruder is not lost in epoch $k$ if it belongs
to ${S}_{\textup{same}}^{k+1}$ or ${S}_{\textup{opp}}^{k+1}$ in the subsequent
epoch $k+1$. Thus, the algorithm captures at least half of all intruders and
is $2$-competitive. ∎

###  IV-C Capture with Patience (CAP) Algorithm

We now present another memoryless algorithm, Capture with Patience (CAP), in
which the vehicle stays in the range $[-\rho,\rho]$ waiting for and capturing
intruders at $\rho$ or $-\rho$. CAP is only $4$-competitive but can operate
beyond the parameter regime of the CaC algorithm.

A key feature in environment $\mathcal{E}$ is the quantity
$z=\frac{1-\rho}{v}$ which represents the time required for any intruder
originating at $+1$ or $-1$ to reach the corresponding location $\rho$ or
$-\rho$. We first describe an algorithm that is provably $4$-competitive for
$\mathcal{E}$ when $z\geq 6\rho$, equivalently $v\leq\frac{1-\rho}{6\rho}$.
This requirement ensures that incoming intruders require at least $6\rho$ time
to get to either $-\rho$ or $\rho$ whereas it takes the vehicle $2\rho$ time
to move from $-\rho$ to $\rho$ or vice versa.

Figure 1: Breakdown of the environment into regions of length $2\rho v$ by the
CAP algorithm. The triangle depicts the vehicle, whereas a dot depicts an
intruder

The algorithm is formally defined in Algorithm 2 and is described as follows.
First, to simplify notation, it defines time 0 to be the moment when the first
intruder arrives. It then breaks time up into intervals of length $2\rho$. The
$i$th interval for $i\geq 1$ is defined as the time interval
$[2(i-1)\rho,2i\rho]$. We say that a set of intruders $S$ is on the same side
as the vehicle if the vehicle is located at $\rho$ (resp. $-\rho$) and
$S\subset(\rho,1]$ (resp. $[-1,-\rho)$). Similarly, we say that $S$ is on the
opposite side of the vehicle if the vehicle is located at $\rho$ (resp.
$-\rho$) and $S\subset[-1,-\rho]$ (resp. $[\rho,1]$).
For $i\geq 1$, let ${S}_{\textup{opp}}^{i}$ and ${S}_{\textup{same}}^{i}$ be
the intruders in an input instance $I$ that arrive in the $i$th time interval
that are on the opposite side and same side of the vehicle, respectively. Let
$|S|$ denote the cardinality of $S$.

The algorithm operates as follows in the steady state, i.e., after time
instant $z$. At any time instant $2j\rho+z$ for $j\geq 0$, the vehicle is
stationed at either $-\rho$ or $\rho$. Without loss of generality, we assume
that the vehicle is stationed at $\rho$.

1 Vehicle stays at origin from time 0 (time first intruder arrives) to time
$2\rho$, same side is right of origin

2 At time $2\rho$, if  _$|{{S}_{\textup{opp}}^{1}}|
>|{{S}_{\textup{same}}^{1}}|$_ then

3 Move to $x_{2}=-\rho$, same side is left of origin

4else

5 Move to $x_{2}=\rho$, same side unchanged

6 end if

7Wait until time $z$

8 for  _each time instant $z+2\rho j,j\geq 0$_ do

9 if  _$|{{S}_{\textup{opp}}^{j+2}}|
>|{{S}_{\textup{same}}^{j+1}}|+|{{S}_{\textup{same}}^{j+2}}|+|{{S}_{\textup{same}}^{j+3}}|$_
then

10 Move to $x_{j+1}=-x_{j}$, same side changes

11 else

12 Stay at $x_{j}$ and capture interval ${S}_{\textup{same}}^{j+1}$.

13

14 end if

15

16 end for

Algorithm 2 Capture with Patience Algorithm

First, we observe that the intruders in ${S}_{\textup{same}}^{j+1}$ are
located between $\rho$ and $\rho+2\rho v$, the intruders in
${S}_{\textup{same}}^{j+2}$ are located between $\rho+2\rho v$ and $\rho+4\rho
v$, and the intruders in ${S}_{\textup{same}}^{j+3}$ are located between
$\rho+4\rho v$ and $\rho+6\rho v$ (Fig. 1). Further, because $z\geq 6\rho$,
this means all the intruders in ${S}_{\textup{same}}^{j+3}$ have arrived by
time $2j\rho+z$. Similar conclusions can be drawn for the intruders in
${S}_{\textup{opp}}^{j+1}$, ${S}_{\textup{opp}}^{j+2}$, and
${S}_{\textup{opp}}^{j+3}$. If
$|{{S}_{\textup{opp}}^{j+2}}|>|{{S}_{\textup{same}}^{j+1}}|+|{{S}_{\textup{same}}^{j+2}}|+|{{S}_{\textup{same}}^{j+3}}|$,
then the vehicle moves to $-\rho$ arriving at time $2(j+1)\rho+z$ which is
just in time to capture all the intruders in ${S}_{\textup{opp}}^{j+2}$. If
not, then the vehicle stays at $\rho$ and captures all the intruders in
${S}_{\textup{same}}^{j+1}$ and reevaluates at time $2(j+1)\rho+z$. The key
observation is that the vehicle moves from $\rho$ to $-\rho$ only when it sees
sufficient benefit in terms of the number of intruders in
${S}_{\textup{opp}}^{j+2}$ to sacrifice all the intruders in
${S}_{\textup{same}}^{j+1}$, ${S}_{\textup{same}}^{j+2}$ and
${S}_{\textup{same}}^{j+3}$.

For the initial case, the vehicle stays at the origin until time $2\rho$. At
time $2\rho$, if $|{{S}_{\textup{opp}}^{1}}|>|{{S}_{\textup{same}}^{1}}|$
(intruders to the left of the origin are considered on the opposite side while
intruders to the right of the origin are considered on the same side for this
special case), then the vehicle will move to $-\rho$. Otherwise, the vehicle
moves to $\rho$. In either case, the vehicle then stays at either $-\rho$ or
$\rho$ until time $z$.

###### Lemma 5

Algorithm 2 never moves the vehicle from $\rho$ to $-\rho$ and then back to
$\rho$ (or vice versa) without capturing at least one interval of intruders.

###### Proof.

This holds as in order to move from $\rho$ to $-\rho$ at time $2j\rho+z$, it
must be true that
$|{{S}_{\textup{opp}}^{j+2}}|>|{{S}_{\textup{same}}^{j+1}}|+|{{S}_{\textup{same}}^{j+2}}|+|{{S}_{\textup{same}}^{j+3}}|$.
This implies $|{{S}_{\textup{opp}}^{j+2}}|>|{{S}_{\textup{same}}^{j+3}}|$. In
order to move directly to $\rho$ without capturing the intruders in the
interval ${S}_{\textup{opp}}^{j+2}$, we would need
$|{{S}_{\textup{same}}^{j+3}}|>|{{S}_{\textup{opp}}^{j+2}}|+|{{S}_{\textup{opp}}^{j+3}}|+|{{S}_{\textup{opp}}^{j+4}}|$,
but this cannot hold by the above observation. ∎

###### Corollary IV.3

For any $i\geq 1$, Algorithm 2 will capture intruders from one of
${S}_{\textup{same}}^{i}$ or ${S}_{\textup{opp}}^{i+1}$.

###### Proof.

At time $z+2\rho(i-1)$, the vehicle is in position to capture
${S}_{\textup{same}}^{i}$ by definition of the algorithm. If it captures,
${S}_{\textup{same}}^{i}$, we are done. If not, it moves to the opposite
capture point and by Lemma 5 will capture ${S}_{\textup{opp}}^{i+1}$. ∎

###### Theorem IV.4

Algorithm 2 is 4-competitive for any environment $\mathcal{E}$ with
$v\leq(1-\rho)/6\rho$.

###### Proof.

The basic idea is that for any input instance $I$, Algorithm 2 captures at
least $1/4$ of all intruders in $I$. We prove this claim using an accounting
analysis where we “charge” lost intruders to captured intruders, or
equivalently, captured intruders “pay” for the lost intruders. One notation
note: our proof will first focus on a captured interval which we identify as
being on the same side and then focus on a lost interval which we identify as
being on the opposite side. All other intervals will be defined as being on
the same side or opposite side relative to these anchor intervals.

We first describe how intervals of captured intruders
${S}_{\textup{same}}^{j}$ pay for intervals of lost intruders. We divide
intervals of captured intruders into two types: type (a) where the vehicle did
not move to capture them meaning the vehicle also captured the previous
interval on the same side (or the interval corresponds to the first interval
${S}_{\textup{same}}^{1}$) and type (b) where the vehicle did move to capture
them meaning the vehicle spent the last $2\rho$ time moving from $\rho$ to
$-\rho$ or vice versa. A type (a) captured interval ${S}_{\textup{same}}^{j}$
will be charged three times, once each to pay for each of the lost intervals
${S}_{\textup{opp}}^{j-1}$, ${S}_{\textup{opp}}^{j}$, and
${S}_{\textup{opp}}^{j+1}$. A type (b) captured interval
${S}_{\textup{same}}^{j}$ will also be charged three times, one charge to pay
all at once for lost intervals ${S}_{\textup{opp}}^{j-1}$,
${S}_{\textup{opp}}^{j}$, and ${S}_{\textup{opp}}^{j+1}$, one charge to help
pay for lost interval ${S}_{\textup{same}}^{j-1}$, and one charge to help pay
for lost interval ${S}_{\textup{same}}^{j-2}$. Because each captured interval
is only charged three times, if we can show that every lost interval of
intruders is fully paid for by this charging scheme, we will have proven that
each captured intruder pays for at most three lost intruders and the result
follows.

We now show that every interval of lost intruders ${S}_{\textup{opp}}^{j}$ is
fully paid for by this charging scheme. We divide intervals of lost intruders
into five types: type (a) where the intervals ${S}_{\textup{same}}^{j-1}$,
${S}_{\textup{same}}^{j}$, and ${S}_{\textup{same}}^{j+1}$ are all captured,
type (b) where the intervals ${S}_{\textup{opp}}^{j-2}$ and
${S}_{\textup{same}}^{j}$ are captured, type (c) where the intervals
${S}_{\textup{opp}}^{j-1}$ and ${S}_{\textup{same}}^{j+1}$ are captured, type
(d) where the intervals ${S}_{\textup{same}}^{j-1}$ and
${S}_{\textup{opp}}^{j+1}$ are captured, and type (e) where the intervals
${S}_{\textup{same}}^{j-1}$, ${S}_{\textup{same}}^{j}$, and
${S}_{\textup{opp}}^{j+2}$ are captured.

We first claim these five types of intervals describe all possible variations
of lost intervals ignoring boundary cases (the first time interval and the
last time interval). This follows from Corollary IV.3 which shows the
algorithm will never fail to capture intruders from both sides from two
consecutive $2\rho$ time intervals. Type (a) lost intervals are fully paid for
by the captured intervals ${S}_{\textup{same}}^{j-1}$,
${S}_{\textup{same}}^{j}$, and ${S}_{\textup{same}}^{j+1}$ because the
algorithm at time $z+2\rho(j-2)$ did not choose to switch sides and capture
${S}_{\textup{opp}}^{j}$, so
$|{{S}_{\textup{opp}}^{j}}|\leq|{{S}_{\textup{same}}^{j-1}}|+|{{S}_{\textup{same}}^{j}}|+|{{S}_{\textup{same}}^{j+1}}|$.

The argument for type (b) and type (c) lost intervals are essentially
identical to each other. Type (b) lost intervals are fully paid for by the
captured interval ${S}_{\textup{same}}^{j}$ because the algorithm at time
$z+2\rho(j-2)$ did choose to switch sides to capture ${S}_{\textup{same}}^{j}$
which means that
$|{{S}_{\textup{same}}^{j}}|>|{{S}_{\textup{opp}}^{j-1}}|+|{{S}_{\textup{opp}}^{j}}|+|{{S}_{\textup{opp}}^{j+1}}|$.
Type (c) lost intervals are fully paid for by the captured interval
${S}_{\textup{same}}^{j+1}$ because the algorithm at time $z+2\rho(j-1)$ did
choose to switch sides to capture ${S}_{\textup{same}}^{j+1}$ which means that
$|{{S}_{\textup{same}}^{j+1}}|>|{{S}_{\textup{opp}}^{j}}|+|{{S}_{\textup{opp}}^{j+1}}|+|{{S}_{\textup{opp}}^{j+2}}|$.

Next, the argument for type (d) and type (e) lost intervals are essentially
identical to each other. Type (d) lost intervals are fully paid for by the
captured intervals ${S}_{\textup{same}}^{j-1}$ and ${S}_{\textup{opp}}^{j+1}$
for the following reasons. First, because the algorithm at time $z+2\rho(j-2)$
did not choose to switch sides and capture ${S}_{\textup{opp}}^{j}$, it
follows that
$|{{S}_{\textup{opp}}^{j}}|\leq|{{S}_{\textup{same}}^{j-1}}|+|{{S}_{\textup{same}}^{j}}|+|{{S}_{\textup{same}}^{j+1}}|$.
Second, because the algorithm at time $z+2\rho(j-1)$ did choose to switch
sides to capture ${S}_{\textup{opp}}^{j+1}$,
$|{{S}_{\textup{opp}}^{j+1}}|>|{{S}_{\textup{same}}^{j}}|+|{{S}_{\textup{same}}^{j+1}}|+|{{S}_{\textup{same}}^{j+2}}|$.
The full payment follows from combining these two observations. The argument
for type (e) lost intervals is essentially the same except they are paid for
by the captured intervals ${S}_{\textup{same}}^{j-1}$,
${S}_{\textup{same}}^{j}$, and ${S}_{\textup{opp}}^{j+2}$.

Finally the boundary cases of the first intervals and the last intervals fall
into these five types if we add dummy intervals ${S}_{\textup{same}}^{0}$ and
${S}_{\textup{same}}^{Y+1}$, all with cardinality 0, where $Y$ denotes the
last interval with actual intruders on either side. We assume the vehicle
captures both of these dummy intervals.

Since we have shown our charging scheme does pay for all lost intruders and
each captured intruder pays for at most three lost intruders, the result
follows. ∎

We now prove some lower bounds on the competitive ratio for the CAP algorithm
including showing that the bound is tight for some parameter settings.

###### Lemma 6

Algorithm 2 is no better than 3-competitive for $v\leq\frac{1-\rho}{6\rho}$
and is no better than 4-competitive for
$v\leq\min\\{\frac{1}{3},\frac{1-\rho}{6\rho}\\}$.

###### Proof.

We prove these results using an input instance $I$ consisting of two streams
of intruders, one stream each arriving at endpoints $1$ and $-1$. At location
$1$, one intruder arrives at time instant $6i\rho$, $0\leq i\leq K$ for some
very large $K$. At location $-1$, one intruder arrives at time instant
$3\rho+\frac{\rho}{v}+i2\rho$, $0\leq i\leq K$ for the same $K$.

As the first intruder at location $1$ arrives $3\rho+\frac{\rho}{v}$ time
units before the first intruder arrives at location $-1$, the CAP algorithm
moves the vehicle to $\rho$ from the origin, reaching $\rho$ at time $3\rho$.
As the intruders at location $1$ arrive every $6\rho$ time units and the
intruders at location $-1$ arrive every $2\rho$ time units, from this moment
on until the end, the vehicle remains at $\rho$ because there will always be
exactly one intruder in ${S}_{\textup{opp}}^{j+2}$ and exactly one intruder in
${S}_{\textup{same}}^{j+1}$, ${S}_{\textup{same}}^{j+2}$ and
${S}_{\textup{same}}^{j+3}$ combined. Thus, except at the beginning and at the
end of the streams, every $6\rho$ time units, the vehicle captures $1$
intruder that arrives at $+1$ but loses $3$ intruders that arrive at $-1$.

For $v\leq\frac{1-\rho}{6\rho}$, there is an obvious offline algorithm that
captures $3/4$ of the intruders; namely, one that moves the vehicle to $-\rho$
and captures all the intruders that arrive at location $-1$. Thus, for the
specified parameter settings, the CAP algorithm cannot be better than
$3$-competitive.

We now show that the optimal algorithm can capture all intruders for specific
parameter settings. First consider $\rho\leq\frac{1}{2}$. Let $p_{1}$ and
$p_{2}$ denote two distinct points which are $\rho$ and $-2\rho$ distance away
from the origin respectively.

The optimal algorithm moves the vehicle towards $p_{1}$ at time instant
$\frac{1-\rho}{v}-\rho$ reaching $p_{1}$ just in time to capture the first
intruder that arrived at endpoint $1$. Since the first intruder at endpoint
$-1$ arrives $3\rho+\frac{\rho}{v}$ time after the arrival of first intruder
at endpoint $+1$, the vehicle captures the second intruder at $p_{2}$ by
moving immediately towards $p_{2}$. This is because the intruder will be
located at a distance of $3\rho v+\rho$ from $-\rho$ at the time when the
vehicle captured the intruder at $p_{1}$. This means that the distance between
the vehicle and the intruder will be $3\rho+3\rho v$ implying that the vehicle
captures this intruder in $3\rho$ time or equivalently at location $p_{2}$.
Note that while moving from $p_{1}$ to $p_{2}$ and back to $p_{1}$ the vehicle
takes $6\rho$ time units. Thus, the vehicle can capture every intruder, that
arrives at endpoint $1$ at time instant $6i\rho$, at location $p_{1}$ at time
instant $\frac{1-\rho}{v}+6i\rho$.

Now let us consider the intruders that arrive at $-1$. Note that the intruders
that arrive at $-1$ arrive $2\rho$ time units apart and we already showed that
the first intruder that arrived at $-1$ can be captured at $p_{2}$. This means
that from the moment the vehicle leaves $p_{2}$ after capturing an intruder,
the next intruder will take $2\rho$ time to reach $p_{2}$ and
$2\rho+\frac{\rho}{v}$ time units to reach $-\rho$, whereas the vehicle will
take $5\rho$ time to move from $p_{2}$ to $p_{1}$ and then to $-\rho$. Thus,
in order to ensure that the next intruder is not lost while the vehicle moves
from $p_{2}$ to $p_{1}$ and then to $-\rho$, we need $5\rho\leq
2\rho+\frac{\rho}{v}$ implying $v\leq\frac{1}{3}$. In summary, after capturing
an intruder at $p_{1}$, the vehicle moves to $p_{2}$, capturing an intruder
that arrives at $-1$ at time $3\rho+\frac{\rho}{v}+6i\rho$ at location
$p_{2}$. Since $v\leq\frac{1}{3}$, the intruders that arrive at times
$5\rho+\frac{\rho}{v}+6i\rho$ and $7\rho+\frac{\rho}{v}+6i\rho$ are captured
on the way to $p_{2}$.

We now consider the case when $\rho>\frac{1}{2}$. Since $\rho>\frac{1}{2}$, we
cannot set the point $p_{2}$ at a distance of $-2\rho$; instead, we set
$p_{2}$ to be $-1$ and have the vehicle idle at $-1$ for $2(2\rho-1)$ time.
Note that the total time that the vehicle takes to move from $p_{1}$ to $-1$
combined with the waiting time at $-1$ is $5\rho-1$. This time is sufficient
for the vehicle to capture the intruder that arrives at time
$3\rho+\frac{\rho}{v}+6i\rho$ immediately. The next intruder, however, arrives
at time $3\rho+\frac{\rho}{v}+6i\rho$ which is after the vehicle leaves $-1$
as the vehicle leaves $-1$ at time $5\rho-1+6i\rho$. This is equivalent to the
intruder arriving at $-1$, $1+\frac{\rho}{v}$ time after the vehicle has left
$-1$. The total time the vehicle takes to move from $-1$ to $\rho$ and then to
$-\rho$ is $1+3\rho$ and the intruder will take
$1+\frac{\rho}{v}+\frac{1-\rho}{v}$ time. Thus, in order to ensure that the
next intruder is not lost, we need $3\rho\leq\frac{1}{v}$ implying
$v\leq\frac{1}{3\rho}$. Since, $v\leq\frac{1}{3}$ from the previous case,
$v\leq\frac{1}{3\rho}$ always holds. Furthermore, since the algorithm is
defined for $v\leq\frac{1-\rho}{6\rho}$, we get the result. ∎

In the CAP algorithm, the vehicle waits for intruders at $\rho$ or $-\rho$ to
capture them. Furthermore, CAP is _memoryless_ , i.e., it depends only the
present state of the vehicle and the intruders. In the following subsection,
we formulate another memoryless algorithm that moves the vehicle beyond the
perimeter and analyze its performance.

Figure 2: Parameter regimes for our algorithms (solid lines, extend to the
left) and lower bounds (dashed lines, extend to the right).

##  V Summary and Numerical Performance

###  V-A Summary of the results

Figure 2 shows a $v$-$\rho$ plot summarizing our results. For $\rho>0.3$, as
the curve defined by the conditions in Theorem IV.2 for the CaC algorithm is
above the curve defined by the conditions in Theorem IV.4 for the CAP
algorithm, one should always implement the CaC algorithm rather than the CAP
algorithm. For any $\rho\leq 0.3$, there exist values of $v$ such that one
might choose any of the three algorithms. The curve defined by the conditions
in Theorem IV.2 for the CaC algorithm is completely below the curve defined by
the condition in Theorem III.2. This suggests that for the values of $v$ and
$\rho$ that lie above the curve defined by the conditions for the CaC
algorithm, either there may still exist an algorithm which is 2-competitive or
it may be possible to tighten the analysis of Theorem III.2 and Lemma 3.

###  V-B Numerical Performance

We now analyze the average case performance, as opposed to the worst case
performance, of our algorithms numerically. Of particular interest is the case
when the intruders are generated stochastically as per a spatio-temporal
arrival process [10].

We performed numerical analysis of our algorithms using the following
procedure. A Poisson process with rate $\lambda$ was used to model the arrival
process of the intruders. The intruders arrive with equal probability on the
endpoints. We simulated 50 runs per algorithm and present the mean and
standard deviation of the _capture fraction_ obtained by each algorithm for
various values of $v$ keeping $\rho$ and $\lambda$ fixed to $0.2$ and $5$
respectively. The _capture fraction_ is defined as the ratio of the total
number of intruders captured to the total number of intruders arrived in the
environment [21]. The value of $\lambda$ was kept high because for low arrival
rate ($\lambda\to 0$), the number of intruders that arrive in the environment
were very few and the capture fraction obtained was misleadingly high.

Figure 3 shows the simulation result for each of the algorithms. For values of
$v$ and $\rho$ that lie above the blue curve in Figure 2, the CaC algorithm
captured, on average, more than half of the intruders that arrived.
Furthermore, the capture fraction of CAP algorithm was approximately $0.5$ on
average for all values of $v$. This is because the intruders being uniformly
distributed, the vehicle can just capture intruders on one side and still
ensure at least half of the total intruders are captured. Moreover, as $v$
increases the capture fraction of Sweep algorithm approaches that of CaC
algorithm. This is because as $v$ increases, the sizes of the sets
${S}_{\textup{same}}$ and ${S}_{\textup{opp}}$ increase and eventually they
cover the entire environment, thereby, converging to the Sweep algorithm.

Figure 3: Simulation result for $\lambda=5$ and $\rho=0.2$. The error bars
indicate $\pm 1$ standard deviation.

##  VI Conclusion and Future Work

This paper addressed a problem in which a single vehicle is tasked to defend a
line segment perimeter from intruders. The key novelty of this work is an
integration of concepts and techniques from competitive analysis of online
algorithms with pursuit of multiple mobile intruders. We designed and analyzed
three algorithms, i.e., Sweeping, Compare and Capture, and Capture with
Patience algorithms, and demonstrated that they are $1$, $2$ and
$4$-competitive, respectively. We also derived fundamental limits on
$c$-competitiveness for any constant $c$.

We plan to extend this work for the case when the intruders need to move
outward or can actively evade the vehicle in order to reach the perimeter.
Cooperative multi-vehicle defense in higher dimensional environments that can
yield lower competitive ratios is another future direction.

## References

  * [1] D. D. Sleator and R. E. Tarjan, “Amortized efficiency of list update and paging rules,” _Communications of ACM_ , vol. 28, no. 2, pp. 202–208, 1985\.
  * [2] R. Isaacs, _Differential games: a mathematical theory with applications to warfare and pursuit, control and optimization_. Courier Corp., 1999.
  * [3] M. Chen, Z. Zhou, and C. J. Tomlin, “Multiplayer reach-avoid games via pairwise outcomes,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 3, pp. 1451–1457, 2016.
  * [4] E. Garcia, A. Von Moll, D. W. Casbeer, and M. Pachter, “Strategies for defending a coastline against multiple attackers,” in _2019 IEEE 58th Conf. on Decision and Control (CDC)_. IEEE, 2019, pp. 7319–7324.
  * [5] K. Margellos and J. Lygeros, “Hamilton–Jacobi formulation for reach–avoid differential games,” _IEEE Transactions on Automatic Control_ , vol. 56, no. 8, pp. 1849–1861, 2011.
  * [6] M. Chen, Z. Zhou, and C. J. Tomlin, “A path defense approach to the multiplayer reach-avoid game,” in _53rd IEEE conference on decision and control_. IEEE, 2014, pp. 2420–2426.
  * [7] R. Yan, X. Duan, Z. Shi, Y. Zhong, and F. Bullo, “Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games,” 2019, online available at:https://arxiv.org/abs/1909.11881.
  * [8] D. Shishika and V. Kumar, “Perimeter-defense game on arbitrary convex shapes,” _arXiv preprint arXiv:1909.03989_ , 2019, online available at:https:https://arxiv.org/abs/1909.03989.
  * [9] H. N. Psaraftis, “Dynamic vehicle routing problems,” _Vehicle routing: Methods and studies_ , vol. 16, pp. 223–248, 1988.
  * [10] D. J. Bertsimas and G. Van Ryzin, “A stochastic and dynamic vehicle routing problem in the Euclidean plane,” _Operations Research_ , vol. 39, no. 4, pp. 601–615, 1991.
  * [11] S. L. Smith, M. Pavone, F. Bullo, and E. Frazzoli, “Dynamic vehicle routing with priority classes of stochastic demands,” _SIAM Journal on Control and Optimization_ , vol. 48, no. 5, pp. 3224–3245, 2010.
  * [12] S. D. Bopardikar and V. Srivastava, “Dynamic vehicle routing in presence of random recalls,” _IEEE Control Systems Letters_ , vol. 4, no. 1, pp. 37–42, 2019.
  * [13] 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.
  * [14] E. Angelelli, M. Grazia Speranza, and M. W. Savelsbergh, “Competitive analysis for dynamic multiperiod uncapacitated routing problems,” _Networks: An International Journal_ , vol. 49, no. 4, pp. 308–317, 2007.
  * [15] M. Blom, S. O. Krumke, W. E. de Paepe, and L. Stougie, “The online TSP against fair adversaries,” _INFORMS Journal on Computing_ , vol. 13, no. 2, pp. 138–148, 2001.
  * [16] S. Henn, “Algorithms for on-line order batching in an order picking warehouse,” _Computers & Operations Research_, vol. 39, no. 11, pp. 2549–2563, 2012.
  * [17] A. Stieber, A. Fügenschuh, M. Epp, M. Knapp, and H. Rothe, “The multiple traveling salesmen problem with moving targets,” _Optimization Letters_ , vol. 9, no. 8, pp. 1569–1583, 2015.
  * [18] M. Hassoun, S. Shoval, E. Simchon, and L. Yedidsion, “The single line moving target traveling salesman problem with release times,” _Annals of Operations Research_ , pp. 1–10, 2019.
  * [19] C. S. Helvig, G. Robins, and A. Zelikovsky, “Moving-target TSP and related problems,” in _European Symposium on Algorithms_. Springer, 1998, pp. 453–464.
  * [20] S. Bajaj and S. D. Bopardikar, “Dynamic boundary guarding against radially incoming targets,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_ , 2019, pp. 4804–4809.
  * [21] 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_ , 2009, pp. 8543–8548.
  * [22] A. Borodin and R. El-Yaniv, _Online computation and competitive analysis_. cambridge university press, 2005\.
  * [23] S. O. Krumke, W. E. De Paepe, D. Poensgen, and L. Stougie, “News from the online traveling repairman,” _Theoretical Computer Science_ , vol. 295, no. 1-3, pp. 279–294, 2003.