Knowledge-State Planning: Semantics and Complexity
Title: Knowledge-State Planning: Semantics and Complexity
Abstract: This research proposes a new declarative planning language called K, based on principles of logic programming. K allows for the representation of transitions between states of knowledge, making it well-suited for planning under incomplete knowledge. The language also supports the use of default principles in the planning process, enabling natural and compact problem representation. The paper provides a thorough analysis of K's computational complexity and discusses different planning problems, including standard planning and secure planning (also known as conformant planning). The results form the theoretical basis for the DLVK system, which implements the language on top of the DLV logic programming system.
Keywords: Answer sets, conformant planning, computational complexity, declarative planning, incomplete information, knowledge-states, secure planning
A Brief Overview of K: K is a logic programming-based language that uses knowledge states to represent transitions between states of the world. This approach allows for a more flexible and natural problem representation, particularly in cases where the initial state of the world is incomplete or uncertain. The language supports both deterministic and nondeterministic action effects, enabling it to handle a wide range of planning problems.
Contributions: The main contributions of this research are:
1. A new declarative planning language (K) based on logic programming principles. 2. A method for representing transitions between states of knowledge, which allows for more natural and compact problem representation. 3. A framework for handling incomplete and uncertain initial state information. 4. An analysis of the computational complexity of K, which shows that the language can be applied to various planning problems with different complexities.
Structure of the Paper: The paper is organized as follows:
1. Introduction: Provides an overview of the research and outlines its main contributions. 2. Language K: Describes the basic syntax, safety restriction, planning domains, and planning problems in K. It also covers the language's semantics, including typed instantiation, states and transitions, and plans. 3. Knowledge Representation in K: Discusses the use of K for deterministic planning with complete knowledge, incomplete initial state descriptions, and nondeterministic action effects. 4. Conclusion: Summarizes the research and highlights its implications for the field of declarative planning and logic programming.
Link to Article: https://arxiv.org/abs/0112006v1 Authors: arXiv ID: 0112006v1