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.
Type de document :
Article dans une revue
International Journal on Artificial Intelligence Tools, World Scientific Publishing, 2007, 16 (4), pp.725-749. 〈10.1142/S0218213007003527〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00509337
Contributeur : Olivier Buffet <>
Soumis le : mercredi 11 août 2010 - 17:26:27
Dernière modification le : jeudi 11 janvier 2018 - 06:19:50

Lien texte intégral

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

262