Eliminating All Redundant Actions from Plans Using SAT and MaxSAT
Tomáš Balyo, Lukáš Chrpa · University of Huddersfield Repository (University of Huddersfield) · 2014
Satisfiability (SAT) techniques are often successfully used for solving planning problems.In this paper we show, that SAT and maximum satisfiability (MaxSAT) can be also used for post-processing optimization of plans.We will restrict ourselves to improving plans by removing redundant actions from them which is a special case of plans optimization.There exist polynomial algorithms for removing redundant actions, but none of them can remove all such actions since guaranteeing that a plan does not contain redundant actions is NP-complete.We introduce two new algorithms, based on SAT and MaxSAT, which remove all redundant actions.The MaxSAT based algorithm additionally guarantees to remove a maximum set of redundant actions.We test the described algorithms on plans obtained by state-of-the-art planners on IPC 2011 benchmarks.The proposed algorithms are very fast for these plans despite the complexity results.