2026-07-24T03:16:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16651 2024-03-06T10:57:58Z ddc:004 open_access

Plotting: A Planning Problem with Complex Transitions Espasa, Joan Miguel, Ian Villaret, Mateu AI Planning Modelling Constraint Programming 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joan Espasa and Ian Miguel and Mateu Villaret 2022 Is Part Of LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2022.22 urn:nbn:de:0030-drops-166514 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.22 eng https://creativecommons.org/licenses/by/4.0/legalcode