A Differentiable Loss Function for Learning Heuristics in A*
This addresses the issue of inefficient heuristic learning in automated planning for researchers and practitioners, though it is incremental as it builds on existing deep neural network methods.
The paper tackles the problem of optimizing heuristic functions for A* search by proposing a new differentiable loss function (L* loss) that upper-bounds excessively expanded states, leading to improved performance in maze domains like Sokoban and teleport mazes, with results including a reduction in expanded states by approximately 50%.
Optimization of heuristic functions for the A* algorithm, realized by deep neural networks, is usually done by minimizing square root loss of estimate of the cost to goal values. This paper argues that this does not necessarily lead to a faster search of A* algorithm since its execution relies on relative values instead of absolute ones. As a mitigation, we propose a L* loss, which upper-bounds the number of excessively expanded states inside the A* search. The L* loss, when used in the optimization of state-of-the-art deep neural networks for automated planning in maze domains like Sokoban and maze with teleports, significantly improves the fraction of solved problems, the quality of founded plans, and reduces the number of expanded states to approximately 50%