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

• URL: http://arxiv.org/abs/2511.11095v1
• Date: Fri, 14 Nov 2025 09:16:32 GMT
• Title: Satisficing and Optimal Generalised Planning via Goal Regression (Extended Version)
• Authors: Dillon Z. Chen, Till Hofmann, Toryn Q. Klassen, Sheila A. McIlraith,
• Abstract summary: Generalised planning (GP) refers to the task of synthesising programs that solve families of related planning problems.<n>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.<n>We formalise and prove the conditions under which our method is guaranteed to learn valid generalised plans and state space pruning axioms for search.
• Score: 16.43772461453855
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• TodoEvolve: Learning to Architect Agent Planning Systems [68.48983335970901]
  TodoEvolve is a meta-planning paradigm that autonomously synthesizes and dynamically revises task-specific planning.<n>PlanFactory provides a common interface for heterogeneous planning patterns.<n>TodoEvolve consistently surpasses carefully engineered planning modules while maintaining economical API costs and runtime overhead.
  arXiv  Detail & Related papers  (2026-02-08T06:37:01Z)
• Closing the Train-Test Gap in World Models for Gradient-Based Planning [64.36544881136405]
  We propose improved methods for training world models that enable efficient gradient-based planning.<n>At test time, our approach outperforms or matches the classical gradient-free cross-entropy method.
  arXiv  Detail & Related papers  (2025-12-10T18:59:45Z)
• Planning with Minimal Disruption [9.722824469961925]
  In many planning applications, we might be interested in finding plans that minimally modify the initial state to achieve the goals.<n>In this paper, we formally introduce it, and define various planning-based compilations that aim to jointly optimize both the sum of action costs and plan disruption.
  arXiv  Detail & Related papers  (2025-08-21T08:38:17Z)
• Parallel Strategies for Best-First Generalized Planning [51.713634067802104]
  Generalized planning (GP) is a research area of AI that studies the automated synthesis of algorithmic-like solutions capable of solving multiple classical planning instances. One of the current advancements has been the introduction of Best-First Generalized Planning (BFGP), a GP algorithm based on a novel solution space that can be explored with search. This paper evaluates the application of parallel search techniques to BFGP, another critical component in closing the performance gap.
  arXiv  Detail & Related papers  (2024-07-31T09:50:22Z)
• Learning adaptive planning representations with natural language guidance [90.24449752926866]
  This paper describes Ada, a framework for automatically constructing task-specific planning representations. Ada interactively learns a library of planner-compatible high-level action abstractions and low-level controllers adapted to a particular domain of planning tasks.
  arXiv  Detail & Related papers  (2023-12-13T23:35:31Z)
• Planning as In-Painting: A Diffusion-Based Embodied Task Planning Framework for Environments under Uncertainty [56.30846158280031]
  Task planning for embodied AI has been one of the most challenging problems. We propose a task-agnostic method named 'planning as in-painting' The proposed framework achieves promising performances in various embodied AI tasks.
  arXiv  Detail & Related papers  (2023-12-02T10:07:17Z)
• Lifted Sequential Planning with Lazy Constraint Generation Solvers [28.405198103927955]
  This paper studies the possibilities made open by the use of Lazy Clause Generation (LCG) based approaches to Constraint Programming (CP) We propose a novel CP model based on seminal ideas on so-called lifted causal encodings for planning as satisfiability. We report that for planning problem instances requiring fewer plan steps our methods compare very well with the state-of-the-art in optimal sequential planning.
  arXiv  Detail & Related papers  (2023-07-17T04:54:58Z)
• Novelty and Lifted Helpful Actions in Generalized Planning [14.513354207511151]
  We introduce the notion of action novelty rank, which computes novelty with respect to a planning program. We propose novelty-based generalized planning solvers, which prune a newly generated planning program if its most frequent action repetition is greater than a given bound $v$.
  arXiv  Detail & Related papers  (2023-07-03T03:44:12Z)
• Robust Hierarchical Planning with Policy Delegation [6.1678491628787455]
  We propose a novel framework and algorithm for hierarchical planning based on the principle of delegation. We show this planning approach is experimentally very competitive to classic planning and reinforcement learning techniques on a variety of domains.
  arXiv  Detail & Related papers  (2020-10-25T04:36:20Z)
• Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
  We consider alternatives to an implicit sequential planning assumption. We propose Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS) for approximating the optimal plan. We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds.
  arXiv  Detail & Related papers  (2020-04-23T18:08:58Z)
• STRIPS Action Discovery [67.73368413278631]
  Recent approaches have shown the success of classical planning at synthesizing action models even when all intermediate states are missing. We propose a new algorithm to unsupervisedly synthesize STRIPS action models with a classical planner when action signatures are unknown.
  arXiv  Detail & Related papers  (2020-01-30T17:08:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.