Focal Discrepancy Search for Learned Heuristics (Extended Abstract)

Abstract

Machine learning allows learning accurate but inadmissible heuristics for hard combinatorial puzzles like the 15-puzzle, the 24-puzzle, and Rubik's cube. In this paper, we investigate how to exploit these learned heuristics in the context of heuristic search with suboptimality guarantees. Specifically, we study how Focal Search (FS), a well-known bounded-suboptimal search algorithm can be modified to better exploit inadmissible learned heuristics. We propose to use Focal Discrepancy Search (FDS) in the context of learned heuristics, which uses a discrepancy function, instead of the learned heuristic, to sort the focal list. In our empirical evaluation, we evaluate FS and FDS using DeepCubeA, an effective learned heuristic for the 15-puzzle. We show that FDS substantially outperforms FS. This suggests that in some domains, when a highly accurate heuristics is available, one should always consider using discrepancies for better search.