Abstract—We consider the Canadian Traveler Problem
(CTP) wherein an agent needs to traverse a given graph's edges
that may or may not be blocked. The agent can observe the
actual status of an edge only upon reaching either end of the
edge. To aid its traversal, the agent is given prior blockage
probabilities associated with each edge. The goal is to devise an
algorithm that minimizes the expected traversal cost between
two given nodes. Both penalty-based and rollout-based
algorithms have been shown separately to provide high quality
policies for CTP. In this study, we compare these two
algorithmic frameworks via computational experiments
involving Delaunay and grid graphs using one specific
penalty-based algorithm and four rollout-based algorithms.
Our results indicate that the penalty-based algorithm executes
several orders of magnitude faster than rollout-based ones
while also providing better policies, suggesting that
penalty-based algorithms stand as a prominent candidate for
fast and efficient sub-optimal solution of CTP.
Index Terms—Probabilistic path planning, canadian traveler
problem, penalty-based algorithm, rollout-based algorithm.
The authors are with the Department of Industrial Engineering, Istanbul
Sehir Univ., Istanbul, 34662, Turkey (e-mail: furkansahin@std.sehir.edu.tr,
aksakalli@sehir.edu.tr).
Cite: O. Furkan Sahin and Vural Aksakalli, "A Comparison of Penalty and Rollout-Based Algorithms for the Canadian Traveler Problem," International Journal of Machine Learning and Computing vol. 5, no. 4, pp. 319-324, 2015.