Brick-by-Brick: Combinatorial Construction with Deep Reinforcement Learning

Abstract

Discovering a solution in a combinatorial space is prevalent in many real-world problems but it is also challenging due to diverse complex constraints and the vast number of possible combinations. To address such a problem, we introduce a novel formulation, combinatorial construction, which requires a building agent to assemble unit primitives (i.e., LEGO bricks) sequentially -- every connection between two bricks must follow a fixed rule, while no bricks mutually overlap. To construct a target object, we provide incomplete knowledge about the desired target (i.e., 2D images) instead of exact and explicit volumetric information to the agent. This problem requires a comprehensive understanding of partial information and long-term planning to append a brick sequentially, which leads us to employ reinforcement learning. The approach has to consider a variable-sized action space where a large number of invalid actions, which would cause overlap between bricks, exist. To resolve these issues, our model, dubbed Brick-by-Brick, adopts an action validity prediction network that efficiently filters invalid actions for an actor-critic network. We demonstrate that the proposed method successfully learns to construct an unseen object conditioned on a single image or multiple views of a target object.

arXiv comment21 pages, 13 figures, 7 tables. Accepted at the 35th Conference on Neural Information Processing Systems (NeurIPS 2021)

References in corpus (11)

• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• High-Dimensional Continuous Control Using Generalized Advantage Estimation
• Learning a Probabilistic Latent Space of Object Shapes via 3D Generative-Adversarial Modeling
• Learning Representations and Generative Models for 3D Point Clouds
• GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
• MolGAN: An implicit generative model for small molecular graphs
• Learning Deep Generative Models of Graphs
• Efficient Graph Generation with Graph Recurrent Attention Networks
• Relational inductive bias for physical construction in humans and machines
• Combinatorial 3D Shape Generation via Sequential Assembly
• Building LEGO Using Deep Generative Models of Graphs