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.
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.
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