Parallel encodings of classical planning as satisfiability

Reference:

Jussi Rintanen, Keijo Heljanko, and Ilkka Niemelä. Parallel encodings of classical planning as satisfiability. In José Júlio Alferes and João Alexandre Leite, editors, Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA'04), volume 3229 of Lecture Notes in Computer Science, pages 307–319, Lisbon, Portugal, September 2004. Springer-Verlag.

Abstract:

We consider a number of semantics for plans with parallel operator application. The standard semantics used most often in earlier work requires that parallel operators are independent and can therefore be executed in any order. We consider a more relaxed definition of parallel plans, first proposed by Dimopoulos et al., as well as normal forms for parallel plans that require every operator to be executed as early as possible. We formalize the semantics of parallel plans emerging in this setting, and propose effective translations of these semantics into the propositional logic. And finally we show that one of the semantics yields an approach to classical planning that is sometimes much more efficient than the existing SAT-based planners.

Keywords:

planning, propositional logic, satisfiability testing

Suggested BibTeX entry:

@inproceedings{RinHelNie:JELIA04,
    address = {Lisbon, Portugal},
    author = {Jussi Rintanen and Keijo Heljanko and Ilkka Niemel{\"a}},
    booktitle = {Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA'04)},
    editor = {Jos{\'e} J{\'u}lio Alferes and Jo{\~a}o Alexandre Leite},
    month = {September},
    pages = {307--319},
    publisher = {Springer-Verlag},
    series = {Lecture Notes in Computer Science},
    title = {Parallel encodings of classical planning as satisfiability},
    volume = {3229},
    year = {2004},
}