Avoiding Errors in Learned Heuristics in Bounded-Suboptimal Search

SOCS-22 Volume 15

Volume

Vol. 15 No. 1 (2022): Fifteenth International Symposium on Combinatorial Search

Student Papers

Despite being very effective, learned heuristics in bounded-suboptimal search can produce heuristic plateaus or move the search to zones of the state space that do not lead to a solution. In addition, it produces inadmissible cost-to-go estimates; therefore, it cannot be exploited with classical algorithms like WA* to produce w-optimal solutions. In this paper, we present two ways in which Focal Search can be modified to exploit a learned heuristic in a bounded suboptimal search: Focal Discrepancy Search, which, to evaluate each state, uses a discrepancy score based on the best-predicted heuristic value; and K-Focal Search, which expands more than one node from the FOCAL list in each expansion cycle. Both algorithms return w-optimal solutions and explore different zones of the state space than the ones that focal search, using the learned heuristic to sort the FOCAL list, would explore.

10.1609/socs.v15i1.21804