Abstract
We present a theory of plan modification applicable to hierarchical nonlinear planning. Our theory utilizes the validation structure of the stored plans to yield a flexible and conservative plan modification framework. The validation structure, which constitutes a hierarchical explanation of correctness of the plan with respect to the planner's own knowledge of the domain, is annotated on the plan as a by-product of initial planning. Plan modification is characterized as a process of removing inconsistencies in the validation structure of a plan when it is being reused in a new (changed) planning situation. The repair of these inconsistencies involves removing unnecessary parts of the plan and adding new non-primitive tasks to the plan to establish missing or failing validations. The resultant partially reduced plan (with a consistent validation structure) is sent to the planner for complete reduction. We discuss the development of this theory in the PRIAR system, and characterize its completeness, coverage, efficiency, and limitations.
Introduction
In classical AI planning, "replanning" has historically been synonymous with "starting over." Early attempts at plan reuse, such as macro-operators, were often brittle "black boxes"—they could repeat a sequence of steps but lacked the internal logic to modify that sequence if conditions changed.
The core challenge is conservative modification: adapting an existing plan to a new goal or initial state while preserving as much of the original work as possible. Without understanding the "why" behind a specific step—its internal dependencies—a system cannot safely remove or replace it. This paper introduces a formal framework for understanding these dependencies in hierarchical, nonlinear plans, implemented in the PRIAR system.
Methods
The PRIAR system is built upon three main pillars:
- Validation Structure: A plan is stored not just as a sequence of actions, but as a set of "validations." A validation links a "source" (an action providing an effect) to a "destination" (an action requiring that effect). This creates a hierarchical explanation of the plan's correctness.
- Annotations: Nodes in a Hierarchical Task Network (HTN) are annotated with E-conditions (effects used externally), E-preconditions (requirements met externally), and P-conditions (conditions that must persist during sub-plan execution).
- The Reuse Cycle: This involves mapping objects from the old plan to the new problem, verifying annotations to identify inconsistencies (failing, unnecessary, or missing validations), and refitting. During refitting, the planner reduces only specific "refit tasks" identified as gaps, using a heuristic control strategy to minimize disturbance to the rest of the plan.
Plans as Explanations
A plan is viewed as a hierarchical explanation of correctness. By knowing the rationale behind every step, the system can pinpoint exactly which parts become redundant or broken when the environment changes. Modification is framed as "repairing inconsistencies." By categorizing failures—such as a failing phantom goal versus a failing filter condition—the system selects the most efficient repair strategy, whether it be pruning, adding a task, or re-reducing a hierarchy.
Results and Evaluation
The theory was evaluated using standard Blocks World benchmarks, including 3-Block Stacking (3BS) as a base case and increasingly complex problems (4BS1, 7BS1, 12BS1).
Empirical results demonstrate that plan modification is significantly more efficient than generative planning:
- Computational Savings: PRIAR achieved 20% to 98% savings in planning effort across various problems.
- Speedup Factors: This corresponds to speedup factors ranging from 1.5 to 50.
- Scalability: Savings remained high as problem size increased, suggesting that reuse scales better than pure generative planning for complex tasks.
Discussion and Limitations
While PRIAR offers significant speedups through conservative modification, it does not guarantee an optimal plan, prioritizing speed over finding the shortest action sequence. Furthermore, the system is dependent on the planner’s domain model; it cannot fix errors stemming from an incomplete understanding of the world. In extreme cases where no part of the old plan is applicable, the system may incur polynomial overhead before essentially planning from scratch. Future work includes exploring more sophisticated mapping strategies and integration with deeper causal models of the domain.
Summary updated