Finding Minimal Plan Reductions Using Classical Planning

Abstract

While classical planning research has made tremendous progress in the last decades, many complex tasks can still only be solved suboptimally. The satisficing plans found for these tasks often contain actions that can be removed while maintaining plan validity. Removing such redundant actions is desirable since it can decrease the plan cost and simplify the plan. Reducing a plan to a minimum-cost plan without redundant actions is NP-complete and previous work addressed this problem with a compilation to weighted MaxSAT. In this work, we propose several simple and natural formulations to encode this problem as a classical planning task, and prove that solving the resulting tasks optimally guarantees finding minimal plan reductions. We analyze the relation of the classical planning formulations to the MaxSAT compilation, and prove theoretical properties of the known concept of plan action landmarks. Finally, we evaluate the new approaches experimentally and show that they are competitive with the previous state of the art in minimal plan reduction.