Reaching a Target in the Plane with no Information

arXiv:1710.07145v1 [cs.DS] 19 Oct 2017

Andrzej Pelc∗

Abstract
A mobile agent has to reach a target in the Euclidean plane. Both the agent and the target
are modeled as points. At the beginning, the agent is at distance at most D > 0 from the target.
Reaching the target means that the agent gets at a sensing distance at most r > 0 from it. The
agent has a measure of length and a compass. We consider two scenarios: in the static scenario
the target is inert, and in the dynamic scenario it may move arbitrarily at any (possibly varying)
speed bounded by v. The agent has no information about the parameters of the problem, in
particular it does not know D, r or v. The goal is to reach the target at lowest possible cost,
measured by the total length of the trajectory of the agent.
Our main result is establishing the minimum cost (up to multiplicative constants) of reaching
the target under both scenarios, and providing the optimal algorithm for the agent. For the
static scenario the minimum cost is Θ((log D + log r1 )D2 /r), and for the dynamic scenario it is
Θ((log M + log 1r )M 2 /r), where M = max(D, v). Under the latter scenario, the speed of the
agent in our algorithm grows exponentially with time, and we prove that for an agent whose
speed grows only polynomially with time, this cost is impossible to achieve.
Keywords: exploration, algorithm, mobile agent, speed, cost, plane.

∗
Département d’informatique, Université du Québec en Outaouais, Gatineau, Québec J8X 3X7, Canada. E-mail:
pelc@uqo.ca. Supported in part by NSERC discovery grant 8136 – 2013 and by the Research Chair in Distributed
Computing of the Université du Québec en Outaouais.

1

Introduction

The background and the problem. Finding a target hidden in various environments is a task
extensively studied in the literature. When the target is inert, this task is often called treasure
hunt, and when it can move, it is called pursuit. In the latter case, the target is sometimes called
the robber and the mobile agents chasing it are called cops.
The novelty of our formulation of this old problem is twofold. The environment is very simple,
it is the Euclidean plane, and the mobile agent that has to find the target has no information
whatsoever about the parameters of the problem. We ask what is the minimum cost, measured by
the total length of the trajectory of the agent to reach the target under this complete ignorance.
There is one mobile agent and the target, both modeled as points. At the beginning, the agent is
at distance at most D > 0 from the target. Reaching the target means that the agent gets at a
sensing distance at most r > 0 from it. When this happens, we say that the agent senses the target.
The agent has a measure of length and a compass showing the cardinal directions. We consider
two scenarios: in the static scenario the target is inert, and in the dynamic scenario it may move
arbitrarily at any (possibly varying) speed bounded by v. The agent has no information about the
parameters of the problem, in particular it does not know D, r or v. This total ignorance may
occur in many applications. If the target is a lost object, its position and even its distance from
the agent may be unknown. If it is a hostile agent able to move, the chasing agent may not know
any bound on its speed. Finally, the sensing distance at which the mobile agent can locate the
target may also be unknown because it may depend on factors impossible to control. For example,
if sensing is visual, the parameter r may depend on the unknown density of the fog, and if it is
chemical, it may depend on the unknown strength of the scent emitted by the target.
Our results. Our main result is establishing the minimum cost (up to multiplicative constants)
of reaching the target under both scenarios, and providing the optimal algorithm for the agent.
For the static scenario the minimum cost is Θ((log D + log 1r )D 2 /r), and for the dynamic scenario
it is Θ((log M + log 1r )M 2 /r), where M = max(D, v). Under the latter scenario, the speed of the
chasing agent in our algorithm grows exponentially with time, and we prove that for a chasing
agent whose speed grows only polynomially with time, this cost is impossible to achieve.
Related work. The problem of searching for a target by one or more mobile agents is an extensively
studied task that was investigated under many different scenarios. The environment where the
target is hidden may be a graph or a plane, the search may be deterministic or randomized, and
the target may be inert or mobile. The book [1] surveys both the search for a fixed target and
the related rendezvous problem, where the target and the finder are both mobile and their role is
symmetric: they both cooperate to meet. This book is concerned mostly with randomized search
strategies. In [9, 11] the authors study relations between the problems of treasure hunt (searching
for a fixed target) and rendezvous in graphs. By contrast, the survey [4] and the book [3] consider
pursuit-evasion games, mostly on graphs, where pursuers try to catch a fugitive trying to escape.
The authors of [2] studied the task of finding a fixed point on the line and in the grid, and initiated
the study of the task of searching for an unknown line in the plane. This research was continued,

