arXiv:1508.06333v2  [cs.RO]  5 Feb 2016
1
Capturing an Omnidirectional Evader in Convex Environments
using a Differential Drive Robot
Ubaldo Ruiz1 and Volkan Isler2
Abstract—We study the problem of capturing an Omnidirectional
Evader in convex environments using a Differential Drive Robot (DDR).
The DDR wins the game if at any time instant it captures (collides with)
the evader. The evader wins if it can avoid capture forever. Both players
are unit disks with the same maximum (bounded) speed, but the DDR
can only change its motion direction at a bounded rate. We show that
despite this limitation, the DDR can capture the evader.
Index Terms—Motion and Path Planning, Surveillance Systems, Non-
holonomic Motion Planning.
I. INTRODUCTION
We introduce a novel pursuit-evasion game closely related to
mobile robotics applications. In the literature, numerous pursuit-
evasion games have been studied [1]. For example, one or more
pursuers could be given the task of finding an evader [2]–[4] in an
environment. Another related problem is to maintain visibility of a
moving evader [5]–[9]. Alternatively, the pursuer might try to capture
the evader by moving to a contact configuration or getting closer than
a given distance [10]–[14].
The kinematic problem of capturing an omnidirectional evader
using a Differential Drive Robot (DDR) in an obstacle-free envi-
ronment was studied in [12]. In that work, it was assumed that the
DDR is faster than the evader, and the game ends when the distance
between the DDR and the evader is smaller than a critical value l.
The DDR wants to minimize the capture time while the evader wants
to maximize it. The main contributions of that work were computing
time-optimal motion strategies for each player using differential game
theory [10] and finding the conditions defining the winner. In contrast
to [12], in this work we consider that the game takes place in
a bounded environment and the players have the same maximum
velocity. This setup requires a new solution and methodology.
Our game is a variant of the lion-and-man game in which a
lion tries to capture a man with equal maximum speed. This game
has received significant attention in robotics [1]. However, in most
previous work on the lion-and-man game, the lion is assumed to
be omnidirectional. This assumption is not true for most robots.
Therefore, in this paper, we study a variant of the original lion-and-
man game in which the pursuer is a differential drive.
In the original version of the game, the lion and man are in a
circular arena (see Fig. 1). They have the same maximum speed and
can observe each other at all times. The lion can get arbitrarily close
to the man using the following strategy first described in [15]: at the
beginning of the game, the lion goes to the center C of the arena.
Afterwards, let M ′ be the position of the man when it is the lion’s
turn. The lion moves on to the radius CM ′. Among all points on
CM ′ within its step-size, the lion chooses the point L′ that is closest
to M ′. By using elementary trigonometry, it can be shown that the
lion captures the man in O(r2) steps when they move in turns. Here,
r is the radius of the arena.
1Ubaldo
Ruiz is
a CONACYT Research
Fellow.
He is
with the
Department
of
Computer
Science,
CICESE,
Baja
California,
Mexico
uruiz@cicese.mx.
2Volkan Isler is with the Department of Computer Science and Engineering,
University of Minnesota, Minneapolis, MN, USA isler@cs.umn.edu
r
M’
M
L
C
L’
Fig. 1. The man moves from point M to point M′. The lion at L moves on
to the radius CM′ and reaches point L′.
Now imagine that both players are unit disks and the pursuer is a
Differential Drive Robot (DDR). It can not directly follow the strategy
described above. In particular, since it must spend time to turn, it
can not reach L′. Can the pursuer capture the man? In this paper, we
present a novel strategy and show that the DDR lion can still capture
the man.
We start by mapping the environment to the evader’s configuration
space. In the new environment both players are represented as points,
and the configurations where the DDR collides with the evader are
characterized by a capture disk of radius rc = 2 centered at the
DDR’s position. This mapping allows us to focus on the differential
constraints and ignore collisions with the boundary due to the shape
of the players. Note that since the players have the same shape, the
reachable part of the workspace is the same for both players. We
propose a pursuit strategy to solve the game and prove that one DDR
pursuer can capture (collide) the evader in upper bounded time.
A. Related Work
The lion and man game is well studied [15]–[17]. In [15], Lit-
tlewood shows that the lion can not reduce the distance to zero in
the continuous time formulation of the problem. Alonso et al. [16]
showed that the lion captures the man in time O( r
s log r
c), where
r is the radius of the circular arena, c is the capture distance and
s is the maximum speed of the players. In [17], Sgall studies the
discrete time version of the problem in the positive quadrant. He
showed under which initial conditions the lion can capture the man.
Recently, it has been shown that a single lion can capture the man in
simply-connected polygons [3], and three lions suffice in polygons
with holes [11]. In this work, we take a step toward modeling more
realistic robotics applications and study the lion and man game where
the pursuer is a DDR that can only change its motion direction
at a bounded rate that is inversely proportional to its translational
speed [12]. Using a novel strategy, we study conditions under which
the DDR lion can capture the man in any convex environment (see
Fig. 2).
II. PROBLEM FORMULATION
A Differential Drive Robot pursuer (DDR) and an omnidirectional
evader move in a convex environment W ∈R2 (see Fig. 2). The DDR
2
p
W
e
Fig. 2.
The game takes place in a convex environment W . The DDR at
position p and the evader at position e are unit disks. The DDR wins the
game if it captures (collides with) the evader. The evader wins if it avoids
capture forever.
r
R
R
ω1
2
ω
(x, y)
ω
θ
ν
r
(a) Model
ν
ω
(b) Control space
Fig. 3. Differential Drive Robot Model
wants to capture the evader, and the evader wants to avoid capture.
The capture condition is satisfied when the DDR is in collision with
the evader. The DDR wins the game if it captures the evader in finite
time. The evader wins if it avoids capture forever. Both players are
unit disks and have the same maximum bounded speed vmax. The
DDR can only change its motion direction at a bounded rate that is
inversely proportional to its translational speed [12]. In this work, we
consider a purely kinematic problem, and neglect any effects due to
dynamic constraints (e.g., acceleration bounds). The motions of the
players are made in turns, with the evader moving first. The duration
of each turn is chosen to be 1/vmax which is the time it takes to
travel a unit distance. Our result holds for any non-zero turn duration
with the appropriate scaling of the number of steps. We assume a
complete information setup, i.e. each player knows the location and
orientation of the other player at all times.
III. PRELIMINARIES
In this section, we present the concepts and definitions used
throughout the paper.
A. Model
The kinematic model for a DDR [12] is given by
˙xp = v cos θp,
˙yp = v sin θp,
˙θp = ω
(1)
where v and ω are the translational and angular velocities of the
DDR. In practice, we control the individual velocities of the wheels.
Therefore, we have that
v = r (ω1 + ω2)
2
,
ω = r (ω2 −ω1)
2R
(2)
where r is the radius of the wheels, and ω1 and ω2 are their angular
velocities. R is the distance between the center of the robot and the
1
e
e
e
e
1
1
p
cr
2
1
1
Fig. 4.
The dashed circle with radius rc centered at the DDR’s position p
characterizes the configurations where the DDR collides with the evader. Note
that since the players are represented by unit disks we have that rc = 2.
wheel’s location (see Fig. 3(a)). For a DDR, assuming vmax > 0, we
have that
| ˙θ| = |ω| ≤1
R(vmax −|v|)
(3)
The angular velocity is inversely proportional to the translation
velocity (see Fig. 3(b)). We assume that the values of the translational
velocity v and the angular velocity w can be chosen directly as long
as they satisfy Eq. (3).
B. Playing space
As mentioned earlier, we map the convex environment W to the
evader’s configuration space simply by removing all points within
unit distance from the boundary. We denote this new environment as
Q. From now on, we represent the players as points in Q. Now we
identify configurations where collisions between the DDR and the
evader are possible in W . In Fig. 4, we observe that collisions in
W occur for the evader’s positions that are at distance at most 2 to
the DDR’s center thus we can characterize those configurations in Q
using a circle of radius rc = 2 centered at p. We denote that circle
as the capture region.
Hereafter p ∈Q represents the position of the DDR, and θp
denotes its orientation (heading) with respect to a line LG which
will be explained shortly. The location of the evader is denoted by
e ∈Q. We assume that both players have the same maximum speed
vmax = 1 and the DDR’s wheels have radius one thus r = 1. Each
player moves during a time-step ∆t = 1. The length of the shortest
path between two points a, b ∈Q is denoted by d(a, b). A chord,
or a diagonal of Q is a line segment joining two non-consecutive
vertices of Q. The diameter of Q is the length of the longest chord
of Q and denoted by diam(Q). The boundary of Q is represented
as ∂Q.
C. Notion of guarding a line segment
Next, we define a fundamental concept behind the notion of
guarding a line segment.
Definition 1 (Projection): Let LG ∈Q be a line segment dividing
Q into two subregions Q1 and Q2, and e ∈Q2. The projection of e
on LG is the closest point eπ ∈LG to e.
In this paper, we take advantage of the fact that the DDR has a
non-zero capture radius. In Lemma 2, we prove that the DDR can be
located at a distance d(p, eπ) = 1
2 on LG, and it captures the evader
if it tries to cross LG.
3
y
L G
p
2
e
eπ
1/2
1/2
RL
x
Fig. 5. We define a local reference frame RL at eπ. In this case, the x-axis
is pointing right.
Definition 2 (Guarding a line): The line segment LG is guarded if
the DDR can prevent the evader from crossing it. That is, the evader
is captured if it crosses LG.
In Lemma 2, we will show that the DDR can guard LG by
maintaining the following invariants at the beginning of each turn
of the evader.
Invariant 1: The heading of the DDR is parallel to LG.
Invariant 2: The DDR is located at a point p ∈LG such that
d(p, eπ) = 1
2.
In Lemma 1, we prove that Invariants 1 and 2 can be established
by the DDR in finite time. Once the invariants have been established
in the game, the DDR has to ensure that after performing its motions
both invariants are restored before its turn ends.
D. Local reference frame
Suppose the DDR is guarding LG. We define a local reference
frame RL with its origin at the point eπ and the x-axis aligned
with LG (see Fig. 5). The positive y-axis points towards the region
containing the evader. If eπ is located to the right side of the DDR
then the positive x-axis is pointing right, otherwise the positive x-axis
is pointing left. The frame RL is created at the beginning of each
evader’s turn taking the projection of the initial position of the evader
as its origin. We use this frame to describe the player’s motion.
Definition 3 (Positive projection): The evader has a positive
projection if after its turn it has a new projection e′
π located on the
positive side of the x-axis in RL.
Definition 4 (Negative projection): The evader has a negative
projection if after its turn it has a new projection e′
π located at the
origin or on the negative side of the x-axis in RL.
E. Notions of progress
We introduce two notions of progress in our game. Those concepts
will be used to prove that the DDR captures the evader in finite time.
Definition 5 (Vertical progress): The DDR makes vertical
progress if it can guard a new line L′
G which is parallel to LG and
closer to the evader.
When the DDR makes vertical progress, it reduces the size of the
region Q2 containing the evader.
Definition 6 (Horizontal progress): The DDR makes horizontal
progress if it increases its x coordinate in RL and guards LG.
When the DDR makes horizontal progress, it pushes the evader
towards ∂Q. Note that in the previous definition it is assumed that at
the beginning of the DDR’s turn the evader has a positive projection.
IV. THE CAPTURE STRATEGY
In this section, we introduce the strategy for capturing the evader.
e
2
Q
Q1
LG
p
Fig. 6. Let Q be the environment obtained from mapping the workspace W
into the evader’s configuration space. The DDR at point p ∈Q guards the
line segment LG ∈Q by maintaining a distance 1
2 to the projection eπ of
the evader’s position e on the line LG. LG divides Q into two subregions
Q1 (light gray) and Q2 (white). In this case, e ∈Q2. If the evader crosses
the line LG it will be captured by the DDR. The DDR moves the line LG
towards the evader’s position e at some stages of the game, increasing the
area of the subregion Q1, until capture is attained.
We divide the strategy into two stages. In the first one, the DDR
moves to a location on a longest chord of Q, and it establishes Invari-
ants 1 and 2. After that both invariants are maintained throughout the
game. In the second stage, the DDR makes vertical progress reducing
the subregion containing the evader until the capture is achieved (see
Fig. 6). For the first stage, in Lemma 1 we show that once the DDR
is located on a longest chord of Q, it can establish Invariants 1 and
2 in a finite number of turns. For the second stage, in Lemma 3 we
prove that the DDR makes vertical progress if after the evader’s turn
one of the following conditions holds: 1) the evader has a negative
projection or 2) the evader has a positive projection and the distance
between its previous and current projections on LG is less than a
threshold value. If the previous conditions do not hold then the DDR
makes horizontal progress. In that case, in Lemma 4 we prove that
after an upper bounded number of steps the evader hits ∂Q and the
DDR can make vertical progress. In Theorem 1, we show that using
this strategy the evader is captured in an upper bounded time.
A. Guarding a line segment
Let L be a longest chord of Q. In this subsection, we first prove
that the DDR can establish Invariants 1 and 2 on L.
Lemma 1: Let L be a longest chord of Q. The DDR can establish
Invariants 1 and 2 on L in ⌈diam(Q)⌉steps. Afterwards, the DDR
can maintain both invariants indefinitely by following the projection
eπ of e on L.
Proof: Suppose the DDR is located at an arbitrary point p on
L and it has aligned its heading with L (Invariant 1). Let e and e′ be
the evader’s position before and after its turn, respectively. We know
that d(e, e′) ≤1. Since Q is convex, eπ and e′
π are the perpendicular
projections of e and e′ on to L, thus d(eπ, e′
π) ≤d(e, e′). The DDR
establishes the invariants as follows. In each turn, the DDR moves
from point p to point p′, both on L, such that d(p, p′) ≤1. The
point p′ is chosen according to the following rule: If d(p, e′
π) > 3
2,
the DDR moves to the point p′ on L such that d(p, p′) = 1 and
d(p′, e′
π) < d(p, e′
π). Otherwise, the DDR moves to the point p′
such that d(p′, e′
π) = 1
2 and d(p, p′) ≤1.
Note that the DDR either takes a full step or catches up with
e′
π. Further, if the evader keeps moving in one direction pushing its
projection away from the DDR and forcing it to take a full step, it
will hit the boundary first since the DDR is on the longest chord and
behind the projection. Therefore, the projection of the evader must
cross the DDR before the DDR hits the boundary. At this point, the
DDR can position itself half a step behind the projection. Therefore,
4
β
G
L
e
p
2
1/2
eπ p’
*
Fig. 7.
The evader is located at point e∗on the boundary of the capture
region. The dashed circle shows all evader’s locations where d(e, e′) = 1.
The DDR can move from point p to point p′ where d(p, p′) ≤1 in one turn.
following this strategy the DDR will position itself on a point p on
L such that d(p, eπ) = 1
2 in at most ⌈diam(Q)⌉steps.
While the DDR is establishing Invariant 2, the evader can cross
L multiple times. This is not a problem: Since Q is convex,
every point in Q has a unique projection on the longest chord.
Furthermore, the projection moves continuously. Thus both invariants
can be established regardless of which side the evader lies. Once the
invariants are established on any line segment LG, they can be easily
maintained. This is because the evader’s projection moves by at most
one unit which allows the pursuer to keep up with the motion of the
projection.
Corollary 1: Let LG be any chord of Q and suppose that the DDR
established Invariants 1 and 2 on LG. The DDR can maintain both
invariants indefinitely.
The goal of establishing the invariants is trapping the evader in
one of the two regions defined by longest chord in Q. This region is
the one which contains the evader when the invariants are established
and is arbitrary.
We now prove that by maintaining Invariants 1 and 2, the pursuer
can prevent the evader from crossing the line segment LG . This
introduces a notion of guarding the line segment which is an
important component of the pursuer strategy.
Lemma 2: After Invariants 1 and 2 are established, the evader
cannot cross the line LG: if the evader moves to a new position e′
such that d(e′, e′
π) <
√
15
2
then the DDR captures the evader in one
turn.
Proof: Let p be the position of the DDR on LG. As Invariant
2 has been established the evader is located on a point e such
that d(p, eπ) =
1
2. Consider the point e∗on the boundary of the
capture region (see Fig. 7). Since Q is convex the segment e∗eπ
is the shortest path from e∗to LG. The length of this segment is
d(e∗, eπ) =
p
22 −(1/2)2 =
√
15/2. Therefore, for all positions
e located outside the capture region and such that d(p, eπ) =
1
2
the distance d(e, eπ) ≥
√
15/2 > 1, thus the evader cannot reach
the line LG without entering the capture region. Note that as eeπ
is the shortest path from e to eπ on LG then any other trajectory
between those points is longer than d(e, eπ) and it cannot be traveled
in one turn. If, instead of crossing the line, the evader moves
closer to it without crossing, it still gets captured: For any evader
move to e′ such that d(e′, e′
π) <
√
15/2, the DDR can move to
location p′ such that d(p′, e′
π) =
1
2 and capture the evader since
d(p′, e′) =
p
(1/2)2 + d(e′, e′π)2 < 2.
p’’
L
x
G
L’G
eπ
y RL
pt
e
e’π
α
p
p’
α
1/2
1/2
e’
Fig. 8. Making vertical progress. The evader has a negative projection. The
DDR makes vertical progress applying the zig-zag strategy.
B. Making progress
In the previous section, we showed that the DDR can establish
Invariants 1 and 2 on the longest chord and guard any chord once the
invariants have been established. Of course, simply guarding does not
suffice for capture. In this subsection, we present a strategy to guard
a new line parallel to LG after Invariants 1 and 2 are established. We
also establish lower bounds for the horizontal and vertical progress
made by the DDR at each turn. Those bounds are used to prove that
the DDR captures the evader in an upper bounded time.
Suppose the evader moves from point e to point e′ such that
d(e, e′) ≤1 and its new projection e′
π is negative. The DDR makes
vertical progress by moving to point p′ in the line perpendicular
to LG having the point p as the intersection of both lines, and
d(p′, e′) < d(p, e) (see Fig. 8). To reach p′ we propose a strategy
consisting of four motions that need to be performed in one turn.
First, the DDR rotates in place an angle α at point p. After that,
the DDR translates a distance d(p, pt) from point p to point pt (see
Fig. 8). Next, the DDR rotates in place an angle −α at point pt.
Finally, the DDR translates a distance d(p, pt) cos α from point pt to
point p′. We call this set of motions the zig-zag strategy (see Fig. 8).
Note that after applying the zig-zag strategy the DDR has established
Invariant 1.
If d(eπ, e′
π) = 0 or d(eπ, e′
π) = 1 then at point p′ the DDR
has also established Invariant 2. If d(eπ, e′
π) is different from the
previous values then the DDR has to perform an additional translation
to establish Invariant 2 (see Fig. 8). In this case, it has to move to
a point p′′ such that d(p′′, e′
π) = 1
2. To reach the point p′′ the DDR
translates a distance 1
2 −d(p′, e′
π).
If the evader has a positive projection and d(eπ, e′
π) < 1 then the
DDR can also make vertical progress by applying the zig-zag strategy
reestablishing Invariant 1. In this case, it has to move to a point p′′
such that d(p′′, e′
π) = 1
2. To reach the point p′′ the DDR translates
a distance d(eπ, e′
π) (see Fig. 9). Note that if d(eπ, e′
π) = 1 then
the DDR can only follow the evader’s projection in order to maintain
Invariants 1 and 2.
Definition 7 (Bounding vertical progress): We denote as kv the
lower bound for the vertical progress made by the DDR when it
applies the zig-zag strategy during its turn.
Definition 8 (Bounding horizontal progress): We denote as kh
the lower bound for the horizontal progress made by the DDR when
it follows a positive projection of the evader.
Lemma 3: The DDR makes vertical progress of at least kv =
0.0156 using the zig-zag strategy if during the evader’s turn one of
the following conditions holds: 1) the evader has a negative projection
or 2) the evader has a positive projection and the distance between
its previous and current projections on LG is less than kh = 0.056.
5
L
L G
e’
e
p
π
y
x e’π
α
pt p’
L’G
e
1/2
1/2
α
p’’
R
Fig. 9. Making horizontal progress. The evader has a positive projection. The
DDR makes vertical progress using the zig-zag strategy if d(eπ, e′
π) < 0.056
otherwise it makes horizontal progress.
Proof: Suppose the evader has a negative projection. Using the
zig-zag strategy the DDR reaches a new position p′ on a parallel
line to LG and it also reestablishes Invariant 1 (see Fig. 8). In order
to maintain Invariant 2, the DDR also needs to translate a distance
1
2 −d(p′, e′
π). The time to perform the strategy described before is
given by the following expression
ts =
2α
vmax + d(pt, p)(1 + cos α)
vmax
+
 1
