TY - JOUR

T1 - Searching in an Unknown Environment

T2 - An Optimal Randomized Algorithm for the Cow-Path Problem

AU - Kao, Ming Yang

AU - Reif, John H.

AU - Tate, Stephen R.

N1 - Funding Information:
* Supported in part by NSF Grant CCR-9101385. -Supported in part by DARPA ISTO Contracts N00014-88-K-0458 and N00014-91-J-1985, NASA Subcontract 550-63 of Prime Contract NAS5-30428, U.S. Israel Binational NSF Grant 88-00282 2, and U.S. Israel Binational NSF Grant 88-00282 2. Supported in part by NSF Grant CCR-9409945.

PY - 1996/11/25

Y1 - 1996/11/25

N2 - Searching for a goal is a central and extensively studied problem in computer science. In classical searching problems, the cost of a search function is simply the number of queries made to an oracle that knows the position of the goal. In many robotics problems, as well as in problems from other areas, we want to charge a cost proportional to the distance between queries (e.g., the time required to travel between two query points). With this cost function in mind, the abstract problem known as the w-lane cow-path problem was designed. There are known optimal deterministic algorithms for the cow-path problem; we give the first randomized algorithm in this paper. We show that our algorithm is optimal for two paths (w = 2) and give evidence that it is optimal for larger values of w. Subsequent to the preliminary version of this paper, Kao et al. (in "Proceedings, 5th ACM-SIAM Symposium on Discrete Algorithm," pp. 372-381, 1994) have shown that our algorithm is indeed optimal for all w≥2. Our randomized algorithm gives expected performance that is almost twice as good as is possible with a deterministic algorithm. For the performance of our algorithm, we also derive the asymptotic growth with respect to w - despite similar complexity results for related problems, it appears that this growth has never been analyzed.

AB - Searching for a goal is a central and extensively studied problem in computer science. In classical searching problems, the cost of a search function is simply the number of queries made to an oracle that knows the position of the goal. In many robotics problems, as well as in problems from other areas, we want to charge a cost proportional to the distance between queries (e.g., the time required to travel between two query points). With this cost function in mind, the abstract problem known as the w-lane cow-path problem was designed. There are known optimal deterministic algorithms for the cow-path problem; we give the first randomized algorithm in this paper. We show that our algorithm is optimal for two paths (w = 2) and give evidence that it is optimal for larger values of w. Subsequent to the preliminary version of this paper, Kao et al. (in "Proceedings, 5th ACM-SIAM Symposium on Discrete Algorithm," pp. 372-381, 1994) have shown that our algorithm is indeed optimal for all w≥2. Our randomized algorithm gives expected performance that is almost twice as good as is possible with a deterministic algorithm. For the performance of our algorithm, we also derive the asymptotic growth with respect to w - despite similar complexity results for related problems, it appears that this growth has never been analyzed.

UR - http://www.scopus.com/inward/record.url?scp=0004512767&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0004512767&partnerID=8YFLogxK

U2 - 10.1006/inco.1996.0092

DO - 10.1006/inco.1996.0092

M3 - Article

AN - SCOPUS:0004512767

SN - 0890-5401

VL - 131

SP - 63

EP - 79

JO - Information and Computation

JF - Information and Computation

IS - 1

ER -