A deductive database approach to A.I. planning

Antonio Brogi, V. S. Subrahmanian, Carlo Zaniolo*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 languageEnglish (US)
Pages (from-to)215-253
Number of pages39
JournalJournal of Intelligent Information Systems
Volume20
Issue number3
DOIs
StatePublished - May 2003
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'A deductive database approach to A.I. planning'. Together they form a unique fingerprint.

Cite this