Penalty-Based Algorithms for the Stochastic Obstacle Scene Problem

• Published in: INFORMS journal on computing 2014-03, Vol.26 (2), p.370-384
• Main Authors: Aksakalli, Vural, Ari, Ibrahim
• Format: Article
• Language: English
• Subjects: Algorithms; Canadian traveler's problem; Dynamic programming; Engineering research; Markov analysis; Markov decision process; Markov processes; Methods; probabilistic path planning; Probability distribution; stochastic dynamic programming; Stochastic models; Stochastic programming; Studies
• ISSN: 1091-9856; 1526-5528; 1091-9856
• DOI: 10.1287/ijoc.2013.0571

We consider the stochastic obstacle scene problem wherein an agent needs to traverse a spatial arrangement of possible obstacles, and the status of the obstacles may be disambiguated en route at a cost. The goal is to find an algorithm that decides what and where to disambiguate en route so that the expected length of the traversal is minimized. We present a polynomial-time method for a graph-theoretical version of the problem when the associated graph is restricted to parallel avenues with fixed policies within the avenues. We show how previously proposed algorithms for the continuous space version can be adapted to a discrete setting. We propose a generalized framework encompassing these algorithms that uses penalty functions to guide the navigation in real time. Within this framework, we introduce a new algorithm that provides near-optimal results within very short execution times. Our algorithms are illustrated via computational experiments involving synthetic data as well as an actual naval minefield data set. Data, as supplemental material, are available at http://dx.doi.org/10.1287/ijoc.2013.0571 .