Introduction
In the early development of symbolic Artificial Intelligence, researchers sought to create systems capable of "Qualitative Reasoning"—understanding the behavior of complex physical systems (like coffee machines or industrial reactors) using common-sense physics rather than precise numerical simulations. A central challenge in this field is the "Lego problem," or consolidation: the ability to automatically derive the behavioral description of a complex device from the descriptions of its individual components.
In his seminal 1991 work, Tom Bylander introduced the Qualitative Difference Resolution (QDR) Rule to overcome the computational barriers that made previous consolidation methods practically unusable for large-scale systems.
The Consolidation Challenge
Qualitative physics typically models devices using Qualitative Differential Equations (QDEs), where variables represent signs (positive, negative, or zero) rather than exact values. While theoretically sound, earlier methods like the Qualitative Resolution (QR) rule suffered from a combinatorial explosion of states. These methods were often intractable, failing to infer global conservation laws (such as "what goes in must come out") from local component interactions.
As shown in Figure 1, a simple network of pipes involves multiple pressures ($P$) and flows ($Q$). Consolidating these into a single behavioral model requires eliminating internal connection variables while maintaining the causal relationships between external ports.
The QDR Methodology
The breakthrough of the QDR rule lies in its shift from absolute qualitative values to Conditional Difference Systems. Bylander identified that modeling with absolute signs (e.g., $[P_1]$) often leads to ambiguity ($?$) during resolution. By focusing on the sign of the difference between pressures ($[P_i - P_j]$), the rule preserves the direction of causality and the gradient-driven nature of fluid flow.
The QDR rule utilizes an algebra of signs (Q1 algebra) to resolve internal variables. As seen in Figure 5, the equations (11-18) define flow as a function of pressure differences. This formulation allows the system to "resolve" or eliminate shared variables at connection points efficiently, leaving only the relationships between the device's external ports.
Results and Complexity
Bylander provided a formal mathematical proof that if components are modeled as difference systems, the consolidation process can be completed in polynomial time ($O(mn^2)$). This transformed consolidation from an exponentially difficult task into one that can be executed in milliseconds for standard engineering models.
Key successes of the QDR rule include:
- Emergent Laws: The rule naturally derives the Qualitative Continuity Rule (a qualitative version of Kirchhoff’s Current Law) without requiring it to be hard-coded.
- Engineering Application: The rule successfully simplified the behavior of a complex pressure regulator, a device consisting of pipes, valves, and sensing mechanisms.
Limitations and Conclusion
While the QDR rule represents a significant leap in tractability, it requires models to be in a specific "conditional difference" format. It may struggle with highly non-linear components, such as a valve's "blocked" state, and can result in some information loss regarding specific component nuances (like the one-way nature of a check valve). Nevertheless, the QDR rule remains a foundational contribution to qualitative physics, proving that specialized mathematical structures can make symbolic reasoning about the physical world computationally feasible.
Summary updated