Introduction
In the evolution of automated reasoning, Truth Maintenance Systems (TMS) emerged as a critical framework for handling "default reasoning"—the capacity for an AI to operate on assumptions until contradictory evidence arises. A cornerstone of this framework was Jon Doyle’s dependency-directed backtracking (DDB) algorithm. However, early implementations of DDB often struggled with efficiency and a lack of domain sensitivity. This paper presents a significant refinement of the DDB algorithm, implemented in the Proteus system, which transforms backtracking from a blind utility into a sophisticated, knowledge-driven reasoning process.
The Limitations of Classical Dependency-Directed Backtracking
By the late 1980s, Doyle’s original DDB was the standard for resolving contradictions in belief networks. When a contradiction was detected, the system would search for a "culprit" assumption to retract. This approach, however, suffered from two primary deficiencies:
- Blind Heuristics: The original algorithm relied on "minimal revision" strategies. These strategies were domain-independent, operating on the principle that the smallest change to the belief set was the best. In complex fields like medicine or engineering, the "smallest" change is rarely the most logical or safest.
- Computational Overhead: The process required complex "Conditional-Proof" justifications and the calculation of "Maximal Assumption Sets" (MAS). These were computationally expensive and often involved exhaustive searches that did not contribute to the final resolution.
The author argues that the gap between low-level truth maintenance and high-level domain expertise must be bridged to create truly effective expert systems.
Technical Innovations: The Proteus System
The revised algorithm introduces several key technical shifts to streamline the TMS and integrate expert knowledge.
Simplified Justifications
Instead of relying on "nogood" nodes and complex conditional proofs, the revised algorithm directly modifies the "OUT-list" of the elective (the new assumption). This approach makes the justification for a new belief explicitly dependent on the failure of the previous state, simplifying the dependency network.
The MAKEOUT/MAKEIN Algorithm
The system employs a recursive approach to status assignment known as MAKEOUT/MAKEIN. This eliminates the need to pre-calculate the MAS. By focusing on local status changes, the algorithm ensures the resulting network is "safe"—meaning it is free from unsatisfiable circularities or "odd loops"—without the exhaustive overhead of previous methods.
Knowledge-Based Search Predicates
The most significant contribution is the introduction of three predicates that allow domain experts to guide the backtracking process:
- PREFER(A, B): Directs the system to retract assumption A before assumption B, allowing for a hierarchy of belief reliability.
- DEFEAT(Culprit, Reason, NewElective): Dynamically generates specific alternatives when a particular assumption fails.
- FIX(Culprit, Ancestor, Elective): Enables the search to "jump" to known common failure points deep within the dependency network, bypassing irrelevant intermediate nodes.
Applications and Qualitative Improvements
The algorithm was evaluated within the Proteus expert system environment and applied to diverse domains, including Semicustom VLSI Design and Printed Wire Board Placement.
A key illustrative example involves medical diagnosis. In a scenario where a patient’s lab results contradict clinical observations of dehydration, a standard DDB might retract the lab result simply because it was the most recent assumption. However, using the PREFER predicate, a medical expert system can be instructed to re-verify simple symptom observations before ordering expensive or invasive lab re-tests. This demonstrates that the revised DDB can mimic human expert behavior by prioritizing certain types of evidence over others.
Key Insights
The paper’s most profound insight is that backtracking is reasoning. Choosing which belief to abandon is not merely a system utility; it is a domain-specific decision that requires the same level of expertise as the initial inference. By streamlining the computational requirements—specifically by showing that the Maximal Assumption Set is often unnecessary—the author provides a framework that is both more efficient and more flexible.
Conclusion and Limitations
The revised DDB algorithm achieves three critical criteria for justifications: they are sufficient to resolve conflicts, safe from infinite loops, and complete in their logic.
However, the system remains dependent on the quality of the provided knowledge. If a developer does not provide specific PREFER or FIX rules, the system reverts to a standard depth-first search. Additionally, while the author argues that the computational cost of checking for "odd loops" is negligible, it remains a factor in system complexity. Despite these challenges, the work represents a pivotal shift toward integrating high-level domain knowledge directly into the foundational mechanisms of automated reasoning.
Summary updated