On-line Parallel Heuristics and Robot Searching under the Competitive Framework
[.ps]
[.pdf]
Abstract
In this paper we investigate parallel searches on
m concurrent rays for a point target
t located at some unknown distance along one of the rays. A group of
p agents or robots moving at unit speed searches for
t. The search succeeds when an agent reaches the point
t. Given a strategy
S the competitive ratio is the ratio of the time needed by the agents to find
t using
S and the time needed if the location of
t had been known in advance. We provide a strategy with competitive ratio of
1+2(m/p-1)(m/(m-p))^{m/p} and prove that this is optimal. This problem has applications in multiple heuristic searches in AI as well as robot motion planning. The case
p=1 is known in the literature as the cow path problem.
Bibtex Entry
