Ahead-of-time Compilation for Diverse Samplers of Constrained Design Spaces
Authors: 
Abdelrahman Madkour, Ross Mawhorter, Stacy Marsella, Adam M. Smith, Steven HoltzenAuthors Info & Claims
Abdelrahman Madkour, Ross Mawhorter, Stacy Marsella, Adam M. Smith, Steven HoltzenAuthors Info & ClaimsArticle No.: 54, Pages 1 - 4
Abstract
We introduce a new approach to deploying constraint-based content generators that better supports online generation. Constraint-based generators ensure that certain properties hold in each design they output. However, when deployed a general-purpose solver is often required, thus guarantees come with unpredictable search times and little control over sequentially-generated outputs. In this paper, we outline how we can encode design constraints into a compact circuit representation that affords generation without search. These generators yield samples that are distributed uniformly over the space of valid designs. We illustrate our approach with binary decision diagrams (BDDs) in comparison to the traditional approach with answer-set programming (ASP) in two scenarios: a grid-based tile placement scenario inspired by WaveFunctionCollapse, and a playable platformer level design scenario. These compiled design-space models make constraint-based methods easier to deploy by improving on both the running time and diversity of previous constraint-based methods.
References
[1]
Mark Chavira and Adnan Darwiche. 2008. On Probabilistic Inference by Weighted Model Counting. Artificial Intelligence 172, 6-7 (April 2008), 772–799. https://doi.org/10.1016/j.artint.2007.11.002
[2]
Seth Cooper. 2022. Sturgeon: Tile-Based Procedural Level Generation via Learned and Designed Constraints. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 18, 1 (Oct. 2022), 26–36. https://doi.org/10.1609/aiide.v18i1.21944
[3]
A. Darwiche and P. Marquis. 2002. A Knowledge Compilation Map. Journal of Artificial Intelligence Research 17 (Sept. 2002), 229–264. https://doi.org/10.1613/jair.989 arxiv:1106.1819
[4]
Paulius Dilkas and Vaishak Belle. 2021. Weighted model counting with conditional weights for Bayesian networks. In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence(Proceedings of Machine Learning Research, Vol. 161), Cassio de Campos and Marloes H. Maathuis (Eds.). PMLR, 386–396. https://proceedings.mlr.press/v161/dilkas21a.html
[5]
Daan Fierens, Guy Van Den Broeck, Joris Renkens, Dimitar Shterionov, Bernd Gutmann, Ingo Thon, Gerda Janssens, and Luc De Raedt. [n. d.]. Inference and Learning in Probabilistic Logic Programs Using Weighted Boolean Formulas. 15, 3 ([n. d.]), 358–401. https://doi.org/10.1017/S1471068414000076
[6]
Ioannis Filippidis, Sumanth Dathathri, Scott C Livingston, Necmiye Ozay, and Richard M Murray. 2016. Control design for hybrid systems with TuLiP: The temporal logic planning toolbox. In 2016 IEEE Conference on Control Applications (CCA). IEEE, 1030–1041.
[7]
Maxim Gumin. 2016. WaveFunctionCollapse. https://github.com/mxgmn/WaveFunctionCollapse
[8]
Ian Horswill. 2018. Catsat: A practical, embedded, sat language for runtime pcg. In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, Vol. 14. 38–44.
[9]
Isaac Karth and Adam M. Smith. 2017. WaveFunctionCollapse Is Constraint Solving in the Wild. In Proceedings of the International Conference on the Foundations of Digital Games - FDG ’17. ACM Press, Hyannis, Massachusetts, 1–10. https://doi.org/10.1145/3102071.3110566
[10]
Isaac Karth and Adam M Smith. 2021. WaveFunctionCollapse: content generation via constraint solving and machine learning. IEEE Transactions on Games 14, 3 (2021), 364–376.
[11]
Donald Ervin Knuth. 2009. The Art of Computer Programming. Volume 4, Fascicle 1. Addison-Wesley.
[12]
Chang-Yeong Lee. 1959. Representation of switching circuits by binary-decision programs. The Bell System Technical Journal 38, 4 (1959), 985–999.
[13]
Johannes Pfau, Jan David Smeddinck, and Rainer Malaka. [n. d.]. The Case for Usable AI: What Industry Professionals Make of Academic AI in Video Games. In Extended Abstracts of the 2020 Annual Symposium on Computer-Human Interaction in Play (New York, NY, USA, 2020-11-03) (CHI PLAY ’20). Association for Computing Machinery, 330–334. https://doi.org/10.1145/3383668.3419905
[14]
Adam M. Smith and Michael Mateas. 2011. Answer Set Programming for Procedural Content Generation: A Design Space Approach. IEEE Transactions on Computational Intelligence and AI in Games 3, 3 (Sept. 2011), 187–200. https://doi.org/10.1109/TCIAIG.2011.2158545
[15]
Nathan Sturtevant and Matheus Ota. 2018. Exhaustive and semi-exhaustive procedural content generation. In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, Vol. 14. 109–115.
[16]
Navin Vemuri, Priyank Kalla, and Russell Tessier. 2002. BDD-Based Logic Synthesis for LUT-Based FPGAs. ACM Trans. Des. Autom. Electron. Syst. 7, 4 (oct 2002), 501–525. https://doi.org/10.1145/605440.605442
[17]
Alexander Zook and Mark Riedl. 2014. Automatic Game Design via Mechanic Generation. Proceedings of the AAAI Conference on Artificial Intelligence 28, 1 (Jun. 2014). https://doi.org/10.1609/aaai.v28i1.8788
Index Terms
- Ahead-of-time Compilation for Diverse Samplers of Constrained Design Spaces
Recommendations
Constrained kinds
OOPSLA '12Modern object-oriented languages such as X10 require a rich framework for types capable of expressing both value-dependency and genericity, and supporting pluggable, domain-specific extensions. In earlier work, we presented a framework for constrained ...
Breaking Symmetry for Knowledge Compilation
SAC '23: Proceedings of the 38th ACM/SIGAPP Symposium on Applied ComputingConstraint programming is a powerful paradigm for solving combinatorial problems. Diagnosis, planning, and product configuration, are example use-cases. While reasoning about the solution space of combinatorial problems is usually intractable, ...
Constrained kinds
OOPSLA '12: Proceedings of the ACM international conference on Object oriented programming systems languages and applicationsModern object-oriented languages such as X10 require a rich framework for types capable of expressing both value-dependency and genericity, and supporting pluggable, domain-specific extensions. In earlier work, we presented a framework for constrained ...
Comments
Information & Contributors
Information
Published In
May 2024
644 pages
ISBN:9798400709555
DOI:10.1145/3649921
Copyright © 2024 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 July 2024
Check for updates
Author Tags
Qualifiers
- Short-paper
- Research
- Refereed limited
Conference
FDG 2024
Acceptance Rates
Overall Acceptance Rate 152 of 415 submissions, 37%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 25Total Downloads
- Downloads (Last 12 months)25
- Downloads (Last 6 weeks)5
Reflects downloads up to 28 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format