Planning as satisfiability: parallel plans and algorithms for plan search

Jussi Rintanen*, Keijo Heljanko, Ilkka Niemelä

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

173 Citations (Scopus)

Abstract

We address two aspects of constructing plans efficiently by means of satisfiability testing: efficient encoding of the problem of existence of plans of a given number t of time points in the propositional logic and strategies for finding plans, given these formulae for different values of t. For the first problem we consider three semantics for plans with parallel operator application in order to make the search for plans more efficient. The standard semantics requires that parallel operators are independent and can therefore be executed in any order. We consider a more relaxed definition of parallel plans which was first proposed by Dimopoulos et al., as well as a normal form for parallel plans that requires every operator to be executed as early as possible. We formalize the semantics of parallel plans emerging in this setting and present translations of these semantics into the propositional logic. The sizes of the translations are asymptotically optimal. Each of the semantics is constructed in such a way that there is a plan following the semantics exactly when there is a sequential plan, and moreover, the existence of a parallel plan implies the existence of a sequential plan with as many operators as in the parallel one. For the second problem we consider strategies based on testing the satisfiability of several formulae representing plans of n time steps for several values of n concurrently by several processes. We show that big efficiency gains can be obtained in comparison to the standard strategy of sequentially testing the satisfiability of formulae for an increasing number of time steps.

Original languageEnglish
Pages (from-to)1031-1080
Number of pages50
JournalArtificial Intelligence
Volume170
Issue number12-13
DOIs
Publication statusPublished - Sept 2006
Externally publishedYes

Fingerprint

Dive into the research topics of 'Planning as satisfiability: parallel plans and algorithms for plan search'. Together they form a unique fingerprint.

Cite this