Learning Admissible Heuristics via Cost Partitioning
2026-06-03 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors address the problem of learning heuristics that help in finding the best plan without overestimating costs, which is tricky. They use a technique called cost partitioning, which safely combines multiple heuristic estimates but is usually slow to compute perfectly. By representing planning states as graphs and using a special algorithm to extract features, their deep learning model predicts cost weights that keep the heuristic safe (admissible) by design. Their experiments show this method reduces the search effort compared to less optimal approaches, making it the first learned heuristic guaranteed to be admissible.
admissible heuristicsoptimal planningcost partitioningLagrangian dualityWeisfeiler-Leman algorithmgraph representationdeep learningself-attentionheuristic search
Authors
Hugo Barral, Quentin Cappart, Marie-José Huguet, Sylvie Thiébaux
Abstract
Admissible heuristics are essential for optimal planning, yet learning them remains challenging due to the risk of overestimation. Cost partitioning combines multiple abstraction heuristics while preserving admissibility, but computing optimal partitions online is expensive. We propose a framework that learns to infer admissible cost partitions by leveraging the Lagrangian dual equivalence between cost partitioning and multiplier prediction. Planning states and patterns are encoded as labelled graphs, and an action-centric variant of the Weisfeiler-Leman algorithm extracts structural feature vectors. A deep architecture with axial self-attention and a softmax output layer maps these features to cost weights that satisfy the partition constraints by construction, ensuring admissibility. Experiments demonstrate reduced node expansions compared to suboptimal partitioning baselines while maintaining strict admissibility. To our knowledge, this is the first machine-learned heuristic guaranteed to be admissible.