Satisficing and Optimal Generalised Planning via Goal Regression

Generalised planning (GP) refers to the task of synthesising programs that can solve families of related problems. In this paper, we describe a novel, yet simple method for GP: given a set of training problems, compute a plan for each single goal atom optimally in some order for each problem, perform goal regression on the resulting plans, and lift the corresponding partial-state, action pairs to obtain a set of first-order rules. The lifted rules can be executed as is, or encoded as planning axioms for state space pruning during search. We formalise and prove the conditions under which this method is guaranteed to learn sound and complete generalised plans, and when state space pruning returns optimal plans when used in 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.