• Jun 14, 2017 News!Vol.6, No.3 has been indexed by EI(Inspec)!   [Click]
  • May 03, 2016 News!Vol.5, No.5 has been indexed by EI(Inspec)!   [Click]
  • May 03, 2016 News!Vol.5, No.4 has been indexed by EI(Inspec)!   [Click]
General Information
    • ISSN: 2010-3700
    • Frequency: Bimonthly
    • DOI: 10.18178/IJMLC
    • Editor-in-Chief: Dr. Lin Huang
    • Executive Editor:  Ms. Cherry L. Chen
    • Abstracing/Indexing: Engineering & Technology Digital Library, Google Scholar, Crossref, ProQuest, Electronic Journals Library, DOAJ and EI (INSPEC, IET).
    • E-mail: ijmlc@ejournal.net
Editor-in-chief
Dr. Lin Huang
Metropolitan State University of Denver, USA
It's my honor to take on the position of editor in chief of IJMLC. We encourage authors to submit papers concerning any branch of machine learning and computing.
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).

[PDF]

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.

Copyright © 2008-2015. International Journal of Machine Learning and Computing. All rights reserved.
E-mail: ijmlc@ejournal.net