2 −d(p′, e′
π)


vmax
(4)
Note that in order to satisfy the inverse relation between the rotational
and translational velocities in Eq. (3), we assume that the rotational
and translational motions are performed separately at maximal speed
in Eq. (4), thus each motion requires an independent amount of time.
Since the DDR must perform the strategy in one turn ts = ∆t = 1.
Substituting the last equation into Eq. (4), we obtain that
d(p, pt) =
1
2 + d(p′, e′
π) −2α
1 + cos α
(5)
From the right triangle △pptp′ in Fig. 8, we have that d(p, p′) =
d(p, pt) sin α. Substituting Eq. (5) into the last expression, and
recalling that tan( α
2 ) =
sin α
1+cos α we obtain an expression for the
distance that the DDR can move perpendicular to LG and allows the
DDR to reestablish Invariants 1 and 2
d(p, p′) =
1
2 + d(p′, e′
π) −2α

tan
α
2

(6)
Eq. (6) depends on the angle α that the DDR initially rotates and the
distance between the DDR’s position p′ and the projection e′
π, then
to find the minimum vertical progress that the DDR can make we
have to do the following. For each value of d(p′, e′
π) we have to find
the value of α that maximizes Eq. (6), this give us a set of triplets
(d(p′, e′
π), α, d(p, p′)) where each d(p, p′) is the maximum vertical
progress made by the DDR for the corresponding value of d(p′, e′
π).
The triplet having the smallest value of d(p, p′) corresponds to the
minimum vertical progress made by the DDR when the evader has
a negative projection. Note that d(p′, e′
π) ∈[0, 1
2] and α ∈[0, π
2 ]
since the DDR can rotate in both clockwise or counter-clockwise
direction. As the value of d(p′, e′
π) decreases the time to establish
Invariant 2 increases, recall that the DDR has to translate a distance
1
2 −d(p′, e′
π), and since the time-step is fixed the time to perform
the zig-zag strategy is reduced. It is not hard to see that the minimal
vertical progress achieved by the zig-zag strategy when Eq. (6) is
maximized corresponds to d(p′, e′
π) = 0 since this requires the
maximum translation to establish Invariant 2. To find the value of
α that maximizes Eq. (6) when d(p′, e′
π) = 0 we need to solve
∂d(p, p′)
∂α
= ∂
 1
