Constrained Decision Revision

Charles J. PetrieAAAI 1992

Abstract

This paper introduces a theory for Constrained Decision Problems (CDPs), bridging the gap between classical AI planning and constraint satisfaction. By using a Truth Maintenance System (TMS) to track the rationale behind every decision, the proposed REDUX architecture allows planners to handle incremental changes, external contingencies, and multiple objectives without needing to restart the planning process from scratch.

Introduction

In the early 1990s, AI research faced a significant divide between classical planning and constraint satisfaction problems (CSPs). Classical planning, such as Hierarchical Nonlinear Planning, excelled at decomposing high-level goals into subtasks but struggled with maintaining consistency under dynamic changes. Conversely, CSPs were robust at finding consistent variable assignments but required a "closed world" where all variables are known upfront. This limitation makes CSPs unsuitable for "constructive" problems where new objects, such as specific flight instances or sub-components, are generated during the search process.

The author identifies Constrained Decision Problems (CDPs)—tasks like travel planning or logistics—as a class of real-world problems requiring both hierarchical decomposition and robust constraint management. The REDUX architecture was developed to bridge this gap by treating planning as a series of revisable decisions backed by a Truth Maintenance System (TMS).

The REDUX Architecture

The core of the REDUX architecture is the treatment of planning decisions as revisable assumptions. Unlike static variables in a CSP, decisions in REDUX are dynamic and context-dependent.

The structure of a decision in the REDUX architecture, showing the relationship between goals, operators, and assignments.

Key Technical Components

  • Decisions as Assumptions: Every choice made by the planner is recorded as an assumption in a TMS. This enables dependency-directed backtracking; if a constraint is violated, the system can pinpoint and retract only the specific decisions that led to the conflict.
  • Admissibility and Operators: Goals are reduced using operators. Each operator has admissibility conditions that must remain valid. If an external event (e.g., a flight cancellation) invalidates these conditions, the TMS automatically propagates this failure to all dependent subgoals.
  • Preference Rules and Multiple Objectives: Instead of a single global objective function, REDUX employs local preference rules to rank operators. This supports Pareto optimality, allowing the system to identify if a solution can be improved for one objective without compromising others.

Evaluation and Examples

The REDUX architecture was evaluated using several scenarios that highlight its ability to handle revisions and dynamic constraints.

Travel Planning

A primary example involves planning a trip from Austin to Arlington. The system must navigate various modes of transport (flight, bus, taxi) while adhering to budget constraints.

A travel planning goal tree demonstrating the handling of failed subgoals and budget constraints.

As shown in Figure 1, the system handles failed subgoals (e.g., a canceled flight) and budget violations by exploring alternative branches without discarding the entire plan.

Real-World Applications

Beyond toy problems, REDUX was applied to:

  1. Telephone Network Multiplexor Configuration: A complex configuration task where REDUX significantly reduced code complexity. In this application, REDUX replaced over 200 Lisp functions with just 5 operators and fewer than 10 rules/constraints.
  2. Course Scheduling: Managing professor and course assignments, specifically handling contingencies like staff illness. A system that previously required 60 complex control rules was reduced to 5 operators and 4 preferences.

Key Insights

  • Constructive Planning: Variables in planning are often created dynamically. REDUX handles this "open world" by creating variables and constraints only when a specific decision path is taken.
  • Replanning as Backtracking: The paper posits that replanning (reacting to external changes) and backtracking (reacting to internal conflicts) are functionally identical when supported by dependency tracking.
  • Human-in-the-Loop: REDUX is designed to notify users of "opportunities" (e.g., a newly available cheaper option) rather than forcing automatic plan changes, preserving user agency in complex scenarios.

Conclusion

The implementation of REDUX led to dramatic simplifications in planning logic and improved debugging capabilities. Because the system tracks the "rationale" for every choice, it can provide clear explanations for why a specific operator was chosen or why a plan failed. By providing a semantic layer for decision rationale, REDUX offers a robust framework for building planners that are both efficient and explainable.

Summary updated

BibTeX
@inproceedings{petrie1992constrained,
  author = {Charles J. Petrie},
  title = {{Constrained Decision Revision}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure