Moving target search with compressed path databases

Adi Botea, Jorge A. Baier, Daniel Harabor, Carlos Hernandez

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

12 Citations (Scopus)


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 previously been used in standard, fixed-target pathfinding. They encode all-pairs shortest paths in a compressed form and require preprocessing and memory to store the database. In moving-target search, our speed results are orders of magnitude 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 limited. 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.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Third International Conference on Automated Planning and Scheduling
EditorsDaniel Borrajo, Simone Fratini, Subbarao Kambhampati, Angelo Oddi
Place of PublicationMenlo Park, California
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages5
ISBN (Print)9781577356097
Publication statusPublished - 2013
Externally publishedYes
EventInternational Conference on Automated Planning and Scheduling 2013 - Rome, Italy
Duration: 10 Jun 201314 Jun 2013
Conference number: 23rd (Proceedings)


ConferenceInternational Conference on Automated Planning and Scheduling 2013
Abbreviated titleICAPS 2013
Internet address

Cite this