Guiding GBFS through Learned Pairwise Rankings

Mingyu Hao, Felipe W. Trevizan, Sylvie Thiébaux, Patrick Ferber, Jörg Hoffmann

Abstract

We propose a new approach based on ranking to learn to guide Greedy Best-First Search (GBFS). As previous ranking approaches, ours is based on the observation that directly learning a heuristic function is overly restrictive, and that GBFS is capable of efficiently finding good plans for a much more flexible class of total quasi-orders over states. In order to learn an optimal ranking function, we introduce a new ranking framework capable of leveraging any neural network regression model and efficiently handling the training data through batching. Compared with previous ranking approaches for planning, ours does not require complex loss functions and allows training on states outside the optimal plan with minimal overhead. Our experiments on the domains of the latest planning competition learning track show that our approach substantially improves the coverage of the underlying neural network models without degrading plan quality.

Introduction

In classical planning, Greedy Best-First Search (GBFS) is a fundamental algorithm that relies on a heuristic function $h(s)$ to estimate the distance from a state $s$ to the goal. Traditionally, deep learning approaches have treated the acquisition of $h(s)$ as a regression problem, attempting to minimize the error between predicted values and true optimal costs ($h^*$).

However, regression may be an unnecessarily restrictive objective for guiding GBFS. The algorithm's search behavior is determined solely by the relative order of states in the priority queue; it only requires that $h(s_1) < h(s_2)$ when $s_1$ is closer to the goal than $s_2$. Forcing models to learn exact numerical values is computationally expensive—requiring optimal solutions for training—and often fails to generalize when cost scales change in larger problem instances.

Methodology: The OptRank Framework

We introduce OptRank, a framework designed to learn a Total Quasi-Order over states rather than absolute costs.

DirectRanker Architecture

The core of our approach is the DirectRanker model. It processes pairs of states through a shared neural network (e.g., a GNN) to generate embeddings. These embeddings are then compared via an element-wise difference and passed through a linear layer to determine the ranking.

The DirectRanker architecture for learning pairwise rankings.

A significant mathematical advantage of this architecture is that because the ranking component is linear and unbiased, we can extract a scalar value $r(s)$ for any state. This allows the model to be integrated into standard GBFS priority queues without the quadratic overhead of pairwise comparisons during search.

Optimal Ranking and Data Efficiency

OptRank defines a target "Optimal Ranking" that compares states on an optimal path only to their immediate "siblings" (other states reachable from the same parent). By exploiting the transitivity of rankings, this strategy reduces data requirements from $O(n^2)$ in previous "Perfect Ranking" methods to $O(n)$, where $n$ is the plan length. This efficiency allows for training on more diverse states and larger datasets.

Experimental Evaluation

We evaluated OptRank using 10 domains from the 2023 International Planning Competition (IPC23) Learning Track. Training was conducted on small instances solved optimally, while testing included "easy," "medium," and "hard" instances to assess generalization to larger, unseen problems. We applied the framework to two state-of-the-art Graph Neural Network (GNN) architectures: STRIPS-HGN and GOOSE.

Results and Discussion

The shift from regression to ranking yielded substantial performance gains. OptRank increased problem-solving coverage by 22% for the GOOSE model and 32% for the STRIPS-HGN model compared to their original regression-based counterparts.

Performance comparison of OptRank(GOOSE) against baselines across Nodes Expanded, Plan Cost, and Search Time.

As shown in the results, OptRank significantly reduces the number of nodes expanded and search time compared to standard GOOSE and the previous PerfRank approach. Notably, the plans generated by OptRank maintain high quality, often matching or exceeding those from regression models despite the lack of explicit cost training. While classical heuristics like $h^{ff}$ still lead in total coverage, OptRank-guided GNNs are effectively closing the gap, particularly on complex "medium" and "hard" problems.

Conclusion

OptRank demonstrates that pairwise ranking is a more effective and efficient objective than regression for training neural search guides. By focusing on relative state quality, the models achieve better generalization and higher coverage with less training data. Future work will focus on extending the theoretical framework to non-unit cost actions and optimizing the inference speed of the underlying GNN architectures to further improve search efficiency.

Summary updated

Abstract

We propose a new approach based on ranking to learn to guide Greedy Best-First Search (GBFS). As previous ranking approaches, ours is based on the observation that directly learning a heuristic function is overly restrictive, and that GBFS is capable of efficiently finding good plans for a much more flexible class of total quasi-orders over states. In order to learn an optimal ranking function, we introduce a new ranking framework capable of leveraging any neural network regression model and efficiently handling the training data through batching. Compared with previous ranking approaches for planning, ours does not require complex loss functions and allows training on states outside the optimal plan with minimal overhead. Our experiments on the domains of the latest planning competition learning track show that our approach substantially improves the coverage of the underlying neural network models without degrading plan quality.
BibTeX
@inproceedings{hao2024guiding,
  author = {Mingyu Hao and Felipe W. Trevizan and Sylvie Thiébaux and Patrick Ferber and Jörg Hoffmann},
  title = {{Guiding GBFS through Learned Pairwise Rankings}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=YREidpyvEl},
}
Figure