2 −2α


tan
 α
2


∂α
= 0
(7)
and verify that
∂2d(p, p′)
∂2α
= ∂2  1
2 −2α


tan
 α
2


∂2α
< 0
(8)
From Eq. (7) we have that
1
4 −α

sec
α
2
2
−2 tan
α
2

= 0
(9)
This nonlinear equation can be solved using a numerical software
package. We have that α = 0.1251 is an approximate solution for
this equation. From Eq. (8) we have that
∂2d(p, p′)
∂2α
= −2 sec
α
2
2
+
1
4 −α

sec
α
2
2
tan
α
2

(10)
Substituting α = 0.1251 into Eq. (10) we have that
∂2d(p,p′)
∂2α
=
−1.9999
<
0, thus α
=
0.1251 maximizes d(p, p′) when
d(p′, e′
π) = 0. Substituting α = 0.1251 into Eq. (6) we obtain
d(p, p′) = 0.0156. This value corresponds to the minimum vertical
progress made by the DDR thus kv = 0.0156.
In an analogous way, if the evader has a positive projection but
the projection is within a bound kh, we found an expression for the
distance that the DDR can move perpendicular to LG and allows the
DDR to reestablish Invariants 1 and 2 (see Fig. 9)
d(p, p′) =
1 −d(eπ, e′
π) −2α


