The Utility of Difference-Based Reasoning

Brian FalkenhainerAAAI 1988

Abstract

Traditional artificial intelligence often prioritizes identifying similarities between cases to solve problems through analogy. This paper argues that the true power for diagnosing failures lies in identifying disanalogies. By focusing exclusively on the differences between a failing situation and a nearly identical successful one, a system can drastically prune its search space. This approach, termed Difference-Based Reasoning (DBR), allows for the rapid generation of plausible hypotheses to explain why expectations were violated.

Introduction: The Challenge of Expectation Failure

In the late 1980s, AI problem-solving typically relied on either first-principles analysis or positive analogical mapping. However, these methods often faltered when faced with "expectation failure"—situations where a system behaves unexpectedly. Brian Falkenhainer identified that looking for similarities to past successes does little to debug a specific failure. For instance, diagnosing a car door that won't close by analyzing every component from scratch is computationally prohibitive. Falkenhainer proposes that the most efficient solution is to ask: "How is this failing door different from the working one on the other side of the car?"

Methodology: Difference-Based Reasoning (DBR)

DBR is a "negative-centered" approach to reasoning that follows three primary steps:

  1. Identify a Positive Exemplar: Find a "working" version or a prototypical instance of the situation that meets expectations.
  2. Compute the Difference Set (Δ): Use the Structure-Mapping Engine (SME) to align the two situations. SME identifies corresponding facts; the "leftovers"—those that do not map—form the difference set.
  3. Focus and Explain: Use the difference set to guide an inference engine (such as the Qualitative Process Engine) to determine if those specific differences account for the change in behavior.
Structural comparison of system states to identify differences between a successful and failed plan.

The core of this method is the Difference Theorem, which states that if a goal is derivable in one set of axioms but not another, the cause of failure must be traceable to the differences between those sets.

Case Studies and Results

The DBR theory was evaluated using three distinct qualitative models:

The Bouncing Ball Pendulum

This physics problem compares a pendulum hitting a vertical wall (infinite bouncing) versus an inclined wall (stopping in finite time). DBR correctly identified that the change in the wall's angle (from zero to non-zero) was the key variable. This allowed the system to invoke more detailed models to explain the "Zeno’s paradox" of the bouncing ball.

The Bouncing Ball Pendulum scenario comparing (a) a vertical wall and (b) an inclined wall.

The Car Door Latch

In a mechanical diagnosis task, the system compared a broken driver-side door to a functional passenger-side door. DBR successfully isolated a missing rubber piece as the cause of failure, making the diagnosis tractable despite a massive number of potential mechanical faults.

The Flat Soufflé

In a planning failure scenario, a strawberry soufflé fails to rise compared to a successful vanilla one. DBR deduced that the liquid content of the strawberries caused a chemical imbalance, without needing to calculate the exact volume of every ingredient.

Discussion: Key Insights and Limitations

The "Aha!" moment of DBR is that the difference set acts as a powerful heuristic. Instead of checking every possible fault, the system only checks hypotheses related to the detected differences. This qualitative approach makes reasoning more robust and human-like by focusing on changes (e.g., "the angle increased") rather than precise numerical values.

However, DBR requires a "working version" or a clear prototype to compare against. If a failure is entirely novel with no successful counterpart, DBR cannot trigger. Furthermore, complex 3D geometric reasoning remains a limitation for current implementations.

Conclusion

Difference-Based Reasoning demonstrates that focusing on disanalogies is a highly effective strategy for theory revision, diagnosis, and planning. By leveraging the differences between success and failure, AI systems can navigate complex problem spaces with significantly greater efficiency.

Summary updated

BibTeX
@inproceedings{falkenhainer1988utility,
  author = {Brian Falkenhainer},
  title = {{The Utility of Difference-Based Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure