The compressed differential heuristic

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 ${\mathrm{A}}^{\ast }$ search driven by the CDH significantly outperforms the ${\mathrm{A}}^{\ast }$ 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 other memory-based technique that is flexible to use as small an amount of memory as that which CDH is capable of. In such low memory situations, the basic ${\mathrm{A}}^{\ast }$ search driven by the CDH provides competitive time performance to some of the best zero-memory techniques in the Grid-Based Path Planning Competition. The latter techniques are non-heuristic and stand to benefit from a heuristic that is capable of using the available memory.