Deordering and Numeric Macro Actions for Plan Repair

Enrico Scala, Pietro TorassoIJCAI 2015

Introduction

In automated planning, plan repair is the process of modifying an existing plan to accommodate unexpected changes in the environment, such as blocked paths or resource depletion. While often more efficient than replanning from scratch, traditional plan repair techniques struggle with numeric domains involving continuous resources like fuel, battery levels, or time. This paper introduces MADE (Macro Actions via DEordering), a novel approach that leverages plan deordering to extract independent, self-contained "macro actions." These macros serve as shortcuts, allowing planners to navigate complex numeric constraints and repair broken plans with significantly higher speed and reliability.

The MADE Framework

The MADE system operates as a domain-independent enhancement layer for existing planners. As illustrated in Figure 1, the architecture integrates plan deordering and macro generation into the execution and monitoring loop.

The MADE system architecture for plan repair via macro actions.

The process begins when a discrepancy is detected during plan execution. Instead of discarding the remaining plan, MADE analyzes the "totally ordered plan" to identify underlying dependencies.

Methodology: Numeric Deordering and Macro Selection

The core of MADE consists of two primary phases: Numeric Deordering and Macro Action Selection.

1. Numeric Deordering

Standard deordering techniques for propositional logic identify which steps satisfy specific boolean conditions. MADE extends this to numeric fluents by introducing the Numeric Dependency Set (NDS). In numeric planning, a single condition (e.g., fuel > 100) might be satisfied by the cumulative effect of multiple actions (e.g., several refuel steps). MADE uses a hill-climbing search to find the minimal set of actions required to satisfy these cumulative numeric requirements, creating a Directed Acyclic Graph (DAG) of dependencies.

2. Macro Action Selection

Once the plan is represented as a deordered DAG, MADE identifies connected components—subsets of actions that are functionally independent of other parts of the plan. These components are packaged into "macro actions."

Comparison between a totally ordered plan (a) and the deordered DAG with identified macro components (b).

By providing the planner with these modular blocks, MADE reduces the search space, preventing the exploration of irrelevant action interleavings.

Experimental Evaluation

The authors evaluated MADE across six domains from the International Planning Competition (IPC), including Depots, Satellite, Rovers, DriverLog, and ZenoTravel. To test plan repair capabilities, 100 test cases per domain were generated by injecting random state or goal discrepancies.

Key Results

  • Superior Coverage: MADE consistently outperformed basic planners (like Metric-FF and Colin) and previous state-of-the-art macro selection methods (e.g., CLMA). In the Rover domain, MADE solved 91 cases, whereas the baseline planner solved only 23.
  • Efficiency: Although the deordering preprocessing adds overhead, the overall time to find a solution was reduced because the resulting search space was significantly smaller.
  • Plan Stability: Repaired plans maintained lengths comparable to the original plans, indicating that the generated macros did not introduce unnecessary complexity or "bloat."

Discussion and Future Work

The "aha moment" of this research is the realization that numeric causality is cumulative. By capturing this "teamwork" between actions through the NDS, MADE provides a robust way to handle continuous resources.

However, limitations remain. In complex domains like Rovers, the deordering process can be computationally expensive, sometimes accounting for up to 77% of execution time. Future work will focus on optimizing NDS discovery and extending the framework to handle temporal constraints, such as concurrent and overlapping actions. Additionally, because the quality of macros depends on the initial plan, investigating ways to refine inefficient source plans during the deordering phase could further enhance performance.

Summary updated

BibTeX
@inproceedings{scala2015deordering,
  author = {Enrico Scala and Pietro Torasso},
  title = {{Deordering and Numeric Macro Actions for Plan Repair}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}

Loading related content...

Figure