Several real world applications require planners that deal with non-deterministic domains and with temporally extended goals. Recent research is addressing this planning problem. However, the ability of dealing in practice with large state spaces is still an open problem. Indeed, this is one of the main obstacles to the practical applicability of planners in such a general setting. In this paper we describe a planning algorithm for extended goals that makes use of BDD-based symbolic model checking techniques. We implement the algorithm in the MBP planner, and evaluate its applicability experimentally. The results show that, in spite of the difficulty of the problem, MBP deals in practice with domains of large size and with goals of a certain complexity. In order to show the benefits of planning based on symbolic model checking w.r.t. explicit-state techniques, we compare MBP with SimPlan, one of the few planners able to deal with temporally extended goals in non-deterministic domains. Finally, we show that the algorithm for extended goals introduces a rather low overhead compared with state-of-the-art planning algorithms customized for reachability goals in non-deterministic domains.
Symbolic techniques for planning with extended goals in non-deterministic domains
Pistore, Marco;Bettin, Renato;Traverso, Paolo
2001-01-01
Abstract
Several real world applications require planners that deal with non-deterministic domains and with temporally extended goals. Recent research is addressing this planning problem. However, the ability of dealing in practice with large state spaces is still an open problem. Indeed, this is one of the main obstacles to the practical applicability of planners in such a general setting. In this paper we describe a planning algorithm for extended goals that makes use of BDD-based symbolic model checking techniques. We implement the algorithm in the MBP planner, and evaluate its applicability experimentally. The results show that, in spite of the difficulty of the problem, MBP deals in practice with domains of large size and with goals of a certain complexity. In order to show the benefits of planning based on symbolic model checking w.r.t. explicit-state techniques, we compare MBP with SimPlan, one of the few planners able to deal with temporally extended goals in non-deterministic domains. Finally, we show that the algorithm for extended goals introduces a rather low overhead compared with state-of-the-art planning algorithms customized for reachability goals in non-deterministic domains.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.