A Demand-Driven Algorithm for Generating Minimal Models

AAAI 2000

TL;DR

This paper introduces a novel algorithm, ALL-MINIMAL (AAM), that efficiently generates minimal models for knowledge bases by exploiting a hierarchical structure called the super dependency graph. This demand-driven approach allows models to be generated one at a time, offering significant advantages for applications like diagnosis and query answering.

What Problem Does This Paper Address?

Computing minimal models of a knowledge base is a fundamental problem in artificial intelligence, crucial for systems like truth maintenance, autoepistemic logic, and diagnosis. Unfortunately, this task is computationally expensive, being NP-hard in general. Existing approaches often struggle with efficiency, especially when dealing with large or complex knowledge bases. The paper aims to address this by providing a more efficient and structured method for generating minimal models, particularly by enabling incremental generation.

Methods

The core of the paper is the ALL-MINIMAL (AAM) algorithm, which leverages a "super dependency graph" (GT) derived from the knowledge base. This graph organizes the knowledge base into strongly connected components (SCCs). AAM traverses this graph from the "bottom up" (sources to sinks), computing minimal models for subproblems associated with each node.

Key algorithmic components include:

  • Dependency Graph Construction: Atoms are grouped into equivalence sets, and a dependency graph is built with nodes representing these sets (ES-nodes) and rules (R-nodes).
  • Super Dependency Graph (GT): This graph is formed by collapsing SCCs of the dependency graph into single nodes, resulting in an acyclic structure.
  • Bottom-Up Traversal: The algorithm processes nodes in GT from sources upwards. For each node s, it combines minimal models from its children (Mc(s)) and then computes minimal models for the local knowledge base (Ts) augmented by these combined models.
  • Demand-Driven Generation: The algorithm is designed to generate models one at a time. This is achieved through the CartesProd procedure, which computes the consistent portion of the Cartesian product of sets of models, and the Convert procedure, which transforms the knowledge base based on a partial model.
  • Hierarchy of Knowledge Bases (Ψk): The paper proposes a hierarchy of knowledge base classes, where Ψk contains knowledge bases with at most k minimal models that can be found efficiently. This hierarchy is directly related to the structure of the super dependency graph.

The paper also extends this approach to first-order logic with the FIRST-ALL-MINIMAL (FAAM) algorithm, which operates on the grounded version of the knowledge base.

Datasets

Not discussed in the paper. The paper focuses on algorithmic development and theoretical analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Exploiting Structure for Efficiency: The super dependency graph provides a crucial structural decomposition of the knowledge base, allowing for a more efficient, modular computation of minimal models.
  • Demand-Driven Generation is Practical: The ability to generate minimal models one at a time is a significant practical advantage for applications where not all models are needed simultaneously, such as in interactive diagnosis or query answering.
  • Hierarchy of Tractability: The proposed hierarchy of knowledge base classes (Ψk) offers a theoretical framework for understanding when minimal model computation is tractable, directly linking complexity to the structure of the knowledge base.
  • Modularity for Updates: The modular nature of the algorithm means that if the knowledge base changes, computation can often be resumed from affected nodes in the super dependency graph, rather than restarting from scratch.

Key Results

  • The paper presents a correct algorithm (AAM) for generating all minimal models of a propositional knowledge base.
  • It introduces a hierarchy of knowledge base classes (Ψk) where membership in Ψk implies at most k minimal models, computable in O(lnk) time.
  • The algorithm can determine the minimum j such that a knowledge base belongs to Ψj in polynomial time.
  • The algorithm is demand-driven, capable of generating models one at a time.
  • A generalization to first-order logic (FAAM) is also presented.

Limitations and Future Work

  • Worst-Case Complexity: While the algorithm offers improvements, the worst-case complexity for finding all minimal models can still be exponential, especially for non-Horn knowledge bases.
  • Intermediate Models: The paper acknowledges that some partial models generated during the computation might be discarded later if they cannot be extended to a full minimal model (illustrated by Example 3.5). However, it notes that in the absence of integrity constraints, generated minimal models are part of the overall minimal models.
  • Distributed Implementation: The authors suggest that the modular nature of the algorithm makes it suitable for distributed implementation, an area they leave for future work.
  • Comparison with Existing Work: While the paper claims advantages over some prior work (e.g., producing only minimal models, not supersets), a comprehensive empirical comparison is omitted due to space constraints.

Summary updated

BibTeX
@inproceedings{2000demand,
  title = {{A Demand-Driven Algorithm for Generating Minimal Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2000},
}
Figure