DYNAMIC BOUNDARY GUARDING AGAINST RADIALLY INCOMING TARGETS 

By 

Shivam Bajaj 

 
 
 
 
 
 
 
 
 
 

A THESIS  

Michigan State University  

in partial fulfillment of the requirements  

Submitted to  

for the degree of 

Electrical Engineering – Master of Science 

2019 

ABSTRACT

DYNAMIC BOUNDARY GUARDING AGAINST RADIALLY INCOMING TARGETS

By

Shivam Bajaj

In this modern era, every physical asset can be defined by a perimeter and guarding these perimeters
is critical from a security and safety perspective. Recent growth in autonomous vehicle technology
has led to assigning these monotonous tasks to the autonomous vehicles. This assignment requires
design of a set of motion laws for these autonomous vehicles that are both effective and efficient,
with provable bounds.
This thesis focuses on designing of strategies for a single autonomous vehicle to intercept multiple
targets. In this work, we introduce a dynamic vehicle routing problem in which a single vehicle
seeks to guard a circular perimeter against radially inward moving targets. The aim of the vehicle
is to maximize the capture fraction, i.e., the fraction of targets intercepted before they enter the
perimeter. We first obtain a fundamental upper bound on the capture fraction which is independent
of any policy followed by the vehicle. We analyze several policies in the low and high arrival
rates of target generation. For low arrival, we propose and analyze a First-Come-First-Served
and a Look-Ahead policy based on repeated computation of the path that passes through maximum
number of unintercepted targets. For high arrival, we design and analyze a policy based on repeated
computation of Euclidean Minimum Hamiltonian path through a fraction of existing targets and
show that it is within a constant factor of the optimal. Finally, we provide a numerical study of the
performance of the policies in parameter regimes beyond the scope of the analysis.

This thesis is dedicated to my parents.

Thank you for supporting and believing in me.

iii

ACKNOWLEDGEMENTS

I consider myself highly fortunate to have had the opportunity to work on this thesis under the
guidance of Dr. Shaunak D. Bopardikar. He has been a great role model, an excellent mentor and
has not only taught me the best research practises but also supported me during difficult times.
My committee members Dr. Zhaojian Li and Dr. Vaibhav Srivastava have been approachable and
co-operative in my final semester. I would also like to offer my thanks to the ECE department of
Michigan State University for providing me with their help and resources from time to time.

I would also like to express my gratitude towards all my teachers for their guidance throughout
the academic journey and my friends and roommates for their support. Most importantly, I would
like to thank my family for their inspiration, love and support throughout this wonderful journey.

iv

TABLE OF CONTENTS

.
.

.
.

.
.

.
.

.
.

.
.

LIST OF TABLES .
LIST OF FIGURES .
CHAPTER 1

.
.
.
.
INTRODUCTION .
1.1 Vehicle Routing Problems .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.1.1 Dynamic Vehicle Routing Problems . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
6
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Contributions .
1.3 Organization .

.
. .

vi

.
.

.
.

.
.

.
.

.
.

2.1 Mathematical Modeling and Problem Statement
2.2 Preliminary Results .

CHAPTER 2 RADIALLY INCOMING TARGETS PROBLEM . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7
7
9
9
9
. . . . . . . . . . . . . . . . . . . . . 10
. . . . . . . . . . . . 11

2.2.1 Longest Paths in Directed Acyclic Graphs (DAG)
2.2.2 Capturable set .
2.2.3 Distribution of Outstanding Targets
2.2.4 Bounds on paths through static and incoming targets

.

.

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1 Low Arrival Rate of Targets . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

CHAPTER 3 CAPTURE FRACTION UPPER BOUND . . . . . . . . . . . . . . . . . . . 13
. 16
CHAPTER 4 POLICIES .
. 16
First-Come-First-Serve (FCFS) policy . . . . . . . . . . . . . . . . . . . . 16
Policies based on Look-ahead . . . . . . . . . . . . . . . . . . . . . . . . . 18
. 23
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.2 High Arrival Rate of Targets
4.3 Discussion .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.1
4.1.2

. .

. .

.

.

.

.

.

.

CHAPTER 5 SIMULATIONS .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
CHAPTER 6 CONCLUSIONS AND FUTURE WORK . . . . . . . . . . . . . . . . . . . 30
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
BIBLIOGRAPHY .

.

.

.

.

.

.

.

.

v

LIST OF TABLES

Table 1.1: Performance of policies for the DTRP problem.

. . . . . . . . . . . . . . . . . .

Table 1.2: Performance of policies for the RIT problem.

. . . . . . . . . . . . . . . . . . .

4

5

vi

LIST OF FIGURES

Figure 2.1: Problem setup. The environment is an annulus of inner radius ρ and outer
radius D. Targets are depicted as black dots approaching the perimeter at
constant speed. The vehicle is shown as a triangle. . . . . . . . . . . . . . . .

.

Figure 2.2: A Directed Acyclic Graph.

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

9

Figure 2.3: The quantity Ti+1 indicates the time taken by the vehicle to move from target

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

i to the target i + 1.
(a) The set ST for RIT problem. The set ¯ST is shown by a solid boundary,
which is a circle of radius (1 + v)T. (b) The area element ζ of length and
width m in ¯ST.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

.

.

.

.

Figure 3.1:

Figure 4.1: The evolution of NCLA policy. The solid line depicts the path planned
including those that have not arrived yet. In contrast, the dashed line is the
path from the causal look ahead policy, which only considers targets that have
arrived. .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

.

.

.

.

.

.

.

Figure 4.2: Scenarios for proof of Theorem 4.1.2.

In (a), vehicle visits 5 targets so
La = 5.(b) vehicle visits 6 targets so m = 6. (r2, θ2) is the highest target on
(b) capturable from pa(t1) thus n = 1. The red line shows the path followed
by the vehicle in NCLA through arrived and unarrived targets. . . . . . . . . . . 19

Figure 4.3: The transformation of the environment from a disk like to a rectangle.

. . . .

. 22

Figure 4.4: The RMHP-fraction policy. The figure on the left shows the EMHP through
all outstanding targets. The figure on the right shows the instant when the
vehicle has followed the path through ρ/v time units and allows some targets
to escape .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

.

.

.

.

.

.

Figure 5.1:

(a) Comparison of FCFS policy with fundamental and theoretical bounds for
v = 0.2. The red dash-dot line shows the fundamental upper bound and red
dash curve shows the theoretical bound for FCFS. (b) Comparison of SAC
with theoretical bound from 4.1.1 and FCFS for v = 0.5. The red dash-dot line
shows the capture fraction of FCFS and red dash curve shows the theoretical
bound for SAC.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

. .

Figure 5.2: Simulation results for NCLA and LA policy for v = 0.8. The red curve shows
the fundamental upper bound. Capture fraction of NCLA is shown by the
blue curve and the theoretical bound analyzed in 4.1.2 is shown in green color.

. 27

vii

Figure 5.3: Simulation results for RMHP-fraction policy for v = 0.04. The red dash-dot
curve is from the policy independent upper bound in Theorem 3.0.1 and the
dashed curve shows the theoretical bound.

. . . . . . . . . . . . . . . . . . . . 28

Figure 5.4: Simulation results for NN policy and comparison with FCFS for v = 0.2. The
black curve shows the capture fraction of FCFS and the green curve shows
the capture fraction of the NN policy.

. . . . . . . . . . . . . . . . . . . . . . 28

Figure 5.5: Simulation results for the case of non-uniform distribution for v = 0.5. The
black curve shows the capture fraction of FCFS. The capture fraction of LA
policy is shown by blue curve and the green curve shows the capture fraction
of the NN policy.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

