Synthesizing Algorithmic Strategies for Planning Domains

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 298 papers104 conceptsfrozen 2026-10-04

In classical artificial intelligence, planning is often treated as a search for a specific sequence of actions. If you want a robot to clear a stack of three blocks, a planner finds the exact moves to relocate Block C, then B, then A. However, if you hand that same robot a stack of four blocks, it is effectively "blind"—it must re-run the entire search process from scratch.

Generalized Planning (GP) shifts the goal from finding a sequence to finding a strategy. Instead of a one-off path, GP aims to synthesize a single program or policy that can solve every possible instance within a domain, regardless of the number of objects or the initial configuration.

From Sequences to Programs

The fundamental insight of generalized planning is that many tasks are algorithmic in nature. Solving a Rubik's Cube or sorting a list doesn't just require a path; it requires a procedure. Early work by Richard E. Korf demonstrated this by learning "macro-operators"—sequences of moves that achieve subgoals without disturbing previous progress—allowing systems to solve complex puzzles by following a strategic recipe rather than an exhaustive search.

To handle an arbitrary number of objects, a plan must be able to "loop." Researchers like Javier Segovia-Aguas, Sergio Jiménez, and Anders Jonsson pioneered techniques to represent plans as programs with control flow, such as Hierarchical Finite State Controllers. By treating the synthesis of these programs as a planning problem itself, they enabled off-the-shelf classical planners to "write" code—complete with loops and recursion—that solves entire families of tasks.

Abstraction and Qualitative Reasoning

How can a single rule apply to both three blocks and a million blocks? The answer lies in abstraction.

If a planner views the world through specific object IDs, it is trapped in the details. However, if it views the world through qualitative properties—such as "is the stack empty?" or "are there more packages to deliver?"—the problem scale becomes irrelevant. Blai Bonet and Hector Geffner developed Qualitative Numeric Planning (QNP), which abstracts numerical quantities into simple boolean indicators (e.g., $n=0$ or $n>0$).

This abstraction allows researchers to reduce complex generalized problems into Fully Observable Non-Deterministic (FOND) problems. In this view, picking an "arbitrary" block is treated as a non-deterministic choice; if a strategy works regardless of which block the environment "chooses" to give the robot, that strategy is truly universal.

Learning Generalization from Small Examples

A recurring theme in recent work is the ability to learn these universal rules from "tiny" training data. Because the underlying logic of a domain (like "stacking") is the same regardless of scale, a system can observe a few optimal plans on small instances and "lift" that logic into a general rule.

  • Logic-Based Synthesis: Kaisheng Wu and Yongmei Liu 0001 use SMT solvers and counterexample-guided refinement to prove that a strategy will work for infinitely many game instances.
  • Neural Relational Policies: Sankalp Garg and Aniket Bajpai introduced SYMNET, which uses Graph Neural Networks (GNNs) to learn policies that are "size-invariant," meaning a model trained on small grids can immediately solve much larger ones in a single forward pass.
  • LLM-Guided Planning: Modern approaches explore using Large Language Models to bridge the gap. Tom Silver and colleagues have shown that LLMs can help synthesize PDDL strategies that generalize across domains, while Dillon Z. Chen uses goal regression to lift optimal plans into first-order rules.

Why It Works: The Power of Lifting

The "secret sauce" of generalized planning is lifting. In standard planning, everything is "grounded" (e.g., Move(BlockA, BlockB)). In generalized planning, everything is "lifted" (e.g., Move(x, y) where x is the top block).

As Roni Khardon noted in his work on symbolic dynamic programming, by reasoning about variables and classes of objects rather than individuals, we can solve stochastic and deterministic problems once and for all. Whether the world contains ten objects or ten million, the symbolic logic remains the same.

By moving from searching for paths to synthesizing programs, generalized planning provides the blueprint for agents that don't just solve tasks, but understand the underlying "how-to" of the domains they inhabit.

Papers in this version

Showing 60 of 98 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 79 papers
  2. Version 1 · 2026-10-04 · 98 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_generalized_planning_bc0dc6b7,
  title = {generalized planning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generalized-planning/rdr_bc0dc6b72e3d45a7a8615b2ba20c303b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_synthesizing_algorithmic_strategies_for__bc0dc6b7_v1,
  title = {Synthesizing Algorithmic Strategies for Planning Domains},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/synthesizing-algorithmic-strategies-for-planning-domains/rdr_bc0dc6b72e3d45a7a8615b2ba20c303b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}