License: 
Creative Commons Attribution 4.0 International 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16651/
Espasa, Joan ;
Miguel, Ian ;
Villaret, Mateu
Plotting: A Planning Problem with Complex Transitions
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}
}
