Canadian Traveler Problem with Neutralizations

Yildirim, S, Aksakalli, V and Fuat Alkaya, A 2019, 'Canadian Traveler Problem with Neutralizations', Expert Systems with Applications, vol. 132, pp. 151-165.


Document type: Journal Article
Collection: Journal Articles

Title Canadian Traveler Problem with Neutralizations
Author(s) Yildirim, S
Aksakalli, V
Fuat Alkaya, A
Year 2019
Journal name Expert Systems with Applications
Volume number 132
Start page 151
End page 165
Total pages 15
Publisher Pergamon Press
Abstract The Canadian Traveler Problem (CTP) and the Obstacle Neutralization Problem (ONP) are two well-studied graph-theoretic path planning problems in the literature and both problems have been shown to be computationally intractable. In CTP, certain edges in a graph are blocked by a known probability and their status is revealed only when the traversing agent is at either end of these edges using the agent's limited disambiguation capability. The goal is to minimize the expected length of the traversal between a starting and a termination vertex by devising a policy that dictates in real-time which edge to disambiguate. In ONP, an agent needs to safely and swiftly navigate from a given source location to a destination through an arrangement of obstacles in the plane. The agent has a limited neutralization capability and uses it to safely pass through an obstacle at a cost of increased traversal length. The agent's goal is to find the sequence of obstacles to be neutralized en route which minimizes the overall traversal length subject to the agent's limited neutralization capability. Both of these problems have important and practical applications within the context of expert and intelligent systems. These include: autonomous robot navigation, adaptive transportation systems, naval and land minefield countermeasures, and navigation inside disaster areas for emergency relief operations. In this study, we consider a new path planning problem in the simultaneous presence of disambiguation and neutralization capabilities. This appears to be the first of its kind in the literature despite the close and inherent relationship between CTP and ONP. We call this problem the Canadian Traveler Problem with Neutralizations (CTPN). We present a Markov decision process formulation of CTPN and propose an optimal algorithm. This is based on an extension of the well-known AO* search algorithm. We provide computational experiments on Delaunay graphs to assess the relative performance of thi
Subject Operations Research
Keyword(s) AO* search
Autonomous navigation
Canadian traveler problem
Markov decision process
Path planning
Reinforcement learning
DOI - identifier 10.1016/j.eswa.2019.05.001
Copyright notice © 2019 Elsevier
ISSN 0957-4174
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 0 times in Scopus Article
Altmetric details:
Access Statistics: 9 Abstract Views  -  Detailed Statistics
Created: Thu, 27 Jun 2019, 10:20:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us