Path Planning with Compressed All-Pairs Shortest Paths Data

Abstract

All-pairs shortest paths (APSP) can eliminate the need to search in a graph, providing optimal moves very fast. A major challenge is storing pre-computed APSP data efficiently. Recently, compression has successfully been employed to scale the use of APSP data to roadmaps and gridmaps of realistic sizes. We develop new techniques that improve the compression power of state-of-the-art methods by up to a factor of 5. We demonstrate our ideas on game gridmpaps and the roadmap of Australia. Part of our ideas have been integrated in the Copa CPD system, one of the two best optimal participants in the grid-based path planning competition GPPC.