Satisficing and Optimal Generalised Planning via Goal Regression (Extended Version)

Dillon Z. Chen, Till Hofmann, Toryn Q. Klassen, Sheila A. McIlraith · 2025

Read Satisficing and Optimal Generalised Planning via Goal Regression (Extended Version) by Dillon Z. Chen, Till Hofmann, Toryn Q. Klassen, Sheila A. McIlraith (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-11095.txt.

Introduction

Dillon Chen, Till Hofmann, and their colleagues introduce a simple method for generalised planning, the task of writing one program that solves a whole family of like planning problems. Hand-writing such a program is hard, and search-based tools can be slow to build one. Their method learns the program from solved examples instead of searching blindly.

For each training problem, they compute a best plan for each goal fact in turn and run goal regression, which works backward from the goal through the plan. The outputs lift into first-order rules that form the shared plan. Tests show gains in build cost, coverage, and plan quality over leading planners.

Catalog record

CREATORDillon Z. Chen, Till Hofmann, Toryn Q. Klassen, Sheila A. McIlraith
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-11095

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Satisficing and Optimal Generalised Planning via Goal Regression (Extended Version) Dillon Z. Chen, Till Hofmann, Toryn Q. Klassen, Sheila A. McIlraith Abstract 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 Condition → \rightarrow 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. 1 Introduction Generalised planning (GP) aims to compute generalised plans: programs that solve families of related planning problems. A grand goal of GP is to amortise synthesis costs by solving families of planning problems faster than general-purpose planners that solve each problem individually. Indeed, there exists several planning domains that are computationally easy to solve and exhibit satisficing policies, such as variants of the package delivery domain ( 37 ) . In the real world, UPS {}^{\text{TM}} delivered over 20 million packages daily across over 200 countries and territories in 2024 ( 83 ) . However, state-of-the-art, general-purpose planners struggle to scale up to a simplified version of the delivery problem with 100 packages ( 79 ) . We consider the GP problem that consists of a planning domain \mathcal{D} , and a set of training problems \mathscr{P}_{\text{train}} and testing problems \mathscr{P}_{\text{test}} drawn from \mathcal{D} , as depicted in Figure 1 . A generalised planner synthesises a generalised plan from \mathcal{D} and \mathscr{P}_{\text{train}} that solves problems in \mathscr{P}_{\text{test}} . Metrics for evaluating the effectiveness of a generalised planner ( 75 ) include the resources it takes to synthesise a generalised plan ( synthesis cost ), the time it takes to instantiate generalised plans on unseen problems ( instantiation cost ), and the quality of instantiated plans ( solution quality ). Figure 1: A common GP setup consisting of a planning domain \mathcal{D} , and a set of training problems \mathscr{P}_{\text{train}} and testing problems \mathscr{P}_{\text{test}} . A generalised planner consists of two modules: (1) synthesis and (2) instantiation. See text for details. In this paper, we introduce a new generalised planner that draws upon insights and long-standing ideas of goal regression from the knowledge representation community and problem relaxation from the planning community to advance the state of the art in GP over the three aforementioned metrics. Our approach consists of an efficient three step process of (1) solving for each goal of each problem in \mathscr{P}_{\text{train}} optimally in an arbitrary order, (2) performing goal regression ( 25 ; 84 ; 53 ; 59 ; 60 ) over the resulting plans, and (3) lifting the corresponding partial-state, macro-action pairs into sets of first-order rules constituting a generalised plan. We treat planning states as databases ( 18 ) and lifted rules as queries, and correspondingly employ database algorithms for instantiating generalised plans quickly on problems in \mathscr{P}_{\text{test}} . We also leverage derived predicates and axioms to encode learned rules for state space pruning in search. Figure 2: Left: a simplified STRIPS transportation domain. Middle: state progression (purple) and goal regression (yellow) via a putDown action. Right: the generalised plan created by lifting the regressed states, goal condition, and plan actions. We formalise the conditions under which our approach learns sound and complete generalised plans, and under which the encoding of learned rules as axioms gives rise to provably optimal plans when combined with optimal search planners. We manifest our contributions in the Moose planner 1 1 1 Available at https://github.com/dillonzchen/moose and conduct experiments with Moose on classical and numeric planning domains and satisficing and optimal planning settings. We observe that Moose outperforms state-of-the-art baseline planners by large margins on Easy-to-Solve, Hard-to-Optimise (ESHO) planning domains — \mathsf{P} -time solvable and \mathsf{NP} -hard to solve optimally domains. We summarily list our contributions as follows. • We introduce algorithms for synthesising and instantiating generalised plans that employ goal regression, problem relaxation, and first-order query techniques. • We formalise the conditions under which our approach is sound and complete for satisficing and optimal planning. • We conduct experiments and demonstrate the effectiveness of our algorithms in satisficing and optimal planning over various classical and numeric planning domains. 2 Planning Background and Notation We adopt standard notation for representing planning problems via the STRIPS fragment of the Planning Domain Definition Language (PDDL) ( 55 ; 33 ) . Our approach also handles a fragment of numeric planning but we defer such definitions to Appendix A . Mathematical Notation Let \mathbb{N} / \mathbb{N}_{0} denote the natural numbers excluding/including 0, \vec{\alpha} denote an ordered sequence of items, \vec{\alpha}_{i} denote the i th element of \vec{\alpha} , \vec{\alpha}_{[i:]} all elements from the i th element onwards in \vec{\alpha} inclusive, and \left|s\right| the size of a set or length of a sequence s . STRIPS Planning A planning problem is represented by two components: a domain, consisting of lifted predicates and action schemata describing the action theory, and a problem specification, consisting of a finite set of objects, an initial state, and a goal condition. A planning domain is a tuple \mathcal{D}=\left<\mathcal{P},\mathcal{C},\mathcal{A}\right> , where \mathcal{P} is a set of predicates, \mathcal{C} a set of constant objects, and \mathcal{A} a set of action schemata. A predicate p\in\mathcal{P} has a set of argument terms x_{1},\ldots,x_{n_{p}} where n_{p}\in\mathbb{N}_{0} depends on p . An action schema a\in\mathcal{A} is a tuple a=\left<\mathit{var}(a),\mathit{pre}(a),\mathit{add}(a),\mathit{del}(a)\right> where \mathit{var}(a) is a set of parameter variables, and preconditions \mathit{pre}(a) , add \mathit{add}(a) and delete \mathit{del}(a) effects are finite sets of predicates from \mathcal{P} with arguments instantiated with variables or objects from \mathit{var}(a)\cup\mathcal{C} . Example 1 (Transportation Domain) . We can model a simplified transportation domain where an agent can transport items between locations in STRIPS, partially depicted in Figure 2 , as follows. We define a domain \mathcal{D}=\left<\mathcal{P},\mathcal{C},\mathcal{A}\right> with \mathcal{P}=\{\mathit{at}(\mathit{?x},\mathit{?y}),\allowbreak\mathit{atRobot}(\mathit{?x}),\allowbreak\mathit{handFree}(),\allowbreak\mathit{holding}(\mathit{?x})\} , \mathcal{C}=\emptyset , and \mathcal{A} containing the three action schemata: \mathit{putDown} \displaystyle\mathit{var} \displaystyle=\{\mathit{?obj},\mathit{?loc}\} \displaystyle\mathit{pre} \displaystyle=\{\mathit{atRobot}(\mathit{?loc}),\mathit{holding}(\mathit{?obj})\} \displaystyle\mathit{add} \displaystyle=\{\mathit{at}(\mathit{?obj},\mathit{?loc}),\mathit{handFree}()\} \displaystyle\mathit{del} \displaystyle=\{\mathit{holding}(\mathit{?obj})\} \mathit{move} \displaystyle\mathit{var} \displaystyle=\{\mathit{?from},\mathit{?to}\} \displaystyle\mathit{pre} \displaystyle=\{\mathit{atRobot}(\mathit{?from})\} \displaystyle\mathit{add} \displaystyle=\{\mathit{atRobot}(\mathit{?to})\} \displaystyle\mathit{del} \displaystyle=\{\mathit{atRobot}(\mathit{?from})\} \mathit{pickUp} \displaystyle\mathit{var} \displaystyle=\{\mathit{?obj},\mathit{?loc}\} \displaystyle\mathit{pre} \displaystyle=\{\mathit{atRobot}(\mathit{?loc}),\mathit{at}(\mathit{?obj},\mathit{?loc}),\mathit{handFree}()\} \displaystyle\mathit{add} \displaystyle=\{\mathit{holding}(\mathit{?obj})\} \displaystyle\mathit{del} \displaystyle=\{\mathit{at}(\mathit{?obj},\mathit{?loc}),\mathit{handFree}()\} A planning problem is a tuple \mathbf{P}=\left<\mathcal{D},s_{0},g,{O}\right> with \mathcal{D} a planning domain, s_{0} the initial state, g the goal condition, and {O}\supseteq\mathcal{C} a finite set of objects. A (ground) atom is a predicate whose argument terms are all instantiated with objects. A state in a planning problem is a set of atoms and operate under the closed world assumption: any atom not in a state is presumed false. The initial state s_{0} and goal condition g are both sets of atoms. A state s is a goal state if g\subseteq s . We say that the problem \mathbf{P} belongs to the domain \mathcal{D} . A (ground) action is an action schema a where each parameter term is instantiated

Read the complete text