DROPS

Document

DOI: 10.4230/LIPIcs.CP.2022.18

A Framework for Generating Informative Benchmark Instances

Authors: Nguyen Dang, Özgür Akgün, Joan Espasa, Ian Miguel, and Peter Nightingale

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract

Benchmarking is an important tool for assessing the relative performance of alternative solving approaches. However, the utility of benchmarking is limited by the quantity and quality of the available problem instances. Modern constraint programming languages typically allow the specification of a class-level model that is parameterised over instance data. This separation presents an opportunity for automated approaches to generate instance data that define instances that are graded (solvable at a certain difficulty level for a solver) or can discriminate between two solving approaches. In this paper, we introduce a framework that combines these two properties to generate a large number of benchmark instances, purposely generated for effective and informative benchmarking. We use five problems that were used in the MiniZinc competition to demonstrate the usage of our framework. In addition to producing a ranking among solvers, our framework gives a broader understanding of the behaviour of each solver for the whole instance space; for example by finding subsets of instances where the solver performance significantly varies from its average performance.

Cite as

Nguyen Dang, Özgür Akgün, Joan Espasa, Ian Miguel, and Peter Nightingale. A Framework for Generating Informative Benchmark Instances. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dang_et_al:LIPIcs.CP.2022.18,
  author =	{Dang, Nguyen and Akg\"{u}n, \"{O}zg\"{u}r and Espasa, Joan and Miguel, Ian and Nightingale, Peter},
  title =	{{A Framework for Generating Informative Benchmark Instances}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{18:1--18:18},
  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/entities/document/10.4230/LIPIcs.CP.2022.18},
  URN =		{urn:nbn:de:0030-drops-166479},
  doi =		{10.4230/LIPIcs.CP.2022.18},
  annote =	{Keywords: Instance generation, Benchmarking, Constraint Programming}
}

Document

DOI: 10.4230/LIPIcs.CP.2022.22

Plotting: A Planning Problem with Complex Transitions

Authors: Joan Espasa, Ian Miguel, and Mateu Villaret

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

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.

Cite as

Joan Espasa, Ian Miguel, and Mateu Villaret. Plotting: A Planning Problem with Complex Transitions. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.CP.2022.22},
  URN =		{urn:nbn:de:0030-drops-166514},
  doi =		{10.4230/LIPIcs.CP.2022.22},
  annote =	{Keywords: AI Planning, Modelling, Constraint Programming}
}

Search Results

Documents authored by Espasa, Joan

A Framework for Generating Informative Benchmark Instances

Abstract

Cite as

Plotting: A Planning Problem with Complex Transitions

Abstract

Cite as

Thanks for your feedback!

Could not send message