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 language | English (US) |
|---|---|
| Title of host publication | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
| Publisher | Publ by ACM |
| Pages | 441-447 |
| Number of pages | 7 |
| State | Published - Jan 1 1993 |
| Event | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA Duration: Jan 25 1993 → Jan 27 1993 |
Other
| Other | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| City | Austin, TX, USA |
| Period | 1/25/93 → 1/27/93 |
ASJC Scopus subject areas
- Engineering(all)