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

AI summary

Overview

Research area: Artificial intelligence planning, specifically generalised planning (GP) and knowledge representation (goal regression, lifted rules, PDDL axioms).

Technical level: Advanced. The paper is framed around formal Definitions, Propositions, Theorems, complexity classes (P, NP-complete, PSPACE-complete), and PDDL-level encodings.

Scope in one sentence: The paper presents a method for synthesising generalised plans — first-order rules that solve families of related planning problems — by optimally solving for individual goals, regressing those goals backwards through the resulting plans, and lifting the results into rules that can be executed directly or used to prune search, with formal soundness, completeness and optimality conditions and experiments on classical and numeric planning domains.

What This Paper Is About

Generalised planning (GP) asks a system to compute a program that solves not just one planning problem but a whole family of related problems drawn from the same domain. Typically the system is given a planning domain plus a set of training problems, and must produce a generalised plan that can be instantiated on unseen test problems. This paper shows that a simple three-step recipe — solve each goal atom of each training problem optimally in some order, perform goal regression over the resulting plans, and lift the outputs into first-order rules — yields generalised plans that can either be executed directly or used to prune the search space, and it proves when those plans are guaranteed to be valid.

Key Contributions

1. Synthesis and instantiation algorithms based on goal regression. The authors introduce algorithms that combine goal regression (Fikes et al. 1972; Waldinger 1977; Lozano-Perez et al. 1984; Reiter 1991; Reiter 2001), problem relaxation, and first-order query techniques. States are treated as databases and lifted rules as queries (Corrêa et al. 2020), so instantiation can use database algorithms. The learned artifacts are called Moose programs, and are implemented in the Moose planner (https://github.com/dillonzchen/moose).

2. Formal soundness and completeness conditions. The paper formalises under what conditions the approach learns sound and complete generalised plans, for both satisficing and optimal planning (Theorems 17 and 18). Theorem 18 states conditions under which encoding Moose programs preserves optimal solutions.

3. Three notions of goal independence plus complexity analysis. The authors define True Goal Independence (TGI), Serialisable Goal Independence (SGI), and Optimal Goal Independence (OGI), together with polynomial variants pTGI, pSGI, and pOGI, and prove the computational complexity of each (Table 1) with proofs in Appendix B.

4. Axiom-based search pruning for optimal planning. Rules, ignoring their precedence values, are encoded as PDDL axioms (Thiébaux et al. 2005) and derived predicates. The paper argues that this avoids writing new solvers, instead relying on existing planners that support the necessary PDDL features.

Main Findings

• A generalised plan is a set of lifted rules with precedence values. A Moose rule is a tuple consisting of free variables, a partial state condition, an unachieved-goal condition, and a sequence of action schemata (which may be a macro action). Each rule carries a precedence value determining execution priority, akin to logic programming. Unlike Yang et al. (2022), who specify a total order on policy rules, Moose specifies a more relaxed partial order.

• Synthesis proceeds by relaxation and order-dependent decomposition. Algorithm 1 iterates over training problems and over a specified number of goal orderings, with a default of 3 permutations. For each ordering it computes an optimal plan for one singleton goal at a time, progresses the state, and extracts rules via Algorithm 2. If no plan exists for the current state and singleton goal pair, no rules are extracted and the state is not progressed.

• Rule extraction is reverse regression plus lifting. Algorithm 2 initialises the to-be-regressed set to the goal, regresses it backwards through the plan, lifts the regressed state, goal, and plan suffix into a rule, and assigns the cost-to-go from the partial state to the goal under the plan suffix as the precedence value.

• Instantiation is a query loop. Algorithm 3 repeatedly queries rules in ascending precedence order (ties broken arbitrarily), grounds a rule whose state condition holds and whose goal condition matches still-unachieved goals, appends the corresponding macro action, and applies it. It returns failure if no rule applies or a cycle is detected.

• The optimality argument is proved under specific conditions. The paper states that the encoding restricts applicable actions at any ground state to the first action of each macro action the rules would generate, and thus prunes the entire search space; the axioms are non-recursive and can be encoded via disjunctive preconditions (Davidson and Garagnani 2002).

• Goal independence results.

  • PlanSat for a GP problem exhibiting TGI is PSPACE-complete (Proposition 8).
  • PlanSat for a GP problem exhibiting SGI is PSPACE-complete (Corollary 9).
  • PlanSat for a GP problem exhibiting pTGI is in P (Proposition 10).
  • PlanSat for a GP problem exhibiting pSGI is NP-complete (Proposition 11).
  • PlanSat for a GP problem exhibiting OGI is PSPACE-complete (Corollary 12).
  • PlanSat for a GP problem exhibiting pOGI is NP-complete (Corollary 13).

  Table 1 summarises this as: TGI — subplans in P; SGI — NP-complete; OGI — NP-complete; with the general (non-polynomial) cases PSPACE-complete throughout.

• Equivalence between problems is defined by a bijection over objects. The relation ~_U holds when a bijection f maps the object sets of two problems, fixes the domain constants, and maps the initial state and goal to one another. Proposition 15 shows ~_U is an equivalence relation; Proposition 16 shows that a sequence of actions is a plan for one problem if and only if its f-image is a plan for the other.

• TGI_C generalisation. For TGI_C problems (TGI with plan lengths bounded by a constant C), the paper states that given sufficiently many training problems, Algorithm 3 using the synthesised program π solves all possible problems with singleton goals. The paper notes that the resulting rule database has finite size but is exponential in the input in the worst case.

• The authors claim large gains over state-of-the-art baselines. The abstract reports "significant improvements over state-of-the-art (generalised) planners" on synthesis cost, planning coverage, and solution quality across various classical and numeric planning domains, in both satisficing and optimal settings, with large margins on Easy-to-Solve, Hard-to-Optimise (ESHO) domains — described as P-time solvable and NP-hard to solve optimally. Specific quantitative results (coverage percentages, synthesis times, plan-quality figures, per-domain tables) are not reported in the available content, which is truncated.

Methodology in Plain English

The approach avoids trying to learn a general program directly over the whole goal. Instead it breaks each training problem into single-goal subproblems and solves them one at a time, in order, with an optimal planner. Because a plan for a single atom is short and focused, it is easier to generalise.

Then it runs that plan backwards: starting from the goal atom, each action is undone — removing its add effects and adding its preconditions — to compute what must have been true before it. Doing this all the way to the start of the plan produces a chain of partial states that are exactly the conditions under which the remaining plan suffix achieves that goal. Those partial states only mention goal-relevant facts (irrelevant facts such as the dog's location are dropped).

Finally, concrete objects appearing in the regressed states, the goal, and the plan suffix are replaced by free variables — the lifting step — producing a rule of the form: in this partial state, when this goal atom is not yet achieved, run this sequence of actions. Because the same goal may be achievable in several orders, the procedure is run for a bounded number of goal permutations (default 3 per problem), accumulating rules with precedence values derived from the cost-to-go.

At run time on an unseen problem, the system simply tries rules in priority order and grounds them against the current state until the goal is met. Alternatively, the rules are compiled into derived predicates and axioms added to the domain, so an existing optimal planner supporting axioms searches only the restricted state space.

Why This Matters

Impact on research. The work connects two historically separate threads — goal regression from the knowledge representation community and problem relaxation from the planning community — into a concrete generalised planner, and it supplies complexity-theoretic characterisation of when such decomposition is tractable. It also gives formal conditions rather than only empirical claims, and it reuses existing PDDL planners instead of requiring new solvers.

Real-world applications.

• Logistics and package delivery: The paper explicitly motivates GP with the observation that UPS delivered over 20 million packages daily across over 200 countries and territories in 2024 (UPS 2025), and that state-of-the-art general-purpose planners struggle to scale to a simplified delivery problem with 100 packages (Taitler et al. 2024).
• Robotic manipulation and mobile robotics: The illustrative domain is a robot that picks up, moves, and puts down items between locations; generalised plans amortise the cost of re-planning across many task instances.
• Numeric planning settings: The approach handles a fragment of numeric planning (definitions deferred to Appendix A), relevant to resource-constrained scheduling and process domains.
• Repeated planning in fixed environments: Any setting where many problems share one domain and recurrent structure — the ESHO class (easy to solve, hard to optimise) described in the paper — benefits from learned rule databases.

Industry relevance. The mechanism of encoding learned rules as PDDL axioms means industrial users can reuse their existing plan libraries and solver stacks; the synthesis cost is paid once, with cheaper instantiation afterwards — the amortisation argument central to the paper's motivation. Rule sets can also prune optimal search, which matters where solution quality is contractual rather than merely convenient.

Future Directions

• Handling domains beyond the goal-independence assumptions. The soundness and completeness guarantees rest on TGI/TGI_C-style structure; extending them to problems requiring genuinely interleaved goal achievement (the classic Sussman anomaly case the paper cites as the historical counterexample) remains open.
• Scaling the rule database. The paper notes the database is finite but exponential in the input in the worst case, raising the question of whether stronger lifting or rule merging can keep synthesis tractable.
• Choosing goal orderings more cleverly. The procedure uses a fixed default of 3 goal permutations per problem; how to select or learn the most informative orderings — and how that interacts with the pSGI/pOGI NP-completeness results — is a natural next question.
• Broadening the numeric fragment and available axiom-supporting planners. The numeric definitions are deferred to Appendix A, and the axiom encoding depends on planners supporting derived predicates and disjunctive preconditions, so generalising to more settings and more solver backends is a logical extension.

Target Audience

Researchers and graduate students in automated planning, knowledge representation and reasoning, and machine learning for planning — particularly those working on generalised planning, policy/rule learning, or plan reuse. It is also relevant to practitioners who build planning systems over large families of related instances and who already run PDDL planners with axiom support, and to readers interested in complexity results that delineate when goal decomposition is tractable versus NP-complete or PSPACE-complete. The paper assumes familiarity with STRIPS/PDDL notation, successor semantics, goal regression, and basic complexity theory; it is not an introductory read.

Authors’ 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 $\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.