.

.

viii

LIST OF ALGORITHMS

1
2
3
4
5

First-Come-First-Serve (FCFS) policy . . . . . . . . . . . . . . . . . . . . . . . .
. 16
Stay-at-center (SAC) policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Look Ahead (LA) policy .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Non-causal Look Ahead (NCLA) policy . . . . . . . . . . . . . . . . . . . . . . . . 20
RMHP-fraction policy .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

.

ix

CHAPTER 1

INTRODUCTION

Autonomous robotic agents have numerical applications, for instance, in environmental monitoring
and surveillance [1], providing or extending network coverage to remote areas [2], search and
rescue [3] and providing aid to the elderly [4]. To accomplish these various tasks, a robotic
agent depends mainly on sensors, manipulation and path planning. Path planning requires a set of
algorithms that determines their motion in the environment. To perform these aforementioned tasks
effectively, these algorithms have to deal with service allocation problems. We focus our attention
to path planning algorithms of a robotic agent, more specifically to dynamic vehicle routing.

Dynamic vehicle routing (DVR) problems are vehicle routing problems in which the vehicles
have to plan their paths through the points of interest which arrive sequentially over time. This
thesis addresses a DVR problem involving moving targets. Targets are generated at the boundary
of an environment and move with a constant speed in order to enter a perimeter. A single vehicle
is assigned a task of capturing as many targets as it can before they enter the perimeter. This
setup is highly relevant in surveillance applications that involve gathering additional information
on mobile targets and in civilian space applications such as protecting the space-stations from
debris. Additional application of this setup are envisioned in guarding of airport runways from
rogue drones. We now review the current literature in these area in the next section.

1.1 Vehicle Routing Problems

Vehicle routing refers to planning optimal vehicle routes for providing service to a given set
of customers or demands. Due to a recent surge in the area of motion planning, researchers have
addressed a lot of variants of the Vehicle Routing Problem(VRP) over the last decade [5]. A VRP
is a challenging problem as most VRPs are NP-hard. A NP-hard problem is the one for which
there does not exist an algorithm that can solve the problem in polynomial time. There are a lot of
extensions of the VRP. The following are the most studied and relevant to this thesis:

1

1. VRP with time-windows – These are the problems in which the demands have to be serviced
in a limited time frame. The VRP with time window is necessary in case of goods delivery or
customer satisfaction enhancement. Significant research has been done in the VRP with time
windows [6], [7]. In [8],the authors have considered the problem of multiple time windows
and has proposed an algorithm based on ant colony system.

2. VRP with moving demands – In these type of problems, the demands move with some velocity.
Several research has been done in this area. Authors in [9] gave an approximation algorithm
for the moving target TSP in which targets move with random velocity. Authors in [10] study
a kinetic variant of the k-delivery TSP where the targets move with the same velocity and a
robotic arm moving with a finite capacity must intercept them. In [11], it was shown that
the moving target TSP can be best approximated by a factor of 2O(√
n) times the optimal.
They also showed that there is a polynomial time approximation if the targets have the same
velocity.

3. Dynamic Vehicle Routing – The class of problems in which the arrival process of the demands

is stochastic. The next subsection discusses the literature in this area in detail.

1.1.1 Dynamic Vehicle Routing Problems

Standard vehicle routing problems in operations research are concerned with planning optimal
vehicle routes to visit a set of fixed targets. This requires solving an underlying combinatorial
optimization problem [12].In contrast, DVR requires that the vehicle routes be re-planned as
new information becomes available over time which was originally introduced on graphs in [13].
In DVR, the planning algorithms should provide policies that suggests how the route should
evolve in real time. Although, some papers consider dynamic travel times [14], in general, the
dynamic aspect comes from the occurrence of a new demand over time. Environments may be
dynamically varying [15, 16] and the targets may have multiple levels of priorities [17]. The
vehicles may be tasked with performing pickup and delivery operations [18],[19]; may possess

2

motion constraints [20, 21, 22] and need not require mutual communication [23]. A review of this
literature was conducted in [24]. A generic mathematical model for dynamic and stochastic vehicle
routing problem, termed as Dynamic Travelling Repairman Problem (DTRP), has been mainly
studied by Bertsimas and Van Ryzin in [25].

In [25], the authors considered a convex, bounded region of area A with demands for service
arriving in time as a Poisson process with rate λ. Each demand requires an independent and
identically distributed amount of on-site service with mean duration ¯s and ¯s2. A single service
vehicle spends ρ amount of time to service a demand with the goal to minimize the system time at
steady state. The authors established two powerful lower bounds on the optimal expected system
time (T∗). In the case of light traffic, i.e., λ → 0, T∗ ≥ E[||X−x∗||]
+ λ¯s2
2(1−ρ) + ¯s, where E[||X − x∗||]
is the first moment of the distance between a uniformly chosen point X and center x∗. In the case of
heavy load, T∗ ≥ γ
, where γ ≈ 0.266. A brief description of the policies analyzed
by Bertsimas and Van Ryzin in [25] is given below.

(1−ρ)2 − 1−2ρ

1−ρ

2 λA

2λ

• First Come First Serve (FCFS) : The demands are served in the order they appear.

• Stochastic Queue Median (SQM) : This is a special policy in FCFS. In this modification,
the vehicle travels from the median to the demand’s location. After service completion, the
vehicle travels back to the median location and waits for the next demand.

• Partitioning policy (PP) : In this policy, the service region is partitioned into smaller subre-

gions. The demands are serviced in those subregions using FCFS policy.

• Travelling Salesman Policy (TSP) : This policy is based on collecting demands into sets that

can be served using a TSP tour.

• Space Filling Curve (SFC) : The demands are serviced as they are encountered in repeated

clockwise sweeps of the region assuming that the demands’ position is maintained.

• Nearest Neighbor (NN) : The closest demand after a service completion is serviced next.

3

Design Regime

Algorithm

Light Load

High
Load

SQM
PART

TSP
SFC

Regime of constant fac-
tor optimality
λ → 0
ρ → 1
ρ → 1
ρ → 1

Factor of optimality

1
2c1
2
γ
2
β
TSP
2
γ
0.66

Table 1.1: Performance of policies for the DTRP problem.

The policies proposed in [25] has been summarized in table 1.1 with their respective factor of
optimality. This thesis draws inspiration from the work done in [25]. Akin to the lower bounds
discussed above, we have obtained a fundamental upper bound to the problem considered in this
work. Later, we proposed and analyzed some policies suitable for low and high arrival rate of
demands.

There has been a recent surge in activity in the area of pursuit of mobile targets that seek to reach
a destination. In [26], the authors consider a setup of guarding a line segment in the case of a single
pursuer and a single evader. They provide with different conditions in which either the defender or
the attacker wins. The authors of [27] consider a pursuit evasion dynamic guarding problem with
two vehicles and one demand moving with constant speeds. The vehicles move cooperatively to
pursue the demand in a planar environment and gives different cooperative strategy between the
two pursuers. The same authors in [28] consider a differential game of attacker-target-defender. In
[10, 29], the authors consider demands that are slower than the vehicle which is moving parallel
to x or y axis.
[30] introduced a DVR boundary guarding problem in which a single vehicle was
assigned to stop the demands from reaching a deadline in a rectangular environment. Authors
in [31] considered the case of targets being generated inside a disk-like environment and moving
radially outward to escape the region.

4

Design Regime

Algorithm

Factor of optimality

Light
Load
High Load

Regime of constant fac-
tor optimality
λ → 0
λ → 0
λ → ∞

