Moving Target Search with Compressed Path Databases

Moving target search, where the goal state changes during a search, has recently seen a revived interest. Incremental Anytime 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 path databases (CPDs) in moving target search. CPDs have pre-viously been used in standard, fixed-target pathfinding. They encode 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 individual move is improved, which is important in real-time search scenarios, where the time available to make a move is lim-ited. The number of hunter moves is very good, since CPDs provide optimal moves along shortest paths. Compared to previous successful methods, such as I-ARA*, our method is simple to understand and implement