Guiding GBFS through Learned Pairwise Rankings

Mingyu Hao, Felipe Trevizan, Sylvie Thiébaux

Abstract

Traditional neural heuristics for classical planning typically treat distance estimation as a regression problem, which is often unnecessarily difficult and data-inefficient. We present a framework that shifts this paradigm toward learning an optimal ranking of states. By utilizing the DirectRanker architecture to learn pairwise preferences, our approach achieves a "total quasi-order" that aligns with the requirements of Greedy Best-First Search (GBFS). Our method incorporates an efficient training strategy based on state siblings and a pointwise transformation that allows for fast inference. Experiments on IPC benchmarks show that our ranking-based models significantly outperform regression-based counterparts in coverage and data efficiency.

Introduction

In classical planning, Greedy Best-First Search (GBFS) is a fundamental algorithm that navigates from a start state to a goal by expanding the most promising node according to a heuristic function $h(s)$. Recent advances have sought to learn these heuristics using machine learning, typically by regressing to the exact distance to the goal. However, this approach is overly restrictive; GBFS only requires a relative ordering of states to make progress. Predicting exact values is harder to learn and requires more precisely labeled data. This paper shifts the focus from regression to ranking, which aligns better with how search algorithms actually operate.

Methodology: The DirectRanker Framework

We propose learning an Optimal Ranking ($\preceq^*$) instead of a numerical distance. Our approach utilizes the DirectRanker architecture, which is designed to learn pairwise preferences while guaranteeing a consistent total quasi-order.

The DirectRanker architecture for learning state preferences through feature computation and ranking computation.

The architecture consists of two weight-sharing sub-networks that generate embeddings for a pair of states. The difference between these embeddings is processed to determine which state is "better." A key innovation is our use of a linear output layer, which allows us to extract a single numerical score $r(s)$ for any state. This transformation ensures that the ranking can be used in standard GBFS without the $O(n \log n)$ overhead of pairwise comparisons.

Efficient Training and Data Generation

To train the model effectively, we move beyond "golden path" states. We train the ranker to prefer states on an optimal path over their "siblings"—other states reachable from the same parent. By exploiting the transitivity of the "better than" relationship, we can represent a vast number of pairwise constraints with a dataset that scales linearly with plan length, requiring roughly 10x less data than alternative ranking approaches.

Experimental Results

We evaluated our framework on 10 domains from the 2023 International Planning Competition (IPC) Learning Track, applying it to state-of-the-art GNN architectures like GOOSE and STRIPS-HGN.

Comparison of nodes expanded across different models, showing the efficiency of OptRank variants compared to regression baselines.

Key findings include:

  • Increased Coverage: The ranking approach improved problem-solving success by 22% for GOOSE and 32% for STRIPS-HGN compared to their original regression-based versions.
  • Data Efficiency: Our method outperforms recent "perfect ranking" methods by massive margins (up to 176%) because it is easier to train and more data-efficient.
  • Generalization: The learned logic generalizes well to "Hard" problems significantly larger than those seen during training, as the model learns the logic of ordering rather than memorizing distances.

Conclusion

Shifting from regression to ranking provides a more natural and efficient way to guide search algorithms in planning. By learning the logic of state ordering rather than memorizing distances, neural planners become more robust and easier to train. Future work will explore extending this framework to non-unit cost problems and other search strategies beyond GBFS.

Summary updated

BibTeX
@inproceedings{hao2024guiding,
  author = {Mingyu Hao and Felipe Trevizan and Sylvie Thiébaux},
  title = {{Guiding GBFS through Learned Pairwise Rankings}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=YREidpyvEl},
}
Figure