# Return to Tradition: Learning Reliable Heuristics with Classical Machine Learning

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 37 references that are in the map.
- First posted on arXiv 25 Mar 2024.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks](https://mlsanity.com/paper/1401.3839/) (2014)
- [Learning Domain-Independent Planning Heuristics with Hypergraph Networks](https://mlsanity.com/paper/1911.13101/) (2019)
- [Learning Generalized Reactive Policies using Deep Neural Networks](https://mlsanity.com/paper/1708.07280/) (2017)
- [Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits](https://mlsanity.com/paper/2109.10129/) (2021)
- [Generalized Planning With Deep Reinforcement Learning](https://mlsanity.com/paper/2005.02305/) (2020)
- [Action Schema Networks: Generalised Policies with Deep Learning](https://mlsanity.com/paper/1709.04271/) (2017)
- [Learning Domain-Independent Heuristics for Grounded and Lifted Planning](https://mlsanity.com/paper/2312.11143/) (2023)
- [Learning to Rank for Synthesizing Planning Heuristics](https://mlsanity.com/paper/1608.01302/) (2016)
- [Learning Generalized Relational Heuristic Networks for Model-Agnostic Planning](https://mlsanity.com/paper/2007.06702/) (2020)
- [Size Independent Neural Transfer for RDDL Planning](https://mlsanity.com/paper/1902.03081/) (2019)
- [Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal](https://mlsanity.com/paper/2310.19463/) (2023)
- [What Planning Problems Can A Relational Neural Network Solve?](https://mlsanity.com/paper/2312.03682/) (2023)

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

- [Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code](https://mlsanity.com/paper/2503.18809/) (2025)
- [Language Models For Generalised PDDL Planning: Synthesising Sound and Programmatic Policies](https://mlsanity.com/paper/2508.18507/) (2025)
- [Graph Learning for Numeric Planning](https://mlsanity.com/paper/2410.24080/) (2024)
- [Symmetry-Aware Transformer Training for Automated Planning](https://mlsanity.com/paper/2508.07743/) (2025)
- [Leveraging Action Relational Structures for Integrated Learning and Planning](https://mlsanity.com/paper/2504.20318/) (2025)
- [Deep Learning for Generalised Planning with Background Knowledge](https://mlsanity.com/paper/2410.07923/) (2024)
- [Learning Efficiency Meets Symmetry Breaking](https://mlsanity.com/paper/2504.19738/) (2025)
- [Vejde: A Framework for Inductive Deep Reinforcement Learning Based on Factor Graph Color Refinement](https://mlsanity.com/paper/2509.09219/) (2025)
- [Learning Admissible Heuristics for A*: Theory and Practice](https://mlsanity.com/paper/2509.22626/) (2025)
- [WLPlan: Relational Features for Symbolic Planning](https://mlsanity.com/paper/2411.00577/) (2024)
- [Graph Learning for Planning: The Story Thus Far and Open Challenges](https://mlsanity.com/paper/2412.02136/) (2024)
- [Exploiting Symbolic Heuristics for the Synthesis of Domain-Specific Temporal Planning Guidance using Reinforcement Learning](https://mlsanity.com/paper/2505.13372/) (2025)
- [Relational GNNs Cannot Learn C2 Features for Planning](https://mlsanity.com/paper/2506.11721/) (2025)
- [Scaling Multi-Agent Epistemic Planning through GNN-Derived Heuristics](https://mlsanity.com/paper/2508.12840/) (2025)
- [Symmetry-Invariant Novelty Heuristics via Unsupervised Weisfeiler-Leman Features](https://mlsanity.com/paper/2508.18520/) (2025)
- [On Sample-Efficient Generalized Planning via Learned Transition Models](https://mlsanity.com/paper/2602.23148/) (2026)
- [Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning](https://mlsanity.com/paper/2605.18674/) (2026)
- [LLM-Evolved Pattern Generators for Optimal Classical Planning](https://mlsanity.com/paper/2606.02438/) (2026)
- [Learning Admissible Heuristics via Cost Partitioning](https://mlsanity.com/paper/2606.04597/) (2026)

## Abstract (arXiv)

Current approaches for learning for planning have yet to achieve competitive performance against classical planners in several domains, and have poor overall performance. In this work, we construct novel graph representations of lifted planning tasks and use the WL algorithm to generate features from them. These features are used with classical machine learning methods which have up to 2 orders of magnitude fewer parameters and train up to 3 orders of magnitude faster than the state-of-the-art deep learning for planning models. Our novel approach, WL-GOOSE, reliably learns heuristics from scratch and outperforms the hFF heuristic in a fair competition setting. It also outperforms or ties with LAMA on 4 out of 10 domains on coverage and 7 out of 10 domains on plan quality. WL-GOOSE is the first learning for planning model which achieves these feats. Furthermore, we study the connections between our novel WL feature generation method, previous theoretically flavoured learning architectures, and Description Logic Features for planning.