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

Ming Yang Kao*, John H. Reif, Stephen R. Tate

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

41 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherPubl by ACM
Pages441-447
Number of pages7
StatePublished - Jan 1 1993
EventProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA
Duration: Jan 25 1993Jan 27 1993

Other

OtherProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
CityAustin, TX, USA
Period1/25/931/27/93

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem'. Together they form a unique fingerprint.

Cite this