Exact Algorithms for the Canadian Traveller Problem on Paths and Trees
Author(s)
Karger, David; Nikolova, Evdokia![Thumbnail](/bitstream/handle/1721.1/40093/MIT-CSAIL-TR-2008-004.pdf.jpg?sequence=6&isAllowed=y)
DownloadMIT-CSAIL-TR-2008-004.pdf (214.0Kb)
Additional downloads
Other Contributors
Theory of Computation
Advisor
David Karger
Metadata
Show full item recordAbstract
The Canadian Traveller problem is a stochastic shortest paths problem in which one learns the cost of an edge only when arriving at one of its endpoints. The goal is to find an adaptive policy (adjusting as one learns more edge lengths) that minimizes the expected cost of travel. The problem is known to be #P hard. Since there has been no significant progress on approximation algorithms for several decades, we have chosen to seek out special cases for which exact solutions exist, in the hope of demonstrating techniques that could lead to further progress. Applying techniques from the theory of Markov Decision Processes, we give an exact solution for graphs of parallel (undirected) paths from source to destination with random two-valued edge costs. We also offer a partial generalization to traversing perfect binary trees.
Date issued
2008-01-28Other identifiers
MIT-CSAIL-TR-2008-004
Keywords
Canadian Traveller, stochastic shortest path, route planning under uncertainty, path planning
Collections
The following license files are associated with this item: