Generalized planning as heuristic search: A new planning search-space that leverages pointers over objects

Javier Segovia-Aguas, Sergio Jiménez Celorrio, Anders Jonsson

Abstract

Generalized Planning (GP) seeks to discover single algorithmic solutions—programs with loops and branches—capable of solving all instances within a specific domain. This paper introduces a novel framework that treats GP as a heuristic search problem. By leveraging a pointer-based representation and grounding-free heuristics, the authors present Best-First Generalized Planning (BFGP), an algorithm capable of synthesizing complex programs like Selection Sort and the Sieve of Eratosthenes. This approach avoids the "grounding bottleneck" of classical planning, allowing for solutions that generalize across varying instance sizes.

Introduction: Beyond Sequence Planning

In classical automated planning, an agent identifies a specific sequence of actions to reach a goal from a fixed initial state. While effective for individual tasks, these solutions lack flexibility; a plan to stack three blocks cannot be directly applied to a four-block scenario. Generalized Planning (GP) addresses this limitation by aiming for "algorithmic" solutions that solve entire problem classes regardless of the number of objects involved.

Generalized planning aims to find a single program that transforms various initial states into a common goal state format, such as sorting lists of different lengths.

The primary challenge in GP has been the inability to apply successful classical techniques, like heuristic search, due to the requirement of "grounding" (pre-calculating all possible states and actions). This paper proposes a paradigm shift: searching through the space of programs rather than action sequences.

Methodology: Pointers and Program Spaces

The authors introduce three core innovations to enable heuristic search in GP:

1. Pointer-based Representation

Inspired by the Random-Access Machine (RAM) model, states are represented using pointers over objects. Instead of hard-coding references to specific entities (e.g., "Block A"), the planner utilizes pointers (e.g., "the object at index $i$"). This abstraction ensures that the resulting logic is independent of the specific instance size or object count.

2. A Novel Search Space

The search space is defined by partially specified planning programs. Each node in the search tree represents a program where certain lines remain unwritten. Crucially, the complexity of this search space scales with the number of program lines and pointers, rather than the size of the planning instances themselves.

3. Best-First Generalized Planning (BFGP)

The BFGP algorithm navigates this program space using grounding-free heuristics. These heuristics evaluate candidate programs based on two criteria:

  • Structural Priors: A preference for simpler, more concise programs (applying Occam’s Razor).
  • Empirical Performance: The candidate program is executed on small sample instances. The heuristic measures progress toward the goal (e.g., using Euclidean distance for numerical objectives) to guide the search.

Evaluation and Key Results

The BFGP approach was tested against a variety of benchmarks, ranging from classical planning domains (Gripper, Blocksworld) to complex algorithmic tasks like the Sieve of Eratosthenes and list sorting.

Visualization of a synthesized algorithmic structure, demonstrating the complex logical dependencies the BFGP algorithm can discover.

The results demonstrate significant advancements:

  • Algorithmic Discovery: BFGP successfully synthesized well-known algorithms from scratch, including Selection Sort.
  • Scalability: By avoiding grounding, BFGP outperformed previous compilation-based solvers, finding solutions in seconds for domains where prior methods timed out.
  • Generalization: Programs "learned" on tiny instances (e.g., lists of size 10) validated perfectly on massive instances (e.g., lists of 100+ elements), proving the pointer-based representation captures the underlying domain logic.

Conclusion and Future Directions

This research bridges the gap between automated planning and program synthesis. While BFGP represents a major step forward, challenges remain. The search space still grows exponentially with program length, and the heuristics can struggle with problems requiring complex intermediate sub-goals. Future work will explore incorporating higher-level programming constructs (like FOR loops) and extending the framework to continuous variables suitable for robotics.

Summary updated

Abstract

Planning as heuristic search is one of the most successful approaches to classical planning but unfortunately, it does not trivially extend to Generalized Planning (GP); GP aims to compute algorithmic solutions that are valid for a set of classical planning instances from a given domain, even if these instances differ in their number of objects, the initial and goal configuration of these objects and hence, in the number (and possible values) of the state variables. State-space search, as it is implemented by heuristic planners, becomes then impractical for GP. In this paper we adapt the planning as heuristic search paradigm to the generalization requirements of GP, and present the first native heuristic search approach to GP. First, the paper introduces a new pointer-based solution space for GP that is independent of the number of classical planning instances in a GP problem and the size of those instances (i.e. the number of objects, state variables and their domain sizes). Second, the paper defines an upgraded version of our GP algorithm, called Best-First Generalized Planning (BFGP), that implements a best-first search in our pointer-based solution space for GP. Lastly, the paper defines a set of evaluation and heuristic functions for BFGP that assess the structural complexity of the candidate GP solutions, as well as their fitness to a given input set of classical planning instances. The computation of these evaluation and heuristic functions does not require grounding states or actions in advance. Therefore our GP as heuristic search approach can handle large sets of state variables with large numerical domains, e.g. integers.
BibTeX
@article{segoviaaguas2024generalized,
  author = {Javier Segovia-Aguas and Sergio Jiménez Celorrio and Anders Jonsson},
  title = {{Generalized planning as heuristic search: A new planning search-space that leverages pointers over objects}},
  journal = {Artificial Intelligence},
  year = {2024},
  doi = {10.1016/j.artint.2024.104097},
}
Figure