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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11582/369
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact