Skip to main content

Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem

Publication ,  Journal Article
Kao, MY; Reif, JH; Tate, SR
Published in: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
January 1, 1993

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, and we give the first randomized algorithms in this paper. We show that our algorithm is optimal for two paths (w = 2), and give evidence that it is indeed optimal for larger values of w. The randomized algorithms give expected performance that is almost twice as good as is possible with a deterministic algorithm.

Duke Scholars

Published In

Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms

Publication Date

January 1, 1993

Start / End Page

441 / 447
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Kao, M. Y., Reif, J. H., & Tate, S. R. (1993). Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 441–447.
Kao, M. Y., J. H. Reif, and S. R. Tate. “Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem.” Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, January 1, 1993, 441–47.
Kao MY, Reif JH, Tate SR. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. 1993 Jan 1;441–7.
Kao, M. Y., et al. “Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem.” Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Jan. 1993, pp. 441–47.
Kao MY, Reif JH, Tate SR. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. 1993 Jan 1;441–447.

Published In

Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms

Publication Date

January 1, 1993

Start / End Page

441 / 447