Context Maintenance

Charles J. PetrieAAAI 1991

Introduction

In the early 1990s, AI researchers utilized Truth Maintenance Systems (TMS) to manage logical dependencies in planning and scheduling. While effective at maintaining consistency, traditional TMS suffered from two major flaws: "syntactic aggression" and "missed opportunities." Syntactic aggression occurred when a minor change in preference triggered a massive ripple effect, undoing dozens of valid assignments. Conversely, systems often missed opportunities to improve a plan because they failed to remember why a superior option had been rejected in the first place.

Charles Petrie's 1991 paper introduces the REDUX architecture to address these issues. By implementing "Context Maintenance," REDUX tracks the semantic rationale behind every decision and rejection, allowing AI planners to navigate changes gracefully.

The REDUX Architecture

REDUX moves away from simple "if-then" dependencies toward a structured model of Decisions. In this framework, every assignment is treated as a decision resulting from applying an operator to a goal.

A core innovation of REDUX is the separation of a choice's validity (whether the assignment is still logically possible) from its optimality (whether it remains the best choice based on current heuristics).

Figure 6: The dependency structure for an optimal decision in REDUX, separating validity, admissibility, and optimality.

Unlike standard backtracking, which simply retracts a choice, REDUX creates a formal justification for the rejection of an alternative. When a conflict occurs, the system records a "nogood" that explains the failure. This record serves as the rationale for why the system moved to a less-preferred context, ensuring that the system only reconsidered that path if the specific cause of the failure is removed.

Illustrative Example: Scheduling Professors

The paper demonstrates these concepts through a "Scheduling Professors" toy problem. The task involves assigning class sections to professors while balancing seniority and departmental constraints (e.g., "only one section of PHL305 per semester").

Figure 4: A dependency graph showing how a rejection rationale (Rejected-Assignment) and a NOGOOD are tracked in the professor scheduling example.

As shown in Figure 4, the assignment of Kant to PHL380 is justified because his preferred assignment (PHL305) was rejected due to a conflict with Descartes. If Descartes' assignment were later retracted, REDUX would automatically recognize that the rationale for rejecting Kant's preferred course no longer holds, identifying a clear opportunity to improve the overall schedule.

Key Insights and Results

REDUX provides several qualitative advantages over contemporary systems:

  • Semantic Control: By placing contradictions on an "agenda" rather than letting the TMS resolve them automatically, the system gives developers control over how and when to resolve conflicts, preventing the "rippling" effect.
  • Precision in Replanning: The architecture precisely locates the effects of changes in a general plan, a feat the author claims was unique at the time.
  • Avoiding "Wishful Thinking": Traditional TMS can be too aggressive in resolving violations, sometimes assuming a contingency just to maintain consistency. REDUX requires explicit evidence for such shifts.

Conclusion and Future Work

While the author admits that constructing "optimality justifications" is computationally complex, the REDUX architecture was successfully applied to complex tasks like VLSI design. Future work suggested extending the system to support multiple simultaneous contexts, further enhancing its ability to explore alternative solutions in parallel. By recording the history of why a path was taken or rejected, REDUX ensures that AI systems can change their minds without breaking the entire plan.

Summary updated

BibTeX
@inproceedings{petrie1991context,
  author = {Charles J. Petrie},
  title = {{Context Maintenance}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}

Loading related content...

Figure