Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2022.22
URN: urn:nbn:de:0030-drops-166514
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16651/
Espasa, Joan ; Miguel, Ian ; Villaret, Mateu
Plotting: A Planning Problem with Complex Transitions
| pdf-format: |
|
Abstract
We focus on a planning problem based on Plotting, a tile-matching puzzle video game published by Taito. The objective of the game is to remove at least a certain number of coloured blocks from a grid by sequentially shooting blocks into the same grid. The interest and difficulty of Plotting is due to the complex transitions after every shot: various blocks are affected directly, while others can be indirectly affected by gravity. We highlight the difficulties and inefficiencies of modelling and solving Plotting using PDDL, the de-facto standard language for AI planners. We also provide two constraint models that are able to capture the inherent complexities of the problem. In addition, we provide a set of benchmark instances, an instance generator and an extensive experimental comparison demonstrating solving performance with SAT, CP, MIP and a state-of-the-art AI planner.
BibTeX - Entry
@InProceedings{espasa_et_al:LIPIcs.CP.2022.22,
author = {Espasa, Joan and Miguel, Ian and Villaret, Mateu},
title = {{Plotting: A Planning Problem with Complex Transitions}},
booktitle = {28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
pages = {22:1--22:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-240-2},
ISSN = {1868-8969},
year = {2022},
volume = {235},
editor = {Solnon, Christine},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16651},
URN = {urn:nbn:de:0030-drops-166514},
doi = {10.4230/LIPIcs.CP.2022.22},
annote = {Keywords: AI Planning, Modelling, Constraint Programming}
}
| Keywords: | AI Planning, Modelling, Constraint Programming | |
| Seminar: | 28th International Conference on Principles and Practice of Constraint Programming (CP 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 23.07.2022 | |
| Supplementary Material: | Software (Source Code and Data): https://github.com/stacs-cp/CP2022-Plotting archived at: https://archive.softwareheritage.org/swh:1:dir:8bb3fab72f1db2cac9715651ed05528cd2cf24c8 |
