• Jul 03, 2017 News!Good News! Since 2017, IJMLC has been indexed by Scopus!
  • Aug 15, 2017 News![CFP] 2017 the annual meeting of IJMLC Editorial Board, ACMLC 2017, will be held in Singapore, December 8-10, 2017.   [Click]
  • Jul 26, 2017 News!The papers published in Vol.7, No.1-3 have all received dois from Crossref.
Search
General Information
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