1

e.g., in [6, 8]. In [10] the authors concentrated on game-theoretic aspects of the situation where
multiple selfish pursuers compete to find a target, e.g., in a ring. The main result of [7] is an optimal
algorithm to sweep a plane in order to locate an unknown fixed target, where locating means to
get the agent originating at point O to a point P such that the target is in the segment OP . In
[5] the authors consider the generalization of the search problem in the plane to the case of several
searchers. To the best of our knowledge, the problem of efficient search for a fixed or a moving
target in the plane, under complete ignorance of the searching agent, has never been studied before.

2

The static scenario

In this section we assume that the target is inert. Our algorithms produce a trajectory of the
mobile agent which is a polygonal line whose segments are parallel to the cardinal directions. For
any positive real x, the instruction (N, x) (resp. (E, x), (S, x) , and (W, x)) has the meaning “go
North (resp. East, South, and West) at distance x”. Juxtaposition is used for concatenation of
trajectories, and T denotes the trajectory reverse with respect to trajectory T . For any positive
real y, let Q(y) denote the square with side y centered at the starting point of the mobile agent.
For any positve integers k and j, the spiral S(k, j) is the trajectory resulting from the following
sequence of instructions: (E, 2−j ), (S, 2−j ), (W, 2·2−j ), (N, 2·2−j ), (E, 3·2−j ), (S, 3·2−j ), (W, 4·2−j ),
(N, 4 · 2−j ), ..., (E, (2k + 1) · 2−j ), (S, (2k + 1) · 2−j ), (W, (2k + 2) · 2−j ), (N, (2k + 2) · 2−j ). Note
that, during the traversal of the spiral S(k, j), the mobile agent gets at distance less than 2−j from
every point of the square Q(2k · 2−j ). Denote by Π(k, j) the trajectory S(k, j)S(k, j).
Consider the infinite matrix A whose rows are numbered by consecutive positive integers and
whose columns are numbered by consecutive positive even integers. The term A(i, j) in row i and
column j is the trajectory Π(2i+j , j). For any positive integer i, denote by ∆[i] the concatenation
Π(2i+2 , 2)Π(2i+3 , 4), . . . Π(21+2i , 2i) of trajectories in the ith diagonal of the matrix.
Now the algorithm can be succinctly formulated as follows.
Algorithm Static
Follow the trajectory ∆[1]∆[2]∆[3] . . . until sensing the target.
Theorem 2.1. The cost of Algorithm Static is O((log D + log 1r )D 2 /r), where D is an upper
bound on the initial distance of the agent from the target and r is the sensing distance.
Proof. Let a = ⌈log D⌉ and let b be the smallest even integer greater or equal to ⌈log 1r ⌉. Thus
b ≤ ⌈log 1r ⌉ + 1. The term A(i, j) of the matrix A is in the (i + 2j − 1)th diagonal. During the
traversal of the spiral S(2a+b , b) the agent reaches the target. Hence it reaches the target while
following the trajectory ∆[a + 2b − 1].
The length of Π(k, j) is 4(1 + 2 + · · · + (2k + 2))2−j = 2(2k + 2)(2k + 3)2−j ≤ 40k2 2−j . Hence the
length of the trajectory ∆[i] is at most 40i22i+2 . The cost of the algorithm is at most the sum of
lengths of trajectories ∆[1], ∆[2], ..., ∆[a + 2b − 1], which is at most 80i22i+2 , where i = a + 2b − 1.
2