tan
α
2

(11)
Note that Eq. (11) depends on the distance between the previous and
current projections of the evader’s position on LG. In this case, we
obtain the value when the horizontal progress made by the DDR
simply following the projection e′
π is the same than the vertical
progress made by the DDR applying the zig-zag strategy. We use
this value as the lower bound for the minimal horizontal progress
kh. To find it we do the following. For each value of d(eπ, e′
π) we
have to find the value of α that maximizes Eq. (11), this give us
a set of triplets (d(eπ, e′
π), α, d(p, p′)) where each d(p, p′) is the
maximum vertical progress made by the DDR for the corresponding
value of d(eπ, e′
π). Note that the value of α that maximizes Eq.
(11) can be computed as it was described in the first part of the
proof. We select the triplet satisfying d(p, p′) = d(eπ, e′
π) and we
set kh = d(eπ, e′
π). This value is d(eπ, e′
π) = 0.056 for which the
DDR performs a rotation α = 0.2371. We use kh as a threshold, if
the evader has a positive projection with d(eπ, e′
π) < kh, the DDR
applies the zig-zag strategy and makes vertical progress moving at
least a perpendicular distance of 0.056 to LG, otherwise, it moves on
LG to maintain Invariant 2, making horizontal progress by translating
at least a distance of 0.056.
Lemma 4: The DDR makes vertical progress after O

