Path planning with compressed all-pairs shortest paths data

Adi Botea, Daniel Harabor

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

16 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
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
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). Association for the Advancement of Artificial Intelligence (AAAI).