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 contribution
SN - 9781577356097
T3 - ICAPS 2013 - Proceedings of the 23rd International Conference on Automated Planning and Scheduling
SP - 293
EP - 297
BT - ICAPS 2013 - Proceedings of the 23rd International Conference on Automated Planning and Scheduling
T2 - 23rd International Conference on Automated Planning and Scheduling, ICAPS 2013
Y2 - 10 June 2013 through 14 June 2013
ER -