On-line Parallel Heuristics and Robot Searching under the Competitive Framework. A. López-Ortiz and S. Schuierer. In Proceedings of Scandinavian Workshop on Algorithm Theory, (SWAT), 2002. 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.