Exact Algorithms for the Canadian Traveller Problem on Paths and Trees
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 know...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Published: |
2008
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/40093 |
| _version_ | 1826192337554898944 |
|---|---|
| author | Karger, David Nikolova, Evdokia |
| author2 | David Karger |
| author_facet | David Karger Karger, David Nikolova, Evdokia |
| author_sort | Karger, David |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T09:10:12Z |
| id | mit-1721.1/40093 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:10:12Z |
| publishDate | 2008 |
| record_format | dspace |
| spelling | mit-1721.1/400932019-04-10T21:08:18Z Exact Algorithms for the Canadian Traveller Problem on Paths and Trees Karger, David Nikolova, Evdokia David Karger Theory of Computation Canadian Traveller, stochastic shortest path, route planning under uncertainty, path planning 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. 2008-01-29T14:15:12Z 2008-01-29T14:15:12Z 2008-01-28 MIT-CSAIL-TR-2008-004 http://hdl.handle.net/1721.1/40093 Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 14 p. application/pdf application/postscript |
| spellingShingle | Canadian Traveller, stochastic shortest path, route planning under uncertainty, path planning Karger, David Nikolova, Evdokia Exact Algorithms for the Canadian Traveller Problem on Paths and Trees |
| title | Exact Algorithms for the Canadian Traveller Problem on Paths and Trees |
| title_full | Exact Algorithms for the Canadian Traveller Problem on Paths and Trees |
| title_fullStr | Exact Algorithms for the Canadian Traveller Problem on Paths and Trees |
| title_full_unstemmed | Exact Algorithms for the Canadian Traveller Problem on Paths and Trees |
| title_short | Exact Algorithms for the Canadian Traveller Problem on Paths and Trees |
| title_sort | exact algorithms for the canadian traveller problem on paths and trees |
| topic | Canadian Traveller, stochastic shortest path, route planning under uncertainty, path planning |
| url | http://hdl.handle.net/1721.1/40093 |
| work_keys_str_mv | AT kargerdavid exactalgorithmsforthecanadiantravellerproblemonpathsandtrees AT nikolovaevdokia exactalgorithmsforthecanadiantravellerproblemonpathsandtrees |