SAC
LA
RMHP

1
1
6.77
Table 1.2: Performance of policies for the RIT problem.

1.2 Contributions

The environment considered in this thesis is an annulus of inner radius ρ and outer radius D.
The targets are generated uniformly and randomly on the boundary as per a Poisson process in
time with rate λ. Upon generation, every target moves with a constant velocity v < 1 towards the
perimeter. A vehicle, modeled as a first-order integrator moving with unit speed, seeks to intercept
the targets before they reach the perimeter. The performance of the vehicle is the expected value of
the capture fraction, i.e., the fraction of the targets that are intercepted, at steady state.

1+λρ

Our contributions are as follows. We first determine a policy independent upper bound on
). Second, we design three
the capture fraction of the targets and show that it scales as O( 1+v√
policies for the vehicle and characterize analytic lower bounds on the resulting capture fraction
In particular, for low arrival rates of the targets, we show that
in limiting parameter regimes.
the capture fraction scales as Ω(
) using a policy based on intercepting the targets as per the
1
first-come-first-served order. We then characterize the performance of a policy with look-ahead
based on repeated computation of a path that maximizes the number of targets intercepted in a
horizon. Third, in the regime of high arrival rates λ → +∞, we analyze the performance of a policy
based on repeated computation of the Euclidean Minimum Hamiltonian Path (EMHP) through the
). In particular, we
radially moving targets and show that its performance scales as Ω(
show that the capture fraction of this policy is within a constant factor of optimal if v → 0+. A
constant factor of optimality is defined as the ratio of fundamental upper bound for RIT problem
to the capture fraction of a policy. Table 1.2 summarizes these lower bounds fro the RIT problem.
Numerical simulations suggest that our analytic bounds generalize beyond the limiting parameter
regimes. Although the focus of the problem is similar to the ones in [30] and in [31], the geometry

1−v
√
v(1+

v)λρ

vλρ

√

5

of the environment and direction of the targets yield distinct results. This work in this thesis is
based on the conference paper [32].

1.3 Organization

This thesis is organized as follows. Chapter 2 comprises the formal problem definition and
a summary of background concepts and novel intermediate properties. In Chapter 3, we derive
a novel policy independent upper bound on the capture fraction.
In Chapter 4, we present two
policies suitable for low arrival rate of the targets and a policy suitable for high arrival rates and
we derive novel lower bounds on their performance. In Chapter 5, we present results of numerical
simulations. Finally, Chapter 6 summarizes this thesis and outlines directions for future research.

6

CHAPTER 2

RADIALLY INCOMING TARGETS PROBLEM

In this chapter, we present a novel vehicle routing problem involving moving targets.
In this
problem, a target moves with a constant velocity in order to breach a perimeter. One application of
this problem is in robotic guarding where it is necessary to stop an agent from entering a perimeter.
We begin with a mathematical description of the problem and provide preliminary properties of
the model considered.

2.1 Mathematical Modeling and Problem Statement

Consider a disk like environment E = {(r, θ) : 0 < ρ ≤ r ≤ D, ∀ θ ∈ [0, 2π)}. Targets appear
uniformly and randomly at the boundary of the disk, i.e., at r = D. Upon generation, every target
moves radially inward towards the inner circular boundary, termed as the perimeter, having radius
ρ in E. The arrival times of the targets are as per a Poisson process with rate λ. We consider a
single service vehicle with motion modeled as a first order integrator with unit speed and with the
ability to move in R2. The vehicle is said to capture a target when it is collocated with a target while
the target is in E. A target gets removed from the environment if it gets captured by the vehicle.
A target is said to escape when it reaches the perimeter and is not intercepted by the vehicle. We
assume that the speed of the targets is less than that of the vehicle (v < 1). Hence, a target must be
captured within (D − ρ)/v time units of being generated. We refer to this problem as RIT problem
for convenience.

Let Q(t) ⊂ E denote the set of all outstanding target locations at time t. If the ith target that
arrives gets captured, then it is placed in Qcapt(t) having cardinality ncapt(t), and is removed from
Q(t). Otherwise, it is placed in Qesc(t) having cardinality nesc(t) and removed from Q(t). Akin to
the work in [30] that formally defined causal nature of policies, we will consider both causal and
non-causal policies for the RIT problem, defined as follows.

Causal Policy: A causal feedback control policy for a vehicle is a map P : E × F → R2, where

7

Figure 2.1: Problem setup. The environment is an annulus of inner radius ρ and outer radius D.
Targets are depicted as black dots approaching the perimeter at constant speed. The vehicle is
shown as a triangle.

F(E) is the set of finite subsets of E, assigning a commanded velocity to the vehicle as a function
of the current state of the system, yielding the kinematic model,

(cid:219)p(t) = P(p(t), Q(t)).

Non-causal Policy: In a non-causal feedback control policy, the velocity of the vehicle is a function
of current and future states of the system. Although these policies are physically unrealizable, they
serve as a means to compare the performance of causal policies against the optimal.

Problem Statement: The aim of this thesis is to design policies P that maximize the fraction of

targets that are captured Fcap(P), termed as capture fraction, where

(cid:20)

(cid:21)

.

Fcap(P) := lim

t→∞ sup E

ncapt(t)

ncapt(t) + nesc(t)

As is typical of DVR problems, we propose different policies that are suitable for low and high
arrival rates of the targets. But we first present some preliminary and novel results in the next
sub-section which will be used to establish the fundamental limit and analyze the policies.

8

Figure 2.2: A Directed Acyclic Graph.

2.2 Preliminary Results

We review a concept related to longest paths on graphs as well as derive some basic results

which will be used to obtain bounds on paths through a set of radially moving targets.

2.2.1 Longest Paths in Directed Acyclic Graphs (DAG)
A graph G = (V, E) is called a directed graph if it consists of a set of vertices V and a set of directed
edges E ⊂ V ×V [30]. A graph is acyclic if its first and the last vertex are not same in the sequence.
A DAG graph is shown in Fig 2.2. Finding the longest path, i.e. to find a path that visits maximum
number of vertices, is NP-hard to solve as its solution requires the solution of Hamiltonian path
problem [33]. However, for a DAG, the longest path problem has an efficient dynamic solution,
[34] with complexity that scales polynomially with the number of vertices.

2.2.2 Capturable set

The capturable set comprises the set of locations of all targets that can be captured from a given
vehicle location, defined formally as follows.

Definition 2.2.1. A vehicle located at (x, 0) can capture targets located in the capturable set,

C(x, v, ρ) := {(r, θ) ∈ E : r < rc,∀θ ∈ [0, 2π)}

9

where,

rc(x, v, ρ, θ) = min{D, ρ + v

(cid:113)

2 + x2 − 2x ρ cos θ}.
ρ

If the vehicle located at(x, 0) requires time T to intercept a target located at(r, θ), then r−vT ≥ ρ.
By setting rc − vT = ρ, we obtain the expression for rc. The location rc corresponds to the location
of the targets that the vehicle can capture before they enter the perimeter.

2.2.3 Distribution of Outstanding Targets

In this subsection, we derive the distribution of targets in any region of the environment at steady
state. Recall that an annular section A(a, b, θ1, θ2) ⊂ R2 is the set A(a, b, θ1, θ2) := {(r, θ) | a ≤
r ≤ b, θ ∈ [θ1, θ2]}.

Lemma 2.2.1 (Outstanding targets). Suppose the arrival of targets starts at time 0 and no targets
are intercepted in the interval [0, t]. Let Q denote the set of all targets in [D, D − vt],∀θ ∈ [0, 2π)
at time t. Then, given a set R(r, ∆r, θ, ∆θ), of infinitesimal area A, contained in Q,

P[|R ∩ Q| = n] =

e− ¯λA( ¯λA)n

n!

, where ¯λ =

λ
2πvr .

Furthermore,

E[|R ∩ Q|] = ¯λr∆r∆θ, and Var[|R ∩ Q|] = ¯λr∆r∆θ.

Proof. Let R(r, ∆r, θ, ∆θ) ⊂ R2 be an area element where ∆r,∆θ are infinitesimally small. Let Q
denote the set of all targets in [D, D − vt], ∀θ ∈ [0, 2π). Then, the probability that R contains n
points out of Q at time t satisfies

P[|R ∩ Q| = n]

∞


=

P[ i targets arrive in [ D − (r + ∆r)
× P[ n of i targets generated in (θ, θ + ∆θ)].

i=n

v

D − r
v

]

,

10

Now,

and

P[i targets arrive in [0,

∆r
v

]] =

P[n of i targets generated in (0, ∆θ)]

,

v

e(−λ∆r
)( λ∆r
v )i
i!
(cid:19)i−n

1 − ∆θ
2π

.

e−λR(λR)i

(i!)(H)n(1 − H)i−n

i!
i=n
e−λR(H)n

n!

i=n
e−λR(λRH)n

∞

∞


(n!)(i − n)!
(λR)i(1 − H)i−n

(i − n)!
((λR)(1 − H))j

j!

j=0
eλR(1−H)

n!

n!

e−λR(λRH)n
e−λRH(λRH)n
e− ¯λA( ¯λA)n

n!

n!

,

=

=

=

=

=

Since the generation is uniform in space and Poisson in time,

P[|R ∩ Q| = n]

∞


i=n

=

P[ i targets arrive in [0,

]

∆r
v

× P[ n of i targets generated in (0, ∆θ)].

n
Let ∆r/v = R and ∆θ/2π = H. Thus,

(cid:18)i

=

(cid:19)n(cid:18)
(cid:19)(cid:18) ∆θ
∞


2π

P[|R ∩ Q| = n] =

where ¯λ = λ/v2πr and A is the area of the annulus sector.

(cid:3)

This result establishes that the number of unintercepted targets in an annulus is Poisson dis-

tributed uniformly with parameter λ

v ∆d, where ∆d is the difference in the radii of the annulus.

2.2.4 Bounds on paths through static and incoming targets

The following result will be used to bound the length of the path through targets in the environment.

11

Figure 2.3: The quantity Ti+1 indicates the time taken by the vehicle to move from target i to the
target i + 1.

Theorem 2.2.1 (Bounds on path through incoming targets). Let T be the length of the actual path
through the incoming targets and Ts be the length of the path through their static initial locations.
Then,

Ts
1 + v

≤ T ≤ Ts
1 − v

.

capture this target at time
i
(ri − v
i+1

j=1 Tj, θi) and (ri+1 − v
i+1

Proof. Let the targets be labeled in the order in which they arrive. Let Tj be the time taken by
the vehicle to capture the jth incoming target. Consider the ith target at (ri, θi). The vehicle will
j=1 Tj. It then moves toward the (i + 1)th target and reaches it in a time
duration of Ti+1 which is equal to the distance covered due to unit speed. Let the distance between
(cid:48)
i+1. Also, let Ts,i+1 be the distance between
(ri − v ¯T, θi) and (ri+1 − v ¯T, θi+1), where ¯T < T. As the distance between two targets moving
(cid:48)
radially inward with same speed is non-increasing function of time, Ts,i+1 ≤ T
i+1. Therefore, from
(cid:48)
i+1/(1 + v) ≥ Ts,i+1/(1 + v).
triangle inequality (Fig. 3), Ti+1 + vTi+1 ≥ T
= Ts1+v . The
(cid:3)

Extending this to all the targets we get the expression, T =
n

proof for the upper bound is similar to the proof above and has been omitted for brevity.

(cid:48)
i+1. This means, Ti+1 ≥ T

j=1 Tj, θi+1) be T

i=1 Ti+1 ≥
n

Ts,i+1
1+v

i=1

The next is a classic result regarding the upper bound on the shortest path through a set of fixed

points in an environment.

Theorem 2.2.2 (Shortest Euclidean path [35]). Given n points in a square of length R, there is a
path through the n points of length not exceeding R

√
2n + 1.75R.

12

CHAPTER 3

CAPTURE FRACTION UPPER BOUND

This chapter summarizes the first of our analytic results – a policy independent upper bound on
the capture fraction. This is a fundamental limit to this problem and is valid for any values of
the problem parameters. First, we derive a lower bound on the expected travel time between two
targets, which will be useful to derive the fundamental bound.

Lemma 3.0.1 (Travel time lower bound). If Td is a random variable denoting the time required to
travel between targets in Q, then

(cid:114) vπ ρ

E[Td] ≥ 1
1 + v

.

2λ

Proof. Let ST comprise the set of targets that can be reached from vehicle position (X, 0) in at most
T time units, as shown in Fig. 3.1. Mathematically,

ST := {(r, θ) ∈ E | X2 + (r − vT)2 − 2X(r − vT) cos θ ≤ T2}.

Also, let

¯ST := {(r, θ) ∈ E | (X − r cos θ)2 + (r sin θ)2 ≤ ((1 + v)T)2}.

Since the relative velocity of any target with respect to the vehicle is less than or equal to (1 + v),
the distance d1 of any point on the boundary of ST from (X, 0) is at most T(1 + v). This means that
the set ST will be contained in a circle centered at the same position (X, 0) of radius (1 + v)T, i.e.,
ST ⊂ ¯ST. If Td denotes the minimum amount of time needed to go from vehicle location (X, 0) to
any target, then, Td > T, if ST is empty i.e., P[Td > T] = P[|ST| = 0]. Moreover,

P[| ¯ST| = 0] = P[|ST| = 0]P[| ¯ST \ ST| = 0] ≤ P[|ST| = 0].

Now, consider an infinitesimal area element ζ of length and width m at (s, 0) from the center

13

Figure 3.1: (a) The set ST for RIT problem. The set ¯ST is shown by a solid boundary, which is a
circle of radius (1 + v)T. (b) The area element ζ of length and width m in ¯ST.

(cf. Fig. 3.1 (b)). From Lemma 2.2.1, the probability that ζ is empty will be:

P[|ζ| = 0] = e

= e

≥ e

= e

−λ2πv
dθdr
m2
−λ2πv
s
−λm2
2πv ρ
−λ2πv ρ

Area(ζ)
,

where the inequality comes from the fact that s ∈ [ρ, D]. Since every compact set can be written
as a countable union of non-overlapping area elements, the result is true for ¯ST as well. Therefore,

P[|ST| = 0] ≥ P[| ¯ST| = 0] ≥ e

−λ2v ρ

((1+v)T)2

,

and thus, the expectation of Td can be bounded as

E[Td] =

=

≥

=

=

P[Td > T]dT
P[|ST| = 0]dT
P[| ¯ST| = 0]dT

(cid:114)2v ρ
(cid:114) πv ρ

λ

.

2λ

Þ ∞
Þ ∞
Þ ∞

0

0

0

√

π

2(1 + v)
1
1 + v

14

We now present the main result of this chapter.

(cid:3)

Theorem 3.0.1 (Upper bound on capture fraction). Any policy P for the RIT problem must satisfy

(cid:40)

Fcap(P) ≤ min

1,(1 + v)

(cid:115) 2

vλπ ρ

(cid:41)

.

Proof. A utilization factor (u) is defined as the ratio of the rate at which demands arrive to the
maximum rate at which the service is done. Thus,

u = average arrival rate × average service time
= cλE[Td].

This comes from the fact that each target takes, on average, service time of E[Td] and the vehicle
services a fraction c ∈ (0, 1] of targets. Note that, the service time is the time taken by the vehicle
to reach a target. As the maximum service rate of the vehicle is unity, we get the expression for
utilization factor.
To service a fraction c ∈ (0, 1] of targets, the service rate of the targets must be greater than the
arrival rate [36], i.e., cλE[Td] ≤ 1. Using Lemma 3.0.1, we obtain this result. Note that, for c = 1,
we get a standard expression for the queueing systems [36].
(cid:3)

With this fundamental limit in place, we will now present several policies and examine their

performance in comparison to this upper bound.

15

CHAPTER 4

POLICIES

In this chapter, we present three main policies and analyze lower bounds on the resulting capture
fraction for the RIT problem. In particular, for low arrival rate of targets, we analyze the performance
of a policy based on first-come-first-served order. We then characterize the performance of a policy
with look-ahead based on repeated computation of a path that maximizes the number of targets
intercepted in a horizon. Third, for high arrival rates λ → +∞, we analyze the performance of
a policy based on repeated computation of the Euclidean Minimum Hamiltonian Path (EMHP)
through the radially moving targets.

4.1 Low Arrival Rate of Targets

We propose two main policies for the parameter regime of low arrival rates of targets. The
FCFS policy is very simple to implement whereas the look ahead (LA) policy requires repeated
computation of longest paths.

4.1.1 First-Come-First-Serve (FCFS) policy

According to this policy, the vehicle intercepts the targets in the order in which they arrive. If there
are no outstanding targets, the vehicle waits at the center of E for the targets to appear. The policy
is summarized in Algorithm 1.

Algorithm 1: First-Come-First-Serve (FCFS) policy
1 Assumes that the vehicle is at the center.
2 if No outstanding targets in E then
Wait for the next target to arrive,
3
4 else
5
6 end
7 Repeat.

Move to intercept the target farthest from the boundary.

16

The FCFS policy is difficult to analyze directly. Thus, we provide the lower bound by analyzing
an even simpler Stay-at-Center (SAC) policy in which the vehicle captures a target just before
the target enters the perimeter and returns back to the center. The algorithm for SAC policy is
summarized in Algorithm 2.

Algorithm 2: Stay-at-center (SAC) policy
1 Assumes that v and ρ is known and vehicle is placed at the center.
2 Intercept a target that appears inside C(x, v, ρ).
3 Return back to center.
4 Repeat from step 2.

Theorem 4.1.1 (SAC capture fraction). For any v ∈ [0, 1), λ ≥ 0, the capture fraction of the SAC
policy satisfies

Fcap(SAC) ≥

1

1 + 2λρ

.

Proof. For ncapt(t) > 0 at some t > 0,

Fcap : = lim

t→+∞ sup E

(cid:20)


(cid:21)

ncapt(t) + nesc(t)

ncapt(t)


(cid:20) nesc(t)

1
1 + nesc(t)
ncapt(t)

ncapt(t)

(cid:21)(cid:19)−1

= lim
t→+∞ sup E

(cid:18)

≥

1 + lim

t→+∞ sup E

where the last inequality comes from an application of Jensen’s inequality applied to the convex
1
function,
(1+x) [37]. Thus, by studying the number of targets that escape per targets captured, we
can determine a lower bound on the capture fraction.

Consider a target i within the capturable set of the vehicle. The time taken by the vehicle to
capture the target just before the perimeter and return back to the center will be 2ρ. Thus, the
number of targets that can breach the perimeter will be equal to the number of targets that enter the
capturable set while the vehicle is capturing the ith target, i.e., all the targets that are at a distance
of 2ρv from the capturable set. Thus, from Lemma 2.2.1, the expected number of targets that will
escape is 2λρ and the result follows.
(cid:3)

17

Figure 4.1: The evolution of NCLA policy. The solid line depicts the path planned including those
that have not arrived yet. In contrast, the dashed line is the path from the causal look ahead policy,
which only considers targets that have arrived.

4.1.2 Policies based on Look-ahead

We now propose and analyze a class of policies in which we constrict the movement of the vehicle
such that the vehicle can only move along the boundary it wants to guard. While such a motion
may be sub-optimal in the present context, it allows us to leverage tools from graph theory and
adapt our earlier ideas on longest path through the mobile targets to design efficient policies [30].

Definition 4.1.1 (Reachable targets). A target located at (r, θ) is reachable from the vehicle location
(ρ, φ) if

r − ρ ≥ v|θ − φ| ρ, for any v ∈ [0, 1).

Definition 4.1.2 (Reachable set). The reachable set from the vehicle position (ρ, φ) ∈ E is

R(ρ, φ) := {(r, θ) ∈ E : r − ρ ≥ v|θ − φ| ρ}.

This means that a target is reachable if it lies in R(ρ, φ). Next, we define the notion of
a reachability graph over the set of radially incoming targets that is inspired out of a similar
construction in [30].

Definition 4.1.3 (Reachability graph). A reachability graph of a set of points{(r1, θ1), . . . ,(rn, θn)} ∈
E, is a DAG with vertex set V := {1, ...n}, and edge set E where, for j, k ∈ V and rj < rk, the edge

18

Figure 4.2: Scenarios for proof of Theorem 4.1.2. In (a), vehicle visits 5 targets so La = 5.(b)
vehicle visits 6 targets so m = 6. (r2, θ2) is the highest target on (b) capturable from pa(t1) thus
n = 1. The red line shows the path followed by the vehicle in NCLA through arrived and unarrived
targets.

(j, k) is in E if and only if

(rk − (rj − ρ), θk) ∈ R(ρ, θ j).

By Section 2.2.1, the time to compute the longest path in a reachability graph scales as O(n2).
We now define a policy based on Look-ahead wherein the vehicle computes the longest path in the
reachability graph of all the targets in E and captures them on the perimeter. Algorithm 3 describes
the algorithm for Look Ahead policy.

Algorithm 3: Look Ahead (LA) policy
1 Assumes that vehicle is located on the perimeter.
2 Compute the reachability graph of all the targets in Q(0) and the vehicle position.
3 Compute the longest path in this graph, starting from the vehicle position.
4 Capture targets in the order they appear at the perimeter.
5 Repeat;

Akin to the rectangular environment considered in [30], Algorithm 3 is difficult to analyze
directly. Instead, we design a Non-causal Look Ahead (NCLA) policy. In this policy, at time 0,
the vehicle computes a reachability graph, from its current position using the information of all the
future targets that are yet to arrive in E (Fig: 4.1). The vehicle then computes the longest path and
captures the targets in the order in which they appear in that path. The algorithm for NCLA policy

19

Algorithm 4: Non-causal Look Ahead (NCLA) policy
1 Assumes that vehicle is located on the perimeter.
2 Compute the reachability graph of all the targets in Q(0) ∪ Qunarrived(0) and the vehicle
3 Compute the longest path in this graph, starting from the vehicle position.
4 Capture targets in the order they reach the perimeter.

position.

is formalized in Algorithm 4.
The following result provides a guarantee on the performance of the LA policy relative to the
NCLA.

Theorem 4.1.2 (LA policy). If D − ρ ≥ vπ ρ, then the capture fraction of the LA policy satisfies

(cid:18)

(cid:19)

Fcap(LA) ≥

1 − vπ ρ
D − ρ

Fcap(NCLA).

Proof. Let the generation of targets begin at t = 0 and consider two scenarios; (a) Look ahead
policy is used by the vehicle, and (b) the vehicle uses the Non-causal look ahead policy (Fig. 4.2).
Then, akin to the steps in the proof of Theorem IV.6 of [30], we can compare the number of targets
captured in both the scenarios.

Consider a time instant t1 where the vehicle is computing the path through all outstanding targets
Q(t1) and denote the path by Πa(t1). The path in scenario (b), denoted as Πb(t1), that the vehicle
will take through Q(t1) be given by ((r1, θ1),(r2, θ2) . . . ,(rm, θm)) ∈ Q(t1). The target (r1, θ1) is
reachable from Πb(t1), but might not be reachable from Πa(t1). The path Πa(t1) comprises targets:
((rn+1, θn+1),(rn+2, θn+2 . . . ,(rm, θm)), n ∈ {0, ..., m − 1}, where (rn+1, θn+1) is the highest target
that is reachable from Πa(t1). Thus, the length of Πa(t1) will satisfy La ≥ m − n, where m is the
length of the path in (b) because the edge weights of the DAG equal unity. Since the worst-case
location for the vehicle is when it is diametrically opposite to the incident target direction, the
vehicle can capture any target i if vπ ρ + ρ ≤ ri. Targets at (r1, θ1), . . . ,(rn, θn) must be at least
vπ ρ + ρ from the center.

If Ntot is the total number of outstanding targets in E at time t1, then by Lemma 2.2.1

E[n | Ntot] = Ntot

vπ ρ
D − ρ

Fcap(NCLA).

20

Therefore, using the fact that La ≥ m − n,

(cid:32)

(cid:32)

(cid:33)

(cid:33)

E[La | Ntot] ≥ Ntot

1 − vπ ρ
D − ρ

Fcap(NCLA),

E[ La
Ntot

| Ntot] ≥

1 − vπ ρ
D − ρ

Fcap(NCLA).

Similarly, in scenario (b),

E[m | Ntot] = NtotFcap(NCLA).

The ratio La/Ntot is the fraction of outstanding targets from the set Q(t1) that will be captured in
scenario (a) and the ratio does not depend on Ntot. Thus, by law of total expectation, we get obtain
the desired claim.
(cid:3)

In Theorem 4.1.2, we established the performance of the LA policy relative to NCLA policy.
However, we can also provide an explicit lower bound on the capture fraction for the LA policy, as
summarized in the result below.

Theorem 4.1.3 (Explicit LA capture fraction). If D − ρ ≥ vπ ρ, then the LA policy satisfies

Fcap(LA) ≥

√

λρ erf(√

1
λπ ρ) + e−λπ ρ

,

π
where erf : R → [−1, 1] is the error function.

Proof. The central idea is to construct an invertible transformation between any realization of
targets and the vehicle in E to a rectangular environment akin to the problem considered in [30].
We then use the analysis from Theorem IV.8 from [30] to arrive at this claim.

Consider an environment E1 that can be constructed by cutting along the radius of E as illustrated
in Fig. 4.3. The transformed environment E1 is an isosceles trapezoid with the two parallel sides
In environment E1, the transformed targets move from an
equal to 2πD and 2π ρ respectively.
initial point on the longer side toward the corresponding point on the smaller side so that the time
taken by every target to reach the smaller side is the same for all targets. This can be achieved by
scaling the speed of each target appropriately as a function of the initial location of the target. E1

21

Figure 4.3: The transformation of the environment from a disk like to a rectangle.

can further be transformed to a rectangular environment E2 in which the transformed targets move
from an initial point on the lower edge toward the upper edge with equal speeds.

Mathematically, consider a target located at (r, θ) in E. This means that the target is r − ρ
distance away from the perimeter. Thus, in E2, the target will be r − ρ distance away from the upper
edge. Similarly, the target will be at a distance of θ ρ from one of the sides in E2. Thus, the location
of the transformed target in E2 will be (θ ρ, r − ρ). Similarly, if the vehicle is located at (ρ, φ) and
constricted to move on the perimeter, its location after transformation in E2 will be φρ distance
away from one of the side and on the upper edge as in E1 and captures targets as per Algorithm 3.
Thus, given any location of the vehicle on the perimeter and any set of locations of targets in
E, we can construct a corresponding vehicle location on the upper edge and a set of locations of
corresponding targets in E2 such that the number of targets intercepted by the vehicle in the E and
E2 is equal. Then, the capture fraction of the LA policy applied to the RIT problem in environment
E is lower bounded by the LA policy applied to the transformed problem in environment E2. In
particular, the LA policy is expected to perform better because of the circular symmetry of E that
allows the vehicle in E to reach certain targets in a shorter duration. This completes the proof. (cid:3)

The policies presented in this section perform well for low arrival rates, but not in high arrival
λ). We seek an improved policy in this regime which

regime since the upper bound scales as O(1/√
is the focus of the next section.

22

Figure 4.4: The RMHP-fraction policy. The figure on the left shows the EMHP through all
outstanding targets. The figure on the right shows the instant when the vehicle has followed the
path through ρ/v time units and allows some targets to escape

4.2 High Arrival Rate of Targets

We now introduce a policy based on repeated computation of the EMHP through outstanding
radially moving targets. We term this policy as the Radial Minimum Hamiltonian Path (RMHP)
policy. The key idea is that the number of targets accumulating near the perimeter is high. Thus,
the time taken by the vehicle to capture successive targets will be small, and therefore, the vehicle
can capture a large number of targets in a single iteration. The vehicle uses solution of the EMHP
path (i.e., a path that visits all the points exactly once) to determine the order of the targets to
capture. In particular, we consider a constrained EMHP problem which starts at a specific point
while visiting all the given set of points [30]. The RMHP-fraction policy is defined in Algorithm
5. In this policy, the vehicle computes the EMHP path through all outstanding targets in (2ρ, 3ρ)
for all θ ∈ [0, 2π) (Fig.4.4). The vehicle captures the targets for ρ
time units and then recomputes
the EMHP path through the outstanding targets, allowing some targets to escape.

v

Theorem 4.2.1 ((RMHP-fraction capture fraction). In the limit as λ → +∞, the capture fraction
of the RMHP-fraction policy, with probability one is

Fcap(RMHP-fraction) ≥ min

where α = 6

√
2.

23

(cid:40)

(cid:112)

(cid:41)

,

1 − v
vλρ(1 +

√

v)

1,

α

Algorithm 5: RMHP-fraction policy
1 Assumes that vehicle is located at a distance of 2ρ from the origin.
2 Compute an EMHP path through the outstanding targets located at distance between 2ρ and

Capture all the outstanding targets by following the computed path.

3ρ from the origin.

3 if time to travel entire path is less than ρ
4
5 else
6
7 end
8 Repeat.

Capture the targets for ρ
v

time units.

v then

Proof. Consider the beginning of an iteration of the policy and assume that the duration of the
previous iteration was ρ/v time units. At this instant, the vehicle will be 2ρ distance away from the
center and suppose there are n outstanding targets in an annulus of radii 2ρ and 3ρ. From Theorem
2.2.1 and Theorem 2.2.2, the length of the tour through these targets can be upper bounded by
time units, it will

2. As the vehicle can capture targets for at most ρ
v

√

n/(1 − v) where, α = 6

√
αρ
capture cn targets, where

From Lemma 2.2.1, the expected value E[n] and the variance σ
Using Chebyshev inequality, P[|n − E[n]| ≥ γ] ≤ σ
n/γ
2, and γ =
2
1
1
v)E[n]] ≤
vE[n] =
λρ

P[n ≥ (1 +

√

.

2
n of the random variable n is λρ
√

v

.

vE[n],

Thus, we have

c ≥ min

1 − v
vλρ(1 +

√

v)

with probability at least 1 − 1
λρ .
Corollary 4.2.1 (Constant factor of optimality:). For v → 0+ and λ → +∞, the capture fraction

(cid:3)

(cid:41)

(cid:41)

c = min

= min

ρ/v
n)/(1 − v)

(cid:41)

.

1,

1,

√
(ρα
1 − v
√
n
vα

(cid:40)
(cid:40)

(cid:40)

1,

α

(cid:112)
(cid:40)

1,

24

(cid:41)

,

c ≥ min

1
√

vλρ

α

which is within a constant of 12/√

π ≈ 6.77.

4.3 Discussion

We presented some policies for low and high arrival rate of the targets in this chapter. Even
though the capture fracture of the EMHP policy is within a constant factor, there is still room for
improvement as the value is too large. One can use the below mentioned theorem to bound the
length of the tour of the vehicle and thus improve the constant factor.

Theorem 4.3.1 (Asymptotic EMHP length). [31] : If a set K of n points is distributed independently
and identically in a compact set Q, then there exists a constant β such that

Þ

Q

ETSP(K)

√

n

lim
n→∞

= β

1/2dq

ψ

where ψ is the density of the absolutely continuous part of the distribution. The constant β is
numerically estimated as β ≈ 0.7120 ± 0.0002 [38].

For this, one can construct an invertible transformation between any realization of targets in E
to a rectangular environment (refer Theorem 4.1.2). In that case, the integrand becomes 1 and thus
we can obtain a better constant of β.

Moreover, these policies, although diverse, are not the only policies for this problem. There are
many other policies one can analyze for the RIT problem. For example, the nearest neighbor (NN)
policy discussed in [39]. However, due to the dependencies among the travel distance between
the targets, it is difficult to analyze that policy. We therefore performed simulation experiments to
compare this policy with FCFS policy. Another policy can be the one in which the environment is
divided into sub-regions and the vehicle captures targets in these sub-regions in an orderly fashion.

25

CHAPTER 5

SIMULATIONS

We now present results of numerical experiments for the policies analyzed in Chapter 4. The
parameter D = 20 and ρ = 3 were kept fixed. The first result compares the FCFS policy to the
lower and fundamental bounds and SAC policy to FCFS policy. Comparison of the LA policy
to the NCLA policy and to the theoretical bounds is shown in the second result. The next result
compares the RMHP-fraction policy to the theoretical bounds. Finally, the last result compares the
NN policy with FCFS and LA.

For the FCFS and SAC policy, we simulated 30 runs for each arrival rate. Fig. 5.1 shows
a comparison of the FCFS policy with the theoretical bounds. To simulate the NCLA and LA
policies, we implement 5 runs for each value of the arrival rate. Fig. 5.2 shows the comparison of
the LA policy with NCLA, fundamental and theoretical bounds. To simulate the RMHP-fraction
policy, the linkern1 solver was used. For each value of the arrival rate, 5 runs of the policy was

Figure 5.1: (a) Comparison of FCFS policy with fundamental and theoretical bounds for v = 0.2.
The red dash-dot line shows the fundamental upper bound and red dash curve shows the theoretical
bound for FCFS. (b) Comparison of SAC with theoretical bound from 4.1.1 and FCFS for v = 0.5.
The red dash-dot line shows the capture fraction of FCFS and red dash curve shows the theoretical
bound for SAC.

1The TSP solver linkern is

freely

http://www.math.uwaterloo.ca/tsp/concorde/.

available

for

academic

research

use

at

26

Figure 5.2: Simulation results for NCLA and LA policy for v = 0.8. The red curve shows the
fundamental upper bound. Capture fraction of NCLA is shown by the blue curve and the theoretical
bound analyzed in 4.1.2 is shown in green color.

taken. The comparison is shown in Fig. 5.3. Note that the experimental results for RMHP-fraction
policy are lower than the theoretical lower bound in Theorem 4.2.1. This is because we have not
reached the limit as v → 0+ and λ → +∞. Moreover, we utilize an approximate solution for the
EMHP generated by the linkern solver. Figure 5.4 compares the capture fraction of the NN policy
with FCFS policy. The NN policy performs slightly better than FCFS policy. This is because in the
NN policy, the vehicle has to travel less distance between the targets and so captures more targets
in comparison to the FCFS policy.
Finally, we also simulated the case when the distribution of targets was non-uniform. For this, the
targets were generated uniformly in the interval [0, π/2]. Figure 5.5, shows the capture fraction of
FCFS, LA, and NN policy in the case of non-uniform distribution. In this non uniform distribution,
the capture fraction of the policies increased as the travel distance and thus the travel time between
the targets decreased.

27

Figure 5.3: Simulation results for RMHP-fraction policy for v = 0.04. The red dash-dot curve
is from the policy independent upper bound in Theorem 3.0.1 and the dashed curve shows the
theoretical bound.

Figure 5.4: Simulation results for NN policy and comparison with FCFS for v = 0.2. The black
curve shows the capture fraction of FCFS and the green curve shows the capture fraction of the NN
policy.

28

Figure 5.5: Simulation results for the case of non-uniform distribution for v = 0.5. The black curve
shows the capture fraction of FCFS. The capture fraction of LA policy is shown by blue curve and
the green curve shows the capture fraction of the NN policy.

29

CHAPTER 6

CONCLUSIONS AND FUTURE WORK

This thesis introduced the RIT problem, in which a vehicle seeks to defend a perimeter from the
radially inward moving targets. We established a policy independent upper bound on the capture
fraction of the targets. We then proposed three different policies suitable for low and high arrival
rates of the targets and analyzed their respective capture fractions. In the case of low arrival rate of
targets, we proposed FCFS, and LA policies. For the latter case, we introduced the RMHP-fraction
policy which is within a constant factor of optimal.

This problem can be extended in many ways. One can consider the case when the speed of the
targets is not constant or the targets can maneuver away from the vehicle to escape in order. Other
extensions include multi-vehicle versions of this problem. These are discussed in detail as follows:

• Multi-vehicle : One of the possible extensions of this work is when there are multiple
vehicles. An interesting work can be when the targets require some or all the vehicles to
intercept them. One of the application of this scenario is when a team of vehicle is required
for a threat detection and the other team is required to actually intercept the targets. Another
extension can be when the vehicle is required to intercept only some specific targets.

• Intelligence : Another case one can consider is when the targets are intelligent, can maneuver
away to escape the vehicle, or can actually communicate with each other so that other targets
can escape from the vehicle. This extension provides a more real life approach to this
problem. Another extension that relates to more realistic application is that the vehicle has
limited sensing.

• Other dimensions : Even though the RIT problem in this thesis is in R2, the capture fraction
of these policies and the fundamental bounds can also be analyzed in Rn.

30

BIBLIOGRAPHY

31

BIBLIOGRAPHY

[1] M. Dunbabin and L. Marques, “Robots for environmental monitoring: Significant advance-
ments and applications,” IEEE Robotics & Automation Magazine - IEEE ROBOT AUTOMAT,
vol. 19, pp. 24–39, March 2012.

[2] A. Dhekne, M. Gowda, and R. R. Choudhury, “Extending cell tower coverage through
drones,” in Proceedings of the 18th International Workshop on Mobile Computing Systems
and Applications, ser. HotMobile ’17. New York, NY, USA: ACM, 2017, pp. 7–12.
[Online]. Available: http://doi.acm.org/10.1145/3032970.3032984

[3] D. Câmara, “Cavalry to the rescue: Drones fleet to help rescuers operations over disasters
scenarios,” in 2014 IEEE Conference on Antenna Measurements & Applications (CAMA).
IEEE, 2014, pp. 1–4.

[4]

J. Broekens, M. Heerink, and H. Rosendal, “Assistive social robots in elderly care: a review,”
Gerontechnology, vol. 8, no. 2, pp. 94–103, 2009.

[5] S. N. Kumar and R. Panneerselvam, “A survey on the vehicle routing problem and its variants,”

Intelligent Information Management, vol. 4, no. 03, p. 66, 2012.

[6] M. W. P. Savelsbergh, “Local search in routing problems with time windows,” Annals
of Operations Research, vol. 4, no. 1, pp. 285–305, Dec 1985. [Online]. Available:
https://doi.org/10.1007/BF02022044

[7] Y. Dumas, J. Desrosiers, and F. Soumis, “The pickup and delivery problem with time win-

dows,” European Journal of Operational Research, vol. 54, pp. 7–22, 09 1991.

[8] D. Favaretto, E. Moretti, and P. Pellegrini, “Ant colony system for a vrp with multiple time
windows and multiple visits,” Journal of Interdisciplinary Mathematics, vol. 10, no. 2, pp.
263–284, 2007. [Online]. Available: https://doi.org/10.1080/09720502.2007.10700491

[9] C. S. Helvig, G. Robins, and A. Zelikovsky, “The moving-target traveling salesman problem,”

J. Algorithms, vol. 49, pp. 153–174, October 2003.

[10] P. Chalasani and R. Motwani, “Approximating capacitated routing and delivery problems,”
SIAM J. Comput., vol. 28, no. 6, pp. 2133–2149, Aug. 1999. [Online]. Available:
https://doi.org/10.1137/S0097539795295468

[11] M. Hammar and B. J. Nilsson, “Approximation results for kinetic variants of tsp,” in "Au-
tomata, Languages and Programming", J. Wiedermann, P. van Emde Boas, and M. Nielsen,
Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999, pp. 392–401.

[12] P. Toth and D. Vigo, “An overview of vehicle routing problems,” in The vehicle routing

problem. SIAM, 2002, pp. 1–26.

32

[13] H. N. Psaraftis, “Dynamic vehicle routing problems,” Vehicle routing: Methods and studies,

vol. 16, pp. 223–248, 1988.

[14] B. Fleischmann, S. Gnutzmann, and E. Sandvoß, “Dynamic vehicle routing based on online

traffic information,” Transportation Science, vol. 38, pp. 420–433, November 2004.

[15] J. D. Papastavrou, “A stochastic and dynamic routing policy using branching processes with
state dependent immigration,” European Journal of Operational Research, vol. 95, no. 1, pp.
167–177, 1996.

[16] M. Pavone, E. Frazzoli, and F. Bullo, “Adaptive and distributed algorithms for vehicle routing
in a stochastic and dynamic environment,” IEEE Trans. on Auto. Cont., vol. 56, no. 6, pp.
1259–1274, 2011.

[17] 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.

[18] H. A. Waisanen, D. Shah, and M. A. Dahleh, “A dynamic pickup and delivery problem in
mobile networks under information constraints,” IEEE Trans. on Auto. Cont., vol. 53, no. 6,
pp. 1419–1433, 2008.

[19] K. Treleaven, M. Pavone, and E. Frazzoli, “Asymptotically optimal algorithms for one-to-one
pickup and delivery problems with applications to transportation systems,” IEEE Transactions
on Automatic Control, vol. 58, no. 9, pp. 2261–2276, 2013.

[20] K. Savla, E. Frazzoli, and F. Bullo, “Traveling salesperson problems for the dubins vehicle,”

IEEE Transactions on Automatic Control, vol. 53, no. 6, pp. 1378–1391, 2008.

[21] K. Savla, F. Bullo, and E. Frazzoli, “Traveling salesperson problems for a double integrator,”

IEEE Transactions on Automatic Control, vol. 54, no. 4, pp. 788–793, 2009.

[22] S. Itani, E. Frazzoli, and M. A. Dahleh, “Dynamic traveling repairperson problem for dynamic
IEEE, 2008, pp. 465–470.

systems,” in 2008 47th IEEE Conference on Decision and Control.

[23] A. Arsie, K. Savla, and E. Frazzoli, “Efficient routing algorithms for multiple vehicles with
no explicit communications,” IEEE Transactions on Automatic Control, vol. 54, no. 10, pp.
2302–2317, 2009.

[24] 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.

[25] D. J. Bertsimas and G. Van Ryzin, “Stochastic and dynamic vehicle routing in the euclidean
plane with multiple capacitated vehicles,” Operations Research, vol. 41, no. 1, pp. 60–76,
1993.

[26] P. Kawecki, B. Kraska, K. Majcherek, and M. Zola, “Guarding a line segment,” Systems and

Control Letters, vol. 58, pp. 540–545, 2009.

33

[27] Z. E. Fuchs, E. Garcia, and D. W. Casbeer, “Two-pursuer, one-evader pursuit evasion differen-
IEEE,

tial game,” in NAECON 2018-IEEE National Aerospace and Electronics Conference.
2018, pp. 457–464.

[28] E. Garcia, D. W. Casbeer, and M. Pachter, “Optimal target capture strategies in the target-

attacker-defender differential game,” June 2018, pp. 68–73.

[29] S. D. Bopardikar, S. L. Smith, F. Bullo, and J. P. Hespanha, “Dynamic vehicle routing for
translating demands: Stability analysis and receding-horizon policies,” IEEE Transactions on
Automatic Control, vol. 55, no. 11, pp. 2554–2569, 2010.

[30] S. L. Smith, S. D. Bopardikar, and F. Bullo, “A dynamic boundary guarding problem with
translating targets,” in Decision and Control, 2009 held jointly with the 2009 28th Chinese
Control Conference. CDC/CCC 2009. Proceedings of the 48th IEEE Conference on.
IEEE,
2009, pp. 8543–8548.

[31] P. Agharkar, S. D. Bopardikar, and F. Bullo, “Vehicle routing algorithms for radially escaping

targets,” SIAM Journal on Control and Optimization, vol. 53, no. 5, pp. 2934–2954, 2015.

[32] S. Bajaj and S. D. Bopardikar, “Boundary guarding against radially incoming targets,” in

Decision and Control (CDC).

IEEE, 2019, submitted.

[33] B. Korte, J. Vygen, B. Korte, and J. Vygen, Combinatorial optimization.

vol. 2.

Springer, 2012,

[34] N. Christofides, Graph Theory: An Algorithmic Approach (Computer Science and Applied

Mathematics). Orlando, FL, USA: Academic Press, Inc., 1975.

[35] L. Few, “The shortest path and the shortest road through n points,” Mathematika, vol. 2, no. 2,

p. 141–144, 1955.

[36] L. Kleinrock, Theory, Volume 1, Queueing Systems.

Interscience, 1975.

New York, NY, USA: Wiley-

[37] Z. Cvetkovski, Convexity, Jensen’s Inequality. Berlin, Heidelberg: Springer Berlin Heidel-

berg, 2012, pp. 69–77.

[38] A. G. Percus and O. C. Martin, “Finite size and dimensional dependence in the euclidean

traveling salesman problem,” Physical Review Letters, vol. 76, no. 8, p. 1188, 1996.

[39] 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.

34