IEEE Robotics & Automation Magazine - December 2016 - 141

Notation
We use the following notation throughout the article. The
game environment is denoted by S with boundary 2S. We
refer to the subset of S that the evader cannot enter without
being captured as the cleared region. The remaining part of
S is referred to as the contaminated region. We refer to a
shortest path in S between points x and y by P (x, y). The
shortest distance between x and y, i.e., the length of P (x, y), is
denoted by d(x,y). When we require that a distance is measured within a subset, such as to Q 3 S , we write dQ(x,y). We
use B (x, r) = {y ! S|d (x, y) # r} to denote the ball of radius
r centered at x.
Lion's Strategy
The lineage of the lion and man game traces back to Rado's
classic version from the 1930s [3]. This game takes place in a circular arena, and both the lion and the man have equal speed.
The lion wins if it becomes colocated with the man in finite
time. The lion's strategy of staying on the man's radius was generally accepted in folklore [3]. The capture time of this turnbased strategy is O(R2), where R is the radius of the
environment. Sgall [4] uses a similar strategy to show finite time
capture when the game takes place in the nonnegative quadrant
of the plane. Alonso et al. [5] proposed a more sophisticated
strategy that guarantees capture in O (R log (R/r)) steps, where
r is the capture radius.
Simple trigonometric arguments can be used to show that
the lion's strategy captures the man. The proof exhibits the two
essential ingredients for verifying that a pursuit strategy succeeds
in finite time. First, we establish an invariant that the pursuer(s)
maintain throughout the game. For the lion's strategy, this
invariant is that p was located on the radius between the center
and the evader. Second, we need a measure of progress to show
that the game ends in finite time. Let d and d l denote the distance between the center c and the lion before and after a move,
respectively [Figure 5(b)]. Let α be the angle between ce1 and p1
p2. We have d l2 = (d + cos a) 2 + sin 2 a = d 2 + 2d cos a + 1.
(Note that p1p2 = 1.) We first show that there exists a point p2 on
ce2 such that a # (r/2). This is because e 1 e 2 # 1, and hence
p 1 q # 1 where q is a point on ce2 such that qp1 is perpendicular
to ce1 [Figure 5(a)]. As a result of a # (r/2) , we have
d l 2 $ d 2 + 1. When coupled with the invariant, this guarantees
capture after at most R2 rounds.
Isler et al. [6] adapted the lion's strategy for pursuit in a
simply connected polygon P. First, the pursuer starts at
point c in the polygon, which is typically a boundary vertex. Thereafter, the pursuer always moves onto the shortest
path between c and the evader, getting as close to e as possible. Note that this shortest path could interact with the
boundary of the polygon, in which case it will be a piecewise linear path (Figure 6). The extended lion's strategy
uses the same invariant (being on the shortest path
between c and e) and the same measure of progress
[increasing d(c,p) at a constant rate] as the lion's strategy.
For a polygon P with diameter diam (P) = max u, v ! P d (u, v),
Beveridge and Cai [7] proved that the capture time is

e2

e2
q

q

p2
α

e1
p1

c

c

(a)

e1

p1

d

(b)

Figure 5. In the lion's strategy, the pursuer can increase its
distance from the center by at least d l - d $ (1/2R) . This is
because (a) the length of p 1 q is less than one. As a result, there
exists a point p2 on ce2 that is closer to e2 than q and, moreover,
is at distance one from p 1 . (b) In fact, a 1 (r/2) .

e1
p1

c

e2
p2

b

Figure 6. The lion's strategy in a polygon.

O (diam (P) 2) . Zhou et
al. [8] show that adding a second pursuer
(as in our introductory
example in the square)
reduces capture time to
O (diam (P)) in simply
connected domains.

Current research in
robotics focuses on games
that take place in more
complex environments

Path Guarding and
(e.g., nonconvex polygons,
Projection Mappings
In this s ection, we
environments with
begin our exploration
of environments with
polygonal obstacles)
obstacles. Obstacles create an advantage for the
and sometimes consider
evader. For example, a
single pursuer cannot
players subject to sensing
catch an evader when
there is one large obstalimitations.
cle in the environment.
Indeed, the evader can
start from a point on the boundary of the obstacle and then
loop around the obstacle, moving away from the pursuer
thereafter. In this section, we describe how a shortest path
can be guarded by a pursuer even in the presence of obstacles. This capability turns out to be a powerful subroutine
for solving the lion and man game. We start with a formal
DECEMBER 2016

*

IEEE ROBOTICS & AUTOMATION MAGAZINE

*

141
Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - December 2016