This is O((log D + log 1r )D 2 /r).
The following result shows that Algorithm Static has cost optimal up to multiplicative constants.
Theorem 2.2. The cost of any algorithm for reaching a fixed target, with unknown bound D on
1
the initial distance and unknown sensing distance r, is at least 16
((log D + log 1r )D 2 /r), for some
couple of parameters D and r, for which this value is arbitrarily large.
Proof. First observe that the cost of reaching a target in any polygon of area P , with sensing
distance r, is at least (P − πr 2 )/(2r) because for any trajectory of length x, the set of points that
are at distance at most r from some point of the trajectory has area at most 2rx + πr 2 .
For any positive integer i, consider couples of integers (Dj , rj ), where Dj = 2j and rj = 2−2(i−j+1) ,
for j = 1, 2, . . . , i. Denote R1 = Q(2) and Rk = Q(2k ) \ Q(2k−1 ), for k > 1. The area of the
polygon Rj is larger than Dj2 /2, and all points of it are at distance smaller than Dj from the origin
of the mobile agent. Suppose that the target is hidden in polygon Rj , with sensing distance rj ,
where j = 1, 2, . . . , i. Hence the cost of any algorithm for reaching the target in Rj is at least
Dj2
4rj

πr

D2

− 2 j ≥ 8rjj = 12 22i . Since polygons Rj are pairwise disjoint, the cost of any algorithm for
reaching the target in every polygon Rj , with sensing distance rj , is at least
2

2

Dj
1 2i 1
1
1
1 Dj
1
i2 = (log Dj + log − 1)
≥
(log Dj + log )
.
2
8
2
rj
rj
16
rj rj

3

The dynamic scenario

In this section we consider the scenario of a target moving arbitrarily at possibly varying speed
bounded by some constant v. Neither the bound D on the initial distance to the target, nor the
sensing distance r, nor the bound v on the speed of the target are known to the mobile agent.
The proposed algorithm is a simple modification of Algorithm Static that specifies the speeds at
which the mobile agent traverses the consecutive diagonals.
Algorithm Dynamic
Follow the trajectory ∆[1]∆[2]∆[3] . . . , using speed 25i on trajectory ∆[i], until sensing the target.
Theorem 3.1. The cost of Algorithm Dynamic is O((log M + log 1r )M 2 /r), where M = max(D, v),
D is an upper bound on the initial distance of the agent from the target, v is an upper bound on
the speed of the moving target, and r is the sensing distance.
Proof. As calculated in the proof of Theorem 2.1, the length of the trajectory ∆[i] is at most
40i22i+2 . Hence it is at most 23i , for i ≥ 11. Since the trajectory ∆[i] is traversed by the agent at

3

