Generalized Planning as Program Synthesis

This direction is merged into another direction: combinatorial search space explosion (program synthesis search complexity). Its last version stays readable and citable here.

Version 1 of 121 papers30 conceptsfrozen 2026-10-04

In classical AI planning, the goal is typically to find a specific sequence of actions—a "path"—that leads from a starting state to a goal. While effective for solving a single puzzle or navigating a specific map, these linear plans are fragile; they break the moment the problem size changes or the starting configuration shifts.

A more robust approach, known as Generalized Planning (GP), seeks to discover a single algorithmic solution—a "program"—that can solve an entire class of problems. Instead of a list of steps, the output is a structure containing loops, conditional branches, and procedures. This research direction focuses on a powerful realization: the task of synthesizing these programs can itself be framed and solved as a classical planning problem.

The Planner as a Programmer

The fundamental intuition behind this direction is that "writing a program" is just another sequence of actions in a specialized environment. In this view, a planner doesn't just move blocks; it moves a "program counter" and assigns instructions to lines of code.

As Anders Jonsson and Sergio Jiménez demonstrate in Computing Plans with Control Flow and Procedures Using a Classical Planner, we can compile the program synthesis task into a standard Planning Domain Definition Language (PDDL) model. In this model:

  • Fluents represent the lines of the program and the current state of the "computer" (e.g., a call stack or pointers).
  • Actions represent the act of "programming" a line with a domain-specific instruction (like move-forward), a conditional jump (if condition goto line X), or a termination command.

By defining the goal as "satisfy the requirements of all provided example instances," off-the-shelf classical planners can search for a valid sequence of programming actions. The result is a compact, reusable algorithm that captures the underlying logic of the domain rather than just a specific solution path.

From Linear Steps to Recursive Controllers

While simple loops allow a plan to handle variable-length lists, more complex domains—like tree traversals or nested structures—require hierarchy and recursion.

To address this, Javier Segovia-Aguas and colleagues introduced Hierarchical Finite State Controllers (HFSCs). In Computing Hierarchical Finite State Controllers With Classical Planning, they show how to compile the search for these controllers into classical planning. By incorporating a call stack into the planning state, the system can synthesize recursive procedures where a controller calls itself. This allows a single, small program to perform complex tasks like depth-first search on trees of any depth.

This shift from flat sequences to hierarchical structures mirrors the evolution of programming languages, moving from assembly-like goto statements to modular, procedural logic.

Why It Works: The Power of Small Examples

A striking finding in this field is the efficiency of generalization. In Computing Programs for Generalized Planning as Heuristic Search, the authors show that a program synthesized to solve a tiny instance (e.g., sorting a list of just six elements) often generalizes perfectly to instances orders of magnitude larger.

This works because the search space for a program is often much smaller and more constrained than the state space of the problem it solves. By using heuristic search—specifically the BFGP algorithm—researchers can navigate the space of possible program structures. Because the program must satisfy both positive examples (what to do) and negative examples (what to avoid), as explored in Generalized Planning with Positive and Negative Examples, the search is guided toward the most robust and minimal logical structure.

Beyond Planning: A Unified View of Induction

The "planning as synthesis" framing has proven surprisingly versatile, extending beyond robot paths into broader areas of computer science:

  1. Grammar Induction: In Generating Context-Free Grammars using Classical Planning, the researchers treat the discovery of recursive linguistic rules as a generalized planning task, allowing a planner to "learn" a grammar from a single example string.
  2. Unsupervised Learning: The work on Unsupervised Classification of Planning Instances reformulates clustering as a planning problem. The planner must synthesize "prototype programs" that act as cluster representatives, effectively performing structured induction through search.
  3. Logic Programming: By combining these ideas with Meta-Interpretive Learning, as seen in the work of Thomas Eiter on HEX-programs, the field bridges the gap between high-level symbolic reasoning and efficient state-space search.

Ultimately, this research direction suggests that the "pipe dream" of analogical planning first described by Diane J. Cook is achievable by treating the synthesis of procedural knowledge not as a separate "learning" task, but as a highly optimized search for the right sequence of instructions.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_generalized_planning_as_program_synthesi_1dc6da04,
  title = {Generalized Planning as Program Synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generalized-planning-as-program-synthesis/rdr_1dc6da04ed9448d99e4a8d1df135c015},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_generalized_planning_as_program_synthesi_1dc6da04_v1,
  title = {Generalized Planning as Program Synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generalized-planning-as-program-synthesis/rdr_1dc6da04ed9448d99e4a8d1df135c015/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}