The compressed differential heuristic Academic Article uri icon


  • Abstract The differential heuristic (DH) is a simple and effective memory-based heuristic for pathfinding in polynomial domains which was independently developed and used by a number of researchers. We present the compressed differential heuristic (CDH)–a family of compressed variants of the DH. We provide an experimental evaluation of the CDH's performance across three real-world domains (game maps, road maps, and a robotic arm) and three synthetically generated domains (rooms maps, mazes, and Delaunay graphs). The search performance of the CDH family is established. Our evaluation shows that, for a given amount of memory, the A∗ search driven by the CDH significantly outperforms the A∗ search driven by the DH of the same size. The CDH is most useful in applications that have limited additional memory beyond that required to store the map. We are not aware of any …

publication date

  • January 1, 2017