Plotting: a planning problem with complex transitions

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Downloads (Pure)

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.
Original languageEnglish
Title of host publication28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
EditorsChristine Solon
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages17
ISBN (Electronic)9783959772402
DOIs
Publication statusPublished - 23 Jul 2022
Event28th International Conference on Principles and Practice of Constraint Programming (CP 2022) - Haifa, Israel
Duration: 31 Jul 20225 Aug 2022
Conference number: 28
https://cp2022.a4cp.org/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl -- Leibniz-Zentrum für Informatik
Volume235
ISSN (Electronic)1868-8969

Conference

Conference28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Abbreviated titleCP 2022
Country/TerritoryIsrael
CityHaifa
Period31/07/225/08/22
Internet address

Keywords

  • AI Planning
  • Modelling
  • Constraint programming

Fingerprint

Dive into the research topics of 'Plotting: a planning problem with complex transitions'. Together they form a unique fingerprint.

Cite this