Planning graphs and propositional clause-learning

Jussi Rintanen*

*Corresponding author for this work

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

    5 Citations (Scopus)


    The planning graph of Blum and Furst is one of the frequently used tools in planning. It is a data structure which can be visualized as a bipartite graph with state variables and actions as nodes and which approximates (upper bound) the set of reachable states with a given number of sets of simultaneous actions. We show that the contents of planning graphs follow from two more general notions: extended clause learning restricted to 2-literal clauses and the representation of parallel plans consisting of STRIPS actions in the classical propositional logic. This is the first time planning graphs have been given an explanation in terms of the inference methods used in SAT solvers. The work helps in bridging the gap between specialized algorithms devised for planning and general-purpose algorithms for automated reasoning.

    Original languageEnglish
    Title of host publicationPrinciples of Knowledge Representation and Reasoning
    Subtitle of host publicationProceedings of the 11th International Conference, KR 2008
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Number of pages9
    ISBN (Print)9781577353843
    Publication statusPublished - 2008
    Event11th International Conference on Principles of Knowledge Representation and Reasoning, KR 2008 - Sydney, NSW, Australia
    Duration: 16 Sept 200819 Sept 2008

    Publication series

    NameProceedings of the International Conference on Knowledge Representation and Reasoning
    ISSN (Print)2334-1025
    ISSN (Electronic)2334-1033


    Conference11th International Conference on Principles of Knowledge Representation and Reasoning, KR 2008
    CitySydney, NSW


    Dive into the research topics of 'Planning graphs and propositional clause-learning'. Together they form a unique fingerprint.

    Cite this