diam(Q)
kh

horizontal steps where kh = 0.056.
Proof:
Let the DDR guards a line segment LG. Suppose
that after each turn the evader has a positive projection and the
distance between its previous and current projections on LG is at
least kh, otherwise, the DDR makes vertical progress by Lemma
3. Since the length of LG is upper bounded by diam(Q) then in
at most O(diam(Q)/kh) steps the projection of the evader reaches
the boundary of LG. After that the evader cannot continue having a
positive projection and the DDR makes vertical progress. Note that
since Q is convex, the DDR starts guarding a longest chord of Q,
and every new line segment LG guarded by the DDR is parallel to
the previous one then the line guarded by the DDR before applying
the zig-zag strategy is the longest line segment in the subregion Q2
containing the evader, therefore the DDR never reaches ∂Q before
the evader.
6
C. Capturing the evader
In our main theorem, we prove that following the strategy described
in previous subsections the DDR captures the evader in an upper
bounded time.
Theorem 1: After Invariants 1 and 2 have been established,
the DDR captures the evader in any convex environment in
O

diam(Q)2
khkv

steps where kv = 0.0156 and kh = 0.056.
Proof: From Lemma 4, the DDR makes vertical progress in at
most O(diam(Q)/0.056) horizontal steps for any line segment LG.
From Lemma 3, the DDR minimal vertical progress is kv = 0.0156,
thus in at most O(diam(Q)/0.0156) vertical steps the DDR captures
the evader by trapping it between the boundary and LG. The result
follows.
Throughout the paper, we assumed that the duration of each time-
step is 1/vmax. If a different time-step ǫ/vmax is chosen, the number
of steps to capture the evader gets scaled by 1/ǫ2.
V. CONCLUSIONS AND FUTURE WORK
In this paper, we studied the kinematic problem of capturing an
omnidirectional evader using a Differential Drive Robot (DDR) in
convex environments. The DDR wins the game if at any time instant
it collides with the evader. We proved that for any convex environment
if both players have the same maximum speed then a single DDR
can capture the evader in O