speed 25i , it follows that the time ti of traversing ∆[i] is at most 2−2i , for i ≥ 11, and consequently
the total time of traversing all trajectories ∆[i] is bounded by some constant q.
Let a = ⌈log D⌉ and let b be the smallest even integer greater or equal to ⌈log 1r ⌉. Thus b ≤
⌈log 1r ⌉ + 1. Let c = ⌈qv⌉. Let D ′ = D + qv. This is the maximum distance from the starting point
′
of the mobile agent that the target can get. Let a′ = max(a, c) + 1. Hence D ′ ≤ 2a . The term
A(a′ , b) is in the yth diagonal of the matrix A, where y = a′ + 2b − 1. If ty ≤ v·21b+1 , then the target
is reached by the time the agent traverses the trajectory ∆y . Indeed, if this inequality is satisfied,
′
1
, and
the agent traverses the spiral S(2a +b , b) faster than the target can traverse the distance 2b+1
hence it must get at distance at most r from the target during the traversal of this spiral. Since
1
2y ≥ b + c, we get ty ≤ 212y ≤ 2b+c
≤ v·21b+1 , for y ≥ 11.
If y ≤ 10 then the cost of the algorithm is O(1), hence we may assume y ≥ 11. In this case the cost
of the algorithm is at most the sum of lengths of trajectories ∆[1], ∆[2], ..., ∆[a′ + 2b − 1], which is
at most 80y22y+2 , where y = a′ + 2b − 1. This is O((log M + log 1r )M 2 /r).
The following result shows that Algorithm Dynamic has cost optimal up to multiplicative constants,
if the adversary can choose the parameters D, r and v.
Theorem 3.2. The cost of any algorithm for reaching a moving target, with unknown bound D
on the initial distance, unknown bound v on the speed of the target, and unknown sensing distance
r, is at least c((log M + log 1r )M 2 /r), where c is some positive constant and M = max(D, v), for
some triple of parameters D, v and r, for which this value is arbitrarily large.
Proof. If D ≥ v, then the theorem follows immediately from Theorem 2.2, with the target choosing
speed 0 ≤ v, i.e., being inert. Hence we may assume that v > D. It is enough to show the lower
bound c((log v + log 1r )v 2 /r) on the cost of any algorithm for reaching the target, for some constant
c > 0, when the initial distance is D = 1. Let O be the starting point of the mobile agent and let P
be the starting point of the moving target. Let S(O, x) denote the disc of radius x centered at O.
Consider any algorithm for the mobile agent, with speed f (t) at time t. Let t0 be the constant
Rt
for which 0 0 f (t)dt = 12 . During the time interval [0, t0 ] the mobile agent must be inside the disc
S(O, 21 ). Suppose that, during the time interval [0, t0 ], the target moves at speed at most v on the
line OP away from the point O. Since the point P can be anywhere at distance 1 from O, it follows
that at time t0 the target can be at any point of the set S(O, 1 + vt0 ) \ S(O, 1). In particular, it can
be at any point Q of a square Z of size 12 vt0 contained in this set. From time t0 on, the adversary
keeps the target inert at point Q. Thus the cost of the algorithm is at least the cost of the best
algorithm in the static scenario, where the inert target is in Z.
Since the area of the square Z is

t20 2
4v ,

by a similar argument as in the proof of the Theorem 2.2, we

t20
128 ((log v

+ log 1r )v 2 /r), for some sensing distance r and some bound
get that this cost is at least
v on the speed of the target that make this value arbitrarily large.
While Algorithm Dynamic has been proved to have cost optimal up to multiplicative constants, its
downside is the fact that the speed of the mobile agent grows exponentially with time. Hence it is
4

natural to ask if the same cost can be achieved with the speed of the mobile agent growing only
polynomially. Our final result shows that this is impossible.
Theorem 3.3. There does not exist an algorithm for reaching a moving target at cost optimal up
to multiplicative constants, with the speed of the mobile agent growing polynomially in time.
Proof. Let O be the starting point of the mobile agent and let P be the starting point of the
moving target. Suppose that the distance between O and P is D = 1 and that the target moves at
speed at most v ≥ 1 on the line OP away from the point O. Let S(O, x) denote the disc of radius
x centered at O. Suppose that there exists an algorithm for reaching the target at cost at most
C(v, r) = d((log v + log 1r )v 2 /r), for some constant d > 0, where r is the sensing distance, and the
mobile agent moves at speed at most tc at time t, for some positive integer constant c.
Let t be the earliest time at which the agent reaches the target. At this time the target can
be anywhere in the set Z = S(O, 1 + vt) \ S(O, 1), and the trajectory of the agent has length
Rt
c+1
at most 0 tc dt = tc+1 . Since the area of the set Z is π(1 + vt)2 − π > π(vt)2 , we must have

