AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Conference on Automated Planning and Scheduling, 29 > Book One

Cutting the Size of Compressed Path Databases with Wildcards and Redundant Symbols

Authors

Mattia Chiari,Shizhe Zhao,Adi Botea,Alfonso E. Gerevini,Daniel Harabor,Alessandro Saetti,Matteo Salvetti,Peter J. Stuckey

University of Brescia,Monash University,IBM,University of Brescia,Monash University,University of Brescia,University of Brescia,The University of Melbourne


Proceedings:

Book One

Volume

Issue:

Proceedings of the International Conference on Automated Planning and Scheduling, 29

Track:

Main Track

Downloads:

Download PDF

Abstract:

Path planning on gridmaps is a common problem in AI and a popular topic in application areas such as computer games. Compressed Path Databases (CPDs) represent a state-of-theart approach to the problem, in terms of the speed of computing full optimal paths and also individual optimal moves. Despite significant improvements in recent years, the memory required to store a CPD can still be a bottleneck for large game maps. In this work we present a new compression approach that can reduce the size of CPDs. Our approach uses an extended notion of wildcards and a novel concept called a redundant symbol. We implement our ideas on top of a state-of-the-art CPD system and, in a range of experiments, we demonstrate a substantial reduction in the size of CPDs.

DOI:

10.1609/icaps.v29i1.3465


ICAPS

Proceedings of the International Conference on Automated Planning and Scheduling, 29