Path planning with compressed all-pairs shortest paths data

Adi Botea, Daniel Harabor

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

14 Citations (Scopus)

Abstract

All-pairs shortest paths (APSP) can eliminate the need to search in a graph, providing optimal moves very fast. A major challenge is storing pre-computed APSP data efficiently. Recently, compression has successfully been employed to scale the use of APSP data to roadmaps and gridmaps of realistic sizes. We develop new techniques that improve the compression power of state-of-the-art methods by up to a factor of 5. We demonstrate our ideas on game gridmpaps and the roadmap of Australia. Part of our ideas have been integrated in the Copa CPD system, one of the two best optimal participants in the grid-based path planning competition GPPC.

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
Pages293-297
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., & Harabor, D. (2013). Path planning with compressed all-pairs shortest paths data. In D. Borrajo, S. Fratini, S. Kambhampati, & A. Oddi (Eds.), Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling (pp. 293-297). Menlo Park, California: AAAI Press.
Botea, Adi ; Harabor, Daniel. / Path planning with compressed all-pairs shortest paths data. 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. 293-297
@inproceedings{3b9f8b1a1a0a49a3ad05ad5fd7f89105,
title = "Path planning with compressed all-pairs shortest paths data",
abstract = "All-pairs shortest paths (APSP) can eliminate the need to search in a graph, providing optimal moves very fast. A major challenge is storing pre-computed APSP data efficiently. Recently, compression has successfully been employed to scale the use of APSP data to roadmaps and gridmaps of realistic sizes. We develop new techniques that improve the compression power of state-of-the-art methods by up to a factor of 5. We demonstrate our ideas on game gridmpaps and the roadmap of Australia. Part of our ideas have been integrated in the Copa CPD system, one of the two best optimal participants in the grid-based path planning competition GPPC.",
author = "Adi Botea and Daniel Harabor",
year = "2013",
language = "English",
isbn = "9781577356097",
pages = "293--297",
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 & Harabor, D 2013, Path planning with compressed all-pairs shortest paths data. 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. 293-297, International Conference on Automated Planning and Scheduling 2013, Rome, Italy, 10/06/13.

Path planning with compressed all-pairs shortest paths data. / Botea, Adi; Harabor, Daniel.

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. 293-297.

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

TY - GEN

T1 - Path planning with compressed all-pairs shortest paths data

AU - Botea, Adi

AU - Harabor, Daniel

PY - 2013

Y1 - 2013

N2 - All-pairs shortest paths (APSP) can eliminate the need to search in a graph, providing optimal moves very fast. A major challenge is storing pre-computed APSP data efficiently. Recently, compression has successfully been employed to scale the use of APSP data to roadmaps and gridmaps of realistic sizes. We develop new techniques that improve the compression power of state-of-the-art methods by up to a factor of 5. We demonstrate our ideas on game gridmpaps and the roadmap of Australia. Part of our ideas have been integrated in the Copa CPD system, one of the two best optimal participants in the grid-based path planning competition GPPC.

AB - All-pairs shortest paths (APSP) can eliminate the need to search in a graph, providing optimal moves very fast. A major challenge is storing pre-computed APSP data efficiently. Recently, compression has successfully been employed to scale the use of APSP data to roadmaps and gridmaps of realistic sizes. We develop new techniques that improve the compression power of state-of-the-art methods by up to a factor of 5. We demonstrate our ideas on game gridmpaps and the roadmap of Australia. Part of our ideas have been integrated in the Copa CPD system, one of the two best optimal participants in the grid-based path planning competition GPPC.

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

M3 - Conference Paper

SN - 9781577356097

SP - 293

EP - 297

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, Harabor D. Path planning with compressed all-pairs shortest paths data. 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. 293-297