2
π(vt)2 −πr 2
> (vt)
2r
2r , for sufficiently large v and sufficiently small r. Thus we must have
1
2
2
> v2r , which implies t > ( (c+1)v
) c−1 . It follows that the cost of the algorithm at time t is
2r
c+1
2
1 (c+1)v2 c−1
larger than c+1
( 2r ) , which is α( vr )β , for some constants α > 0 and β > 1. However, we
2
2
2
have C(v, r) = d((log v + log 1r )v 2 /r) ≤ d(log vr ) vr < α( vr )β , for sufficiently large v and sufficiently

tc+1
c+1
tc−1
c+1

≥

small r, which is a contradiction.

4

Conclusion

We established the optimal cost (up to multiplicative constants) of reaching a target in the plane
by a mobile agent ignorant of the parameters of the problem, which are a bound D on the initial
distance from the target, the sensing distance r, and a bound v on the speed of the target.
Our assumption about the target was that it moves at a bounded (although possibly varying) speed,
and our assumption about the mobile agent was that it has a compass and a measure of length. Is
it possible to weaken or eliminate these assumptions? Notice that without any assumption on the
speed of the target, the adversary could assign it the same speed as that of the agent at all times
(which is possible if the agent does not know anything about the speed of the target) and make it
go away from the agent, (on the extension of the segment between the initial positions of the agent
and of the target) which clearly precludes reaching the target. As for the assumption about the
capabilities of the agent, having a measure of distance seems necessary, as otherwise no meaningful
algorithm to move in the plane can be formulated. On the other hand, the availability of a compass
could be removed. In our algorithms the only needed features are the possibility of going straight
at some chosen distance in a chosen direction, and forming right angles in the plane. Thus, e.g.,
an arbitrarily distorted compass with a fixed distortion, e.g., always showing South-East as North,
would be sufficient. In fact, since drawing right angles is possible with an available measure of
distance, no compass is needed, as long as the agent has the ability of going straight (which is
5

difficult in dense fog, but easy on a clear day on the snow).

References
[1] S.Alpern and S.Gal, The Theory of Search Games and Rendezvous, Kluwer Academic Publications, 2003.
[2] R. Baeza-Yates, J. Culberson, and J. Rawlins, Searching the plane, Information and Computation 106 (1993), 234252.
[3] A. Bonato and R.J. Nowakowski, The Game of Cops and Robbers on Graphs, American
Mathematical Society, 2011.
[4] T.H. Chung, G.A. Hollinger and V. Isler, Search and pursuit-evasion in mobile robotics: A
survey, Auton. Robot 31 (2011), 299316.
[5] G. M. Fricke, J. P. Hecker, A. D. Griego, L. T. Tran and Melanie E. Moses, A Distributed
Deterministic Spiral Search Algorithm for Swarms, Proc. IEEE/RSJ International Conference
on Intelligent Robots and Systems (IROS 2016), 4430-4436.
[6] A. Jez and J. Lopuszanski, On the two-dimensional cow search problem, Information Processing Letters 109 (2009), 543 - 547.
[7] E. Langetepe, On the Optimality of Spiral Search, Proc. 21st Ann. ACM-SIAM Symp. Disc.
Algor. (SODA 2010), 112.
[8] E. Langetepe, Searching for an axis-parallel shoreline, Theoretical Computer Science 447
(2012), 85-99.
[9] A. Miller, A. Pelc, Tradeoffs between cost and information for rendezvous and treasure hunt,
Journal of Parallel and Distributed Computing 83 (2015), 159-167.
[10] K. Spieser and E. Frazzoli, The Cow-Path Game: A Competitive Vehicle Routing Problem,
Proc. 51st IEEE Conference on Decision and Control (2012), 6513 - 6520.
[11] A. Ta-Shma and U. Zwick, Deterministic rendezvous, treasure hunts and strongly universal
exploration sequences. ACM Transactions on Algorithms 10 (2014), 12:1-12:15.

6

