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

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
PublisherAAAI Press
Pages288-292
Number of pages5
ISBN (Print)9781577356097
Publication statusPublished - 2013
Externally publishedYes
EventInternational Conference on Automated Planning and Scheduling 2013 - Auditorium Antonianum, Rome, Italy
Duration: 10 Jun 201314 Jun 2013
Conference number: 23
http://icaps13.icaps-conference.org/

Conference

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

Cite this

Botea, A., Baier, J. A., Harabor, D., & Hernandez, C. (2013). Moving target search with compressed path databases. In D. Borrajo, S. Fratini, S. Kambhampati, & A. Oddi (Eds.), Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling (pp. 288-292). Menlo Park, California: AAAI Press.
Botea, Adi ; Baier, Jorge A. ; Harabor, Daniel ; Hernandez, Carlos. / Moving target search with compressed path databases. Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling. editor / Daniel Borrajo ; Simone Fratini ; Subbarao Kambhampati ; Angelo Oddi. Menlo Park, California : AAAI Press, 2013. pp. 288-292
@inproceedings{c70b1898a6a443519bb56b30361ce141,
title = "Moving target search with compressed path databases",
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.",
author = "Adi Botea and Baier, {Jorge A.} and Daniel Harabor and Carlos Hernandez",
year = "2013",
language = "English",
isbn = "9781577356097",
pages = "288--292",
editor = "Daniel Borrajo and Simone Fratini and Subbarao Kambhampati and Angelo Oddi",
booktitle = "Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling",
publisher = "AAAI Press",

}

Botea, A, Baier, JA, Harabor, D & Hernandez, C 2013, Moving target search with compressed path databases. in D Borrajo, S Fratini, S Kambhampati & A Oddi (eds), Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling. AAAI Press, Menlo Park, California, pp. 288-292, International Conference on Automated Planning and Scheduling 2013, Rome, Italy, 10/06/13.

Moving target search with compressed path databases. / Botea, Adi; Baier, Jorge A.; Harabor, Daniel; Hernandez, Carlos.

Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling. ed. / Daniel Borrajo; Simone Fratini; Subbarao Kambhampati; Angelo Oddi. Menlo Park, California : AAAI Press, 2013. p. 288-292.

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

TY - GEN

T1 - Moving target search with compressed path databases

AU - Botea, Adi

AU - Baier, Jorge A.

AU - Harabor, Daniel

AU - Hernandez, Carlos

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84889769846&partnerID=8YFLogxK

M3 - Conference Paper

SN - 9781577356097

SP - 288

EP - 292

BT - Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling

A2 - Borrajo, Daniel

A2 - Fratini, Simone

A2 - Kambhampati, Subbarao

A2 - Oddi, Angelo

PB - AAAI Press

CY - Menlo Park, California

ER -

Botea A, Baier JA, Harabor D, Hernandez C. Moving target search with compressed path databases. In Borrajo D, Fratini S, Kambhampati S, Oddi A, editors, Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling. Menlo Park, California: AAAI Press. 2013. p. 288-292