A Logic Programming Approach to Knowledge-State Planning: Semantics and Complexity
Authors:
Preprint
Abstract
We propose a new declarative planning language, called K, which is based on principles and methods of logic programming. In this language, transitions between states of knowledge can be described, rather than transitions between completely described states of the world, which makes the language well-suited for planning under incomplete knowledge. Furthermore, it enables the use of default principles in the planning process by supporting negation as failure. Nonetheless, K also supports the representation of transitions between states of the world (i.e., states of complete knowledge) as a special case, which shows that the language is very flexible. As we demonstrate on particular examples, the use of knowledge states may allow for a natural and compact problem representation. We then provide a thorough analysis of the computational complexity of K, and consider different planning problems, including standard planning and secure planning (also known as conformant planning) problems. We show that these problems have different complexities under various restrictions, ranging from NP to NEXPTIME in the propositional case. Our results form the theoretical basis for the DLV^K system, which implements the language K on top of the DLV logic programming system.Keywords
All Related Versions
- Version 1, 2001-12-05, ArXiv
- Published version: Artificial Intelligence, 144 (1-2), 157.
This publication has 20 references indexed in Scilit:
- Polynomial-Length Planning Spans the Polynomial HierarchyLecture Notes in Computer Science, 2002
- Computational complexity of planning and approximate planning in the presence of incompletenessArtificial Intelligence, 2000
- Complexity, decidability and undecidability results for domain-independent planningArtificial Intelligence, 1995
- The computational complexity of propositional STRIPS planningArtificial Intelligence, 1994
- Representing action and change by logic programsThe Journal of Logic Programming, 1993
- On the relations between stable and well-founded semantics of logic programsTheoretical Computer Science, 1992
- Classical negation in logic programs and disjunctive databasesNew Generation Computing, 1991
- Nonmonotonic logic and temporal projectionArtificial Intelligence, 1987
- A logic-based calculus of eventsNew Generation Computing, 1986
- Strips: A new approach to the application of theorem proving to problem solvingArtificial Intelligence, 1971