Abstract
In automated planning, finding the absolute best solution is often computationally prohibitive. Most AI planners settle for "satisficing" solutions—plans that are valid but often suboptimal. This survey explores the field of plan optimization, the process of post-processing these initial plans to reduce costs, remove redundancies, and increase execution flexibility. We categorize the current landscape of techniques, from action elimination to partial ordering, and discuss the theoretical and empirical trade-offs involved in plan refinement.
Introduction: The "Find then Refine" Paradigm
Automated planning aims to find a sequence of actions that transitions an agent from an initial state to a goal. While optimal planning (finding the cheapest or shortest path) is desirable, the search space is often exponentially large. Consequently, modern planners frequently employ satisficing techniques to find any valid plan quickly. However, these plans are often "messy," containing redundant steps or unnecessarily rigid sequences. This survey addresses the "optimality gap" by reviewing methods that refine these initial solutions.
Methodologies for Plan Refinement
The survey categorizes optimization techniques based on their underlying representation (e.g., STRIPS, Partially Ordered plans) and their specific goals.
Action Elimination
Action elimination focuses on identifying and removing "redundant" actions that do not contribute to the goal. The authors distinguish between various levels of "justification." For instance, a "backward-justified" action is one required by a subsequent action or the goal itself. "Perfectly justified" plans are those where no subsequence forms a valid plan.
Subplan Replacement
Rather than simple deletion, subplan replacement analyzes a "window" of the plan to find a more efficient sequence of actions that achieves the same state transition. This often involves local search or encoding the sub-problem as a SAT or MaxSAT instance to find a local optimum.
Deordering and Reordering
These methods transform a linear sequence of actions into a Partial Order Causal Link (POCL) plan. By relaxing unnecessary ordering constraints, the plan becomes more flexible for real-world execution, allowing actions to be performed in parallel or adjusted dynamically in response to delays.
Key Insights and Complexity
The survey highlights several critical findings in the field:
- The Complexity Paradox: Even seemingly simple optimization tasks, such as checking if a single action can be removed from a partially ordered plan, are NP-complete.
- Efficiency of Greedy Approaches: Despite theoretical hardness, simple greedy algorithms for action elimination often capture over 80% of the potential cost reduction compared to exhaustive methods.
- Representation Matters: The choice between a linear sequence and a POCL plan fundamentally changes the available optimization space. "Block-decomposed" partial orders can yield up to a 40% greater improvement in plan quality compared to optimizing totally ordered sequences.
Conclusion and Future Directions
While plan optimization has matured, several "open frontiers" remain. The authors identify a need to understand the "stiffness" of certain plans—why some are harder to optimize than others despite being highly suboptimal. Furthermore, exploring the synergy between cost reduction and flexibility optimization remains a promising area for future research. Interleaving these methods could unlock significantly higher plan quality than treating them as isolated tasks.
Summary updated