Goal Probability Analysis in MDP Probabilistic Planning: Exploring and Enhancing the State of the Art

Abstract : Unavoidable dead-ends are common in many probabilistic planning problems, e.g. when actions may fail or when operating under resource constraints. An important objective in such settings is MaxProb, determining the maximal probability with which the goal can be reached, and a policy achieving that probability. Yet algorithms for MaxProb probabilistic planning are severely under-explored, to the extent that there is scant evidence of what the empirical state of the art actually is. We close this gap with a comprehensive empirical analysis. We design and explore a large space of heuristic search algorithms, systematizing known algorithms and contributing several new algorithm variants. We consider MaxProb, as well as weaker objectives that we baptize AtLeastProb (requiring to achieve a given goal probabilty threshold) and ApproxProb (requiring to compute the maximum goal probability up to a given accuracy). We explore both the general case where there may be 0-reward cycles, and the practically relevant special case of acyclic planning, such as planning with a limited action-cost budget. We design suitable termination criteria, search algorithm variants, dead-end pruning methods using classical planning heuristics, and node selection strategies. We design a benchmark suite comprising more than 1000 instances adapted from the IPPC, resource-constrained planning, and simulated penetration testing. Our evaluation clarifies the state of the art, characterizes the behavior of a wide range of heuristic search algorithms, and demonstrates significant benefits of our new algorithm variants.
Type de document :
Article dans une revue
Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2016, 57, pp.229 - 271. 〈http://www.jair.org/papers/paper5153.html〉. 〈10.1613/jair.5153〉
Liste complète des métadonnées

Littérature citée [72 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01413047
Contributeur : Olivier Buffet <>
Soumis le : vendredi 9 décembre 2016 - 11:44:53
Dernière modification le : jeudi 11 janvier 2018 - 06:25:24
Document(s) archivé(s) le : jeudi 23 mars 2017 - 09:45:20

Fichier

jair16b.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Marcel Steinmetz, Joerg Hoffmann, Olivier Buffet. Goal Probability Analysis in MDP Probabilistic Planning: Exploring and Enhancing the State of the Art. Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2016, 57, pp.229 - 271. 〈http://www.jair.org/papers/paper5153.html〉. 〈10.1613/jair.5153〉. 〈hal-01413047〉

Partager

Métriques

Consultations de la notice

118

Téléchargements de fichiers

51