Skip to Main content Skip to Navigation
Journal articles

Reachability Analysis for Uncertain SSPs

Olivier Buffet 1, 2 
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Stochastic Shortest Path problems (SSPs) can be efficiently dealt with by the Real-Time Dynamic Programming algorithm (RTDP). Yet, RTDP requires that a goal state is always reachable. This article presents an algorithm checking for goal reachability, especially in the complex case of an uncertain SSP where only a possible interval is known for each transition probability. This gives an analysis method for determining if SSP algorithms such as RTDP are applicable, even if the exact model is not known. As this is a time-consuming algorithm, we also present a simple process that often speeds it up dramatically. Yet, the main improvement still needed is to turn to a symbolic analysis in order to avoid a complete state-space enumeration.
Document type :
Journal articles
Complete list of metadata
Contributor : Olivier Buffet Connect in order to contact the contributor
Submitted on : Wednesday, August 11, 2010 - 5:26:27 PM
Last modification on : Saturday, June 25, 2022 - 7:41:51 PM




Olivier Buffet. Reachability Analysis for Uncertain SSPs. International Journal on Artificial Intelligence Tools, World Scientific Publishing, 2007, 16 (4), pp.725-749. ⟨10.1142/S0218213007003527⟩. ⟨inria-00509337⟩



Record views