Back to Search Start Over

Penalty-Based Algorithms for the Stochastic Obstacle Scene Problem.

Authors :
Aksakalli, Vural
Ari, Ibrahim
Source :
INFORMS Journal on Computing. Spring2014, Vol. 26 Issue 2, p370-384. 15p.
Publication Year :
2014

Abstract

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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
10919856
Volume :
26
Issue :
2
Database :
Academic Search Index
Journal :
INFORMS Journal on Computing
Publication Type :
Academic Journal
Accession number :
99583965
Full Text :
https://doi.org/10.1287/ijoc.2013.0571