An AO* Based Exact Algorithm for the Canadian Traveler Problem

The Canadian traveler problem (CTP) is a simple, yet challenging, stochastic optimization problem wherein an agent is given a graph where some edges are blocked with certain probabilities and the status of these edges can be disambiguated dynamically upon reaching an incident vertex. The goal is to devise a traversal policy that results in the shortest expected walk length between a given starting vertex and a termination vertex. CTP has been shown to be intractable in many broad settings. In this paper, we introduce an optimal algorithm for the problem based on a Markov decision process formulation, which is a new improvement on AO* search that takes advantage of the special problem structure in CTP. We call our algorithm CAO*, which stands for AO* with caching. CAO* uses a caching mechanism to avoid re-expansion of previously visited states and makes use of admissible upper bounds at a node level for dynamic state-space pruning. CAO* is not polynomial time, but it can dramatically shorten the execution time needed to find an exact solution for moderately sized instances. We present computational experiments on a realistic variant of the problem involving an actual maritime minefield data set.