Publication
SoCS 2012
Conference paper

Fast, optimal pathfinding with compressed path databases

Abstract

Most existing pathfinding methods are based on runtime search. Despite an impressive progress achieved in recent years, search-based methods could explore, in bad cases, large portions of a map, leading to an increased running time. We take a significantly different approach from search-based methods. Given a map, our program precomputes all-pairs shortest paths (APSP) information. APSP data are compressed, reducing the size dramatically with no information loss. We call the resulting data a compressed path database (CPD). At runtime, optimal moves are retrieved one by one until a complete (or partial, if desired) optimal path is retrieved. CPDs lead to a fast path computation, eliminating the need for runtime search. The first move lag is very low, as each move is retrieved independently from subsequent moves. The price to pay includes a significant preprocessing time and memory to build and store a CPD.

Date

Publication

SoCS 2012

Authors

Share