You-Only-Randomize-Once: Shaping Statistical Properties in Constraint-based PCG

• URL: http://arxiv.org/abs/2409.00837v1
• Date: Sun, 1 Sep 2024 20:43:55 GMT
• Title: You-Only-Randomize-Once: Shaping Statistical Properties in Constraint-based PCG
• Authors: Jediah Katz, Bahar Bateni, Adam M. Smith,
• Abstract summary: We introduce You-Only-Randomize-Once (YORO) pre-rolling, a method for crafting a decision variable ordering for a constraint solver. We show that this technique effectively controls the statistics of tile-grid outputs generated by several off-the-shelf SAT solvers.
• Score: 3.581471126368696
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In procedural content generation, modeling the generation task as a constraint satisfaction problem lets us define local and global constraints on the generated output. However, a generator's perceived quality often involves statistics rather than just hard constraints. For example, we may desire that generated outputs use design elements with a similar distribution to that of reference designs. However, such statistical properties cannot be expressed directly as a hard constraint on the generation of any one output. In contrast, methods which do not use a general-purpose constraint solver, such as Gumin's implementation of the WaveFunctionCollapse (WFC) algorithm, can control output statistics but have limited constraint propagation ability and cannot express non-local constraints. In this paper, we introduce You-Only-Randomize-Once (YORO) pre-rolling, a method for crafting a decision variable ordering for a constraint solver that encodes desired statistics in a constraint-based generator. Using a solver-based WFC as an example, we show that this technique effectively controls the statistics of tile-grid outputs generated by several off-the-shelf SAT solvers, while still enforcing global constraints on the outputs.1 Our approach is immediately applicable to WFC-like generation problems and it offers a conceptual starting point for controlling the design element statistics in other constraint-based generators.

Related papers

• Punch Out Model Synthesis: A Stochastic Algorithm for Constraint Based Tiling Generation [0.0]
  Constraint Based Tiling Generation (CBTG) algorithms can help to automatically create level realizations from a set of tiles and placement constraints. We present Punch Out Model Synthesis (POMS), a Constraint Based Tiling Generation algorithm that can handle large problem sizes.
  arXiv  Detail & Related papers  (2025-01-05T21:49:50Z)
• Generalizing Constraint Models in Constraint Acquisition [6.305123652677644]
  Constraint Acquisition (CA) aims to widen the use of constraint programming by assisting users in the modeling process. Most CA methods suffer from a significant drawback: they learn a single set of individual constraints for a specific problem instance, but cannot generalize these constraints to the parameterized constraint specifications of the problem. We propose GenCon, a novel approach to learn parameterized constraint models capable of modeling varying instances of the same problem.
  arXiv  Detail & Related papers  (2024-12-19T15:31:29Z)
• Diffusion Predictive Control with Constraints [51.91057765703533]
  Diffusion predictive control with constraints (DPCC) An algorithm for diffusion-based control with explicit state and action constraints that can deviate from those in the training data. We show through simulations of a robot manipulator that DPCC outperforms existing methods in satisfying novel test-time constraints while maintaining performance on the learned control task.
  arXiv  Detail & Related papers  (2024-12-12T15:10:22Z)
• Controllable Generation via Locally Constrained Resampling [77.48624621592523]
  We propose a tractable probabilistic approach that performs Bayesian conditioning to draw samples subject to a constraint. Our approach considers the entire sequence, leading to a more globally optimal constrained generation than current greedy methods. We show that our approach is able to steer the model's outputs away from toxic generations, outperforming similar approaches to detoxification.
  arXiv  Detail & Related papers  (2024-10-17T00:49:53Z)
• Compositional Diffusion-Based Continuous Constraint Solvers [98.1702285470628]
  This paper introduces an approach for learning to solve continuous constraint satisfaction problems (CCSP) in robotic reasoning and planning. By contrast, our model, the compositional diffusion continuous constraint solver (Diffusion-CCSP), derives global solutions to CCSPs.
  arXiv  Detail & Related papers  (2023-09-02T15:20:36Z)
• A New Computationally Simple Approach for Implementing Neural Networks with Output Hard Constraints [5.482532589225552]
  A new method of imposing hard convex constraints on the neural network output values is proposed. The mapping is implemented by the additional neural network layer with constraints for output. The proposed method is simply extended to the case when constraints are imposed not only on the output vectors, but also on joint constraints depending on inputs.
  arXiv  Detail & Related papers  (2023-07-19T21:06:43Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics [69.8062252611486]
  Cold decoding is a flexible framework that can be applied directly to off-the-shelf left-to-right language models. Our experiments on constrained generation tasks point to the effectiveness of our approach, both in terms of automatic and human evaluation.
  arXiv  Detail & Related papers  (2022-02-23T18:59:27Z)
• Discrete fully probabilistic design: a tool to design control policies from examples [2.6749261270690425]
  We present a discretized design that expounds an algorithm recently introduced in Gagliardi and Russo (2021) to synthesize control policies. The constraints do not need to be fulfilled in the possibly noisy example data, which in turn might be collected from a system that is different from the one under control.
  arXiv  Detail & Related papers  (2021-12-21T13:44:48Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.