Factored Cost-Optimal Planning Using Message Passing Algorithms

Abstract : This paper proposes an approach to solve cost-optimal factored planning problems. Planning consists in organizing actions in order to reach some predefined goal. In factored planning one considers several interacting planning problems and has to design an action plan for each of them. But one must also guarantee that all these local plans are compatible: actions shared among several problems must be jointly performed or jointly rejected. We enrich the problem with the extra requirement that the global plan computed in this modular manner must also minimize the sum of all action costs. A solution is provided to this problem, based on classical message passing algorithms, known as belief propagation in the setting of Bayesian networks. Here, messages carry complex information under the form of weighted (or (min; +)) automata, and all computations are performed with these objects. At the time our first paper on this topic was published, this method was the only one to solve cost-optimal factored planning problems in a modular way. Since then, new approaches were proposed. Experiments on classical benchmarks show that it is a valuable alternative to existing methods.
Type de document :
Article dans une revue
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2015, 139 (4), 〈10.3233/FI-2015-1239〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01247346
Contributeur : Eric Fabre <>
Soumis le : lundi 21 décembre 2015 - 17:22:11
Dernière modification le : vendredi 16 novembre 2018 - 01:40:35

Identifiants

Citation

Loïg Jezequel, Eric Fabre. Factored Cost-Optimal Planning Using Message Passing Algorithms. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2015, 139 (4), 〈10.3233/FI-2015-1239〉. 〈hal-01247346〉

Partager

Métriques

Consultations de la notice

273