Abstract
Compressed Path Databases (CPDs) are a leading technique for optimal pathfinding in graphs
with static edge costs. In this work we investigate
CPDs as admissible heuristic functions and we apply them in two distinct settings: problems where
the graph is subject to dynamically changing costs,
and anytime settings where deliberation time is limited. Conventional heuristics derive cost-to-go estimates by reasoning about a tentative and usually
infeasible path, from the current node to the target.
CPD-based heuristics derive cost-to-go estimates
by computing a concrete and usually feasible path.
We exploit such paths to bound the optimal solution, not just from below but also from above. We
demonstrate the benefit of this approach in a range
of experiments on standard gridmaps and in comparison to Landmarks, a popular alternative also developed for searching in explicit state-spaces