Guiding GBFS through Learned Pairwise Rankings

Guiding GBFS through Learned Pairwise Rankings

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

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 6724-6732. https://doi.org/10.24963/ijcai.2024/743

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.
Keywords:
Planning and Scheduling: PS: Learning in planning and scheduling