Production Systems Need Negation as Failure

AAAI 1996

TL;DR

This paper introduces "negation as failure to find a course of actions" into production systems, enabling more natural and expressive modeling of real-world problems. They propose an argumentation-based framework to provide a declarative semantics for these extended systems, unifying various nonmonotonic reasoning approaches.

What Problem Does This Paper Address?

Traditional production systems, commonly used in AI for rule-based reasoning, typically rely on classical negation (e.g., "if not X then Y"). However, many real-world scenarios involve a more nuanced form of negation: "if there's no way to achieve X, then Y." For instance, a doctor might decide to amputate a limb only if there is no other way to save the patient. Representing this with classical negation is problematic because it implies a direct, observable state ("no limb") rather than the absence of a successful process or sequence of actions. This paper addresses this expressiveness gap by incorporating "negation as failure to find a course of actions" into production systems, making them more suitable for modeling complex, reactive, and commonsense reasoning scenarios.

Methods

The core contribution is the introduction of "negation as failure" (NAF) into production rules. This is formalized as not l, meaning "it is not possible to find a course of actions to achieve l." To provide a formal semantics for these extended systems, the authors leverage an argumentation-based approach. They view possible partial computations of a production system as "arguments." An argument (computation) can "attack" another if it can defeat an assumption made by that computation (specifically, if it can achieve a literal l that was assumed to be unachievable via not l). This framework allows them to define standard nonmonotonic semantics like grounded, preferred, and stable semantics for production systems. They also introduce the concept of stratified production systems, a subclass where NAF can be computed efficiently using a bottom-up operator, and where the different semantics coincide.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • "Negation as Failure to Find a Course of Actions" is Crucial: The paper convincingly demonstrates with examples (washing clothes, faculty tenure decisions, robot firefighters) that NAF is essential for naturally and accurately modeling real-world situations where the absence of a successful process is the key condition.
  • Argumentation as a Unifying Framework: The authors show that the semantics of production systems with NAF can be elegantly captured by argumentation theory. This provides a powerful, unified way to understand and define different reasoning behaviors (grounded, preferred, stable).
  • NAF as a Specification Mechanism: Even when NAF isn't directly used in the final system, it can serve as a valuable specification tool for ensuring the correctness of classical production rules.
  • Stratified Systems for Efficiency: The identification of stratified production systems is important for practical implementation, as it allows for efficient, bottom-up computation of NAF, aligning with efficient reasoning strategies.

Key Results

The paper provides a formal declarative semantics for production systems with both classical negation and negation as failure. They demonstrate that their argumentation-based approach can define grounded, preferred, and stable semantics. For stratified production systems, they prove that these three semantics coincide and can be computed efficiently via a bottom-up operator.

Limitations and Future Work

The authors acknowledge that their semantics reflect the inherent nondeterminism of production systems, where multiple complete computations can arise from the same initial state. They suggest that while their declarative semantics is a basis for reasoning about correctness, further research is needed to study computational strategies that might select a single "expected" computation in cases where determinism is desirable. They also highlight ongoing work in applying their approach to active databases and exploring the relationship between "negation as failure to find a course of actions" and "negation as failure to prove" in logic programming.

Summary updated

BibTeX
@inproceedings{1996production,
  title = {{Production Systems Need Negation as Failure}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure