On-line Parallel Heuristics and Robot Searching under the Competitive Framework. A. López-Ortiz and Sven Schuierer. Theoretical Computer Science, vol. 310, no.1-3, pp. 527-537, 2004. [PostScript file]

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.