Repairing Compressed Path Databases on Maps with Dynamic Changes

Abstract

Single-agent pathfinding on grid maps can exploit online compiled knowledge produced offline and saved as a Compressed Path Database (CPD). Such a knowledge is distilled by performing repeated searches in a graph, where each node corresponds to a distinct grid cell, typically by algorithms such as Dijkstra's. All-pairs shortest paths (APSPs) are computed and the first move along a shortest path is persistently stored in the CPD. This way, an optimal move can efficiently be retrieved for any pair of source and target cells that is considered while the agent is navigating. However, a CPD supports a static grid, that is, a grid where each cell is permanently either traversable or non-traversable. Our work instead assumes that the cells in the map can undergo dynamic changes. Reasoning about the altered map would require a new CPD. As creating it from scratch is computationally expensive, we present techniques to repair an existing CPD. We prove that using our technique leads to correct and optimal solutions. Experiments demonstrate the benefits of our approach. When a single obstacle of a given size is added or removed, the repair costs often are a small fraction of a recomputation from scratch.