# Hierarchical Decomposition and Analysis for Generalized Planning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 46 references that are in the map.
- First posted on arXiv 6 Dec 2022.

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

- [Learning Domain-Independent Planning Heuristics with Hypergraph Networks](https://mlsanity.com/paper/1911.13101/) (2019)
- [ASNets: Deep Learning for Generalised Planning](https://mlsanity.com/paper/1908.01362/) (2019)
- [Generalized Planning With Deep Reinforcement Learning](https://mlsanity.com/paper/2005.02305/) (2020)
- [Features, Projections, and Representation Change for Generalized Planning](https://mlsanity.com/paper/1801.10055/) (2018)
- [Learning Generalized Relational Heuristic Networks for Model-Agnostic Planning](https://mlsanity.com/paper/2007.06702/) (2020)
- [Learning Generalized Policies Without Supervision Using GNNs](https://mlsanity.com/paper/2205.06002/) (2022)
- [Qualitative Numeric Planning: Reductions and Complexity](https://mlsanity.com/paper/1912.04816/) (2019)
- [Generalized Planning as Heuristic Search](https://mlsanity.com/paper/2103.14434/) (2021)
- [Scaling-up Generalized Planning as Heuristic Search with Landmarks](https://mlsanity.com/paper/2205.04850/) (2022)
- [Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width: Extended Version](https://mlsanity.com/paper/2203.14852/) (2022)
- [Generalized Planning: Non-Deterministic Abstractions and Trajectory Constraints](https://mlsanity.com/paper/1909.12135/) (2019)
- [Relational Abstractions for Generalized Reinforcement Learning on Symbolic Problems](https://mlsanity.com/paper/2204.12665/) (2022)
- [Generalized Planning with Positive and Negative Examples](https://mlsanity.com/paper/1911.09365/) (2019)
- [Learning Generalized Policy Automata for Relational Stochastic Shortest Path Problems](https://mlsanity.com/paper/2204.04301/) (2022)

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

- [Symmetries and Expressive Requirements for Learning General Policies](https://mlsanity.com/paper/2409.15892/) (2024)
- [Graph Learning for Numeric Planning](https://mlsanity.com/paper/2410.24080/) (2024)
- [Deep Learning for Generalised Planning with Background Knowledge](https://mlsanity.com/paper/2410.07923/) (2024)
- [An Automatic Sound and Complete Abstraction Method for Generalized Planning with Baggable Types](https://mlsanity.com/paper/2501.15249/) (2025)

## Abstract (arXiv)

This paper presents new methods for analyzing and evaluating generalized plans that can solve broad classes of related planning problems. Although synthesis and learning of generalized plans has been a longstanding goal in AI, it remains challenging due to fundamental gaps in methods for analyzing the scope and utility of a given generalized plan. This paper addresses these gaps by developing a new conceptual framework along with proof techniques and algorithmic processes for assessing termination and goal-reachability related properties of generalized plans. We build upon classic results from graph theory to decompose generalized plans into smaller components that are then used to derive hierarchical termination arguments. These methods can be used to determine the utility of a given generalized plan, as well as to guide the synthesis and learning processes for generalized plans. We present theoretical as well as empirical results illustrating the scope of this new approach. Our analysis shows that this approach significantly extends the class of generalized plans that can be assessed automatically, thereby reducing barriers in the synthesis and learning of reliable generalized plans.