Classical automated planning typically operates on a fixed, grounded state space. If you ask a classical planner to clear a table of three blocks, it outputs a linear sequence of actions tailored precisely to those three blocks. However, if a fourth block is added, or if the initial configuration changes slightly, this plan breaks completely, requiring the solver to recompute a solution from scratch.
As Blai Bonet et al. observe in Policies that Generalize: Solving Many Planning Problems with the Same Policy, human-designed rules—like a vacuum cleaner moving right until it hits a wall—work regardless of whether a room is 5 meters or 50 meters long. The goal of generalized planning is to automatically synthesize these universal, instance-independent strategies that capture the underlying logic of a domain rather than the specifics of a single problem instance.
Mapping Infinite Worlds to Finite Abstractions
The core reason generalized planning works is abstraction. Instead of tracking the unique identity of every object in a massive or infinite state space, generalized planners group similar objects into equivalence classes, effectively reducing an infinite family of problems into a compact, solvable model.
For example, León Illanes et al. introduced LOOM in Generalized Planning via Abstraction: Arbitrary Numbers of Objects, which treats the selection of identical objects as a form of non-determinism. By forcing the planner to find a strategy that succeeds regardless of which specific object is chosen, the system naturally discovers rules that scale to an arbitrary number of items.
Similarly, Zheyuan Shi et al. formalize this by identifying "baggable types"—groups of objects that are completely indistinguishable within certain contexts—to automatically compile large-scale problems into sound and complete abstract models (An Automatic Sound and Complete Abstraction Method for Generalized Planning with Baggable Types).
From Linear Sequences to Algorithmic Programs
To handle variable scales and object counts, a generalized plan cannot be a simple list of actions; it must resemble a computer program equipped with loops and conditional branches.
One powerful way to achieve this is by repurposing existing classical tools. Anders Jonsson et al. demonstrated in Computing Plans with Control Flow and Procedures Using a Classical Planner that the program synthesis process itself can be compiled into a classical planning problem. By treating control flow mechanisms like goto statements and procedural calls as actions within the planning environment, an off-the-shelf planner can discover compact, loopy programs that solve entire problem classes.
Alternatively, the search for these programs can be framed as a logical optimization problem. Blai Bonet et al. utilize Description Logic and Weighted Max-SAT formulations to learn general planning policies from a handful of small examples without requiring any human supervision or gold-standard plans (Learning General Planning Policies from Small Examples Without Supervision).
Proving Correctness and Termination
Introducing loops into plans creates a major theoretical and practical challenge: how do we guarantee that a generalized plan won't get stuck in an infinite loop?
To prove termination across unbounded domains, researchers often reduce generalized planning to numerical or non-deterministic frameworks. Blai Bonet et al. showed that Qualitative Numeric Planning (QNP)—where numerical variables are incremented or decremented qualitatively rather than quantitatively—is computationally equivalent to Fully Observable Non-Deterministic (FOND) planning (Qualitative Numeric Planning: Reductions and Complexity). This equivalence allows powerful, off-the-shelf FOND solvers to verify that a loopy policy will safely terminate.
Another foundational approach, pioneered by Siddharth Srivastava et al., adapts 3-valued logic and canonical abstraction from static program analysis to track abstract counts, providing mathematical proofs of correctness for plans operating on an unbounded number of objects (Using Abstraction for Generalized Planning).
Neural Relational Generalization
While symbolic methods offer strong mathematical guarantees, recent work has extended generalized planning into the neural domain to bypass manual feature engineering and exploit structural symmetries.
Instead of learning explicit programmatic rules, these approaches learn size-invariant neural representations over relational graphs. Sankalp Garg developed SYMNET, a domain-independent neural relational planner that maps symbolic logic into instance graphs, allowing a single network to solve scaled-up versions of a problem in a single forward pass without retraining (Symbolic Network: Generalized Neural Policies for Relational MDPs).
To guide these searches across completely unseen environments, William Shen et al. introduced hypergraph networks to extract domain-independent heuristics entirely from scratch (Learning Domain-Independent Planning Heuristics with Hypergraph Networks). This direction was further advanced by Dillon Z. Chen through "lifted" graph representations that avoid the need for full problem grounding, enabling neural models to generalize from tiny training examples to massive planning problems (Learning Domain-Independent Heuristics for Grounded and Lifted Planning).