A Survey on Plan Optimization

Pascal Bercher, Patrik Haslum, Christian Muise, Wenjia Wang

Abstract

Finding mathematically optimal solutions to automated planning problems is often computationally intractable. Consequently, practical systems frequently generate suboptimal plans that are later refined—a process known as plan optimization. This paper provides the first comprehensive survey of the field, mapping the computational complexity of various optimization goals and the diverse techniques used to eliminate redundancy and increase plan flexibility. We categorize these methods into action and ordering optimizations, analyzing their theoretical foundations and empirical performance across standard benchmarks like Blocksworld. Our findings highlight the practical effectiveness of greedy refinement strategies and identify key challenges in optimizing hierarchical plans.

What Problem Does This Paper Address?

In automated planning, agents seek a sequence of actions to reach a specific goal, such as a robot organizing a warehouse. While the ideal outcome is the "cheapest" or "shortest" plan, finding the absolute optimum is notoriously difficult, often requiring exponential search time even with advanced heuristics.

Most planners therefore settle for "any" valid solution. These initial plans are frequently "bloated," containing redundant steps or unnecessarily rigid sequences. This survey addresses the challenge of post-processing: given a valid but imperfect plan, how can we efficiently remove redundant actions, replace inefficient sub-sequences, or relax action ordering to improve the plan's quality?

Methods

The authors categorize plan optimization algorithms into three primary pillars:

  1. Complexity Analysis: The paper reviews the theoretical hardness of optimization. For instance, while identifying some redundancies is computationally simple, finding a perfectly justified minimal subplan is NP-complete.
  2. Action Optimization: These techniques focus on reducing plan length or cost.
  3. Action Elimination: Identifying and removing "redundant" actions that do not affect the plan's validity.
  4. Subplan Replacement: Re-solving specific segments of a plan to find more efficient local paths.
  5. Neighborhood Search: Exploring the state-space around an existing plan for local improvements.
  6. Ordering Optimization: These methods involve "deordering" (removing unnecessary sequence constraints) or "reordering" (optimizing execution time). These often leverage MaxSAT, Mixed-Integer Programming (MIP), or Constraint Satisfaction (CSP) solvers.
Figure 3: A totally ordered plan identifying removable actions (putdown and pickup of block A) that do not contribute to the final goal state.

Datasets

As a theoretical survey, this work references standard benchmarks rather than introducing new datasets:

  • Blocksworld: A classic domain used for illustrative examples of stacking and moving blocks.
  • International Planning Competition (IPC) Benchmarks: The standard PDDL (Planning Domain Definition Language) problems used to evaluate the efficiency of the surveyed techniques.

Key Insights and Ideas

  • The "Optimality Trap": The authors highlight that even with nearly perfect heuristics, searching for absolute optimality can force an exponential exploration of state space, justifying post-optimization as a more practical route.
  • Data Structures Matter: The choice of representation—Totally Ordered, Partially Ordered (PO), or Partial Order Causal Link (POCL)—dictates possible optimizations. POCL plans, for example, allow for more sophisticated deordering than standard PO plans.
Figure 1: A POCL plan for a 2-gripper Blocksworld problem, illustrating a non-totally ordered structure that allows for parallel execution.
  • The Hardness of Deletion: In POCL plans, checking if even a single action can be safely removed is NP-complete, as it requires proving the remaining actions can be validly re-linked.
  • Greedy is Good: Despite high theoretical complexity, simple greedy action elimination often achieves over 80% of possible cost reductions in practice.

Key Results

  • Empirical Efficiency: Local "sliding window" approaches (replacing small plan segments) are highly effective at reducing plan length with minimal computational overhead.
  • Flexibility Gains: Deordering significantly increases the number of valid execution paths (flexibility), which is critical for robots in dynamic environments where specific paths might be obstructed.
  • Hierarchical Planning (HTN): Optimization in HTN is significantly more complex because changes must adhere to the original task hierarchy, making verification an NP-hard problem.

Limitations and Future Work

  • The "Hard-to-Optimize" Gap: It remains unknown if certain plans are both highly suboptimal and extremely difficult to optimize.
  • Synergy Exploration: Most current work treats action removal and reordering as separate tasks. Combining them—where reordering might reveal new redundancies—is a promising frontier.
  • HTN Optimization: There is a notable lack of diverse techniques for optimizing hierarchical plans compared to classical "flat" planning.

Summary updated

BibTeX
@inproceedings{bercher2024survey,
  author = {Pascal Bercher and Patrik Haslum and Christian Muise and Wenjia Wang},
  title = {{A Survey on Plan Optimization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure