Akademik Veri Yönetim Sistemi
EXPERT SYSTEMS WITH APPLICATIONS, cilt.132, ss.151-165, 2019 (SCI-Expanded)
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 this algorithm in comparison to the well-known value iteration and AO* algorithms. We then investigate the relative utility and importance of the disambiguation and neutralization capabilities in order to assist decision-makers with financial constraints as well as navigation performance decisions. (C) 2019 Elsevier Ltd. All rights reserved.