Planning as satisfiability with relaxed ∃-step plans

Martin Wehrle*, Jussi Rintanen

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    30 Citations (Scopus)

    Abstract

    Planning as satisfiability is a powerful approach to solving domain independent planning problems. In this paper, we consider a relaxed semantics for plans with parallel operator application based on ∃-step semantics. Operators can be applied in parallel if there is at least one ordering in which they can be sequentially executed. Under certain conditions, we allow them to be executed simultaneously in a state s even if not all of them are applicable in s. In this case, we guarantee that they are enabled by other operators that are applied at the same time point. We formalize the semantics of parallel plans in this setting, and propose an effective translation for STRIPS problems into the propositional logic. We finally show that this relaxed semantics yields an approach to classical planning that is sometimes much more efficient than the existing SAT-based planners.

    Original languageEnglish
    Title of host publicationAI 2007
    Subtitle of host publicationAdvances in Artificial Intelligence - 20th Australian Joint Conference on Artificial Intelligence, Proceedings
    Pages244-253
    Number of pages10
    Publication statusPublished - 2007
    Event20th Australian Joint Conference on Artificial Intelligence, AI 2007 - Gold Coast, Australia
    Duration: 2 Dec 20076 Dec 2007

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume4830 LNAI
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference20th Australian Joint Conference on Artificial Intelligence, AI 2007
    Country/TerritoryAustralia
    CityGold Coast
    Period2/12/076/12/07

    Fingerprint

    Dive into the research topics of 'Planning as satisfiability with relaxed ∃-step plans'. Together they form a unique fingerprint.

    Cite this