Adaptive Width Best-First Search: Dynamic Frontier Expansion for GNN-based Heuristics (Extended Abstract)

Abstract

In this paper, we introduce Adaptive Width Best-First Search (AWBFS), a search algorithm designed to better exploit batched heuristic evaluation while preserving the guidance of Greedy Best-First Search (GBFS) when using learning-based heuristics on GPU architectures. The method targets domains in which learned heuristics are effective, but standard GBFS can stagnate on heuristic plateaus, a situation that is common in numeric planning. AWBFS addresses this issue by dynamically adjusting the number of frontier nodes expanded at each step. Starting from standard GBFS behavior, the algorithm increases the expansion width when no improvement in heuristic value is observed. For the use with learning-based heuristics, AWBFS tracks GPU memory usage to ensure it never exceeds the input limit. Experimental results show that AWBFS yields better performance than standard GBFS when paired with GNN-based heuristics.