# Scaling-up Generalized Planning as Heuristic Search with Landmarks

arXiv: https://arxiv.org/abs/2205.04850 · HTML: https://mlsanity.com/paper/2205.04850/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 43 references that are in the map.
- First posted on arXiv 10 May 2022.

## Builds on (most cited first, 7 of 7)

- [Mastering Atari with Discrete World Models](https://mlsanity.com/paper/2010.02193/) (2020)
- [The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks](https://mlsanity.com/paper/1401.3839/) (2014)
- [ASNets: Deep Learning for Generalised Planning](https://mlsanity.com/paper/1908.01362/) (2019)
- [Learning Features and Abstract Actions for Computing Generalized Plans](https://mlsanity.com/paper/1811.07231/) (2018)
- [Learning Generalized Relational Heuristic Networks for Model-Agnostic Planning](https://mlsanity.com/paper/2007.06702/) (2020)
- [Generalized Planning as Heuristic Search](https://mlsanity.com/paper/2103.14434/) (2021)
- [Learning General Policies from Small Examples Without Supervision](https://mlsanity.com/paper/2101.00692/) (2021)

## Built on by (most cited first, 14 of 14)

- [Generalized Planning for the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2401.07426/) (2024)
- [Generalized Planning as Heuristic Search: A new planning search-space that leverages pointers over objects](https://mlsanity.com/paper/2301.11087/) (2023)
- [Novelty and Lifted Helpful Actions in Generalized Planning](https://mlsanity.com/paper/2307.00735/) (2023)
- [Graph Learning for Numeric Planning](https://mlsanity.com/paper/2410.24080/) (2024)
- [Hierarchical Decomposition and Analysis for Generalized Planning](https://mlsanity.com/paper/2212.02823/) (2022)
- [Computing Programs for Generalized Planning as Heuristic Search](https://mlsanity.com/paper/2205.06259/) (2022)
- [Deep Learning for Generalised Planning with Background Knowledge](https://mlsanity.com/paper/2410.07923/) (2024)
- [Weisfeiler-Leman Features for Planning: A 1,000,000 Sample Size Hyperparameter Study](https://mlsanity.com/paper/2508.18515/) (2025)
- [Representation and Synthesis of C++ Programs for Generalized Planning](https://mlsanity.com/paper/2206.14480/) (2022)
- [Relevance Score: A Landmark-Like Heuristic for Planning](https://mlsanity.com/paper/2403.07510/) (2024)
- [Synthesis of Procedural Models for Deterministic Transition Systems](https://mlsanity.com/paper/2307.14368/) (2023)
- [Revisiting Landmarks: Learning from Previous Plans to Generalize over Problem Instances](https://mlsanity.com/paper/2508.21564/) (2025)
- [From domain-landmark graph learning to problem-landmark graph generation](https://mlsanity.com/paper/2509.17062/) (2025)
- [Multi Graph Search for High-Dimensional Robot Motion Planning](https://mlsanity.com/paper/2602.12096/) (2026)

## Abstract (arXiv)

Landmarks are one of the most effective search heuristics for classical planning, but largely ignored in generalized planning. Generalized planning (GP) is usually addressed as a combinatorial search in a given space of algorithmic solutions, where candidate solutions are evaluated w.r.t.~the instances they solve. This type of solution evaluation ignores any sub-goal information that is not explicit in the representation of the planning instances, causing plateaus in the space of candidate generalized plans. Furthermore, node expansion in GP is a run-time bottleneck since it requires evaluating every child node over the entire batch of classical planning instances in a GP problem. In this paper we define a landmark counting heuristic for GP (that considers sub-goal information that is not explicitly represented in the planning instances), and a novel heuristic search algorithm for GP (that we call PGP) and that progressively processes subsets of the planning instances of a GP problem. Our two orthogonal contributions are analyzed in an ablation study, showing that both improve the state-of-the-art in GP as heuristic search, and that both benefit from each other when used in combination.