diam(Q)2
kvkh

steps where kv = 0.0156
and kh = 0.056. Our result is one of the few closed form solutions
of a differential game in a geometric setting.
One avenue for future research is to improve the capture time:
From Alonso et al. [16] we have that an omnidirectional lion captures
the man in time O( r
s log r
c ), where r is the radius of the circular
arena, c is the capture distance and s is the maximum speed of
the players. Hence there might be room for improvement in capture
time. The second avenue for research is to investigate the class of
environments in which the DDR wins the game. We conjecture that
the DDR lion can win the game in any simply-connected domain.
In practice, following the strategy presented in this paper might
be difficult for some systems with dynamic constrains. In particular,
following the zig-zag strategy may require large acceleration. Still,
the pursuit strategy presented in this paper can be modified for some
practical applications. For example, if the robot can not follow the
zig-zag trajectory in a single time step, the duration of a step can be
increased. In this case, our algorithm would guarantee capture within
distance traveled in a single time step. Also, the robot does not need
to perform the exact zig-zag motion, it just needs to arrive at the
same configuration, i.e., reach a position where it makes progress
and maintains Invariants 1 and 2. An interesting extension could be
finding a smoother trajectory to reach that point using an optimization
technique. Additional alternatives are increasing the capture radius or
models where the DDR is faster than the evader. Studying systems
with general dynamics is an interesting and challenging avenue for
future research.
VI. ACKNOWLEDGMENTS
This material is based in part upon work supported by the Na-
tional Science Foundation under Grant Numbers IIS-1317788, IIS-
1111638 and IIS-0917676. Any opinions, findings, and conclusions
or recommendations expressed in this material are those of the
author(s) and do not necessarily reflect the views of the National
Science Foundation. Most of this work was done when Ubaldo
Ruiz was a postdoctoral fellow in the Department of Computer
Science and Engineering of the University of Minnesota. He was
financially supported by Consejo Nacional de Ciencia y Tecnolog´ıa
(CONACYT), M´exico.
REFERENCES
[1] T. Chung, G. Hollinger and V. Isler, Search and pursuit-evasion in mobile
robotics: A survey, Special Issue on Search and Pursuit/Evasion, Auton.
Robot, 31(4): 299-316, 2011.
[2] L. Guibas, J.-C. Latombe, S.M. LaValle, D. Lin, R. Motwani, Visibility-
based pursuit-evasion in a polygonal environment, Int. J. Comput. Geom.
Appl., 9(5):471-494, 1999.
[3] V. Isler, S. Kannan and S. Khanna, Randomized Pursuit-Evasion in a
Polygonal Environment. IEEE Transactions on Robotics, 5(21):864-875,
2005.
[4] B. Tovar and S. M. LaValle: Visibility-based Pursuit - Evasion with
Bounded Speed. I. J. Robotic Res, 27(11-12): 1350-1360, 2008.
[5] S.M. LaValle, H.H. Gonz´alez-Ba˜nos, C. Becker and J.-C. Latombe,
Motion Strategies for Maintaining Visibility of a Moving Target In Proc.
IEEE Int. Conf. Robot. Autom., 1997.
[6] H.H. Gonz´alez, C.-Y. Lee and J.-C. Latombe, Real-Time Combinatorial
Tracking of a Target Moving Unpredictably Among Obstacles, In Proc
IEEE Int. Conf. Robot. Autom., 2002.
[7] B. Jung and G. Sukhatme, Tracking targets using multiple robots: the
effect of environment occlusion. In Auton Robot, 13(3):191-205, 2002.
[8] S. Bhattacharya and S. Hutchinson. On the existence of nash equilibrium
for a two player pursuit-evasion game with visibility constraints. Int.
Journal of Robotics Research, 29(7):831–839, 2010.
[9] R. Murrieta-Cid, U. Ruiz, J.L. Marroquin, J.P. Laumond and S. Hutchin-
son, Tracking an Omnidirectional Evader with a Differential Drive
Robot, Special Issue on Search and Pursuit/Evasion, Auton Robot, 31(4):
345-366, 2011.
[10] R. Isaacs. Differential Games. Wiley, New York, 1965.
[11] D. Bhadauria, K. Klein, V. Isler, S. Suri: Capturing an evader in
polygonal environments with obstacles: The full visibility case. Int.
Journal of Robotics Research, 31(10): 1176-1189, 2012.
[12] U. Ruiz, R. Murrieta-Cid and J.L. Marroquin, Time-Optimal Motion
Strategies for Capturing an Omnidirectional Evader Using a Differential
Drive Robot, IEEE Transactions on Robotics, 29(5):1180-1196, 2013.
[13] N. Noori and V. Isler, Lion and man with visibility in monotone
polygons, Int. Journal of Robotics Research, 33(1): 155-181, 2014.
[14] N.M. Stiffler and J.M. O’Kane. A Complete Algorithm for Visibility-
Based Pursuit-Evasion with Multiple Pursuers. In Proc. IEEE Int. Conf.
Robot. Autom., 2014.
[15] J.E. Littlewood. A Mathematician’s Miscellany. London, U.K., Methuen,
1953.
[16] L. Alonso, A.S. Goldstein, and E.M. Reingold, “Lion and man”: Upper
and lower bounds, ORSA J. Comput., 4(4):447-452, 1992.
[17] J.Sgall. “Solution of David Gale’s lion and man problem”, Theoret.
Comput. Sci., 259(1-2): 663-670, 2001.