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
Go to the corresponding LIPIcs Volume Portal

Espasa, Joan ; Miguel, Ian ; Villaret, Mateu

Plotting: A Planning Problem with Complex Transitions

LIPIcs-CP-2022-22.pdf (0.9 MB)


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

  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 =		{},
  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
Collection: 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): archived at:

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI