Theoretical and Experimental Analysis of the Canadian Traveler Problem
  Devising an optimal strategy for navigation in a partially observable
environment is one of the key objectives in AI. One of the problem in this
context is the Canadian Traveler Problem (CTP). CTP is a navigation problem
where an agent is tasked to travel from source to target in a partially
observable weighted graph, whose edge might be blocked with a certain
probability and observing such blockage occurs only when reaching upon one of
the edges end points. The goal is to find a strategy that minimizes the
expected travel cost. The problem is known to be P$\#$ hard. In this work we
study the CTP theoretically and empirically. First, we study the Dep-CTP, a CTP
variant we introduce which assumes dependencies between the edges status. We
show that Dep-CTP is intractable, and further we analyze two of its subclasses
on disjoint paths graph. Second, we develop a general algorithm Gen-PAO that
optimally solve the CTP. Gen-PAO is capable of solving two other types of CTP
called Sensing-CTP and Expensive-Edges CTP. Since the CTP is intractable,
Gen-PAO use some pruning methods to reduce the space search for the optimal
solution. We also define some variants of Gen-PAO, compare their performance
and show some benefits of Gen-PAO over existing work.
