Introduction
The quest to imbuing artificial intelligence with "common sense" has long faced a fundamental trade-off between logical expressivity and computational efficiency. While classical logic provides a rigorous framework for deduction, it is notoriously brittle; a single contradiction can collapse an entire system. Human reasoning, by contrast, is inherently nonmonotonic, relying on "defaults"—rules that are generally true but subject to exceptions (e.g., "Birds fly," but "Penguins are birds that do not fly").
Presented at AAAI-91, James P. Delgrande’s research represents a significant step in making this type of reasoning computationally feasible. By integrating default reasoning into the efficient structure of Horn clause theories, Delgrande offers a method to handle exceptions without succumbing to the exponential complexity typical of general nonmonotonic systems.
The Problem: The Cost of Common Sense
In the late 1980s and early 90s, the field of nonmonotonic reasoning was dominated by powerful but computationally "hopeless" frameworks, such as Reiter’s Default Logic or McCarthy’s Circumscription. These systems were often undecidable or resided in high-complexity classes, making them impossible to implement for large-scale knowledge bases.
Conversely, Horn clause theories—a restricted subset of first-order logic—offered high efficiency, often allowing for linear-time reasoning. They served as the backbone for logic programming languages like Prolog. The central challenge Delgrande addresses is whether the power of default reasoning can be added to Horn clauses without losing these inherent computational benefits.
The Proposed Framework
Delgrande introduces a dual-layered theory consisting of two distinct types of implications:
- Strict Implications ($\alpha \supset \beta$): Standard Horn clauses representing absolute, invariant truths.
- Default Assertions ($\alpha \Rightarrow \beta$): Clauses using a new operator to represent "normally true" statements.
The innovation lies in how these defaults are processed. Rather than treating every default as a potential branching point in a search space, the system maps them to a Canonical Structure.
The Canonical Structure Construction
The reasoning process follows a structured four-step algorithm:
- Step 1: Build a Poset. The system translates default rules into a partially ordered set (poset) of formulae. This hierarchy represents different "levels of exceptionality" derived from the underlying logic.
- Step 2: Normality Assumption. When given a set of facts, the system assumes the world is as "unexceptional" as possible. It locates the "least exceptional" point in the structure that matches the current facts.
- Step 3: Maximum Applicability. It then pulls in as many default rules as possible from "nearby" points in the structure, provided they do not create a contradiction with the strict facts.
- Step 4: Standard Reasoning. Finally, it performs standard, efficient Horn clause satisfaction on the combined set of strict and "activated" default rules.
Key Insights: Specificity and Soundness
One of the most significant contributions of this approach is its handling of specificity. In many AI systems, ensuring that a more specific rule (e.g., "Penguins don't fly") overrides a general rule ("Birds fly") requires manual priority tagging. In Delgrande’s framework, this happens automatically. The "Penguin" rule is naturally situated at a more "exceptional" level than the "Bird" rule, allowing it to take precedence without ad hoc heuristics.
Furthermore, the system is grounded in a formal conditional logic ($N$). This ensures that the conclusions reached are not merely heuristic guesses but are mathematically justified and sound with respect to previous, more complex models of default reasoning.
Computational Results
The paper’s primary breakthrough is its complexity analysis. For propositional Horn default theories, the overall complexity is shown to be $O(n^2m)$, where $n$ is the number of default rules and $m$ is the total length of the formulae. This polynomial-time complexity is a massive improvement over the exponential nature of general default logics.
However, Delgrande identifies a critical boundary in tractability:
- Efficient: Finding one consistent world view (an extension) is computationally tractable.
- Intractable: "Skeptical reasoning"—determining if a fact is true in all possible valid world views—remains NP-hard.
Limitations and Future Work
While the framework is a major step forward, it has limitations. The inclusion of function symbols in the logic could lead to infinite canonical structures, potentially causing the algorithm to loop. Additionally, the author suggests that future work could involve "on-the-fly" construction of the canonical structure to handle rapidly changing knowledge bases more efficiently.
Conclusion
By constraining the logic to Horn clauses and utilizing a structured approach to defaults, Delgrande demonstrated that nonmonotonic reasoning does not always require computational ruin. This paper remains a foundational contribution for researchers seeking to balance the nuances of human-like reasoning with the practical requirements of algorithmic efficiency.
Summary updated