Assembling a Device

Jean-Luc Dormoy, Olivier RaimanAAAI 1988

Introduction

In the foundational era of Qualitative Physics, researchers sought to bridge the gap between human-like engineering intuition and computational logic. A seminal 1988 paper introduced a formal method for "compiling" the behavior of physical devices. By moving beyond simple step-by-step propagation to a robust "qualitative resolution rule," the authors demonstrated how global behavior could be systematically derived from local component descriptions.

The Challenge of Qualitative Propagation

In the late 1980s, the primary goal of Qualitative Physics was to enable computers to reason about physical systems—such as circuits, fluid networks, or engines—using the same sign-based logic (+, -, 0) that engineers often employ. The standard approach at the time was "propagation": if the pressure at an inlet increases (+), that change is propagated through connected components.

However, this simple propagation is frequently incomplete. It falters in systems characterized by feedback loops or simultaneous constraints where no single variable can be isolated for deduction. While traditional algebra utilizes Gaussian elimination to resolve such systems, qualitative algebra is inherently more complex. Because one cannot always "subtract" variables to eliminate them without introducing ambiguity (the '?' sign), a mathematically sound method was needed to deduce global properties from local laws.

Methods: The Two-Step Framework

The authors proposed a two-step framework to transform complex, ambiguous reasoning tasks into efficient propagation problems.

The two-step framework for qualitative reasoning: Assembling and Simulation.

1. Assembling the Device

The core innovation is the Qualitative Resolution Rule. This rule allows the system to eliminate "internal" variables to create global relations. Formally, if two qualitative equations (confluences) exist such as $x + y = a$ and $-x + z = b$, one can deduce $y + z = a + b$, provided that $x$ is not "ambiguous" (the '?' sign). This serves as a qualitative analogue to the resolution principle in logic or Gaussian elimination in linear algebra.

2. Task-Oriented Simulation

Once the device is "assembled" into a set of global laws tailored to a specific task—such as simulation or diagnosis—predicting behavior becomes a computationally inexpensive propagation task. This "compilation" step ensures that the heavy lifting is done upfront.

Benchmarks and Validation

The approach was validated using classic benchmark models in the field of Qualitative Physics:

  • Two Connected Pipes: This simple model demonstrates how local descriptions of pressure and flow at different segments can be merged into a single global law governing the entire conduit.
  • The Pressure Regulator: A more sophisticated benchmark, originally proposed by De Kleer and Brown, used to show how the resolution rule handles multiple internal variables and complex feedback mechanisms.
The pressure regulator benchmark and its associated qualitative confluences.

Key Insights

  • Knowledge Compilation: The "Assembling" phase is essentially a compilation process. Although finding global laws is NP-complete, it is a one-time cost. Subsequent simulations run in polynomial time, making the system highly efficient for repeated use.
  • Completeness in the "Square Case": The authors proved that for "square" systems—where the number of equations equals the number of variables—the resolution rule is complete. If a value can be logically deduced from the qualitative model, this rule is guaranteed to find it.
  • Navigating Ambiguity: The primary obstacle in qualitative reasoning is the "ambiguous" sign ($?$), representing the unknown sum of positive and negative values. The resolution rule is specifically designed to navigate around these points of uncertainty.

Results and Impact

The formalization of Qualitative Resolution filled a critical gap in the "signs algebra" used by early AI researchers. By bifurcating the problem into an assembly phase and a simulation phase, the authors enabled qualitative reasoning on systems far more complex than those manageable by previous methods. Furthermore, the paper provided a necessary mathematical correction to earlier attempts at qualitative completeness, establishing a more rigorous foundation for the field.

Limitations and Future Directions

Despite its strengths, the framework has limitations. The formal proof of completeness is currently restricted to "square" systems. Additionally, the NP-complete nature of the assembly process suggests that for massive systems with hundreds of components, the initial compilation could become a bottleneck. Future work was suggested to extend these rules to "orders of magnitude" reasoning, dealing with concepts like "much larger than" rather than just simple signs.

Summary updated

BibTeX
@inproceedings{dormoy1988assembling,
  author = {Jean-Luc Dormoy and Olivier Raiman},
  title = {{Assembling a Device}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure