Satisficing and Optimal Generalised Planning via Goal Regression (Extended Version)
This addresses the challenge of efficient generalised planning for AI systems, offering a method that can be used for direct execution or search space pruning, though it appears incremental in its approach.
The authors tackled the problem of synthesizing programs that solve families of related planning problems by introducing a novel method based on goal regression, which computes optimal plans for training problems and lifts them to first-order rules. The result showed significant improvements over state-of-the-art planners in synthesis cost, planning coverage, and solution quality across various domains.
Generalised planning (GP) refers to the task of synthesising programs that solve families of related planning problems. We introduce a novel, yet simple method for GP: given a set of training problems, for each problem, compute an optimal plan for each goal atom in some order, perform goal regression on the resulting plans, and lift the corresponding outputs to obtain a set of first-order $\textit{Condition} \rightarrow \textit{Actions}$ rules. The rules collectively constitute a generalised plan that can be executed as is or alternatively be used to prune the planning search space. We formalise and prove the conditions under which our method is guaranteed to learn valid generalised plans and state space pruning axioms for search. Experiments demonstrate significant improvements over state-of-the-art (generalised) planners with respect to the 3 metrics of synthesis cost, planning coverage, and solution quality on various classical and numeric planning domains.