Cutting the size of Compressed Path Databases with wildcards and redundant symbols

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

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

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.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling
EditorsJ. Benton, Nir Lipovetzky, Eva Onaindia, David E. Smith, Siddharth Srivastava
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages106-113
Number of pages8
Volume29
Publication statusPublished - 5 Jul 2019
EventInternational Conference on Automated Planning and Scheduling 2019 - Berkeley, United States of America
Duration: 13 Jul 201915 Jul 2019
Conference number: 29th
https://icaps19.icaps-conference.org/

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2019
Abbreviated titleICAPS 2019
CountryUnited States of America
CityBerkeley
Period13/07/1915/07/19
Internet address

Cite this

Chiari, M., Zhao, S., Botea, A., Gerevini, A., Harabor, D., Saetti, A., Salvetti, M., & Stuckey, P. J. (2019). Cutting the size of Compressed Path Databases with wildcards and redundant symbols. In J. Benton, N. Lipovetzky, E. Onaindia, D. E. Smith, & S. Srivastava (Eds.), Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling (Vol. 29, pp. 106-113). Association for the Advancement of Artificial Intelligence (AAAI). https://aaai.org/ojs/index.php/ICAPS/article/view/3465