Computer Science – Artificial Intelligence
Scientific paper
2001-12-05
Artificial Intelligence 144:157-211, 2003
Computer Science
Artificial Intelligence
48 pages, appeared as a Technical Report at KBS of the Vienna University of Technology, see http://www.kr.tuwien.ac.at/researc
Scientific paper
10.1016/S0004-3702(02)00367-3
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.
Eiter Thomas
Faber Wolfgang
Leone Nicola
Pfeifer Gerald
Polleres Axel
No associations
LandOfFree
A Logic Programming Approach to Knowledge-State Planning: Semantics and Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Logic Programming Approach to Knowledge-State Planning: Semantics and Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Logic Programming Approach to Knowledge-State Planning: Semantics and Complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-174267