Route Planning Under Uncertainty: The Canadian Traveller Problem

Abstract

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 opti-mal policy 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 a mix of tech-niques from algorithm analysis and the theory of Markov De-cision Processes, we provide efficient exact algorithms for directed acyclic graphs and (undirected) graphs of disjoint paths from source to destination with random two-valued edge costs. We also give worst-case performance analysis and experimental data for two natural heuristics.