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

11 Citations (Scopus)

Abstract

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)
Pages288-292
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
http://icaps13.icaps-conference.org/
https://dl.acm.org/doi/proceedings/10.5555/3038718 (Proceedings)

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2013
Abbreviated titleICAPS 2013
CountryItaly
CityRome
Period10/06/1314/06/13
Internet address

Cite this