Learning Generalized Relational Heuristic Networks for Model-Agnostic Planning

Rushang Karia, Siddharth Srivastava

Abstract

Computing goal-directed behavior is essential to designing efficient AI systems. Due to the computational complexity of planning, current approaches rely primarily upon hand-coded symbolic action models and hand-coded heuristic function generators for efficiency. Learned heuristics for such problems have been of limited utility as they are difficult to apply to problems with objects and object quantities that are significantly different from those in the training data. This paper develops a new approach for learning generalized heuristics in the absence of symbolic action models using deep neural networks that utilize an input predicate vocabulary but are agnostic to object names and quantities. It uses an abstract state representation to facilitate data-efficient, generalizable learning. Empirical evaluation on a range of benchmark domains shows that in contrast to prior approaches, generalized heuristics computed by this method can be transferred easily to problems with different objects and with object quantities much larger than those in the training data.

Introduction

Automated planning—the process of finding a sequence of actions to reach a goal—is a fundamental challenge in artificial intelligence. To navigate the vast search spaces of these problems, researchers typically rely on heuristics to guide search algorithms. However, traditional heuristic generation faces two critical bottlenecks: the Model Bottleneck, which requires precise symbolic models (like PDDL) that are difficult to author for complex systems, and the Generalization Bottleneck, where machine-learning-based heuristics fail when encountering more objects than seen during training.

This paper introduces Generalized Relational Heuristic Networks (GHNs), a model-agnostic deep learning framework designed to learn heuristics directly from state observations. By leveraging state abstraction, GHNs can generalize to problem instances with significantly larger object counts and different object names than those present in the training set.

Methodology

Canonical Abstraction

The primary innovation of GHNs is the use of Canonical Abstraction. Instead of processing raw object data, the system groups objects into "roles" based on the unary predicates they satisfy in a given state. For instance, in a logistics domain, all "empty trucks" might be grouped into one role, while "trucks carrying packages" form another. This representation allows the network to learn the underlying logic of a domain rather than memorizing specific configurations.

Network Architecture

The GHN architecture consists of two specialized components:

  1. The Action Network ($NN_A$): Predicts the likelihood of an action being part of an optimal plan using "Binned Inputs" (categorical counts like zero, one, or many) to maintain scale invariance.
  2. The Plan Length Network ($NN_{len}$): Estimates the number of steps remaining to reach the goal using "Absolute Inputs" (exact counts of objects in roles).
The GHN architecture integrates an Action Network for policy guidance and a Plan Length Network for distance estimation.

Leapfrogging

To overcome the lack of large-scale training data, the authors employ Leapfrogging, a bootstrapping technique. The process begins by solving trivial problems via blind search, training the GHN on these solutions, and then using the trained model to solve incrementally larger and more complex problems. This iterative cycle allows the network to "self-teach" complex behaviors from minimal initial knowledge.

Experimental Evaluation

The approach was evaluated on 13 benchmark domains from the International Planning Competition (IPC), including classic puzzles like Blocksworld and Sokoban, as well as navigation and logistics tasks like Visitall and Ferry. A key focus was the generalization test: models were trained on small instances (e.g., 2–8 blocks) and tested on much larger ones (up to 48 blocks).

Results and Discussion

Empirical results demonstrate that GHNs offer superior search efficiency compared to standard heuristics like $h_{FF}$. In several domains, GHNs expanded orders of magnitude fewer nodes to reach a solution. Notably, in domains like Spanner, where traditional "delete-relaxation" heuristics are known to fail, the GHN approach remained highly effective.

Performance comparison showing the percentage of problems solved versus nodes expanded and time taken across multiple IPC domains.

Key Insights

  • Abstraction as Generalization: Representing states as counts of roles prevents overfitting to specific map layouts or object counts.
  • Goal Hints: Including "done" and "goal" predicates helps the network recognize relational progress toward the objective.
  • Model-Agnostic Viability: The results confirm that symbolic action models are not strictly necessary for learning effective heuristics; observing action effects in a simulator is sufficient.

Limitations and Future Work

While GHNs show remarkable scaling, they face challenges in domains with high plan diversity, such as Logistics, where high network loss during training can impede performance. Additionally, the computational overhead of neural network inference at each search step is higher than that of simple mathematical heuristics. Future research may explore optimizing inference engines or incorporating first-order logic with transitive closure to better handle long-range dependencies in complex environments.

Summary updated

Abstract

Computing goal-directed behavior is essential to designing efficient AI systems. Due to the computational complexity of planning, current approaches rely primarily upon hand-coded symbolic action models and hand-coded heuristic function generators for efficiency. Learned heuristics for such problems have been of limited utility as they are difficult to apply to problems with objects and object quantities that are significantly different from those in the training data. This paper develops a new approach for learning generalized heuristics in the absence of symbolic action models using deep neural networks that utilize an input predicate vocabulary but are agnostic to object names and quantities. It uses an abstract state representation to facilitate data-efficient, generalizable learning. Empirical evaluation on a range of benchmark domains shows that in contrast to prior approaches, generalized heuristics computed by this method can be transferred easily to problems with different objects and with object quantities much larger than those in the training data.
BibTeX
@inproceedings{karia2021learning,
  author = {Rushang Karia and Siddharth Srivastava},
  title = {{Learning Generalized Relational Heuristic Networks for Model-Agnostic Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=sjYYtwrdS5},
}
Figure