DROPS

Document

DOI: 10.4230/LIPIcs.CP.2023.29

Distribution Optimization in Constraint Programming

Authors: Guillaume Perez, Gaël Glorian, Wijnand Suijlen, and Arnaud Lallouet

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract

Stochastic Constraint Programming introduces stochastic variables following a probability distribution to model uncertainty. In the classical setting, probability distributions are given and constant. We propose a framework in which random variables are given a set of possible distributions and only one should be selected. A solution is obtained when all variable distributions are assigned, and all decision variables are assigned too. In such a setting, a constraint on random variables limits the possible distributions its random variables may take. We generalize the notion of chance as the probability of satisfaction of a constraint, called probabilization, given variable distributions. Probabilization can be seen as a generalization of reification in a random setting whose result is a random variable. We define minimal arithmetic to work with stochastic variables having a variable distribution. Using the introduced representation, our framework can in theory save an exponential number of decisions, and represents problems that were previously not representable with finite integer domains. Finally, we model and solve two industrial problems that require this extension - virtual network configuration and assignment of chemical delivery - and show improvement in terms of quality of solution and speed.

Cite as

Guillaume Perez, Gaël Glorian, Wijnand Suijlen, and Arnaud Lallouet. Distribution Optimization in Constraint Programming. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 29:1-29:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{perez_et_al:LIPIcs.CP.2023.29,
  author =	{Perez, Guillaume and Glorian, Ga\"{e}l and Suijlen, Wijnand and Lallouet, Arnaud},
  title =	{{Distribution Optimization in Constraint Programming}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{29:1--29:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.29},
  URN =		{urn:nbn:de:0030-drops-190664},
  doi =		{10.4230/LIPIcs.CP.2023.29},
  annote =	{Keywords: Constraint Programming, Optimization, Stochastic Optimization}
}

Document

DOI: 10.4230/LIPIcs.CP.2021.27

The Dungeon Variations Problem Using Constraint Programming

Authors: Gaël Glorian, Adrien Debesson, Sylvain Yvon-Paliot, and Laurent Simon

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract

The video games industry generates billions of dollars in sales every year. Video games can offer increasingly complex gaming experiences, with gigantic (but consistent) open worlds, thanks to larger and larger teams of developers and artists. In this paper, we propose a constraint-based approach for procedural dungeon generation in an open world/universe context, in order to provide players with consistent, open worlds with an excellent quality of storytelling. Thanks to a global description capturing all the possible rooms and situations of a given dungeon, our approach allows enumerating variations of this global pattern, which can then be presented to the player for more diversity. We formalise this problem in constraint programming by exploiting a graph abstraction of the dungeon pattern structure. Every path of the graph represents a possible variation matching a given set of constraints. We introduce a new propagator extending the "connected" graph constraint, which allows considering directed graphs with cycles. We show that thanks to this model and the proposed new propagator, it is possible to handle scenarios at the forefront of the game industry (AAA+ games). We demonstrate that our approach outperforms non-specialised solutions consisting of filtering only the relevant solutions a posteriori. We then conclude and offer several exciting perspectives raised by this approach to the Dungeon Variations Problem.

Cite as

Gaël Glorian, Adrien Debesson, Sylvain Yvon-Paliot, and Laurent Simon. The Dungeon Variations Problem Using Constraint Programming. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{glorian_et_al:LIPIcs.CP.2021.27,
  author =	{Glorian, Ga\"{e}l and Debesson, Adrien and Yvon-Paliot, Sylvain and Simon, Laurent},
  title =	{{The Dungeon Variations Problem Using Constraint Programming}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.27},
  URN =		{urn:nbn:de:0030-drops-153181},
  doi =		{10.4230/LIPIcs.CP.2021.27},
  annote =	{Keywords: constraint programming, video games, modelization, procedural generation}
}

Search Results

Documents authored by Glorian, Gaël

Distribution Optimization in Constraint Programming

Abstract

Cite as

The Dungeon Variations Problem Using Constraint Programming

Abstract

Cite as

Thanks for your feedback!

Could not send message