Moving Target Search with Compressed Path Databases

Abstract

Moving target search, where the goal state changes duringa search, has recently seen a revived interest. IncrementalAnytime Repairing A* (I-ARA*) is a very recent, state-of-the-art algorithm for moving target search in a known terrain.In this work, we address the problem using compressed pathdatabases (CPDs) in moving target search. CPDs have pre-viously been used in standard, fixed-target pathfinding. Theyencode all-pairs shortest paths in a compressed form and re-quire preprocessing and memory to store the database.In moving-target search, our speed results are orders of mag-nitude better than state of the art. The time per individualmove is improved, which is important in real-time searchscenarios, where the time available to make a move is lim-ited. The number of hunter moves is very good, since CPDsprovide optimal moves along shortest paths. Compared toprevious successful methods, such as I-ARA*, our method issimple to understand and implement.