Knowledge-Based Validity Maintenance for Production Systems

Philip Schaefer, H. Isil Bozma, Randall D. BeerAAAI 1986

In the mid-1980s, expert systems faced a significant hurdle: non-monotonic reasoning. Standard production systems operated on a "trigger-and-forget" basis. Once a rule's conditions were met, its conclusion was asserted into memory indefinitely. If the underlying facts changed, the conclusion remained, leading to inconsistencies unless developers wrote complex, manual "cleanup" rules. This paper, presented at AAAI-86, introduces a structural solution to this problem by bridging the gap between high-level human reasoning and low-level Truth Maintenance Systems (TMS).

The IF/THEN/AS-LONG-AS Construct

The authors propose extending the traditional production rule syntax with a third clause: AS-LONG-AS. This allows a knowledge engineer to distinguish between the conditions required to initiate an action and the conditions required for that action to remain valid.

  1. Syntax: IF <trigger> THEN <conclusion> AS-LONG-AS <validity-condition>.
  2. Mechanism: When a rule fires, the system records a dependency link. This link connects the conclusion to the specific data elements in the AS-LONG-AS clause.
  3. Maintenance: The system automatically monitors these dependencies. If a validity condition is violated, the system recursively retracts the conclusion and any subsequent inferences derived from it.
Dependency links and AS-LONG-AS rules illustrating how conclusions are tied to their justifications.

Implementation and Automation

By embedding validity maintenance into the rule structure, the system automates the "bookkeeping" of truth. This preserves the modularity of the rule base; the programmer no longer needs to write specific rules to handle every possible data retraction scenario. The algorithm follows a three-step cycle: Note (record dependencies), Check (monitor memory changes), and Invalidate (recursive retraction).

Evaluation: The Meeting Scheduler

The approach was evaluated using a meeting scheduler domain and a system called DIFF (Domain Independent Form Filler). In the scheduler example, the system manages attendees and potential conflicts.

The initial state of the meeting scheduler domain, showing the relationship between participants and meeting objects.

In this scenario, if a new meeting is added that creates a conflict for an attendee, the AS-LONG-AS condition for the original meeting time fails. The system then automatically "unschedules" the conflicting meeting. This triggers a chain reaction where a separate rescheduling rule detects the missing time and proposes a new slot. This entire recovery process occurs without explicit "if-conflict-then-delete" logic, demonstrating the power of recursive retraction.

Conclusion and Future Directions

The AS-LONG-AS construct successfully hides the complexity of dependency networks behind a natural syntax. While the authors noted limitations—such as the need for more sophisticated "dependency-directed backtracking" to choose which assumptions to break during contradictions—the system provided a robust framework for maintaining consistency in dynamic environments. This work laid important groundwork for integrating automated truth maintenance into large-scale production systems.

Summary updated

BibTeX
@inproceedings{schaefer1986knowledge,
  author = {Philip Schaefer and H. Isil Bozma and Randall D. Beer},
  title = {{Knowledge-Based Validity Maintenance for Production Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure