Track: Operations Research

Abstract

The stochastic obstacle scene problem (SOSP) is a challenging probabilistic path planning problem wherein an agent needs to traverse a spatial arrangement of possible obstacles and the agent can disambiguate the actual status of the obstacles (as true or false) en route at a cost. The goal is to find a policy that decides what and where to disambiguate so as to minimize the expected length of the traversal. Traditionally, optimization algorithms for SOSP first perform a lattice discretization of the obstacle field and then consider all (discrete) disambiguation points associated with the possible obstacles. In this work, using an AO*-based exact algorithm for SOSP, we illustrate that a random sampling of a small subset of all the available disambiguation points results in significant computational savings (more than 300-fold in some cases) at the expense of only minor deviations from the optimal expected path length. Our methodology is illustrated via computational experiments involving synthetic data as well as an actual naval minefield data set.