An AO*Based Exact Algorithm for the Canadian Traveler Problem
Vural Aksakalli, O. Furkan Sahin, Ibrahim Ari
INFORMS Journal on Computing · 2016 · Volume 28 · Issue 1
Abstract
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.
Keywords
path planning, Canadian traveler problem, Markov decision process, AO* search
Enable JavaScript for citation tools and additional paper interactions.