Note: [*] This paper regroups results from two conference papers [13, 14], with the addition of the proofs of these results and of new material (the extensions presented in Sections 4 and 5).
Note: [†] Address for correspondence: INRIA Rennes Bretagne Atlantique, Rennes, France.
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.
Keywords: Factored planning, weighted automata, networks of automata, concurrency
