Eliminating Redundant Actions from Plans Using Classical Planning

Even though automated planning is PSPACE-complete in general, satisficing planners are able to solve large planning tasks quickly. However, the found plans are often far from optimal and may even contain actions that can be removed while maintaining a valid plan. The problem of finding and eliminating the most expensive set of such redundant actions in a plan is NP-complete and there is a compilation to MaxSAT that solves it. Here, we introduce a simple and natural formulation of the problem as a planning task. Solving it with an optimal planner guarantees finding a minimal reduction. Our experiments show that this is competitive with the previous state of the art for optimal action elimination.