Home > Archive > 2015 > Volume 5 Number 4 (Aug. 2015) >
IJMLC 2015 Vol. 5(4): 319-324 ISSN: 2010-3700
DOI: 10.7763/IJMLC.2015.V5.527

A Comparison of Penalty and Rollout-Based Algorithms for the Canadian Traveler Problem

O. Furkan Sahin and Vural Aksakalli

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.

General Information

  • E-ISSN: 2972-368X
  • Abbreviated Title: Int. J. Mach. Learn.
  • Frequency: Quaterly
  • DOI: 10.18178/IJML
  • Editor-in-Chief: Dr. Lin Huang
  • Executive Editor:  Ms. Cherry L. Chen
  • Abstracing/Indexing: Inspec (IET), Google Scholar, Crossref, ProQuest, Electronic Journals LibraryCNKI.
  • E-mail: ijml@ejournal.net

Article Metrics in Dimensions