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

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

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

5 Citations (Scopus)

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 language	English
Title of host publication	Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling
Editors	J. Benton, Nir Lipovetzky, Eva Onaindia, David E. Smith, Siddharth Srivastava
Place of Publication	Palo Alto CA USA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	106-113
Number of pages	8
ISBN (Electronic)	9781577358077
Publication status	Published - 5 Jul 2019
Event	International Conference on Automated Planning and Scheduling 2019 - Berkeley, United States of America Duration: 13 Jul 2019 → 15 Jul 2019 Conference number: 29th https://icaps19.icaps-conference.org/ https://ojs.aaai.org/index.php/ICAPS/issue/view/239 (Proceedings)

Publication series

Name	Proceedings International Conference on Automated Planning and Scheduling, ICAPS
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Volume	29
ISSN (Print)	2334-0835
ISSN (Electronic)	2334-0843

Conference

Conference	International Conference on Automated Planning and Scheduling 2019
Abbreviated title	ICAPS 2019
Country/Territory	United States of America
City	Berkeley
Period	13/07/19 → 15/07/19
Internet address	https://icaps19.icaps-conference.org/ https://ojs.aaai.org/index.php/ICAPS/issue/view/239 (Proceedings)

Access to Document

279249471-oaFinal published version, 3.05 MB

https://aaai.org/ojs/index.php/ICAPS/article/view/3465

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 (pp. 106-113). (Proceedings International Conference on Automated Planning and Scheduling, ICAPS; Vol. 29). Association for the Advancement of Artificial Intelligence (AAAI). https://aaai.org/ojs/index.php/ICAPS/article/view/3465

Chiari, Mattia ; Zhao, Shizhe ; Botea, Adi et al. / Cutting the size of Compressed Path Databases with wildcards and redundant symbols. Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling. editor / J. Benton ; Nir Lipovetzky ; Eva Onaindia ; David E. Smith ; Siddharth Srivastava. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2019. pp. 106-113 (Proceedings International Conference on Automated Planning and Scheduling, ICAPS).

@inproceedings{8558f91f38dc473883c45f6a815ab30b,

title = "Cutting the size of Compressed Path Databases with wildcards and redundant symbols",

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.",

author = "Mattia Chiari and Shizhe Zhao and Adi Botea and Alfonso Gerevini and Daniel Harabor and Alessandro Saetti and Matteo Salvetti and Stuckey, {Peter J.}",

year = "2019",

month = jul,

day = "5",

language = "English",

series = "Proceedings International Conference on Automated Planning and Scheduling, ICAPS",

publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

pages = "106--113",

editor = "Benton, {J. } and Nir Lipovetzky and Onaindia, {Eva } and {E. Smith}, {David } and Siddharth Srivastava",

booktitle = "Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling",

address = "United States of America",

note = "International Conference on Automated Planning and Scheduling 2019, ICAPS 2019 ; Conference date: 13-07-2019 Through 15-07-2019",

url = "https://icaps19.icaps-conference.org/, https://ojs.aaai.org/index.php/ICAPS/issue/view/239",

}

Chiari, M, Zhao, S, Botea, A, Gerevini, A, Harabor, D, Saetti, A, Salvetti, M & Stuckey, PJ 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. Proceedings International Conference on Automated Planning and Scheduling, ICAPS, vol. 29, Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 106-113, International Conference on Automated Planning and Scheduling 2019, Berkeley, California, United States of America, 13/07/19. <https://aaai.org/ojs/index.php/ICAPS/article/view/3465>

Cutting the size of Compressed Path Databases with wildcards and redundant symbols. / Chiari, Mattia; Zhao, Shizhe; Botea, Adi et al.

Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling. ed. / J. Benton; Nir Lipovetzky; Eva Onaindia; David E. Smith; Siddharth Srivastava. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2019. p. 106-113 (Proceedings International Conference on Automated Planning and Scheduling, ICAPS; Vol. 29).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

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

AU - Chiari, Mattia

AU - Zhao, Shizhe

AU - Botea, Adi

AU - Gerevini, Alfonso

AU - Harabor, Daniel

AU - Saetti, Alessandro

AU - Salvetti, Matteo

AU - Stuckey, Peter J.

N1 - Conference code: 29th

PY - 2019/7/5

Y1 - 2019/7/5

N2 - 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.

AB - 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.

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

M3 - Conference Paper

T3 - Proceedings International Conference on Automated Planning and Scheduling, ICAPS

SP - 106

EP - 113

BT - Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling

A2 - Benton, J.

A2 - Lipovetzky, Nir

A2 - Onaindia, Eva

A2 - E. Smith, David

A2 - Srivastava, Siddharth

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Palo Alto CA USA

T2 - International Conference on Automated Planning and Scheduling 2019

Y2 - 13 July 2019 through 15 July 2019

ER -

Chiari M, Zhao S, Botea A, Gerevini A, Harabor D, Saetti A et al. Cutting the size of Compressed Path Databases with wildcards and redundant symbols. In Benton J, Lipovetzky N, Onaindia E, E. Smith D, Srivastava S, editors, Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2019. p. 106-113. (Proceedings International Conference on Automated Planning and Scheduling, ICAPS).

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this