Finding Minimal Plan Reductions Using Classical Planning

Filiación correcta para investigadores uc3m: Universidad Carlos III de Madrid
Published: Oct 6, 2025

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

Finding Minimal Plan Reductions Using Classical Planning Articles