Trackability with Imprecise Localization∗
Kyle Klein and Subhash Suri
Department of Computer Science
University of California Santa Barbara
Santa Barbara, CA, USA 93106
{kyleklein, suri}@cs.ucsb.edu
Abstract
Imagine a tracking agent P who wants to follow a moving target Q in d-dimensional
Euclidean space. The tracker has access to a noisy location sensor that reports an
estimate ˜Q(t) of the target’s true location Q(t) at time t, where ||Q(t)−˜Q(t)|| represents
the sensor’s localization error. We study the limits of tracking performance under this
kind of sensing imprecision. In particular, we investigate (1) what is P’s best strategy
to follow Q if both P and Q can move with equal speed, (2) at what rate does the
distance ||Q(t) −P(t)|| grow under worst-case localization noise, (3) if P wants to
keep Q within a prescribed distance L, how much faster does it need to move, and (4)
what is the effect of obstacles on the tracking performance, etc. Under a relative error
model of noise, we are able to give upper and lower bounds for the worst-case tracking
performance, both with or without obstacles.
1
Introduction
The problem of tracking a single known target is a classical one with a long history in arti-
ficial intelligence, robotics, computational geometry, graph theory and control systems. The
underlying motivation is that many robotic applications including search-and-rescue, surveil-
lance, reconnaissance and environmental monitoring have components that are best modeled
as a tracking problem. The problem is often formulated as a pursuit-evasion game, with col-
orful names such as Man-and-the-Lion, Cops-and-Robbers, Hunter-and-Rabbit, Homicidal
Chauffeur, and Princess-and-Monster [1, 2, 4, 8]. Visibility-based pursuit evasion [7, 19], in
particular, has been a topic of great interest, in part due to its simple but realistic model:
∗This research was supported in part by the National Science Foundation grants IIS-0904501, CNS-
1035917, and the National Science Foundation Graduate Research Fellowship under Grant No.
DGE-
1144085.
1
arXiv:1312.6573v1  [cs.RO]  19 Dec 2013
a team of pursuers is tasked with locating a single adversarial evader in an geometric en-
vironment with polygonal obstacles where pursuers learn the evader’s position only when
the latter is in their line-of-sight. After two decades of research, tight bounds are known
for detection or capture of the evader for many basic formulations of the problem [3, 7, 11],
although the topic remains a rich subject of ongoing research [12, 15].
Most theoretical analyses of tracking, however, assume an idealized sensing model, ig-
noring the fact that all location sensing is noisy and imprecise in practice: the target’s
position is rarely known with complete and error-free precision. Although some papers have
explored models to incorporate practical limitations of idealized visibility including angular
visibility [10], beam sensing [16], field-of-view sensors [6], and range-bounded visibility [5],
the topic of sensing noise or imprecision has largely been handled heuristically or through
probabilistic techniques such as Kalman filters [9, 14, 18, 20]. One exception is [17], where
Rote investigates a tracking problem under the absolute error model: in this model, the
target’s position is always known to lie within distance 1 of its true location, regardless of
its distance from the tracker. The analysis in [17] shows that, under this noise model, the
distance between the tracker and the target can grow at the rate of Θ(t1/3), where t is the
time parameter. Our model, by comparison, deals with a more severe form of noise, with
imprecision proportional to the distance from the tracker. In [13], Kuntsevich et al. consider
the same relative error model as ours, but without any obstacles. Their work has a control-
theoretic perspective, with a primary goal of deriving a bound on the time needed by the
tracker to capture the target. Our main contribution is to analyze the worst-case behavior
of trackability as a function of the localization precision parameter λ.
Motivation and the Problem Statement.
This paper takes a small step towards bridg-
ing the gap between theory and practice of trackability, and analyzes the effect of noisy
sensing. In particular, we consider a tracking agent P who wants to follow a moving target
Q in d-dimensional Euclidean space using a noisy location sensor. For simplicity, we analyze
the problem in two dimensions, but the results easily extend to d dimensions, as discussed in
Section 5. We use the notation Q(t) and P(t) to denote the (true) positions of the target and
the tracker at time t. We adopt a simple but realistic model of relative error in sensing noise:
the localization error is proportional to the true distance between the tracker and the target.
More precisely, the localization error is upper bounded as ||Q(t) −˜Q(t)|| ≤
1
λ||P(t) −Q(t)||
at all times t, where λ ≥1 is the quality measure of localization precision. Thus, the closer
the target, smaller the error, and a larger λ means better localization accuracy, while λ = 1
represents the completely noisy case when the target can be anywhere within a disk of radius
||P(t) −Q(t)|| around Q(t). It is important to note that the parameter λ is used only for the
analysis, and is not part of information revealed to the tracker. In other words, the tracker
only observes the approximate location ˜Q(t), and not the uncertainty disk containing the
target. The relative error model is intuitively simple (farther the object, larger the mea-
surement error) and captures the realism of many sensors: for instance, the resolution error
in camera-based tracking systems is proportional to the target’s distance, and in network-
based tracking, latency causes a proportionate localization uncertainty because of target’s
2
movement before the signal is received by the tracker.
We study the tracking problem as a game between two players, the tracker P and the
target Q, which is played in continuous time and space: that is, each player is able to instan-
taneously observe and react to other’s position, and the environment is the two-dimensional
plane, with or without polygonal obstacles. Both the target and the tracker can move with
equal speed, which we normalize to one, without loss of generality. With the unit-speed
assumption, the following holds, for all times t1 ≤t2:
||Q(t2) −Q(t1)|| ≤|t2 −t1|,
||P(t2) −P(t1)|| ≤|t2 −t1|
Under the relative localization error model, the reported location of the target ˜Q(t)
always satisfies the following bound, where λ is the accuracy parameter:
||Q(t) −˜Q(t)|| ≤||P(t) −Q(t)||
λ
We measure the tracking performance by analyzing the distance function between the
target and the tracker, namely, D(t) = d(P(t), Q(t)), over time, with D(0) being the distance
at the beginning of the game. Under error-free localization, the distance remains bounded
as D(t) ≤D(0). We analyze how ||D(t) −D(0)|| grows under the relative error model, as a
function of λ. Our main results are as follows.
Our Results.
We show that the simple greedy strategy of “always move to the observed
location of the target” achieves D(t) ≤D(0) + t/λ2. That is, the target’s distance from
the tracker can grow at most at the rate of O(λ−2), the inverse quadratic function of the
localization parameter. We prove this rate to be worst-case optimal with a matching lower
bound: a strategy for the target that ensures that, under the relative error model, it can
increase its distance as D(t) ≥D(0) + Ω(t/λ2).
We then extend this analysis to environments with polygonal obstacles, and show that
the tracker can increase its distance by Ω(t) in time t for any finite λ. This is unsurprising
because two points within a small margin of sensing error can be far apart in free-space,
thereby fooling the tracker into “blind alleys.”
More surprisingly, however, if we adopt
a localization error that is proportional to the geodesic distance (and not the Euclidean
distance) between the target and the tracker, then the distance increases at a rate of Θ(λ−1).
This bound is also tight within a constant factor: the tracker can maintain a distance of
D(t) ≤D(0) + O(t/λ) by the greedy strategy, while the target has a strategy to ensure
that the distance function grows as at least D(t) ≥D(0) + Ω(t/λ).
Our analysis also helps answer some other questions related to tracking performance. For
instance, a natural way to achieve good tracking performance in the presence of noisy sensing
is to let the tracker move at a faster speed than the target. Then, what is the minimum
speedup necessary for the tracker to reach the target (or, keep within a certain distance
of it)? We derive upper and lower bounds for this speedup function, which are within a
constant factor of each other as long as λ ≥2.
3
Organization.
The paper is organized as follows.
Section 2 investigates the tracking
problem in the Euclidean plane without obstacles. Section 3 derives bounds on the speedup
function. Section 4 explores the tracking performance in the presence of polygonal obstacles.
Section 5 briefly discussed the straight-forward extension of our results to d-dimensions.
Section 6 offers a summary and concluding remarks.
2
Tracking in the Unobstructed Plane
We begin with the simple setting in which a tracking agent P wants to follow a moving target
Q in the two-dimensional plane without any obstacles. We show that the trivial “aim for
the target’s observed location” achieves essentially the best possible worst-case performance.
We first prove the upper bound on the derivative D′(t) of the distance function D(t), and
then describe an adversary’s strategy that matches this upper bound.
2.1
Tracker’s Strategy and the Upper Bound
Our tracker uses the following obvious algorithm, whose performance is analyzed in Theo-
rem 1 below.
GreedyTrack.
At time t, the tracker P moves directly towards the target’s observed
location ˜Q(t).
Theorem 1. By using GreedyTrack, the tracker can ensure that D(t) ≤D(0)+O(t/λ2),
for all t ≥0.
Proof. Consider the true and the observed positions of the target, namely Q(t) and ˜Q(t),
respectively, at time t, and let γ be the angle formed by them at P(t).
See Figure 1.
Consider an arbitrarily small time period ∆t during which P moves towards ˜Q(t) and Q(t)
moves away from P(t). We want to compute the derivative of the distance function, given
as Equation (1).
D′(t) = lim
∆t→0
D(t + ∆t) −D(t)
∆t
(1)
The new distance between the target and the tracker is given by bc in Fig. 1. In the
triangle abc, we have ab = ∆t sin γ and ac = D(t) + ∆t −∆t cos γ. We, therefore, can bound
D(t + ∆t) as follows (where the final inequality uses the fact √1 + x ≤1 + x
2):
D(t + ∆t) =
p
(∆t sin γ)2 + (D(t) + ∆t −∆t cos γ)2
=
q
∆t2 sin2 γ + D(t)2 + 2D(t)∆t(1 −cos γ) + ∆t2 −2∆t2 cos γ + ∆t2 cos2 γ
=
p
∆t2 + D(t)2 + 2D(t)∆t(1 −cos γ) + ∆t2 −2∆t2 cos γ
=
p
(D(t) + ∆t)2 −2D(t)∆cos γ + ∆t2 −2∆t2 cos γ
4
Q
D(t)
λ
˜Q
P ∆t
∆t
D(t)
γa
b
c
Figure 1: Proof of Theorem 1.
=
p
(D(t) + ∆t)2 −2∆t(D(t) + ∆t) + ∆t2 −2D(t)∆cos γ −2∆t2 cos γ + 2∆t(D(t) + ∆t)
=
p
(D(t) + ∆t −∆t)2 −2D(t)∆t cos γ −2∆t2 cos γ + 2∆t(D(t) + ∆t)
=
p
D(t)2 + 2∆t(D(t) + ∆t)(1 −cos γ)
= D(t)
p
1 + 2∆t(D(t) + ∆t)(1 −cos γ)/D(t)2
≤D(t) + (∆t)(1 + ∆t/D(t))(1 −cos γ)
Returning to Equation (1), we get
D′(t) = lim
∆t→0
D(t + ∆t) −D(t)
∆t
≤lim
∆t→0(1 + ∆t/D(t))(1 −cos γ) = 1 −cos γ
Finally, since sin γ ≤1
λ, we get D′(t) ≤1−
q
1 −1
λ2, which simplifies by the Taylor series
expansion:
D′(t) ≤1 −(1 −
1
2λ2 −
1
8λ4 −· · · ) =
1
2λ2 +
1
8λ4 + · · · ≤
1
λ2
This completes the proof that D(t) ≤D(0) + t/λ2.
2.2
Target’s Strategy and the Lower Bound
We now show that this bound is asymptotically tight, by demonstrating a strategy for the
target to grow its distance from the tracker at the rate of D(t) ≥D(0) + Ω(t/λ2), for all
t ≥0. We think of the target as an adversary who can choose its observed location at any
time subject only to the constraints of the error bound: ||Q(t) −˜Q(t)|| ≤1
λ(||P(t) −Q(t)||).
(Recall that the tracker only observes the location ˜Q(t), and has no direct knowledge of
either the parameter λ or the distance ||P(t) −Q(t)||. Those quantities are only used in the
analysis. However, the lower bound holds even if the tracker knows the uncertainty disk,
namely, the localization error 1
λ(||P(t) −Q(t)||).)
5
In order to analyze the lower bound, we divide the time into phases, and show that the
distance from the tracker increases by a multiplicative factor in each phase, resulting in a
growth rate of Ω(1+λ−2). If the ith phase begins at time ti, then we let di = ||Q(ti)−P(ti)||
denote the distance between the target and the tracker at ti. During the ith phase, the
target maintains the following invariant for a constant 0 < α < 1 to be chosen later.
Gap Invariant.
Throughout the ith phase, the target moves along a path Q(t) such that
||Q(t)−P(t)|| ≥αdi, for all times t, and all reported locations satisfy ||Q(t)−˜Q(t)|| ≤αdi/λ.
See Figure 2(i) for an illustration. Consider the isosceles triangle with vertices at Q(ti), qa
and qb, whose base qaqb is perpendicular to the line P(ti)Q(ti). The equal sides of the triangle
have length 2di, the base has length 2αdi/λ, and let qc be the midpoint of the base. The
target’s strategy is to move from Q(ti) to either qa or qb, and report its location ˜Q(t) at the
closest point on the line Q(ti)qc; i.e. at all times, ˜Q(t) is the perpendicular projection of Q(t)
onto the line Q(ti)qc. By the symmetric construction, and the choice of the points qa and
qb, the tracker cannot tell whether the target is moving to qa or qb. Thus, any deterministic
tracker makes an incorrect choice in one of the two possible scenarios. For the worst-case
performance bound, we can equivalently assume that the target non-deterministically guesses
the tracker’s intention, and moves to the better of the two possible locations, qa or qb. The
tracker makes this choice based on whether the tracker is on or below the line Q(ti)qc, or
not. In the former case, the target moves to qa, and to to qb otherwise. The ith phase
terminates when the target reaches either qa or qb, and the next phase begins. (We note
that, after i phases, there are 2i possible choices made by the tracker, reflected in whether
it is above or below the line Q(ti)qc at the conclusion of each phases. For each of these
possible “worlds” there is a corresponding deterministic strategy of the target that “fools”
the tracker in every phase, resulting in the maximum distance increase.) There is one subtle
point worth mentioning here. It is possible that during the phase, the distance between the
players may shrink if the tracker temporarily moves towards the same final location as the
target—however, our Gap Invariant ensures that that the target’s noisy location remains
within the permissible error bound throughout the phase. The following lemma shows that
this simple strategy of the target can maintain the Gap Invariant for any choice of α ≤0.927.
Lemma 1. The target can maintain the Gap Invariant for any α ≤0.927.
Proof. Consider an arbitrary phase i. By construction, we have ||Q(t)−˜Q(t)|| ≤αdi
λ through-
out this phase, so we only need to show D(t) ≥αdi. There is one subtle point worth men-
tioning here. While the target’s strategy will ensure that its distance from the tracker grows
by a certain multiplicative factor at the end of the phase, the distance between the players
may shrink during the phases. This happens when the tracker temporarily moves towards
the same final location as the target. In spite of this temporary “lucky” guess by the tracker,
we need to ensure that the target’s noisy location remains within the permissible error bound
throughout the phase. The constant α is introduced precisely to guarantee this validity, and
we arrive at its value as follows.
6
P(ti)
Q(ti)
qa
qb
qc
di
2di
2di
αdi
λ
αdi
λ
(i)
P(ti)
Q(ti)
qa
qc
di
2di
αdi
λ
di
P(ti+1)
(ii)
Figure 2: Target’s strategy during the ith phase (i), and proofs of Lemmas 1 and 2 (ii).
Let di+1 be the distance between P and Q if both moved toward qa for the duration
of phase i.
Note that di+1 is the length of the segment P(ti)qa minus 2di, as shown in
Figure 2(ii). The length of P(ti)qa can be calculated from the right triangle qaP(ti)qc, while
the length of qaqc is known by construction. Finally, Q(ti)qc has length di less than P(ti)qc.
Thus, we have:
di+1 =
s
(
r
4d2
i −d2
i α2
λ2
+ di)2 + d2
i α2
λ2
−2di
=
s
5d2
i −d2
i α2
λ2
+ 2di
r
4d2
i −d2
i α2
λ2
+ d2
i α2
λ2
−2di
= di
s
5 + 4
r
1 −α2
4λ2 −2di
In order to satisfy the Gap Invariant, we must choose an α such that the following
inequality holds:
αdi ≤di
s
5 + 4
r
1 −α2
4λ2 −2di
α2 + 4α + 4 ≤5 + 4
r
1 −α2
4λ2
α2 + 4α + 4 ≤5 + 4 −α2
2λ2
α2(1 +
1
2λ2) + 4α −5 ≤0
7
This gives the following upper bound:
α ≤
−4 ±
q
16 + 4(1 +
1
2λ2)5
2(1 +
1
2λ2)
≤1
3(
√
46 −4)
The preceding lemma shows that our construction satisfies the Gap Invariant, and so we
can now lower bound the distance growth during a single phase.
Lemma 2. At the start of phase i + 1, we have di+1 ≥di
q
1 + α2
2λ2, where α = 0.927 is an
absolute constant.
Proof. Suppose, without loss of generality, that the target is at qa at the termination of
the ith phase, which means the tracker is on or below the line Q(ti)qc. By the unit speed
assumption, the target needs exactly 2di time for this move. The minimum value of di+1 is
at least as large as if P had moved directly to qc by distance 2di, as shown in Figure 2(ii).
We can calculate di+1 from the right triangle qaP(ti+1)qc, as follows:
di+1 ≥
s
(
r
4d2
i −α2d2
i
λ2
−di)2 + α2d2
i
λ2
=
s
d2
i −2di
r
4d2
i −α2d2
i
λ2
+ 4d2
i −α2d2
i
λ2
+ α2d2
i
λ2
= di
s
5 −4
r
1 −α2
4λ2
≥di
r
5 −(4 −α2
2λ2)
= di
r
1 + α2
2λ2
We can now prove the main result of this section.
Theorem 2. Under the relative error localization model, a target can increase its distance
from an equally fast tracker at the rate of Ω(λ−2). In other words, the target can ensure that
D(t) ≥D(0) + Ω(t/λ2) after any phase ending at time t.
Proof. The target follows the phase strategy, where that after the ith phase that lasts 2di time
units, the distance between the tracker and the target is at least di
q
1 + α2
2λ2. Therefore, the
distance increases during the ith phase by at least the following multiplicative factor (using
a Taylor series expansion):
8
di
q
1 + α2
2λ2 −di
2di
=
q
1 + α2
2λ2 −1
2
≥
α2
4λ2 −α4
16λ4 = Ω( 1
λ2)
3
Trackability with a Faster Tracker
The results of the previous section establish bounds on the relative advantage available to
the target by the localization imprecision. Its distance from the tracker can grow at the
rate of Θ(λ−2) with time. A tracking system can employ a number of different strategies to
compensate for this disadvantage. In this section, we explore one such natural mechanism:
allow the tracker to move at a faster speed than the target. A natural question then is: what
is the minimum speedup necessary to cancel out the localization noise as a function of λ?
We give bounds on the necessary and sufficient speedups, which match up to small constant
factors as long as λ ≥2. The general form of the speedup function is (1 −
1
λ2)−1/2. The
following theorem proves the sufficiency condition.
Theorem 3. Suppose the target moves with speed one, and the tracker has speed σ =
q
1
1−1/λ2, where λ is the localization precision parameter. Then, the tracker can maintain
D(t) ≤D(0), for all times t ≥0.
Proof. Our analysis closely follows the proof of Theorem 1, and calculates the increase in
the distance during time ∆t. During this time, the tracker is able to move σ∆t, while the
target can move at most ∆t. We can then calculate distance at time t+∆t from the triangle
abc (Fig. 1), where ab = σ∆t sin γ and ac = D(t) + ∆t −σ∆t cos γ, as follows:
D(t + ∆t) =
p
(σ∆t sin γ)2 + (D(t) + ∆t −σ∆t cos γ)2
=
p
σ2∆t2 sin(α)2 + D(t)2 + 2D(t)∆t(1 −σ cos(α)) + ∆t2 −2∆t2σ cos(α) + ∆t2σ2 cos(α)2
=
p
σ2∆t2 + D(t)2 + 2D(t)∆t(1 −σ cos(α)) + ∆t2 −2∆t2σ cos(α)
=
p
(D(t) + ∆t)2 + σ2∆t2 −2D(t)∆tσ cos(α) −2∆t2σ cos(α)
=
p
(D(t) + ∆t −∆t)2 + σ2∆t2 + 2∆t(D(t) + ∆t) −∆t2 −2D(t)∆tσ cos(α) −2∆t2σ cos(α)
= D(t)
p
1 + σ2∆t2/D(t)2 −∆t2/D(t)2 + 2∆t(D(t) + ∆t)(1 −σ cos(α))/D(t)2
≤D(t) + σ2∆t2/2D(t) −∆t2/2D(t) + ∆t(1 + ∆t/D(t))(1 −σ cos γ)
This allows us to bound D′(t) ≤1−σ cos γ, from which it follows that D′(t) ≤0 as long
as σ ≥
q
1
1−1/λ2.
We now show that if λ ≥2, this is the minimum speedup necessary as a function of
λ, up to a small constant factor. We use the phase-based strategy of Theorem 2, however,
9
the value of α determined by Lemma 1 is not sufficient to maintain the Gap Invariant in
this case because of the higher speed of the tracker. Instead, the following lemma gives the
sufficient choice of α.
Lemma 3. Let λ ≥2 and and α ≤0.68 be a constant. Then, the Gap Invariant can be
maintained in any phase as long as σ ≤
1
√
1−1/λ2.
Proof. As in Lemma 1 we need only show that D(t) ≥αdi, and again let di+1 be the distance
between P and Q if both moved toward qa for the duration of phase i. Note that di+1 is
found as the length of the segment P(ti)qa as in Lemma 1 except now minus 2σdi instead of
2di. Thus, we have:
di+1 =
s
(
r
4d2
i −d2
i α2
λ2
+ di)2 + d2
i α2
λ2
−2σdi
=
s
5d2
i −d2
i α2
λ2
+ 2di
r
4d2
i −d2
i α2
λ2
+ d2
i α2
λ2
−2σdi
= di
s
5 + 4
r
1 −α2
4λ2 −2σdi
In order to satisfy the Gap Invariant, we must choose an α such that the following
inequality holds:
αdi ≤di
s
5 + 4
r
1 −α2
4λ2 −2σdi
α2 + 4ασ + 4σ2 ≤5 + 4
r
1 −α2
4λ2
α2 + 4ασ + 4σ2 ≤5 + 4 −α2
2λ2
α2(1 + ϵ2/2) + 4ασ + 4σ2 −9 ≤0
This gives the following upper bound when λ is minimum and σ is maximum, which by
assumption is 2 and 1/
p
1 −(1/22), respectively.
α ≤−4σ +
p
16σ2 −4(1 + 1/2λ2)(4σ2 −9)
2(1 + 1/2λ2)
≤0.68
We can now prove a lower bound on the increase in the distance during the ith phase.
Lemma 4. If λ ≥2, α ≤0.68, and σ ≤(1 −1/λ2)−1/2, then at the start of the i + 1 phase,
we have di+1 ≥di
p
(2σ −3)2 + α2(σ −1/2)/λ2, where α = 0.68 is an absolute constant.
10
Proof. Suppose, without loss of generality, that the target is at qa at the termination of the
ith phase, which means the tracker is below the line Q(ti)qc. By the unit speed assumption,
the target needs exactly 2di time for this move. The minimum value of di+1 is at least as
large as if P had moved directly to qc by distance 2σdi, as shown in Figure 2(ii). We can
calculate di+1 from the right triangle qaP(ti+1)qc, as follows:
di+1 ≥
s
(
r
4d2
i −α2d2
i
λ2
−(2σdi −di))2 + α2d2
i
λ2
= di
s
5 + 4σ2 −4σ −2(2σ −1)
r
4 −α2
λ2
≥di
p
5 + 4σ2 −4σ −4(2σ −1)(1 −α2/8λ2)
= di
p
4σ2 −12σ + 9 + σα2/λ2 −α2/2λ2
= di
p
(2σ −3)2 + α2(σ −1/2)/λ2
Remark.
The preceding lemma can be used to calculate the maximum tracker speed for
which the target can still force a non-negative distance for a specific λ as follows:
p
(2σ −3)2 + α2(σ −1/2)/λ2 = 1
4σ2 −12σ + α2σ
λ2 = −8 + α2
2λ2
2σ −
12 −(α/λ)2
4
2
−
12 −α2/λ2
4
2
= −8 + α2
2λ2
2σ −12 −α2/λ2
4
= −
r
−8 + α2
2λ2 + (12 −α2/λ2
4
)2
σ =
−
q
−8 + α2
2λ2 + ( 12−α2/λ2
4
)2 + 12−α2/λ2
4
2
As λ gets large, the upper and lower bound are within a constant factor of each other.
Indeed, with a more careful choice of α, we can show that the upper and lower bounds are
within a factor of 5.32 (as opposed to 10.23 for the above simple analysis) of each other for
λ ≥2, but we omit those details from this abstract.
4
Tracking in the Presence of Obstacles
The presence of obstacles makes the tracking problem considerably harder under the local-
ization noise. The following simple example (Fig. 3) shows that the target can grow its
11
distance from the tracker as D(t) ≥D(0)+t, for any finite value of λ. The obstacle consists
of a single U-shaped non-convex polygon. Initially, the target is at distance D(0) from the
tracker, and the “width” of the obstacle is less than D(0)/2λ, so that the localization error
is unable to distinguish between a target moving inside the U channel, or around its outer
boundary. One can show that no matter how the tracker pursues, its distance from the
target can grow linearly with time.
D(0)/2λ
Q
P
Q(t)
˜Q(t)
D(0)
Figure 3: Impossibility of tracking among obstacles.
Path Proportionate Error.
In order to get around this impossibility of tracking, we
propose a path proportionate error measure, where the localization error is proportional to
the shortest path distance between the target and the tracker, and not the Euclidean distance
as used before. That is, the tracking signal and the physical movement of the agents follow
the same path metric. Formally, the localization error at time t always obeys the following
bound:
d(Q(t), ˜Q(t)) ≤d(P(t), Q(t))
λ
We show that the best tracking performance in this model is D(t) = D(0) + Θ(t/λ);
that is the distance grows linearly with 1/λ, as opposed to the inverse quadratic function for
the unobstructed case.
4.1
Tracking Upper Bound
The tracker’s strategy in this case is also greedy, except now the tracker makes short-term
commitments in phases, instead of continuously changing its path towards the new observed
location. In particular, for each phase, the tracker fixes its goal as the observed position of
the target at the start of the phase, moves along the shortest path to this goal, and then
begins the next phase.
Algorithm 1 (ModifiedGreedy). The initial phase begins at time t = 0. During the
ith phase, which begins at time ti, the tracker moves along the shortest path to the observed
location of the target at ti, namely, ˜Q(ti). When tracker reaches ˜Q(ti), the ith phase ends,
and the next phase begins.
The upper bound on the tracking performance is given by the following theorem.
12
Theorem 4. Using ModifiedGreedy, the tracker can ensure that D(t) ≤D(0)+O(t/λ).
Proof. First note that because d( ˜Q(ti), Q(ti)) ≤D(ti)/λ, it follows that ti+1 −ti = D(ti) +
xD(ti), where −1
λ ≤x ≤1
λ. Thus, the target’s progress during the ith phase is upper bounded
as d(Q(ti), Q(ti+1)) ≤D(ti)+xD(ti). Next, by applying the triangle inequality, the distance
between P and Q at the beginning of phase ti+1 is upper bounded as
d(P(ti+1), Q(ti+1)) = d( ˜Q(ti), Q(ti+1))
≤d( ˜Q(ti), Q(ti)) + d(Q(ti), Q(ti+1))
≤D(ti)
λ
+ D(ti) + xD(ti)
Finally, the upper bound on the rate of distance increase can be derived as follows:
d(P(ti+1), Q(ti+1)) −d(P(ti), Q(ti))
ti+1 −ti
≤D(ti) + D(ti)/λ + xD(ti) −D(ti)
D(ti) + xD(ti)
= 1/λ + x
1 + x
≤
2
λ + 1
where the final inequality uses the fact that the minimum value occurs when x = 1/λ. In
conclusion, during each phase the distance between the tracker and the target increases by
at most a factor of
2
λ+1, giving the bound D(t) ≤D(0) + O( t
λ)
4.2
Tracking Lower Bound.
Our final result is to prove that the trackability achieved by ModifiedGreedy is essen-
tially optimal. In particular, we construct an environment with polygonal obstacles and a
movement strategy for the target that ensures D(t) ≥D(0) + Ω(t/λ). The construction
of the polygonal environment is somewhat complicated and requires a carefully designed set
of obstacles. The main schema of the construction is shown in Figure 4, where each edge
of the “tree-like” diagram corresponds to a “channel” bounded by obstacles, and each face
corresponds to a “gadget” consisting of a group of carefully constructed obstacles, with the
outer face occupied entire by a single large obstacle.
As in the proof of Theorem 2, the target moves either to top or the bottom point of the
gadget during a phase, depending on the tracker’s location. The gadget construction is such
that the movement of the target along either path is indistinguishable to the tracker because
both paths are satisfied by a common set of observed locations throughout the path. Thus,
by invoking the earlier equivalence principle, we may as well assume that the target knows
the tracker’s choices. If the target moves to the top, then the next phase occurs in the top
gadget, otherwise the bottom, and so on.
To realize the geometric scheme of Figure 4, we replace each edge of the graph with a
channel as shown in Figure 5(i). The desired edge length can be realized by adding any
13
d0
d0
λ
(1 + 1
λ)d1
d1
λ
d2
λ
(1 + 1
λ)d0
(1 + 1
λ)d0
d1
λ
d2
λ
d2
λ
d2
λ
(1 + 1
λ)d1
(1 + 1
λ)d1
(1 + 1
λ)d1
(1 + 1
λ)d2
(1 + 1
λ)d2
(1 + 1
λ)d2
Figure 4: A high level schema for the lower bound construction. The numbers next to the
edges denote the “path length” in the corresponding channels.
number of arbitrarily skinny bends such that the length of the shortest path through each
channel equals the edge length. Each face is replaced with a set of obstacles, called a gadget,
see Figure 5(ii) for an abstract illustration. The jagged line between each pair of nodes
corresponds to a channel such that shortest path through that channel has the given length.
The target will move along the shortest path through either the top or bottom channel while
reporting its location in the center channel. Meanwhile, the channels connecting the top and
bottom to the center will guarantee that d(Q(t), ˜Q(t)) ≤1
λd(Q(t), P(t)) at all times t during
a phase.
ϵ
L
ϵ
(i)
{
(1 + 1
λ)di
{
di
4λ
di
2λ
di
2λ
di
2λ
di
2λ
Q(ti)
qa
qc
qb
{
(ii)
Figure 5: The channel construction in (i). In (ii) the shortest paths between nodes on the
center path have length di
4λ, and the remaining all have length di
2λ.
4.2.1
Gadget Construction and its Properties
We now describe the construction of our gadgets and establish the geometric properties
needed for the correctness of our lower bound. Each gadget is constructed out of two building
blocks, the bent channels seen in Figure 5(i), and intersections depicted in Figure 6(i). Each
intersection has the property that the shortest path between any two of the points among
14
a, b and c has length 2δ, where δ can be made arbitrarily close to 0. Thus we can construct a
channel that branches into two channels such that the path length through the intersection
is the same regardless of the branch chosen. In Figure 6(ii), we depict the construction of a
gadget using only intersections (triangles) and channels (jagged lines).
c
a
b
δ
δ
δ
δ
δ
δ
(i)
Q(ti)
qa
qc
qb
di
4λ −δ
di
4λ −δ
di
4λ −δ
di
4λ −δ
di
4λ −δ
di
4λ −δ
di
2λ −2δ
di
2λ −2δ
di
2λ −2δ
di
4λ −2δ
di
4λ −2δ
di
4λ −2δ
di
2λ −4δ
di
2λ −4δ
...
...
...
≤di
4λ −2δ
≤di
4λ −3δ
≤di
4λ −δ
(ii)
Figure 6: In (i) an example intersection such that the shortest path between any pair of a b
and c has length 2δ. In (ii) an example gadget construction, where each triangle corresponds
to an intersection with corners representing the points a b and c. The horizontal channels
have length di
4λ between each pair of vertical dashed lines, except for the initial distance before
the first line (which can be made arbitrarily small), and the remaining spillover distance after
the last dashed line.
As in the lower bound for the unobstructed case, the target starts the phase at Q(ti),
and moves to qa or qb while the observed location of the targets moves along the shortest path
from Q(ti) to qc. In particular, let Πa, Πc, and Πb denote the shortest paths from Q(ti) to
qa, qc and qb respectively. The following lemma establishes several properties needed for the
feasibility of the target’s strategy.
Lemma 5. We can construct a gadget for each phase i such that (1) Πa, Πc and Πb have
length (1 + 1
λ)di and (2) for any point xc at distance ℓalong Πc, the corresponding points xa
and xb distance ℓalong Πa and Πb, respectively, satisfy d(xc, xa) ≤di
λ and d(xc, xb) ≤di
λ .
Proof. By construction, the shortest path in each channel between the dashed lines in Fig-
ure 6(ii) has length
di
4λ, and therefore this construction can be extended until Πa, Πc and
Πb have length exactly (1 + 1
λ)di. Next, by the symmetry of the construction, we need only
show that d(xc, xa) ≤di/λ. We ignore the case where xc lies in the channels before the first
dashed lines, as the length of such channels can be made arbitrarily small to guarantee that
d(xa, xc) ≤di/λ. The maximum distance between xa and xc then occurs when xa lies at the
midpoint between two intersections in the top channel. However, in this case one can easily
verify that the following holds:
d(xc, xa) = δ + di
4λ −2δ + 2δ + di
2λ −2δ + 2δ + di
4λ −δ = di
λ
This completes the proof.
15
4.2.2
Gap Invariant and the Proof of the Lower Bound
We now formulate the invariant maintained by the target so that its motion is valid under
our (path proportionate) localization error and achieves the desired lower bound.
SP-Gap Invariant.
Throughout the ith phase, the target moves along a path Q(t) such
that D(t) ≥di for all times t, and all reported locations satisfy d(Q(t), ˜Q(t)) ≤di
λ .
Lemma 6. For the duration of phase i, SP-Gap Invariant is maintained.
Proof. Whether Q moves along Πa or Πb, they are both shortest paths (and this cannot
be shortcut by P), implying that D(t) ≥di for the duration of the phase. Without loss
of generality, suppose Q chooses Πa. Then, after time t, both the target and its observed
position have moved a distance of t along Πa and Πc, respectively. Therefore, by Lemma 5,
we have d(Q(t), ˜Q(t)) ≤di
λ .
We can prove our lower bound.
Theorem 5. The target’s strategy guarantees that after each phase ending at time t, the
distance function satisfies D(t) ≥D(0) + Ω( t
λ).
Proof. The proof is by induction on the phase i. The basis of the induction is i = 0. Since
the localization error makes target’s top and bottom paths indistinguishable to the tracker,
the target can ensure that at the end of phase 0 the target is on the side of Πc that is opposite
P. Without loss of generality, suppose that that target has reached qa. Then the best case
for P is if it moved d0
λ along Πc, which achieves D(t1) ≥D(0) + D(0)
2λ .
Now assume by induction that after phase i−1 ends at time ti, we have D(ti) ≥D(ti−1)+
D(ti−1)/2λ = di. Suppose now that P has yet to reach the gadget corresponding to phase i
when Q has finished phase i at time ti+1. Then necessarily D(ti+1) ≥di +di/λ, as that is the
length Πa and Πb. Otherwise if P has moved into the gadget, then the inequality D(ti) ≥di
ensures that the closest the target can be to the tracker is if P has moved di
λ along Πc, which
implies D(ti+1) ≥D(ti) + D(ti)
2λ .
Thus, in a round with duration (1 + 1
λ)di, the distance increases by at least di/2λ. Thus,
in the ith phase, the distance increases by a factor of at least
di/2λ
(1 + 1
λ)di
=
1
2λ(1 + 1
λ) =
1
2 + 2λ
Thus, at the end of any phase, we have the inequality D(t) ≥D(0) + Ω(t/λ), which
completes the lower bound.
5
Extension to d dimensions
Our analysis of trackability was carried out for 2-dimensional Euclidean plane, but the results
generalize easily to d dimensions. Indeed, in the unobstructed case, our analysis of the upper
16
bound only makes use of the triangle inequality: the region of interest is the triangle formed
by P(t), Q(t), and ˜Q(t), and the target Q moves directly away from P. Thus, within an
arbitrarily small time interval ∆t, P and Q are moving within the two-dimensional plane
of the triangle P(t)Q(t) ˜Q(t). The upper bound analysis therefore extend to any dimension
d ≥2. The same reasoning also holds in the presence of obstacles. Finally, the lower bound
construction of d = 2 immediately implies that the trackability lower bound holds in all
dimensions d ≥2.
6
Conclusion
Our paper is an attempt to formally study the worst-case impact of noisy localization on
the performance of tracking systems.
We analyzed a simple, but fundamental, problem
where a tracker wants to pursue a target but the tracker’s location sensor can measure the
target’s position only approximately, with a relative error parameterized by quantity λ. We
prove upper and lower bound on the tracking performance as a function of this localization
parameter λ. A few surprising consequences of our results are (1) that the naive strategy
of “always move to the observed location” is asymptotically optimal, (2) the tracking error
has a nice analytic form, showing an inverse quadratic dependence on λ, and (3) under
the natural “path proportional error”for environments with obstacles, the trackability has
qualitatively a different dependence of the form Ω(1/λ).
Compared to often-used heuristics such as Kalman filters, our work offers a more theo-
retical perspective for analyzing motion and localization errors in the presence of inevitable
noise, which may be especially useful in situations where worst-case bounds are important,
such as adversarial tracking or surveillance. In addition to improving the constant factors
in our bounds, it will also be interesting to study the noisy sensing model for other more
complex settings.
17
References
[1] M. Aigner and M. Fromme. A game of cops and robbers. Discrete Applied Mathematics,
8(1):1 – 12, 1984.
[2] S. Alpern, R. Fokkink, R. Lindelauf, and G.-J. Olsder. The ”princess and monster”
game on an interval. SIAM J. on Control and Optimization, 47(3):1178–1190, 2008.
[3] D. Bhadauria, K. Klein, V. Isler, and S. Suri. Capturing an evader in polygonal en-
vironments with obstacles: The full visibility case. International Journal of Robotics
Research, 31(10):1176–1189, September 2012.
[4] S. D. Bopardikar, F. Bullo, and J. P. Hespanha. A cooperative homicidal chauffeur
game. In 46th IEEE Conference on Decision and Control, pages 4857 –4862, 2007.
[5] S. D. Bopardikar, F. Bullo, and J. P. Hespanha. On discrete-time pursuit-evasion games
with sensing limitations. IEEE Transactions on Robotics, 24(6):1429–1439, 2008.
[6] B. P. Gerkey, S. Thrun, and G. J. Geoffrey. Visibility-based pursuit-evasion with limited
field of view. International Journal of Robotics Research, 25(4):299–315, 2006.
[7] L. J. Guibas, J.-C. Latombe, S. M. LaValle, D. Lin, and R. Motwani. Visibility-based
pursuit-evasion in a polygonal environment. International Journal of Computational
Geometry and Applications, 9(5):471–494, 1999.
[8] V. Isler and N. Karnad. The role of information in the cop-robber game. TCS, 399(3):179
– 190, 2008.
[9] R. E. Kalman. A new approach to linear filtering and prediction problems. Transactions
of the ASME–Journal of Basic Engineering, 82:35–45, 1960.
[10] N. Karnad and V. Isler. Bearing-only pursuit. In Proc. IEEE Int. Conf. on Robotics
and Automation, 2008.
[11] K. Klein and S. Suri. Capture bounds for visibility-based pursuit evasion. In Proc. of
the 29th Symposium on Computational Geometry, SoCG ’13, pages 329–338, New York,
NY, USA, 2013. ACM.
[12] K. Klein and S. Suri. Pursuit evasion on polyhedral surfaces. In Proc. of 24th Interna-
tional Conference on Algorithms and Computation (ISAAC), 2013.
[13] V. M. Kuntsevich and A. V. Kuntsevich. Analysis of the pursuit-evasion process for
moving plants under uncertain observation errors dependent on states. In Proc. of the
15th International Federation of Automatic Control, 2002.
[14] L. Liao, D. Fox, J. Hightower, H. Kautz, and D. Schulz. Voronoi tracking: Location
estimation using sparse and noisy sensor data. In Proc. of International Conference on
Intelligent Robots and Systems (IROS, 2003.
18
[15] N. Noori and V. Isler. Lion and man with visibility in monotone polygons. International
Journal of Robotics Research.
[16] S.-M. Park, J.-H. Lee, and K.-Y. Chwa. Visibility-based pursuit-evasion in a polygonal
region by a searcher. In Proc. of ICALP, pages 281–290. Springer-Verlag, 2001.
[17] G. Rote. Pursuit-evasion with imprecise target location. In Proc. of 14th ACM-SIAM
Symposium on Discrete algorithms, SODA ’03, pages 747–753, Philadelphia, PA, USA,
2003. Society for Industrial and Applied Mathematics.
[18] X. Sheng, Y.-H. Hu, and P. Ramanathan. Distributed particle filter with GMM ap-
proximation for multiple targets localization and tracking in wireless sensor network.
In Proc. of the 4th International Symposium on Information Processing in Sensor Net-
works, 2005.
[19] I. Suzuki and M. Yamashita. Searching for a mobile intruder in a polygonal region.
SIAM Journal on Computing, 21:863–888, October 1992.
[20] S. Thrun, D. Fox, W. Burgard, and F. Dellaert. Robust monte carlo localization for
mobile robots. Artif. Intell., 128(1-2):99–141, 2001.
19
Trackability with Imprecise Localization∗
Kyle Klein and Subhash Suri
Department of Computer Science
University of California Santa Barbara
Santa Barbara, CA, USA 93106
{kyleklein, suri}@cs.ucsb.edu
Abstract
Imagine a tracking agent P who wants to follow a moving target Q in d-dimensional
Euclidean space. The tracker has access to a noisy location sensor that reports an
estimate ˜Q(t) of the target’s true location Q(t) at time t, where ||Q(t)−˜Q(t)|| represents
the sensor’s localization error. We study the limits of tracking performance under this
kind of sensing imprecision. In particular, we investigate (1) what is P’s best strategy
to follow Q if both P and Q can move with equal speed, (2) at what rate does the
distance ||Q(t) −P(t)|| grow under worst-case localization noise, (3) if P wants to
keep Q within a prescribed distance L, how much faster does it need to move, and (4)
what is the effect of obstacles on the tracking performance, etc. Under a relative error
model of noise, we are able to give upper and lower bounds for the worst-case tracking
performance, both with or without obstacles.
1
Introduction
The problem of tracking a single known target is a classical one with a long history in arti-
ficial intelligence, robotics, computational geometry, graph theory and control systems. The
underlying motivation is that many robotic applications including search-and-rescue, surveil-
lance, reconnaissance and environmental monitoring have components that are best modeled
as a tracking problem. The problem is often formulated as a pursuit-evasion game, with col-
orful names such as Man-and-the-Lion, Cops-and-Robbers, Hunter-and-Rabbit, Homicidal
Chauffeur, and Princess-and-Monster [1, 2, 4, 8]. Visibility-based pursuit evasion [7, 19], in
particular, has been a topic of great interest, in part due to its simple but realistic model:
∗This research was supported in part by the National Science Foundation grants IIS-0904501, CNS-
1035917, and the National Science Foundation Graduate Research Fellowship under Grant No.
DGE-
1144085.
1
arXiv:1312.6573v1  [cs.RO]  19 Dec 2013
a team of pursuers is tasked with locating a single adversarial evader in an geometric en-
vironment with polygonal obstacles where pursuers learn the evader’s position only when
the latter is in their line-of-sight. After two decades of research, tight bounds are known
for detection or capture of the evader for many basic formulations of the problem [3, 7, 11],
although the topic remains a rich subject of ongoing research [12, 15].
Most theoretical analyses of tracking, however, assume an idealized sensing model, ig-
noring the fact that all location sensing is noisy and imprecise in practice: the target’s
position is rarely known with complete and error-free precision. Although some papers have
explored models to incorporate practical limitations of idealized visibility including angular
visibility [10], beam sensing [16], field-of-view sensors [6], and range-bounded visibility [5],
the topic of sensing noise or imprecision has largely been handled heuristically or through
probabilistic techniques such as Kalman filters [9, 14, 18, 20]. One exception is [17], where
Rote investigates a tracking problem under the absolute error model: in this model, the
target’s position is always known to lie within distance 1 of its true location, regardless of
its distance from the tracker. The analysis in [17] shows that, under this noise model, the
distance between the tracker and the target can grow at the rate of Θ(t1/3), where t is the
time parameter. Our model, by comparison, deals with a more severe form of noise, with
imprecision proportional to the distance from the tracker. In [13], Kuntsevich et al. consider
the same relative error model as ours, but without any obstacles. Their work has a control-
theoretic perspective, with a primary goal of deriving a bound on the time needed by the
tracker to capture the target. Our main contribution is to analyze the worst-case behavior
of trackability as a function of the localization precision parameter λ.
Motivation and the Problem Statement.
This paper takes a small step towards bridg-
ing the gap between theory and practice of trackability, and analyzes the effect of noisy
sensing. In particular, we consider a tracking agent P who wants to follow a moving target
Q in d-dimensional Euclidean space using a noisy location sensor. For simplicity, we analyze
the problem in two dimensions, but the results easily extend to d dimensions, as discussed in
Section 5. We use the notation Q(t) and P(t) to denote the (true) positions of the target and
the tracker at time t. We adopt a simple but realistic model of relative error in sensing noise:
the localization error is proportional to the true distance between the tracker and the target.
More precisely, the localization error is upper bounded as ||Q(t) −˜Q(t)|| ≤
1
λ||P(t) −Q(t)||
at all times t, where λ ≥1 is the quality measure of localization precision. Thus, the closer
the target, smaller the error, and a larger λ means better localization accuracy, while λ = 1
represents the completely noisy case when the target can be anywhere within a disk of radius
||P(t) −Q(t)|| around Q(t). It is important to note that the parameter λ is used only for the
analysis, and is not part of information revealed to the tracker. In other words, the tracker
only observes the approximate location ˜Q(t), and not the uncertainty disk containing the
target. The relative error model is intuitively simple (farther the object, larger the mea-
surement error) and captures the realism of many sensors: for instance, the resolution error
in camera-based tracking systems is proportional to the target’s distance, and in network-
based tracking, latency causes a proportionate localization uncertainty because of target’s
2
movement before the signal is received by the tracker.
We study the tracking problem as a game between two players, the tracker P and the
target Q, which is played in continuous time and space: that is, each player is able to instan-
taneously observe and react to other’s position, and the environment is the two-dimensional
plane, with or without polygonal obstacles. Both the target and the tracker can move with
equal speed, which we normalize to one, without loss of generality. With the unit-speed
assumption, the following holds, for all times t1 ≤t2:
||Q(t2) −Q(t1)|| ≤|t2 −t1|,
||P(t2) −P(t1)|| ≤|t2 −t1|
Under the relative localization error model, the reported location of the target ˜Q(t)
always satisfies the following bound, where λ is the accuracy parameter:
||Q(t) −˜Q(t)|| ≤||P(t) −Q(t)||
λ
We measure the tracking performance by analyzing the distance function between the
target and the tracker, namely, D(t) = d(P(t), Q(t)), over time, with D(0) being the distance
at the beginning of the game. Under error-free localization, the distance remains bounded
as D(t) ≤D(0). We analyze how ||D(t) −D(0)|| grows under the relative error model, as a
function of λ. Our main results are as follows.
Our Results.
We show that the simple greedy strategy of “always move to the observed
location of the target” achieves D(t) ≤D(0) + t/λ2. That is, the target’s distance from
the tracker can grow at most at the rate of O(λ−2), the inverse quadratic function of the
localization parameter. We prove this rate to be worst-case optimal with a matching lower
bound: a strategy for the target that ensures that, under the relative error model, it can
increase its distance as D(t) ≥D(0) + Ω(t/λ2).
We then extend this analysis to environments with polygonal obstacles, and show that
the tracker can increase its distance by Ω(t) in time t for any finite λ. This is unsurprising
because two points within a small margin of sensing error can be far apart in free-space,
thereby fooling the tracker into “blind alleys.”
More surprisingly, however, if we adopt
a localization error that is proportional to the geodesic distance (and not the Euclidean
distance) between the target and the tracker, then the distance increases at a rate of Θ(λ−1).
This bound is also tight within a constant factor: the tracker can maintain a distance of
D(t) ≤D(0) + O(t/λ) by the greedy strategy, while the target has a strategy to ensure
that the distance function grows as at least D(t) ≥D(0) + Ω(t/λ).
Our analysis also helps answer some other questions related to tracking performance. For
instance, a natural way to achieve good tracking performance in the presence of noisy sensing
is to let the tracker move at a faster speed than the target. Then, what is the minimum
speedup necessary for the tracker to reach the target (or, keep within a certain distance
of it)? We derive upper and lower bounds for this speedup function, which are within a
constant factor of each other as long as λ ≥2.
3
Organization.
The paper is organized as follows.
Section 2 investigates the tracking
problem in the Euclidean plane without obstacles. Section 3 derives bounds on the speedup
function. Section 4 explores the tracking performance in the presence of polygonal obstacles.
Section 5 briefly discussed the straight-forward extension of our results to d-dimensions.
Section 6 offers a summary and concluding remarks.
2
Tracking in the Unobstructed Plane
We begin with the simple setting in which a tracking agent P wants to follow a moving target
Q in the two-dimensional plane without any obstacles. We show that the trivial “aim for
the target’s observed location” achieves essentially the best possible worst-case performance.
We first prove the upper bound on the derivative D′(t) of the distance function D(t), and
then describe an adversary’s strategy that matches this upper bound.
2.1
Tracker’s Strategy and the Upper Bound
Our tracker uses the following obvious algorithm, whose performance is analyzed in Theo-
rem 1 below.
GreedyTrack.
At time t, the tracker P moves directly towards the target’s observed
location ˜Q(t).
Theorem 1. By using GreedyTrack, the tracker can ensure that D(t) ≤D(0)+O(t/λ2),
for all t ≥0.
Proof. Consider the true and the observed positions of the target, namely Q(t) and ˜Q(t),
respectively, at time t, and let γ be the angle formed by them at P(t).
See Figure 1.
Consider an arbitrarily small time period ∆t during which P moves towards ˜Q(t) and Q(t)
moves away from P(t). We want to compute the derivative of the distance function, given
as Equation (1).
D′(t) = lim
∆t→0
D(t + ∆t) −D(t)
∆t
(1)
The new distance between the target and the tracker is given by bc in Fig. 1. In the
triangle abc, we have ab = ∆t sin γ and ac = D(t) + ∆t −∆t cos γ. We, therefore, can bound
D(t + ∆t) as follows (where the final inequality uses the fact √1 + x ≤1 + x
2):
D(t + ∆t) =
p
(∆t sin γ)2 + (D(t) + ∆t −∆t cos γ)2
=
q
∆t2 sin2 γ + D(t)2 + 2D(t)∆t(1 −cos γ) + ∆t2 −2∆t2 cos γ + ∆t2 cos2 γ
=
p
∆t2 + D(t)2 + 2D(t)∆t(1 −cos γ) + ∆t2 −2∆t2 cos γ
=
p
(D(t) + ∆t)2 −2D(t)∆cos γ + ∆t2 −2∆t2 cos γ
4
Q
D(t)
λ
˜Q
P ∆t
∆t
D(t)
γa
b
c
Figure 1: Proof of Theorem 1.
=
p
(D(t) + ∆t)2 −2∆t(D(t) + ∆t) + ∆t2 −2D(t)∆cos γ −2∆t2 cos γ + 2∆t(D(t) + ∆t)
=
p
(D(t) + ∆t −∆t)2 −2D(t)∆t cos γ −2∆t2 cos γ + 2∆t(D(t) + ∆t)
=
p
D(t)2 + 2∆t(D(t) + ∆t)(1 −cos γ)
= D(t)
p
1 + 2∆t(D(t) + ∆t)(1 −cos γ)/D(t)2
≤D(t) + (∆t)(1 + ∆t/D(t))(1 −cos γ)
Returning to Equation (1), we get
D′(t) = lim
∆t→0
D(t + ∆t) −D(t)
∆t
≤lim
∆t→0(1 + ∆t/D(t))(1 −cos γ) = 1 −cos γ
Finally, since sin γ ≤1
λ, we get D′(t) ≤1−
q
1 −1
λ2, which simplifies by the Taylor series
expansion:
D′(t) ≤1 −(1 −
1
2λ2 −
1
8λ4 −· · · ) =
1
2λ2 +
1
8λ4 + · · · ≤
1
λ2
This completes the proof that D(t) ≤D(0) + t/λ2.
2.2
Target’s Strategy and the Lower Bound
We now show that this bound is asymptotically tight, by demonstrating a strategy for the
target to grow its distance from the tracker at the rate of D(t) ≥D(0) + Ω(t/λ2), for all
t ≥0. We think of the target as an adversary who can choose its observed location at any
time subject only to the constraints of the error bound: ||Q(t) −˜Q(t)|| ≤1
λ(||P(t) −Q(t)||).
(Recall that the tracker only observes the location ˜Q(t), and has no direct knowledge of
either the parameter λ or the distance ||P(t) −Q(t)||. Those quantities are only used in the
analysis. However, the lower bound holds even if the tracker knows the uncertainty disk,
namely, the localization error 1
λ(||P(t) −Q(t)||).)
5
In order to analyze the lower bound, we divide the time into phases, and show that the
distance from the tracker increases by a multiplicative factor in each phase, resulting in a
growth rate of Ω(1+λ−2). If the ith phase begins at time ti, then we let di = ||Q(ti)−P(ti)||
denote the distance between the target and the tracker at ti. During the ith phase, the
target maintains the following invariant for a constant 0 < α < 1 to be chosen later.
Gap Invariant.
Throughout the ith phase, the target moves along a path Q(t) such that
||Q(t)−P(t)|| ≥αdi, for all times t, and all reported locations satisfy ||Q(t)−˜Q(t)|| ≤αdi/λ.
See Figure 2(i) for an illustration. Consider the isosceles triangle with vertices at Q(ti), qa
and qb, whose base qaqb is perpendicular to the line P(ti)Q(ti). The equal sides of the triangle
have length 2di, the base has length 2αdi/λ, and let qc be the midpoint of the base. The
target’s strategy is to move from Q(ti) to either qa or qb, and report its location ˜Q(t) at the
closest point on the line Q(ti)qc; i.e. at all times, ˜Q(t) is the perpendicular projection of Q(t)
onto the line Q(ti)qc. By the symmetric construction, and the choice of the points qa and
qb, the tracker cannot tell whether the target is moving to qa or qb. Thus, any deterministic
tracker makes an incorrect choice in one of the two possible scenarios. For the worst-case
performance bound, we can equivalently assume that the target non-deterministically guesses
the tracker’s intention, and moves to the better of the two possible locations, qa or qb. The
tracker makes this choice based on whether the tracker is on or below the line Q(ti)qc, or
not. In the former case, the target moves to qa, and to to qb otherwise. The ith phase
terminates when the target reaches either qa or qb, and the next phase begins. (We note
that, after i phases, there are 2i possible choices made by the tracker, reflected in whether
it is above or below the line Q(ti)qc at the conclusion of each phases. For each of these
possible “worlds” there is a corresponding deterministic strategy of the target that “fools”
the tracker in every phase, resulting in the maximum distance increase.) There is one subtle
point worth mentioning here. It is possible that during the phase, the distance between the
players may shrink if the tracker temporarily moves towards the same final location as the
target—however, our Gap Invariant ensures that that the target’s noisy location remains
within the permissible error bound throughout the phase. The following lemma shows that
this simple strategy of the target can maintain the Gap Invariant for any choice of α ≤0.927.
Lemma 1. The target can maintain the Gap Invariant for any α ≤0.927.
Proof. Consider an arbitrary phase i. By construction, we have ||Q(t)−˜Q(t)|| ≤αdi
λ through-
out this phase, so we only need to show D(t) ≥αdi. There is one subtle point worth men-
tioning here. While the target’s strategy will ensure that its distance from the tracker grows
by a certain multiplicative factor at the end of the phase, the distance between the players
may shrink during the phases. This happens when the tracker temporarily moves towards
the same final location as the target. In spite of this temporary “lucky” guess by the tracker,
we need to ensure that the target’s noisy location remains within the permissible error bound
throughout the phase. The constant α is introduced precisely to guarantee this validity, and
we arrive at its value as follows.
6
P(ti)
Q(ti)
qa
qb
qc
di
2di
2di
αdi
λ
αdi
λ
(i)
P(ti)
Q(ti)
qa
qc
di
2di
αdi
λ
di
P(ti+1)
(ii)
Figure 2: Target’s strategy during the ith phase (i), and proofs of Lemmas 1 and 2 (ii).
Let di+1 be the distance between P and Q if both moved toward qa for the duration
of phase i.
Note that di+1 is the length of the segment P(ti)qa minus 2di, as shown in
Figure 2(ii). The length of P(ti)qa can be calculated from the right triangle qaP(ti)qc, while
the length of qaqc is known by construction. Finally, Q(ti)qc has length di less than P(ti)qc.
Thus, we have:
di+1 =
s
(
r
4d2
i −d2
i α2
λ2
+ di)2 + d2
i α2
λ2
−2di
=
s
5d2
i −d2
i α2
λ2
+ 2di
r
4d2
i −d2
i α2
λ2
+ d2
i α2
λ2
−2di
= di
s
5 + 4
r
1 −α2
4λ2 −2di
In order to satisfy the Gap Invariant, we must choose an α such that the following
inequality holds:
αdi ≤di
s
5 + 4
r
1 −α2
4λ2 −2di
α2 + 4α + 4 ≤5 + 4
r
1 −α2
4λ2
α2 + 4α + 4 ≤5 + 4 −α2
2λ2
α2(1 +
1
2λ2) + 4α −5 ≤0
7
This gives the following upper bound:
α ≤
−4 ±
q
16 + 4(1 +
1
2λ2)5
2(1 +
1
2λ2)
≤1
3(
√
46 −4)
The preceding lemma shows that our construction satisfies the Gap Invariant, and so we
can now lower bound the distance growth during a single phase.
Lemma 2. At the start of phase i + 1, we have di+1 ≥di
q
1 + α2
2λ2, where α = 0.927 is an
absolute constant.
Proof. Suppose, without loss of generality, that the target is at qa at the termination of
the ith phase, which means the tracker is on or below the line Q(ti)qc. By the unit speed
assumption, the target needs exactly 2di time for this move. The minimum value of di+1 is
at least as large as if P had moved directly to qc by distance 2di, as shown in Figure 2(ii).
We can calculate di+1 from the right triangle qaP(ti+1)qc, as follows:
di+1 ≥
s
(
r
4d2
i −α2d2
i
λ2
−di)2 + α2d2
i
λ2
=
s
d2
i −2di
r
4d2
i −α2d2
i
λ2
+ 4d2
i −α2d2
i
λ2
+ α2d2
i
λ2
= di
s
5 −4
r
1 −α2
4λ2
≥di
r
5 −(4 −α2
2λ2)
= di
r
1 + α2
2λ2
We can now prove the main result of this section.
Theorem 2. Under the relative error localization model, a target can increase its distance
from an equally fast tracker at the rate of Ω(λ−2). In other words, the target can ensure that
D(t) ≥D(0) + Ω(t/λ2) after any phase ending at time t.
Proof. The target follows the phase strategy, where that after the ith phase that lasts 2di time
units, the distance between the tracker and the target is at least di
q
1 + α2
2λ2. Therefore, the
distance increases during the ith phase by at least the following multiplicative factor (using
a Taylor series expansion):
8
di
q
1 + α2
2λ2 −di
2di
=
q
1 + α2
2λ2 −1
2
≥
α2
4λ2 −α4
16λ4 = Ω( 1
λ2)
3
Trackability with a Faster Tracker
The results of the previous section establish bounds on the relative advantage available to
the target by the localization imprecision. Its distance from the tracker can grow at the
rate of Θ(λ−2) with time. A tracking system can employ a number of different strategies to
compensate for this disadvantage. In this section, we explore one such natural mechanism:
allow the tracker to move at a faster speed than the target. A natural question then is: what
is the minimum speedup necessary to cancel out the localization noise as a function of λ?
We give bounds on the necessary and sufficient speedups, which match up to small constant
factors as long as λ ≥2. The general form of the speedup function is (1 −
1
λ2)−1/2. The
following theorem proves the sufficiency condition.
Theorem 3. Suppose the target moves with speed one, and the tracker has speed σ =
q
1
1−1/λ2, where λ is the localization precision parameter. Then, the tracker can maintain
D(t) ≤D(0), for all times t ≥0.
Proof. Our analysis closely follows the proof of Theorem 1, and calculates the increase in
the distance during time ∆t. During this time, the tracker is able to move σ∆t, while the
target can move at most ∆t. We can then calculate distance at time t+∆t from the triangle
abc (Fig. 1), where ab = σ∆t sin γ and ac = D(t) + ∆t −σ∆t cos γ, as follows:
D(t + ∆t) =
p
(σ∆t sin γ)2 + (D(t) + ∆t −σ∆t cos γ)2
=
p
σ2∆t2 sin(α)2 + D(t)2 + 2D(t)∆t(1 −σ cos(α)) + ∆t2 −2∆t2σ cos(α) + ∆t2σ2 cos(α)2
=
p
σ2∆t2 + D(t)2 + 2D(t)∆t(1 −σ cos(α)) + ∆t2 −2∆t2σ cos(α)
=
p
(D(t) + ∆t)2 + σ2∆t2 −2D(t)∆tσ cos(α) −2∆t2σ cos(α)
=
p
(D(t) + ∆t −∆t)2 + σ2∆t2 + 2∆t(D(t) + ∆t) −∆t2 −2D(t)∆tσ cos(α) −2∆t2σ cos(α)
= D(t)
p
1 + σ2∆t2/D(t)2 −∆t2/D(t)2 + 2∆t(D(t) + ∆t)(1 −σ cos(α))/D(t)2
≤D(t) + σ2∆t2/2D(t) −∆t2/2D(t) + ∆t(1 + ∆t/D(t))(1 −σ cos γ)
This allows us to bound D′(t) ≤1−σ cos γ, from which it follows that D′(t) ≤0 as long
as σ ≥
q
1
1−1/λ2.
We now show that if λ ≥2, this is the minimum speedup necessary as a function of
λ, up to a small constant factor. We use the phase-based strategy of Theorem 2, however,
9
the value of α determined by Lemma 1 is not sufficient to maintain the Gap Invariant in
this case because of the higher speed of the tracker. Instead, the following lemma gives the
sufficient choice of α.
Lemma 3. Let λ ≥2 and and α ≤0.68 be a constant. Then, the Gap Invariant can be
maintained in any phase as long as σ ≤
1
√
1−1/λ2.
Proof. As in Lemma 1 we need only show that D(t) ≥αdi, and again let di+1 be the distance
between P and Q if both moved toward qa for the duration of phase i. Note that di+1 is
found as the length of the segment P(ti)qa as in Lemma 1 except now minus 2σdi instead of
2di. Thus, we have:
di+1 =
s
(
r
4d2
i −d2
i α2
λ2
+ di)2 + d2
i α2
λ2
−2σdi
=
s
5d2
i −d2
i α2
λ2
+ 2di
r
4d2
i −d2
i α2
λ2
+ d2
i α2
λ2
−2σdi
= di
s
5 + 4
r
1 −α2
4λ2 −2σdi
In order to satisfy the Gap Invariant, we must choose an α such that the following
inequality holds:
αdi ≤di
s
5 + 4
r
1 −α2
4λ2 −2σdi
α2 + 4ασ + 4σ2 ≤5 + 4
r
1 −α2
4λ2
α2 + 4ασ + 4σ2 ≤5 + 4 −α2
2λ2
α2(1 + ϵ2/2) + 4ασ + 4σ2 −9 ≤0
This gives the following upper bound when λ is minimum and σ is maximum, which by
assumption is 2 and 1/
p
1 −(1/22), respectively.
α ≤−4σ +
p
16σ2 −4(1 + 1/2λ2)(4σ2 −9)
2(1 + 1/2λ2)
≤0.68
We can now prove a lower bound on the increase in the distance during the ith phase.
Lemma 4. If λ ≥2, α ≤0.68, and σ ≤(1 −1/λ2)−1/2, then at the start of the i + 1 phase,
we have di+1 ≥di
p
(2σ −3)2 + α2(σ −1/2)/λ2, where α = 0.68 is an absolute constant.
10
Proof. Suppose, without loss of generality, that the target is at qa at the termination of the
ith phase, which means the tracker is below the line Q(ti)qc. By the unit speed assumption,
the target needs exactly 2di time for this move. The minimum value of di+1 is at least as
large as if P had moved directly to qc by distance 2σdi, as shown in Figure 2(ii). We can
calculate di+1 from the right triangle qaP(ti+1)qc, as follows:
di+1 ≥
s
(
r
4d2
i −α2d2
i
λ2
−(2σdi −di))2 + α2d2
i
λ2
= di
s
5 + 4σ2 −4σ −2(2σ −1)
r
4 −α2
λ2
≥di
p
5 + 4σ2 −4σ −4(2σ −1)(1 −α2/8λ2)
= di
p
4σ2 −12σ + 9 + σα2/λ2 −α2/2λ2
= di
p
(2σ −3)2 + α2(σ −1/2)/λ2
Remark.
The preceding lemma can be used to calculate the maximum tracker speed for
which the target can still force a non-negative distance for a specific λ as follows:
p
(2σ −3)2 + α2(σ −1/2)/λ2 = 1
4σ2 −12σ + α2σ
λ2 = −8 + α2
2λ2
2σ −
12 −(α/λ)2
4
2
−
12 −α2/λ2
4
2
= −8 + α2
2λ2
2σ −12 −α2/λ2
4
= −
r
−8 + α2
2λ2 + (12 −α2/λ2
4
)2
σ =
−
q
−8 + α2
2λ2 + ( 12−α2/λ2
4
)2 + 12−α2/λ2
4
2
As λ gets large, the upper and lower bound are within a constant factor of each other.
Indeed, with a more careful choice of α, we can show that the upper and lower bounds are
within a factor of 5.32 (as opposed to 10.23 for the above simple analysis) of each other for
λ ≥2, but we omit those details from this abstract.
4
Tracking in the Presence of Obstacles
The presence of obstacles makes the tracking problem considerably harder under the local-
ization noise. The following simple example (Fig. 3) shows that the target can grow its
11
distance from the tracker as D(t) ≥D(0)+t, for any finite value of λ. The obstacle consists
of a single U-shaped non-convex polygon. Initially, the target is at distance D(0) from the
tracker, and the “width” of the obstacle is less than D(0)/2λ, so that the localization error
is unable to distinguish between a target moving inside the U channel, or around its outer
boundary. One can show that no matter how the tracker pursues, its distance from the
target can grow linearly with time.
D(0)/2λ
Q
P
Q(t)
˜Q(t)
D(0)
Figure 3: Impossibility of tracking among obstacles.
Path Proportionate Error.
In order to get around this impossibility of tracking, we
propose a path proportionate error measure, where the localization error is proportional to
the shortest path distance between the target and the tracker, and not the Euclidean distance
as used before. That is, the tracking signal and the physical movement of the agents follow
the same path metric. Formally, the localization error at time t always obeys the following
bound:
d(Q(t), ˜Q(t)) ≤d(P(t), Q(t))
λ
We show that the best tracking performance in this model is D(t) = D(0) + Θ(t/λ);
that is the distance grows linearly with 1/λ, as opposed to the inverse quadratic function for
the unobstructed case.
4.1
Tracking Upper Bound
The tracker’s strategy in this case is also greedy, except now the tracker makes short-term
commitments in phases, instead of continuously changing its path towards the new observed
location. In particular, for each phase, the tracker fixes its goal as the observed position of
the target at the start of the phase, moves along the shortest path to this goal, and then
begins the next phase.
Algorithm 1 (ModifiedGreedy). The initial phase begins at time t = 0. During the
ith phase, which begins at time ti, the tracker moves along the shortest path to the observed
location of the target at ti, namely, ˜Q(ti). When tracker reaches ˜Q(ti), the ith phase ends,
and the next phase begins.
The upper bound on the tracking performance is given by the following theorem.
12
Theorem 4. Using ModifiedGreedy, the tracker can ensure that D(t) ≤D(0)+O(t/λ).
Proof. First note that because d( ˜Q(ti), Q(ti)) ≤D(ti)/λ, it follows that ti+1 −ti = D(ti) +
xD(ti), where −1
λ ≤x ≤1
λ. Thus, the target’s progress during the ith phase is upper bounded
as d(Q(ti), Q(ti+1)) ≤D(ti)+xD(ti). Next, by applying the triangle inequality, the distance
between P and Q at the beginning of phase ti+1 is upper bounded as
d(P(ti+1), Q(ti+1)) = d( ˜Q(ti), Q(ti+1))
≤d( ˜Q(ti), Q(ti)) + d(Q(ti), Q(ti+1))
≤D(ti)
λ
+ D(ti) + xD(ti)
Finally, the upper bound on the rate of distance increase can be derived as follows:
d(P(ti+1), Q(ti+1)) −d(P(ti), Q(ti))
ti+1 −ti
≤D(ti) + D(ti)/λ + xD(ti) −D(ti)
D(ti) + xD(ti)
= 1/λ + x
1 + x
≤
2
λ + 1
where the final inequality uses the fact that the minimum value occurs when x = 1/λ. In
conclusion, during each phase the distance between the tracker and the target increases by
at most a factor of
2
λ+1, giving the bound D(t) ≤D(0) + O( t
λ)
4.2
Tracking Lower Bound.
Our final result is to prove that the trackability achieved by ModifiedGreedy is essen-
tially optimal. In particular, we construct an environment with polygonal obstacles and a
movement strategy for the target that ensures D(t) ≥D(0) + Ω(t/λ). The construction
of the polygonal environment is somewhat complicated and requires a carefully designed set
of obstacles. The main schema of the construction is shown in Figure 4, where each edge
of the “tree-like” diagram corresponds to a “channel” bounded by obstacles, and each face
corresponds to a “gadget” consisting of a group of carefully constructed obstacles, with the
outer face occupied entire by a single large obstacle.
As in the proof of Theorem 2, the target moves either to top or the bottom point of the
gadget during a phase, depending on the tracker’s location. The gadget construction is such
that the movement of the target along either path is indistinguishable to the tracker because
both paths are satisfied by a common set of observed locations throughout the path. Thus,
by invoking the earlier equivalence principle, we may as well assume that the target knows
the tracker’s choices. If the target moves to the top, then the next phase occurs in the top
gadget, otherwise the bottom, and so on.
To realize the geometric scheme of Figure 4, we replace each edge of the graph with a
channel as shown in Figure 5(i). The desired edge length can be realized by adding any
13
d0
d0
λ
(1 + 1
λ)d1
d1
λ
d2
λ
(1 + 1
λ)d0
(1 + 1
λ)d0
d1
λ
d2
λ
d2
λ
d2
λ
(1 + 1
λ)d1
(1 + 1
λ)d1
(1 + 1
λ)d1
(1 + 1
λ)d2
(1 + 1
λ)d2
(1 + 1
λ)d2
Figure 4: A high level schema for the lower bound construction. The numbers next to the
edges denote the “path length” in the corresponding channels.
number of arbitrarily skinny bends such that the length of the shortest path through each
channel equals the edge length. Each face is replaced with a set of obstacles, called a gadget,
see Figure 5(ii) for an abstract illustration. The jagged line between each pair of nodes
corresponds to a channel such that shortest path through that channel has the given length.
The target will move along the shortest path through either the top or bottom channel while
reporting its location in the center channel. Meanwhile, the channels connecting the top and
bottom to the center will guarantee that d(Q(t), ˜Q(t)) ≤1
λd(Q(t), P(t)) at all times t during
a phase.
ϵ
L
ϵ
(i)
{
(1 + 1
λ)di
{
di
4λ
di
2λ
di
2λ
di
2λ
di
2λ
Q(ti)
qa
qc
qb
{
(ii)
Figure 5: The channel construction in (i). In (ii) the shortest paths between nodes on the
center path have length di
4λ, and the remaining all have length di
2λ.
4.2.1
Gadget Construction and its Properties
We now describe the construction of our gadgets and establish the geometric properties
needed for the correctness of our lower bound. Each gadget is constructed out of two building
blocks, the bent channels seen in Figure 5(i), and intersections depicted in Figure 6(i). Each
intersection has the property that the shortest path between any two of the points among
14
a, b and c has length 2δ, where δ can be made arbitrarily close to 0. Thus we can construct a
channel that branches into two channels such that the path length through the intersection
is the same regardless of the branch chosen. In Figure 6(ii), we depict the construction of a
gadget using only intersections (triangles) and channels (jagged lines).
c
a
b
δ
δ
δ
δ
δ
δ
(i)
Q(ti)
qa
qc
qb
di
4λ −δ
di
4λ −δ
di
4λ −δ
di
4λ −δ
di
4λ −δ
di
4λ −δ
di
2λ −2δ
di
2λ −2δ
di
2λ −2δ
di
4λ −2δ
di
4λ −2δ
di
4λ −2δ
di
2λ −4δ
di
2λ −4δ
...
...
...
≤di
4λ −2δ
≤di
4λ −3δ
≤di
4λ −δ
(ii)
Figure 6: In (i) an example intersection such that the shortest path between any pair of a b
and c has length 2δ. In (ii) an example gadget construction, where each triangle corresponds
to an intersection with corners representing the points a b and c. The horizontal channels
have length di
4λ between each pair of vertical dashed lines, except for the initial distance before
the first line (which can be made arbitrarily small), and the remaining spillover distance after
the last dashed line.
As in the lower bound for the unobstructed case, the target starts the phase at Q(ti),
and moves to qa or qb while the observed location of the targets moves along the shortest path
from Q(ti) to qc. In particular, let Πa, Πc, and Πb denote the shortest paths from Q(ti) to
qa, qc and qb respectively. The following lemma establishes several properties needed for the
feasibility of the target’s strategy.
Lemma 5. We can construct a gadget for each phase i such that (1) Πa, Πc and Πb have
length (1 + 1
λ)di and (2) for any point xc at distance ℓalong Πc, the corresponding points xa
and xb distance ℓalong Πa and Πb, respectively, satisfy d(xc, xa) ≤di
λ and d(xc, xb) ≤di
λ .
Proof. By construction, the shortest path in each channel between the dashed lines in Fig-
ure 6(ii) has length
di
4λ, and therefore this construction can be extended until Πa, Πc and
Πb have length exactly (1 + 1
λ)di. Next, by the symmetry of the construction, we need only
show that d(xc, xa) ≤di/λ. We ignore the case where xc lies in the channels before the first
dashed lines, as the length of such channels can be made arbitrarily small to guarantee that
d(xa, xc) ≤di/λ. The maximum distance between xa and xc then occurs when xa lies at the
midpoint between two intersections in the top channel. However, in this case one can easily
verify that the following holds:
d(xc, xa) = δ + di
4λ −2δ + 2δ + di
2λ −2δ + 2δ + di
4λ −δ = di
λ
This completes the proof.
15
4.2.2
Gap Invariant and the Proof of the Lower Bound
We now formulate the invariant maintained by the target so that its motion is valid under
our (path proportionate) localization error and achieves the desired lower bound.
SP-Gap Invariant.
Throughout the ith phase, the target moves along a path Q(t) such
that D(t) ≥di for all times t, and all reported locations satisfy d(Q(t), ˜Q(t)) ≤di
λ .
Lemma 6. For the duration of phase i, SP-Gap Invariant is maintained.
Proof. Whether Q moves along Πa or Πb, they are both shortest paths (and this cannot
be shortcut by P), implying that D(t) ≥di for the duration of the phase. Without loss
of generality, suppose Q chooses Πa. Then, after time t, both the target and its observed
position have moved a distance of t along Πa and Πc, respectively. Therefore, by Lemma 5,
we have d(Q(t), ˜Q(t)) ≤di
λ .
We can prove our lower bound.
Theorem 5. The target’s strategy guarantees that after each phase ending at time t, the
distance function satisfies D(t) ≥D(0) + Ω( t
λ).
Proof. The proof is by induction on the phase i. The basis of the induction is i = 0. Since
the localization error makes target’s top and bottom paths indistinguishable to the tracker,
the target can ensure that at the end of phase 0 the target is on the side of Πc that is opposite
P. Without loss of generality, suppose that that target has reached qa. Then the best case
for P is if it moved d0
λ along Πc, which achieves D(t1) ≥D(0) + D(0)
2λ .
Now assume by induction that after phase i−1 ends at time ti, we have D(ti) ≥D(ti−1)+
D(ti−1)/2λ = di. Suppose now that P has yet to reach the gadget corresponding to phase i
when Q has finished phase i at time ti+1. Then necessarily D(ti+1) ≥di +di/λ, as that is the
length Πa and Πb. Otherwise if P has moved into the gadget, then the inequality D(ti) ≥di
ensures that the closest the target can be to the tracker is if P has moved di
λ along Πc, which
implies D(ti+1) ≥D(ti) + D(ti)
2λ .
Thus, in a round with duration (1 + 1
λ)di, the distance increases by at least di/2λ. Thus,
in the ith phase, the distance increases by a factor of at least
di/2λ
(1 + 1
λ)di
=
1
2λ(1 + 1
λ) =
1
2 + 2λ
Thus, at the end of any phase, we have the inequality D(t) ≥D(0) + Ω(t/λ), which
completes the lower bound.
5
Extension to d dimensions
Our analysis of trackability was carried out for 2-dimensional Euclidean plane, but the results
generalize easily to d dimensions. Indeed, in the unobstructed case, our analysis of the upper
16
bound only makes use of the triangle inequality: the region of interest is the triangle formed
by P(t), Q(t), and ˜Q(t), and the target Q moves directly away from P. Thus, within an
arbitrarily small time interval ∆t, P and Q are moving within the two-dimensional plane
of the triangle P(t)Q(t) ˜Q(t). The upper bound analysis therefore extend to any dimension
d ≥2. The same reasoning also holds in the presence of obstacles. Finally, the lower bound
construction of d = 2 immediately implies that the trackability lower bound holds in all
dimensions d ≥2.
6
Conclusion
Our paper is an attempt to formally study the worst-case impact of noisy localization on
the performance of tracking systems.
We analyzed a simple, but fundamental, problem
where a tracker wants to pursue a target but the tracker’s location sensor can measure the
target’s position only approximately, with a relative error parameterized by quantity λ. We
prove upper and lower bound on the tracking performance as a function of this localization
parameter λ. A few surprising consequences of our results are (1) that the naive strategy
of “always move to the observed location” is asymptotically optimal, (2) the tracking error
has a nice analytic form, showing an inverse quadratic dependence on λ, and (3) under
the natural “path proportional error”for environments with obstacles, the trackability has
qualitatively a different dependence of the form Ω(1/λ).
Compared to often-used heuristics such as Kalman filters, our work offers a more theo-
retical perspective for analyzing motion and localization errors in the presence of inevitable
noise, which may be especially useful in situations where worst-case bounds are important,
such as adversarial tracking or surveillance. In addition to improving the constant factors
in our bounds, it will also be interesting to study the noisy sensing model for other more
complex settings.
17
References
[1] M. Aigner and M. Fromme. A game of cops and robbers. Discrete Applied Mathematics,
8(1):1 – 12, 1984.
[2] S. Alpern, R. Fokkink, R. Lindelauf, and G.-J. Olsder. The ”princess and monster”
game on an interval. SIAM J. on Control and Optimization, 47(3):1178–1190, 2008.
[3] D. Bhadauria, K. Klein, V. Isler, and S. Suri. Capturing an evader in polygonal en-
vironments with obstacles: The full visibility case. International Journal of Robotics
Research, 31(10):1176–1189, September 2012.
[4] S. D. Bopardikar, F. Bullo, and J. P. Hespanha. A cooperative homicidal chauffeur
game. In 46th IEEE Conference on Decision and Control, pages 4857 –4862, 2007.
[5] S. D. Bopardikar, F. Bullo, and J. P. Hespanha. On discrete-time pursuit-evasion games
with sensing limitations. IEEE Transactions on Robotics, 24(6):1429–1439, 2008.
[6] B. P. Gerkey, S. Thrun, and G. J. Geoffrey. Visibility-based pursuit-evasion with limited
field of view. International Journal of Robotics Research, 25(4):299–315, 2006.
[7] L. J. Guibas, J.-C. Latombe, S. M. LaValle, D. Lin, and R. Motwani. Visibility-based
pursuit-evasion in a polygonal environment. International Journal of Computational
Geometry and Applications, 9(5):471–494, 1999.
[8] V. Isler and N. Karnad. The role of information in the cop-robber game. TCS, 399(3):179
– 190, 2008.
[9] R. E. Kalman. A new approach to linear filtering and prediction problems. Transactions
of the ASME–Journal of Basic Engineering, 82:35–45, 1960.
[10] N. Karnad and V. Isler. Bearing-only pursuit. In Proc. IEEE Int. Conf. on Robotics
and Automation, 2008.
[11] K. Klein and S. Suri. Capture bounds for visibility-based pursuit evasion. In Proc. of
the 29th Symposium on Computational Geometry, SoCG ’13, pages 329–338, New York,
NY, USA, 2013. ACM.
[12] K. Klein and S. Suri. Pursuit evasion on polyhedral surfaces. In Proc. of 24th Interna-
tional Conference on Algorithms and Computation (ISAAC), 2013.
[13] V. M. Kuntsevich and A. V. Kuntsevich. Analysis of the pursuit-evasion process for
moving plants under uncertain observation errors dependent on states. In Proc. of the
15th International Federation of Automatic Control, 2002.
[14] L. Liao, D. Fox, J. Hightower, H. Kautz, and D. Schulz. Voronoi tracking: Location
estimation using sparse and noisy sensor data. In Proc. of International Conference on
Intelligent Robots and Systems (IROS, 2003.
18
[15] N. Noori and V. Isler. Lion and man with visibility in monotone polygons. International
Journal of Robotics Research.
[16] S.-M. Park, J.-H. Lee, and K.-Y. Chwa. Visibility-based pursuit-evasion in a polygonal
region by a searcher. In Proc. of ICALP, pages 281–290. Springer-Verlag, 2001.
[17] G. Rote. Pursuit-evasion with imprecise target location. In Proc. of 14th ACM-SIAM
Symposium on Discrete algorithms, SODA ’03, pages 747–753, Philadelphia, PA, USA,
2003. Society for Industrial and Applied Mathematics.
[18] X. Sheng, Y.-H. Hu, and P. Ramanathan. Distributed particle filter with GMM ap-
proximation for multiple targets localization and tracking in wireless sensor network.
In Proc. of the 4th International Symposium on Information Processing in Sensor Net-
works, 2005.
[19] I. Suzuki and M. Yamashita. Searching for a mobile intruder in a polygonal region.
SIAM Journal on Computing, 21:863–888, October 1992.
[20] S. Thrun, D. Fox, W. Burgard, and F. Dellaert. Robust monte carlo localization for
mobile robots. Artif. Intell., 128(1-2):99–141, 2001.
19