Abstract
In this paper, we show that the classical A.I. planning problem can be modelled using simple database constructs with logic-based semantics. The approach is similar to that used to model updates and nondeterminism in active database rules. We begin by showing that planning problems can be automatically converted to Datalog1S programs with nondeterministic choice constructs, for which we provide a formal semantics using the concept of stable models. The resulting programs are characterized by a syntactic structure (XY-stratification) that makes them amenable to efficient implementation using compilation and fixpoint computation techniques developed for deductive database systems. We first develop the approach for sequential plans, and then we illustrate its flexibility and expressiveness by formalizing a model for parallel plans, where several actions can be executed simultaneously. The characterization of parallel plans as partially ordered plans allows us to develop (parallel) versions of partially ordered plans that can often be executed faster than the original partially ordered plans.
Original language | English (US) |
---|---|
Pages (from-to) | 215-253 |
Number of pages | 39 |
Journal | Journal of Intelligent Information Systems |
Volume | 20 |
Issue number | 3 |
DOIs | |
State | Published - May 2003 |
Externally published | Yes |
Funding
The authors would like to thank the reviewers for the improvements they have suggested. This work was supported in part by the Army Research Lab under contract number DAAL0197K0135, the Army Research Office under grant number DAAD190010484, by DARPA/RL contract number F306029910552, and by the ARL CTA on Advanced Decision Architectures. This research was also supported by the National Science Foundation under grant NSF-IIS 0070135.
Keywords
- Databases and logic
- Datalog
- Nonmontonic reasoning
- Systematic planning
ASJC Scopus subject areas
- Software
- Information Systems
- Hardware and Architecture
- Computer Networks and Communications
- Artificial Intelligence