arXiv:1703.06737v1  [math.OC]  17 Mar 2017
An improved lion strategy for the lion and man problem
Marco Casini, Andrea Garulli
Abstract
In this paper, a novel lion strategy for David Gale’s lion and man problem is proposed. The devised approach
enhances a popular strategy proposed by Sgall, which relies on the computation of a suitable “center”. The key
idea of the new strategy is to update the center at each move, instead of computing it once and for all at the
beginning of the game. Convergence of the proposed lion strategy is proven and an upper bound on the game
length is derived, which dominates the existing bounds.
Index Terms
Lion and man problems, pursuit-evasion games, combinatorial games
I. INTRODUCTION
Pursuit-evasion games have attracted the interest of researchers for long time, both for the intriguing mathematics
they require (see [1] for a nice introduction), and for the variety of applications they find in different contexts,
ranging from mobile robotics to surveillance, resource harvesting, network security and many others. When the
game is played in a limited environment, problems become even more challenging. Among the huge number
of different formulations (an extensive survey is provided in [2]), two main classifications can be singled out,
concerning respectively time and space being continuous or discrete. If continuous time is assumed, it is well
known that an evader can indefinitely escape a single pursuer travelling at the same velocity, even in very simple
continuous environments, like a circle [3]. On the other hand, if time is discrete, the pursuer can capture the
evader in finite time, in many situations of interest. This has generated a rich literature, considering different
assumptions on the number of pursuers, the structure of the environment and the information available to the
players (see, e.g., [4], [5], [6], [7], [8] and references therein).
A fundamental problem at the basis of the above literature is the so-called lion and man problem, whose
formulation is ascribed to Gale (see problem 31 in [9]). A lion and a man move alternately in the positive
quadrant of the plane, travelling a distance of at most one unit at each move. It is known that the lion can
catch the man in finite time, provided that his initial coordinates are componentwise larger than those of the
man. Nevertheless, the optimal lion strategy is still an open problem. In [10], Sgall has proposed a nice strategy
for the lion, which guarantees capture in finite time. Moreover, he has given an upper bound on the capture
time which is achieved for some specific initial conditions. Sgall’s strategy is based on the definition of a fixed
center, depending on the initial lion and man positions: then, the lion always keeps on the line connecting
M. Casini and A. Garulli are with the Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche, Universit`a degli Studi di
Siena, via Roma 56, 53100 Siena, Italy. E-mail: casini@dii.unisi.it, garulli@dii.unisi.it.
the center to the man’s position, until capture occurs. This strategy has been used in several mobile robotics
application, as reported in the tutorial [11]. In particular, a slight variation of the solution proposed in [10] is
adopted iteratively in [4], where it is instrumental to devise a strategy for two pursuers to capture an evader in
simply connected polygonal environments. A similar variation is employed in [12], when dealing with pursuer
evasion games in monotone polygons with line-of-sight visibility.
In this paper, a new lion strategy is proposed for the lion and man problem, which improves the one proposed
in [10]. The main idea is to compute a new center at each move, in order to enhance the advantage gained by
the lion in a single step. This turns out to be effective also on the whole, as it allows one to derive an upper
bound on the maximum number of moves required to guarantee capture, which dominates the one given in
[10].
The paper is organized as follows. In Section II, the lion and man problem is formulated. The solution proposed
in [10] is reviewed in Section III, along with some useful properties. The new strategy is introduced in Section
IV and its convergence properties are derived in Section V. Concluding remarks are reported in Section VI.
II. PROBLEM FORMULATION
The notation adopted in the paper is standard. Let N and Rn
+ denote the set of all natural numbers and the
n-dimensional Euclidean space of non-negative numbers, respectively. Let ⌈x⌉be the smallest integer greater
or equal to x. A row vector with elements v1, . . . , vn is denoted by V = [v1, . . . , vn], while V ′ is the transpose
of V .
In this paper, we consider the version of the lion and man problem formulated by David Gale. Two players, a
man and a lion, can move in the first quadrant of the Cartesian plane. Time is assumed discrete, while space
is continuous. At each round (hereafter called time) both players are allowed to move to any point inside the
non-negative quadrant, with distance less or equal to a given radius r from their current position. Hereafter,
it will be assumed r = 1 without loss of generality. The man moves first, after that the lion moves. Let us
denote by Mt ∈R2
+ and Lt ∈R2
+ the man and lion position at time t, respectively. Hence, ∥Mt+1 −Mt∥≤1,
∥Lt+1 −Lt∥≤1. The game ends (lion wins) if the lion moves exactly to the man position. If the man can
escape indefinitely from the lion, the man wins. It is assumed that the initial man coordinates are strictly smaller
than the corresponding lion coordinates, otherwise it is straightforward to observe that the man wins the game
by moving straight up or right.
III. FIXED CENTER LION STRATEGY
Before introducing the proposed lion strategy, let us recall the one devised in [10], hereafter referred to as
Fixed Center Lion Strategy (FCLS). If the initial man coordinates are strictly smaller than the corresponding
lion coordinates, the FCLS allows the lion to capture the man in a finite number of moves, for any man strategy.
In order to state the FCLS, the following definition is needed.
Definition 1: Let M0 and L0 be the man and lion position at time 0, respectively. Let C0 = [x0, y0]′ ∈R2
+ be
the point satisfying
1) C0 = L0 + η(L0 −M0), with η > 0 ;
2) ∥C0 −L0∥= max{x0, y0} .
Then C0 is called the center of the FCLS.
Fixed Center Lion Strategy
Let C0 be the center of the FCLS. Such a center is fixed and does not change during the game. At a given
time t, let the man move from Mt to Mt+1. The lion adopts the following strategy:
• if ∥Mt+1 −Lt∥≤1, then the lion moves to Mt+1 and catches the man;
• otherwise, the lion moves to a point on the line connecting Mt+1 to C0 with unitary distance from Lt.
Between the two points satisfying such a condition, he chooses the one farther from C0.
Let C0 = [x0, y0]′ and denote by r0 and m0 the greatest and smallest element of C0, respectively, i.e.,
r0 = max{x0, y0} and m0 = min{x0, y0}. Let us denote by N F CLS
max
the upper bound derived in [10] on the
maximum number of moves needed by the lion to catch the man by using FCLS. Let us recall some results
proved in [10] which will be useful in the following.
Proposition 1: Let the lion play the FCLS. At every t, one has
i)
∥Lt −C0∥2 + 1 ≤∥Lt+1 −C0∥2 ≤∥C0∥2 ;
ii)
both elements of C0 −Lt are strictly positive.
Proposition 2: Let the lion play the FCLS. Then, the lion captures the man in a number of moves equal at
most to
N F CLS
max
=

∥C0∥2 −∥C0−L0∥2
=

r2
0 + m2
0 −r2
0

=

m2
0

(1)
The bound in (1) has been proved to be tight whenever the lion and the man start sufficiently close to each
other. In this case, the optimal strategy for the man is to move orthogonally w.r.t. the line connecting him to
C0.
IV. NOVEL LION STRATEGY
In this section, the proposed lion strategy, hereafter referred to as Moving Center Lion Strategy (MCLS), is
introduced. The main difference between MCLS and FCLN regards the computation of the center. While in
FCLS the center in computed once and for all at the beginning of the game, in the proposed strategy it is
updated at each move, and then it is used to compute the lion move.
Before describing the devised lion strategy, let us introduce the following definitions which will be used
throughout the paper.
Definition 2: Let Mt and Lt be the man and lion position at time t, respectively. Let Ct = [xt, yt]′ ∈R2
+ be
the point satisfying
1) Ct = Lt + η(Lt −Mt), with η > 0
2) ∥Ct −Lt∥= max{xt, yt} .
Then Ct is called the center of the MCLS at time t.
Definition 3: At a given time t, let us define the following quantities:
1) rt = max{xt, yt} = ∥Ct −Lt∥
2) mt = min{xt, yt}
3) ˜rt+1 = ∥Lt+1 −Ct∥.
Moving Center Lion Strategy
At a given time t, let the man move from Mt to Mt+1. The lion moves according to the following strategy:
• compute the center Ct, based on man and lion position at time t, according to Definition 2;
• if ∥Mt+1 −Lt∥≤1, then the lion moves to Mt+1 and catches the man;
• otherwise, the lion moves to a point on the line connecting Mt+1 to Ct with unitary distance from Lt.
Between the two points satisfying such a condition, he chooses the one farther from Ct.
The following propositions hold.
Proposition 3: Let the lion play the MCLS. At every time t, one has
i)
∥Lt −Ct∥2 + 1 ≤∥Lt+1 −Ct∥2 ≤∥Ct∥2 ;
ii)
both elements of Ct −Lt+1 are strictly positive ;
iii)
the following inequalities hold
r2
t + 1 ≤˜r2
t+1 ≤r2
t + m2
t .
(2)
Proof: Items i) −ii) follow directly from Proposition 1, because at each time t, the center Ct is defined
in the same way as C0 in Definition 1; item iii) stems from Definition 3 and item i).
Proposition 4: At a given time t, let mt ≤1 and let the lion play the MCLS. Then, the lion captures the man
in one move.
Proof: The proof is a direct consequence of Proposition 2, with C0 = Ct and L0 = Lt.
V. CONVERGENCE ANALYSIS
In this section, an upper bound to the maximum number of moves needed by the lion to catch the man, when
using the MCLS, is derived. Moreover, it is shown that such an upper bound is always smaller than the upper
bound N F CLS
max
provided by the FCLS.
Before stating the main result, the following lemmas are needed.
Lemma 1: Let rt = ∥Ct −Lt∥and ˜rt+1 = ∥Ct −Lt+1∥. Then, xt+1 < xt and yt+1 < yt.
Proof: According to the MCLS, Lt+1 lies on the line connecting Ct and Mt+1. On the other hand, by
Definition 2, Ct+1 lies on the line joining Lt+1 and Mt+1. Hence, Ct, Lt+1 and Ct+1 belong to the same line,
i.e.
Ct+1 = Ct + (Ct −Lt+1)α ≜Ct +

dx
dy

, α, dx, dy ∈R.
By Proposition 3, Ct −Lt+1 has both coordinates strictly positive, i.e., sign(dx) = sign(dy) = sign(α).
Hence, it is sufficient to show that α < 0.
By contradiction, assume α ≥0 and let us define d =
q
d2x + d2y ≥0, see Fig. 1. Then, being dx ≥0 and
dy ≥0, one has
∥Ct+1 −Lt+1∥= ˜rt+1 + d > rt + d ≥rt + max{dx, dy}
≥max{xt + dx, yt + dy} = max{xt+1, yt+1}
where the strict inequality comes from (2). Since ∥Ct+1 −Lt+1∥> max{xt+1, yt+1}, Ct+1 cannot be a center,
according to Definition 2.
Ct+1
Ct
Lt
Lt+1
yt
yt+1
xt+1
xt
dx
dy
d
rt = max{xt, yt}
Fig. 1.
Sketch of proof of Lemma 1.
Lemma 2: Let Ct and ˜rt+1 > rt be given. Let Lt+1 satisfy ∥Ct −Lt+1∥= ˜rt+1. Then,
bmt+1 ≜
sup
Lt+1:∥Ct−Lt+1∥=˜rt+1
mt+1
= max


mt
rt−
q
˜r2
t+1 −m2
t
˜rt+1−
q
˜r2
t+1 −m2
t
, rt
mt−
q
˜r2
t+1 −r2
t
˜rt+1−
q
˜r2
t+1 −r2
t


.
(3)
Proof: Let us consider the case rt = xt (the case rt = yt is analogous).
Let Ct+1 = [xt+1, yt+1] be the center at time t + 1, and θ be the angle between the x axis and the vector
Ct −Lt+1. Notice that, since Ct+1 lies on the line connecting Lt+1 and Ct, θ is also the angle between the x
axis and the vector Ct+1 −Lt+1 (see Fig. 2). It follows that θ ∈[θ, θ] where
θ = arccos
 rt
˜rt+1

and
θ = arcsin
 mt
˜rt+1

.
Let us define δ = ˜rt+1 −rt+1. By Definition 2 and Lemma 1, it turns out δ > 0. Moreover, one has
xt+1 =
rt −δ cos θ
≜fx(θ)
(4)
yt+1 =
mt −δ sin θ
≜fy(θ) .
(5)
Ct
mt
rt
˜rt+1
O
θ
θ
θ
Lt+1
Ct+1
rt+1
xt+1
yt+1
Fig. 2.
Sketch of proof of Lemma 2.
Let us define
M(θ) = min{fx(θ), fy(θ)}
and
R(θ) = max{fx(θ), fy(θ)}.
Then, finding bmt+1 defined in (3), boils down to
bmt+1
=
sup
θ∈[θ, θ]
min{xt+1, yt+1}
=
sup
θ∈[θ, θ]
min{fx(θ), fy(θ)} =
sup
θ∈[θ, θ]
M(θ) .
(6)
Let us analyze the case M(θ) = fx(θ), R(θ) = fy(θ). Notice that there exists at least one value of θ such
that this condition is satisfied. In fact, for θ = θ one has
M(θ)
=
fx(θ) = rt −(˜rt+1 −rt+1) cos(θ)
=
rt+1 rt
˜rt+1
< rt+1 = fy(θ) = R(θ) .
Since R(θ) = fy(θ) = rt+1, by (5), one has
rt+1 = mt −(˜rt+1 −rt+1) sin(θ)
which leads to
rt+1 = mt −˜rt+1 sin(θ)
1 −sin(θ)
.
(7)
By substituting (7) into (4), after some algebra one gets
M(θ)
=
fx(θ) = rt −(˜rt+1 −rt+1) cos(θ)
=
rt −(˜rt+1 −mt) cos(θ)
1 −sin(θ)
.
(8)
By deriving (8) w.r.t. θ one obtains
∂M(θ)
∂θ
= mt −˜rt+1
1 −sin(θ) < 0
since ˜rt+1 > rt ≥mt. Because the minimum feasible value of θ is θ and by (7), one has, under the hypothesis
M(θ) = fx(θ),
sup
θ:M(θ)=fx(θ)
M(θ) = M(θ) = rt+1 rt
˜rt+1
=
rt
˜rt+1
mt −˜rt+1 sin(θ)
1 −sin(θ)
= rt
mt −
q
˜r2
t+1 −r2
t
˜rt+1 −
q
˜r2
t+1 −r2
t
.
(9)
Let us now repeat the same reasoning for the case in which M(θ) = fy(θ). Notice that θ = θ satisfies such a
condition, yielding
M(θ)
=
fy(θ) = mt −(˜rt+1 −rt+1) sin(θ) = rt+1 mt
˜rt+1
<
rt+1 = fx(θ) = R(θ) .
Since R(θ) = fx(θ) = rt+1, by (4), one has
rt+1 = rt −(˜rt+1 −rt+1) cos(θ)
which leads to
rt+1 = rt −˜rt+1 cos(θ)
1 −cos(θ)
.
(10)
Substituting (10) into (5), after some algebra one gets
M(θ)
=
fy(θ) = rt −(˜rt+1 −rt+1) sin(θ)
=
mt −(˜rt+1 −rt) sin(θ)
1 −cos(θ)
.
(11)
By deriving (11) w.r.t. θ one obtains
∂M(θ)
∂θ
= ˜rt+1 −rt
1 −cos(θ) > 0 .
Thus,
sup
θ:M(θ)=fy(θ)
M(θ)
=
M(θ) = rt+1 mt
˜rt+1
=
mt
˜rt+1
rt −˜rt+1 cos(θ)
1 −cos(θ)
=
mt
rt −
q
˜r2
t+1 −m2
t
˜rt+1 −
q
˜r2
t+1 −m2
t
.
(12)
The result follows directly by (9) and (12).
In order to show that the MCLS leads to capture of the man in a finite number of moves, it is sufficient to prove
that the strategy leads to mt ≤1 for some finite t (recall Proposition 4). In this respect, the worst situation for
the lion is the one in which mt is maximized. Lemma 2 states that for given Ct and ˜rt+1, the lion location
Lt+1 which maximizes the smallest element of Ct+1, is one of the two points on the coordinate axes with
distance ˜rt+1 from Ct. These points correspond to the extreme angles θ and θ for the direction of Ct −Lt+1
in Fig. 2.
Lemma 3: At a given time t, let bmt+1 be defined as in (3). Then,
r∗
t ≜arg sup
rt≥mt
bmt+1 = mt
and
m∗
t+1 ≜sup
rt≥mt
bmt+1 = mt
mt −
q
˜r2
t+1 −m2
t
˜rt+1 −
q
˜r2
t+1 −m2
t
(13)
Proof: Recalling (2), let rt ≜βmt with β ≥1. We want to find
β∗= arg sup
β≥1
bmt+1 .
Let ˜rt+1 ≜γrt, γ > 1 and define p =
q
˜r2
t+1 −m2
t = mt
p
β2γ2 −1, and q =
q
˜r2
t+1 −r2
t = βmt
p
γ2 −1.
For given rt, mt and ˜rt+1, Lemma 2 states that
bmt+1 =
sup
Lt+1:∥Ct−Lt+1∥=˜rt+1
mt+1
= max
(
mt
β −
p
β2γ2 −1
βγ −
p
β2γ2 −1
, mt
1 −β
p
γ2 −1
γ −
p
γ2 −1
)
.
(14)
Let us consider the case
bmt+1 = mt
β −
p
β2γ2 −1
βγ −
p
β2γ2 −1
.
(15)
By deriving (15) w.r.t. β one obtains
∂bmt+1
∂β
=
mt

1 −
βγ2
√
β2γ2−1
 
βγ −
p
β2γ2 −1


βγ −
p
β2γ2 −1
2
−mt

β −
p
β2γ2 −1
 
γ −
βγ2
√
β2γ2−1


βγ −
p
β2γ2 −1
2
=
mt
(γ −1)
p
β2γ2 −1 −
β2γ2
√
β2γ2−1


βγ −
p
β2γ2 −1
2
=
mt(1 −γ)
p
β2γ2 −1

βγ −
p
β2γ2 −1
2 < 0 .
Since ∂bmt+1
∂β
< 0, β∗corresponds to its minimum feasible value, i.e., β∗= 1, leading to r∗
t = mt.
By following the same reasoning, for the case in which
bmt+1 = mt
1 −β
p
γ2 −1
γ −
p
γ2 −1
.
(16)
one gets again ∂bmt+1
∂β
< 0, and then r∗
t = mt. Expression (13) is obtained by direct substitution into (3).
Lemma 3 states that, for a given mt, the center Ct which (potentially) leads to the maximum mt+1 at the
subsequent step is Ct = [mt, mt]′. This is instrumental to define a bound to the evolution of mt.
Theorem 1: Let mt > 1 and let the lion play the MCLS. Then, for any possible man strategy, one has
mt+1 ≤
mt(mt −1)
p
1 + m2
t −1
.
Proof: By Lemma 2 and Lemma 3, one has
m∗
t+1
=
sup
rt≥mt
sup
Lt+1:∥Ct−Lt+1∥=˜rt+1
mt+1
=
sup
rt≥mt
bmt+1 = mt
mt −
q
˜r2
t+1 −m2
t
˜rt+1 −
q
˜r2
t+1 −m2
t
.
(17)
Let us define ˆr = ˜rt+1/mt. By substituting into (17), one has
m∗
t+1 = mt
1 −
√
ˆr2 −1
ˆr −
√
ˆr2 −1
.
(18)
By deriving m∗
t+1 w.r.t. ˆr, one has
∂m∗
t+1
∂ˆr
= mt
ˆr −1 −
√
ˆr2 −1
ˆr −
√
ˆr2 −1

2
which vanishes for ˆr = 1. It can be easily checked that ˆr = 1 corresponds to a maximum and
∂m∗
t+1
∂ˆr
< 0,
∀ˆr > 1, i.e. ∀˜rt+1 > mt. Since by (2) one has that ˜r2
t+1 ≥r2
t + 1 = m2
t + 1, the maximum value for m∗
t+1 is
achieved for ˜rt+1 =
p
m2
t + 1. By substituting in (18) one has
m∗
t+1
=
mt
mt −
p
m2
t + 1 −m2
t
p
m2
t + 1 −
p
m2
t + 1 −m2
t
=
mt
mt −1
p
m2
t + 1 −1
which concludes the proof.
A direct consequence of Theorem 1 is that MCLS leads to capture of the man in a finite number of moves.
An upper bound to such a number is now derived.
Let us consider the recursion
bt+1 =
bt(bt −1)
p
1 + b2
t −1
≜g(bt) .
(19)
Let us fix b0 = m0 > 1. Since the function g(bt) is monotone increasing for bt > 1, by Theorem 1 one has
that, if mt ≤bt, then
mt+1 ≤g(mt) ≤g(bt) = bt+1 .
Therefore, recursion (19) returns an upper bound of mt, for all t. By Proposition 4, if mt ≤1 then the game
ends at the next move. Since g(bt) < 0 when bt < 1, an upper bound to the maximum number of moves before
the game ends can be computed as follows
N MCLS
max
= min{t ∈N : bt < 0} .
Notice that N MCLS
max
is a function of m0, although it seems difficult to express this dependence explicitly.
Clearly, N MCLS
max
can be numerically computed by recursively evaluating bt in (19). In Fig. 3, N MCLS
max
and
N F CLS
max
= ⌈m2
0⌉are compared for m0 ∈[1, 10].
1
2
3
4
5
6
7
8
9
10
0
10
20
30
40
50
60
70
80
90
100
 
 
FCLS
MCLS
PSfrag replacements
m0
Upper bound on the number of moves
Fig. 3.
Upper bounds on the number of moves for different values of m0. Comparison between NF CLS
max
(blue) and MNMCLS
max
CLS
(red).
From Fig. 3 it is apparent that N MCLS
max
≤N F CLS
max
, where equality holds only for small values of m0 (due to
the discretization introduced by the fact that the number of moves must be integer). This fact is proved in the
following theorem for every m0 > 1.
Theorem 2: Let m0 > 1. Then, N MCLS
max
≤N F CLS
max
= ⌈m2
0⌉.
Proof: System (19) can be rewritten as
bt+1 = (bt −1)(
p
1 + b2
t + 1)
bt
which leads to
b2
t+1 = (bt −1)2(b2
t + 2 + 2
p
1 + b2
t)
b2
t
= b2
t −2b3
t −3b2
t + 4bt −2 −2(bt −1)2p
1 + b2
t
b2
t
.
(20)
For a given m0, let us consider the system
m2
t+1 = m2
t −1 .
(21)
Clearly, min{t ∈N : mt < 0} = ⌈m2
0⌉= N F CLS
max
. Therefore, to prove the theorem it is sufficient to show
that system (20) decays to zero always faster than (21), which amounts to show that
2b3
t −3b2
t + 4bt −2 −2(bt −1)2p
1 + b2
t
b2
t
> 1
for all bt > 1. This easily follows from standard calculus arguments.
VI. CONCLUSIONS
A new lion strategy has been devised for the discrete-time version of the lion and man problem. This solution
dominates the one proposed by Sgall in [10] in terms of maximum number of moves required to guarantee
man capture.
An interesting feature of the proposed approach is that the upper bound on the number of moves does not seem
to be tight. Indeed, for randomly chosen initial conditions of lion and man, numerical simulations show that the
actual number of steps in which the lion reaches the man turns out to be much smaller than that predicted by
the bound. Unfortunately, the optimal man strategy for counteracting the proposed lion algorithm, for generic
initial conditions, is still an open problem. It is expected that such a result would allow one to significantly
improve the upper bound on the number of moves.
We believe that the proposed result is helpful in all the contexts in which the lion and man problem solution is
used as a building block within more complex strategies for pursuit-evasion games, like in [4]. The application
of the new lion algorithm in these problems and the evaluation of its benefits is the subject of ongoing research.
REFERENCES
[1] P. J. Nahin, Chases and escapes: the mathematics of pursuit and evasion.
Princeton University Press, 2012.
[2] T. H. Chung, G. A. Hollinger, and V. Isler, “Search and pursuit-evasion in mobile robotics,” Autonomous robots, vol. 31, no. 4, pp.
299–316, 2011.
[3] J. E. Littlewood, Littlewood’s miscellany.
Cambridge University Press, 1986.
[4] V. Isler, S. Kannan, and S. Khanna, “Randomized pursuit-evasion in a polygonal environment,” IEEE Transactions on Robotics,
vol. 21, no. 5, pp. 875–884, 2005.
[5] S. D. Bopardikar, F. Bullo, and J. P. Hespanha, “On discrete-time pursuit-evasion games with sensing limitations,” IEEE Transactions
on Robotics, vol. 24, no. 6, pp. 1429–1439, 2008.
[6] D. Bhadauria, K. Klein, V. Isler, and S. Suri, “Capturing an evader in polygonal environments with obstacles: The full visibility case,”
The International Journal of Robotics Research, vol. 31, no. 10, pp. 1176–1189, 2012.
[7] B. Ames, A. Beveridge, R. Carlson, C. Djang, V. Isler, S. Ragain, and M. Savage, “A leapfrog strategy for pursuit-evasion in a
polygonal environment,” International Journal of Computational Geometry & Applications, vol. 25, no. 02, pp. 77–100, 2015.
[8] S. A. Aleem, C. Nowzari, and G. J. Pappas, “Self-triggered pursuit of a single evader,” in 2015 54th IEEE Conference on Decision
and Control (CDC), 2015, pp. 1433–1440.
[9] R. K. Guy, “Unsolved problems in combinatorial games,” in Combinatorics Advances.
Springer, 1995, pp. 161–179.
[10] J. Sgall, “Solution of David Gale’s lion and man problem,” Theoretical Computer Science, vol. 259, no. 1, pp. 663–670, 2001.
[11] N. Noori, A. Beveridge, and V. Isler, “Pursuit-evasion: A toolkit to make applications more accessible,” IEEE Robotics & Automation
Magazine, vol. 23, no. 4, pp. 138–149, 2016.
[12] N. Noori and V. Isler, “Lion and man with visibility in monotone polygons,” The International Journal of Robotics Research, vol. 33,
no. 1, pp. 155–181, 2014.