Information Technology Reference
In-Depth Information
1.3 Search in Unbounded Domains
All search games that considered so far had a bounded search region. If the region
is unbounded, then the search game with an immobile hider becomes very difficult
to solve, even if the probability distribution of the hider's position is known.
1.3.1 The Linear Search Problem
Computer scientists who considered the cow path problem in the 1990s were not
aware that this problem was already being researched by mathematicians for more
than 20 years. This problem was first introduced by Bellman [ 10 ] and, indepen-
dently, by Beck [ 11 ]asthe linear search problem described as follows:
A target is located on the real line at a point H with a known probability dis-
tribution. A searcher, whose maximal velocity is 1
starts from the origin O
and wishes to discover the target in minimal expected time. It is assumed that
changing the direction of motion can be done instantaneously.
,
Much research has been carried out by Beck, e.g. [ 12 , 13 ], and others, who found
some general properties of the optimal solution and presented the optimal solution
for several interesting specific distributions. For example, Beck has showed that if
the hiding distribution is uniform, then the optimal search trajectory is to simply go
to one end and then back to the other end, but if the distribution is triangular, then
the optimal trajectory has, surprisingly, an infinite number of turning points.
The linear search problem for a general probability distribution is unsolved yet.
However, a dynamic programming algorithm can produce a solution for any discrete
distribution, [ 16 ], and also an approximate solution [ 4 ], with any desired accuracy,
for any probability distribution.
The seminal paper by Beck and Newman [ 14 ] considers the linear search problem
as a search game. Obviously, the hider's strategies have to be restricted, leading to
assuming that the expected distance from O of the hider's location is at most
λ .
The
constant
is assumed to be known to the searcher but it turns out that the optimal
search strategies do not depend on
λ
They show that the minmax search trajectory
is to double the step size each time. The doubling trajectory guarantees capture by
time 9
λ .
and 9 is the smallest constant that can be achieved by a fixed trajectory.
The optimal (mixed) search strategy uses a geometric trajectory, with the generator
g
|
H
|
g + 1
ln g ,
g u
,
where g minimizes
multiplied by a random constant c u =
,
where u is
chosen at random by the uniform distribution in the interval
[
0
,
2
) .
The n -th step
size is c u g n
.
The value of the games satisfies
v
=(
1
+
g
) λ
4
.
6
λ
so the best possible constant for mixed strategies is 4
.
6.
 
Search WWH ::




Custom Search