Plotting: A Planning Problem with Complex Transitions
Plotting: A Planning Problem with Complex Transitions
复制标题
DOI：
10.4230/lipics.cp.2022.22
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Joan Espasa;Ian Miguel;Mateu Villaret
中科院分区：
文献类型：
--
作者：
Joan Espasa;Ian Miguel;Mateu Villaret
我们专注于一个规划问题的基础上Plotting，瓷砖匹配的益智视频游戏Taito出版。游戏的目标是通过顺序地将方块射击到同一网格中，从网格中移除至少一定数量的彩色方块。Plotting的兴趣和难度在于每个镜头后的复杂过渡：各种块直接受到影响，而其他块可能受到重力的间接影响。我们强调了使用PDDL建模和解决Plotting的困难和效率低下，PDDL是AI规划者的事实上的标准语言。我们还提供了两个约束模型，能够捕捉问题的内在复杂性。此外，我们还提供了一组基准实例，一个实例生成器和一个广泛的实验比较，展示了SAT，CP，MIP和最先进的AI规划器的解决性能
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