Tweety - Still Flying: Some Remarks on Abnormal Birds Applicable Rules and a Default Prover

Gerhard BrewkaAAAI 1986

TL;DR

This paper introduces FAULTY, a default reasoning system that tackles the semi-decidability issues of existing nonmonotonic logics by restricting them to decidable subsets of first-order logic, specifically Horn clauses. FAULTY offers a practical approach to default reasoning by allowing explicit control over default applicability, thus avoiding problematic "odd loops" and enabling more robust inference.

What Problem Does This Paper Address?

Nonmonotonic reasoning is crucial for AI systems that need to reason with incomplete information and make default assumptions (e.g., "birds typically fly"). However, prominent formalisms like McDermott and Doyle's Nonmonotonic Logic I (NML I) and Reiter's Default Logic suffer from a lack of semi-decidability. This means that determining whether a statement is provable can depend on proving that other statements are unprovable, leading to computational intractability. Truth Maintenance Systems (TMS) offer an alternative by focusing on "believability" rather than strict provability, but they can exhibit unstable behavior, like changing a formula's status without new information, and struggle with "odd loops" where a belief depends on its own disbelief. The authors aim to bridge this gap by creating a system that is both computationally tractable and capable of robust default reasoning.

Methods

FAULTY is built upon McDermott and Doyle's Nonmonotonic Logic I (NML I) but with crucial restrictions to ensure decidability. The core innovation lies in how defaults are represented and managed:

  • Restricted NML I: The modal operator 'M' (representing consistency) is only allowed within default rules and not in general statements. This prevents the logic from being used to make direct claims about consistency, thus avoiding the weaknesses of NML I in that regard.
  • Explicit Default Applicability: Defaults are augmented with a special predicate APPL (e.g., M APPL(R1,x) & ADULT(x) & M MARRIED(x)) -> MARRIED(x)). This allows users to explicitly control when a default rule should be applied.
  • Blocking Defaults: By stating that a default is not applicable (e.g., STUDENT(x) -> -APPL(R1,x)), FAULTY can prevent unwanted inferences and resolve conflicts between defaults. This is analogous to McCarthy's "abnormal" predicate but integrated directly into the logic.
  • Proof Procedure: FAULTY employs a proof procedure that involves standard resolution refutation. When a conflict arises (an "M-clause" is derived), it initiates sub-proofs to check the consistency of the negated literals. If these sub-proofs fail, the corresponding literals can be assumed consistent and added to the main proof.

Datasets

Not discussed in the paper. The examples provided are illustrative knowledge bases created by the authors.

Key Insights and Ideas

  • Decidability through Restriction: The paper convincingly argues that restricting nonmonotonic logics to decidable fragments of FOL (like Horn clauses) is a viable path to achieving tractability without sacrificing the core functionality of default reasoning.
  • Controlling Defaults is Key: The explicit mechanism for blocking default applicability is a significant contribution. It provides a clear and intuitive way to handle interacting defaults, resolving conflicts by simply stating which defaults should not apply in specific situations. This is more direct than the implicit minimization in circumscription.
  • NML I's Strength in Restriction: While NML I has known weaknesses for general consistency reasoning, the authors demonstrate that these weaknesses are mitigated when 'M' is confined to default rules, making it suitable for FAULTY's purpose.
  • Fixed Points and Agnosticism: The paper discusses the choice between taking the intersection of fixed points (McDermott/Doyle) versus any fixed point (Reiter). FAULTY defaults to the intersection, reflecting an agnostic stance on conflicting evidence, though an alternative mode is mentioned.

Key Results

The paper presents an informal description of FAULTY's proof procedure and demonstrates its capabilities through examples. The primary result is the successful implementation of a default prover that:

  • Handles Horn clauses without functions, a decidable subset of FOL.
  • Avoids the semi-decidability issues of NML I and Default Logic.
  • Effectively manages interacting defaults through explicit applicability control.
  • Provides a more intuitive representation of defaults compared to circumscription.

The paper includes example dialogues showing how FAULTY can prove or disprove statements based on default rules and exceptions.

Limitations and Future Work

  • Efficiency: The authors acknowledge that FAULTY's efficiency is a primary concern, as it relies on multiple standard resolution proofs. They express optimism due to the potential for parallelization.
  • Recording Results: FAULTY is described as a "pure prover" and does not record its inferences. The authors suggest combining FAULTY with Truth Maintenance Systems to create a more comprehensive reasoning system that can track inferences and allow for axiom updates without recomputation. This system, named TINA, is under development.

Summary updated

BibTeX
@inproceedings{brewka1986tweety,
  author = {Gerhard Brewka},
  title = {{Tweety - Still Flying: Some Remarks on Abnormal Birds Applicable Rules and a Default Prover}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure