Budget-Aware Sequential Brick Assembly with Efficient Constraint Satisfaction
Authors: Seokjun Ahn
Jungtaek Kim
Minsu Cho
Jaesik Park
Venue: Accepted by TMLR ()

Abstract: We tackle the problem of sequential brick assembly with LEGO bricks to create combinatorial 3D structures. This problem is challenging since this brick assembly task encompasses the characteristics of combinatorial optimization problems. In particular, the number of assemblable structures increases exponentially as the number of bricks used increases. To solve this problem, we propose a new method to predict the scores of the next brick position by employing a U-shaped sparse 3D convolutional neural network. Along with the 3D convolutional network, a one-initialized brick-sized convolution filter is used to efficiently validate assembly constraints between bricks without training itself. By the nature of this one-initialized convolution filter, we can readily consider several different brick types by benefiting from modern implementation of convolution operations. To generate a novel structure, we devise a sampling strategy to determine the next brick position considering the satisfaction of assembly constraints. Moreover, our method is designed for either budget-free or budget-aware scenario where a budget may confine the number of bricks and their types. We demonstrate that our method successfully generates a variety of brick structures and outperforms existing methods with Bayesian optimization, deep graph generative model, and reinforcement learning.

Published in Transactions on Machine Learning Research (09/2024)
Budget-Aware Sequential Brick Assembly with Efficient Constraint Satisfaction
Seokjun Ahn POSTECH
sdeveloperdpooseehh.ckkk
Jungtack Kim University of Pittsburgh
jungtack.kimäkydte edu
Minsu Cho POSTECH
mscho@@postech.oc.k
Jaesik Park Scoul National University
joesik. manssk.pakk@snu..c... oc.kr
Reviewed on OpenReview: https: //
// openreview. net/ forum? id- OmR Q00kgk
Abstract
We tackle the problem of sequential brick assembly with LEGO bricks to create combinatorial 3D structures. This problem is challenging since this brick assembly lask encompasses the characteristics of combinatorial optimization problems. In particular, the number of assemblable structures increases exponentially the number of bricks used increases. To solve this problem, propose new method to predict the scores of the next brick position by employing a U-shaped sparse 3D convolutional neural network. Along with the 3D convolutional network, a one-initialized brick-sizer convolution filter is used to efficiently validate assembly constraints between bricks without training itself. By the nature of this one-initialized convolution filter, we can readily consider several different brick types by benefiting from modern implementation of convolution operations. To generate a novel structure, we devise a sampling strategy to determine the next brick position considering the satisfaction of assembly constraints. Moreover, our method is designed for either budget- free or budget-awart aware scenario where budget may confine the number of bricks and their types. We demonstrate that our method successfully generates variety of brick structures and out performs existing methods with Bayesian optimization, deep graph generative model, and reinforcement learning.
1 Introduction
Most real-world 3D structures are constructed with smaller primitives. A broad range of studies have lackled interesting assembly problems such as molecule generation (Ertl et al.
2017 Neil et al.
2018 You et al.
2018), building construction (Talton et al. 2011 Martinovic Van Gool
2013 Ritchie et al. 2015). and
assembly generation (Sung al.] 2017] Lee al. 2021; Jones al.) 2002bb]
Lee al. 2022 In particular,
if unit primitives are used to construct 3D structures
desire to assemble, this task becomes instance of combinatorial optimization problems, in which search space increases exponentially
search depth increases. Formally, given n primitives with & possible connections between two primitives, the search space increases by (k:"). In addition to the combinatorial property, the consideration of assembly constraints between unit primitives makes the problem more challenging.
"Equal contribution.
The implementation of our method available at http:://gtthbb..mmm/oaaa//////tt

---

Published in Transactions on Machine Learning Research (09/2024)
Table Comparisons of the existing approaches and our method. SA, BayesOpt, GGM, RL, and SL stand for sequential assembly, Bayesian optimization, graph generative model, reinforcement learning, and supervised learning, respectively.
Unit
Target
Constraint Satisfaction
Method
Algorithm
Primitives
Conditioning
SA w/ BayesOpt
Single
BayesOpt
Target volume
Subsampling
DGMLG Srick-by-Bried
Single
GGM
Class label
Masking
Single
RL
Single- or multi-view images
SL
No larget conditioning for generation task Incomplete target volume for a completion task
Convolution
BrRCS (Ours)
Multiple
SL.
operations
The problem of sequential assembly with LEGO bricks inherits the aforementioned properties, in that a decision-making process sequentially determines where brick is placed. Supposing that we are given many bricks to assemble, there
large number of assemblable combinations. Morcover, the docision-making process must consider complex assembly constraints, i.e., the disallowance of overlap, isolated bricks, and LEGO-specific connections. Compared to generic 3D generation methods (Wu et al. 2016 Gadelha et al. 2018 Achlioptas et al. 2018), our brick assembly task can generate 3D structures in an open space and provide brick-wise instructions to build the structures.
Several attempts have been employed to solve sequential brick assembly by utilizing Bayesian optimiza- tion (Kim et al.) 2020 deep graph generative models (Thompson al. 2020),, ; and reinforcement learn- ing Chung et al. 2021). as summarized in Table Those methods end with the consideration of the assembly with only 2 4 LEGO bricks they might. be capable of assembling other brick types without significant modification, though. Moreover, the previous literature has several respective limitations. The Bayesian optimization-basee method (Kim et al., 2020) requires heavy computations due to its iterative optimization process. Another method (Thompson et al. 2020) has been proposed using masks to filter out invalid actions along with their graph generative model, but the use of masks degrades assembly performance. To predict a valid action, the recent work (Chung et al., 2021] utilizes an auxiliary neural network that often fails to predict legitimate moves perfectly. More importantly, these methods share common limitation: they inevitably become slower in validating assembly construints as the number of bricks increases, due to the exponentially incrcasing scarch spaces.
To tackle the limitations mentioned above, we devise a novel brick assembly method with a U-shaped neural network utilizing a one-initialized brick-sized convolution filter to validate complex constraints efficiently. Notably, our ono-initialized convolution filter enables our method validate the constraints in a parallelizable and scalable manner without training itself, where several different brick types are considered. Using the sampling procedure proposed in this work, method can create diverse sequences of LEGO bricks to generate high-fidelity brick structures. Furthermore, we consider two scenarios, budget-free and budget- aware assembly pipelines where budget limits the number of bricks and their types. Henceforth, we refer to our method as sequential Brick assembly with Efficient Constraint Satisfaction (BrECS).
In summarr, the contributions of this work are as follows:
We propose a novel sequential brick assembly model, which validates assembly constraints with a one-initialized brick-sized convolution filter and generates high-fidelity 3D structures;
We utilize a U-shaped sparse 3D convolutional neural network that is trained with a voxelized dataset of 4040 (Wu et al. 2015
We show that our model successfully assembles different brick types in various circumstances, in- cluding budget-aware scenario.
2

---

Published in Transactions on Machine Learning Research (09/2024)
2
Related Work
3D Shape Generation. Point cloud and voxel representations are widely used in 3D shape genera- tion. Various methods with variational auto-encoders (Gadelha et al.] 2018 generative adversarial net- works (Achlioptas et al. 2018), and normalizing flows (Yang et al., 2019 have been proposed to generate point clouds. On the other hand, voxel-based 3D shape generation has been studied. Wu et al. (2016) pro- pose a generative adversarial network to generate voxel occupancy. Choy al. (2019) generate 3D shapes on voxel grids with a fully convolutional network that includes efficient sparse convolution. Zhang et al. (0221 propose method to generate high-quality voxel-based shapes applying 3D convolutional networks.
Sequential Part Assembly. Similar to the sequential ial brick assembly problem, sequential part assembly shares common difficulties with a combinatorial optimization problem. [Cenn et al. (2022) introduce a pairwise shape assembly model but the model is limited to the pairwise assembly. (oonss et al. (2021a);
Willis et al. (2022) suggest CAD parts assembly model which assembles parts by exploiting semantic CAD shape information and extracting features from it. Ghasemipour et al. (2022) aim to assemble multi-part objects and tackle the problem with large-scale reinforcement learning and graph-based model architecture. Sung et al. (2017) assemble incomplete 3D parts with a part retrieval network and a position prediction network. Hu et al. (2020) propose a model that sequentially moves a piled box into another container with different shapes. They tackle the problem by representing previous boxes into graphs and reinforcement learning with rewards considering physical constraints in a new container.
Sequential Brick Assembly. Unlike generic 3D shape generation methods and part assembly methods
the sequential brick assembly approaches (Kim et al. 2020 Thompson et al. 2020 Chung et al. 2021
consider the assembly constraints that are introduced by allachable connections between two adjacent bricks
and the disallowance of brick overlap, as shown in Figure 2 As discussed in the work (Kim et al.) 2020).
these constraints encourage us to accentuate the nature of combinatorial optimization since a huge number of assemblable combinations exist in the presence of complex constraints. However, is not trivial to validate such constraints. As in Table 1 overcome these difficulties, Kim et al. (2020) sample a subset of available next brick positions, Thompson et al. (2020) mask out invalid positions by validating all possible positions, and Chung et al. (2021) train an auxiliary network for validating positions.
Brick Assembly in Physical World. Luo et al. 2015 show a method to find LEGO brick structures in
consideration of physical constraints. Nägele et al. (2020) propose a two-layer planning approach for multi- robot LEGO brick assembly. Li et al. (2021) suggest a bi-level robot framework to learn to design and build bridges with blocks under the assumption that blueprint is not accessible. [Lu et al. (2023) develop a robot
system to learn assembly and disassembly processes from human demonstration. [iu al. (2024) provide analysis on the physical stability of 3D structures with LEGO bricks examining force balancing equations.
3 Budget-Aware Sequential Brick Assembly
In this section we introduce the brick assembly problem tackled in this paper.
Formulation. Similar to the previous work (Chung et al. 2021 a new brick is connected to one or (possibly) more bricks of previously assembled bricks. It implies that the position of the next brick can be determined as relative displacement from a certain brick directly connected to the next brick. we denote this indicator brick as a pivot brick. After choosing the pivot brick, we finally determine a relative position to assemble from the pivot brick. Ultimately, the goal of this work is to predict a sequence of brick placements from scratch or from incomplete brick structure. In particular, in inference stage, our model does not utilize any guidance for final brick structures.
Objectives. Our sequential brick assembly aims at assembling LEGO bricks to 3D structures that resemble the 3D structures used in the training of our proposed model. As described above, we do not provide any guidance for final target structures in an inference stage and construct 3D structures from scratch or from incomplete brick structures. Note that a scenario of building 3D structures from scratch is called generation
3

---

Published in Transactions on Machine Learning Research (09/2024)
Next brick position predictor
1992
A4-3
U-Net
Voxel-wise scores
Brick-wisc scorcs
Next brick position selection
B,
Apply brick-sized convolution filter K
+
C Validated brick scores
Place a brick using scores
Brrl
2 x
Brick-wise validity
Apply brick-sized
Brick position validator
convolution filter
Figure 1: Illustration of the efficient constraint satisfaction method with convolution filters for sequential brick assembly. U-Net and @ denote a U-shaped neural network with sparse 3D convolutional layers and element-wise multiplication, respectively.
task and a scenario of building 3D structures from incomplete brick structures is called a completion task. Moreover, we consider budget-free or budget-aware scenario in sequential brick assembly.
Constraints. Inspired by the standard LEGO bricks, we take into account three constraints in the brick assembly problem: (i) bricks should not overlap with each other (NO-OVERLAP); (ii) all bricks of the current structure should be connected each other so that the current structure is represented as one connected structure (NO-IBOLATION); (ifi) new brick must be directly attached to the upper lower position of other bricks (VERTTCAL-ASSEMBLEE)
Budgets. Suppose that brick budget is predefined, where a budget indicates the number of assemblable bricks for each brick type. For example, if we are given four 2 4 and two 2 LEGO bricks as a brick budget, we can only assemble those six bricks in total. On the other hand, we are given an infinite budget, our framework choose any brick type without restriction.
4 Proposed Approach
Here, we explain four steps of our method BrECS, which are illustrated in Figure 1 To up, generate brick structure under assembly constraints by repeating the following steps: (i) score computation of next brick positions, (ii) exclusion of invalid positions, (iii) sampling of pivot brick, and (iv) determination of a relative brick position. Note that neural network for computing the scores of next brick positions an only learnable component in our framework.
4.1 Efficient Constraint Satisfaction
We propose a novel method to tackle the challenge of satisfying the following constraints: NO-OVERLAP, which is validated by using convolution operations; NO-ISOLATION and VERTICAL-ASSEMBLLE, which are satisfied by following the brick assembly formulation with pivot bricks and relative brick positions. Borrowing the concept of constraint satisfaction (Tsang 1993), which is the problem of finding solutions that satisfy predefined set of constraints, our method is designed to establish an approach to efficient constraint satisfaction for sequential brick assembly.
Predicting Next Brick Positions. Given a voxel representation of structure at step t, which is denoted B, {0, laxxxa where is the size of 3D space, first feed the voxel representation B, into U-shaped
4

---

Published in Transactions on Machine Learning Research (09/2024)
a
(b)
V t+1
(c)
Figure Illustratoon of how one-initialized brick-size convolution filters work where red brick a pivot brick and green brick has been assembled to the red brick. The grid shows the validity V of each brick position on the red brick for brick type 2x2. The pixels in red rectangle indicate attachable brick positions on the red brick. The green pixels indicate that overlap with the green brick will occur if a new brick is attached to the corresponding position. Therefore, (a) and (c) violate NO-OVERLAP and NO-ISOLATION, respectively, and (b) sat isfies the assembly constraints.
sparse 3D convolutional neural network, inspired by Choy al. 2011
B U-Net(Btt,
(1)
in order to capture global and local contexts effectively and retain the same dimensionality. Due to its pyramidal feature extraction structure, the U-Net extracts robust features understanding multi-dimensional contexts. In particular, we validate that the U-Net effectively extracts important contexts and thus improves overall performance compared to other neural networks; see Table for thorough study on neural archi- tectures. Moreover, 3D structure, which is represented by a probability of voxel occupancy. Note that the network parameters in this U-Net are the only learnable component in our framework BrECS. In this section, we assume that we are given the pretrained U-Net.
expect that neural network produces likely complete potentially next-step
After obtaining By Rexaaxa scores for next brick positions A E Baxaxa are computed by sliding a convolution filter K Rwsxd,x1 across B/:
A = B' K
(2)
where is convolution operation. We match the size of Att1 to the size of B, by applying zero padding. In particular, the size of the convolution filter is the same as the brick size we assemble ws x de where w, and d, are the width and depth the brick, respectively, so that we can determine the scores over all the possible positions of the next brick by aggregating the corresponding voxels. For example, if we use 2 4 bricks, the size of the convolution filter is 2 x 1. Moreover, K always initialized as tensor filled with without updating its values in training stage to aggregate wods voxels equally with single convolution operation.
5

---

Published in Transactions on Machine Learning Research (09/2024)
In the case of assembling structure with r brick types, we use 2r convolution filters of the same size with brick types and repeat the above process for each convolution filter. Notably, for each brick type, we employ two convolutional filters (i.e., wh x do x 1 and de x wh x 1) to consider brick rotation.
Filtering out Invalid Brick Positions. As shown in Figure 1 to predict the validity of the next brick positions, a one-initialized brick-sized convolution filter is applied B,:
V, B. K.
(3)
The filter K is identical to the filter used in computing the score for the next brick positions. After applying the convolution filter across B,, all attachable brick positions are determined if the value of the position of interest is zero, which means that no overlap exists within the brick positions. As visualized in Figure 2 the validity of each position in terms of overlap and the number of attachable positions with respect to the brick of interest are readily determined by applying the convolution filter of the corresponding brick type.
Using these two branches for computing Ast1 and V,, which are shown in Equations ( and 3 we can define validated scores for next. brick positions C++1- Each entry of C++1 is equal to its score for next brick positions filtering out invalid brick positions. Formally, we describe C++1 of assembling a wy x dl brick on a pivot brick:
C++1 (idlasee vijke(a) (Vi) O A++1
B Vi..ke(a] (B, K) (U-Net(B:)) * =)),
(4)
where 1[v vi.jAe[4 is an indicator function, K E xxxx1 the one-initialized convolution filter, and is convolution operation. Since the calculation of the masked score tensor C2+1 uses convolution operations, we efficiently compute it with modern GPU devices. Specifically, while the validity check of (64, 64, 64) voxels without parallelization takes 4.7 seconds, the identical validity check with our method takes only 0.0021 seconds; ours yields approximately 2,300 times faster inference on the validity check.
Selecting Pivot Bricks by Sampling. To place single brick, we need to choose one of previously assembled bricks, i.e., pivot brick, to attach new brick. The motivation of our method to select a pivol brick is that pivot brick with higher sum of attachable brick scores should be preferable to one with lower sum of attachable brick scores, rather than choosing a pivot brick that is connected to position with the highest score of C++1. Since neural network tends to memorize training samples and their assembly sequences, choosing a position with the highest score fails to create a novel structure. Instead of a deterministic approach based on C2+1, we alter a method to select a pivot brick into a sampling method. To compare the number of altachable positions, we define a pivot score Tijk of the pivot of (i,j,k) k) to aggregate scores of attachable positions:
<+( -1
-+(
Tisk
Σ
Σ
Σ Cimns
(5)
Imi- ([wr) j= -11 (R-1,
where w' = wwttie d' do and wp x dp is the size of a pivot brick candidate. After computing pivot 2 2;
scores, we employ a sampling strategy to determine a pivot brick:
b,, P,
(6)
where
Tisk
Dplu E(em, ()l.mn))epivots Timn
(7)
Our sequential procedure for pivot brick predictions is inspired by Monte-Carlo tree search (MCTS) (Coulom 2006). MCTS evaluates possible actions by expanding a search tree with Monte-Carld simulations and back- ups. Similar to this, our method also evaluates pivot brick candidates by aggregating their attachable brick scores, so that pivot with more attachable bricks will more likely be selected. Our method utilizes the U- shaped sparse 3D convolutional neural network predict possible brick positions, which is analogous to a policy network of the MCTS method (Silver et al., 2016), which employs a neural network to predict prior distributions for search tree expansion.

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm Assembly of single brick
Input: Voxels of structure current time step B, list of assembled brick positions P, and brick size
Wb x d,
Output: Position of a pivot brick (a, b)), a relative position of the next brick (2r, V/
1: Initialize one-initialized brick-sized convolution filter K E RRxxxdxx x1 list of pivot scores T = 6. and
possible relative connections .V with values satisfying the conditions of Equations
and (10)
2: Calculate C using Equation (4). for each pivot (a,b, c) E P do Calculate Tabe using Equation TUUU (Tabe).
end for Sample pivot brick (a, Σver" T'
Tabe
8: Determine a relative position of the next brick: (a, y, 2) = arg (abcce Catn.byyccs.
Determining Relative Brick Positions. After choosing a pivot brick, a relative brick position to the pivot brick is determined to complete the brick placement. Possible relative brick positions (ær, y, x) for assembling a wy x d, brick on a pivot brick of size up x dp are inherently integer-valued positions satisfying following conditions:
+ Upp
Wh + Upp
-1505
1,
(8)
2
2
dp + dp
dg + dp
- -
1,
(9)
2
2 2 (-1,11
(10)
choose the relative brick position (z, 2,2 with the highest score of C.+1. A brick must be attached to the pivot brick add scores of every attachable brick in Equation 5 In this step, we do not employ sampling method due to its poor empirical results.
By considering the conditions described in Equations S 9 and 10
As a result, Algorithm presents the overall procedure to assemble a single brick. By repeating Algorithm we can assemble a number of bricks where either budget-free or budget-aware scenario is assumed.
4.2 Training Procedure of the Score Function
Similar research on language modeling (Mikolov et al., 2010 Sutskever et al. 2014) and reinforcement learning (Sutton & Barto 2018). our model also predicts a next brick position sequentially. To train such a prediction model, a pair of ground-truth state transition is required as a training sample. However, final voxel occupancy is only available ground-truth information. It implics that cannot access intermediate states explicitly. To resolve this issue, we generate an assembly sequence [Bo, Bi,..., Br from the ground-truth voxel occupancy following the procedure described in this section. Eventually, we can utilize this generated sequence to train a model in an autoregressive manner. In addition, generated sequences are unique and diverse, since the stochasticity injected from the sampling strategy previously introduced.
Since there exist numerous possible sequences assemble bricks to a certain 3D structure, a single-step look-ahead with a pair of contiguous states, i.e, (B,, B,+1), is not enough to model practical assembly scenarios. In addition, the training becomes unstable even though the training pairs slightly change. To address these issues, we train our sequential model to predict k-step look-ahead state using pairs of states at step / and step ++ k, i.e., (B,, B+++). From now, we call this technique sequence skipping.
We employ a vixel-wise binary cross-entropy to train our model. By restricting the voxel prediction using a sigmoid function and minimizing the voxel-wise binary cross-cntropy, our model learns to predict valid voxel-wise probabilities of the Bernoulii distribution. To sum up, we train our sequential prediction model follows:
7

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm 2 Model training for brick assembly
Input: Dataset D, a batch size M, a sequence skipping value It
Output: Model parameters for brick assembly 0
Generate ground-truth brick assembly sequences Bor and store in D, using voxel shapes x; E D. (5) Initialize buffer B with (B O.T, Fz, 0) where 2j D, B (i) 0:T E D,.
3: repeat.
4: C
5: Sample and remove a batch ((B (Bo.7: Ti, W))s from B. for (B Fis 4)) in batch do
L + L + log log po (B tc+ ( if 4 + k = T then
7:
8:
Push (B (B,,, T2, into B where Tj ~ D and B()
9:
o:r E D..
10:
else
B BU ( 2. 1)}.
11:
12:
end if end for
13:
14:
dC 0- 0 + 70
15:
until convergence
We generate a sequence of voxel occupancy tensors [Bo, BI....,,Br by rumning our brick assembly method with the ground-truth voxel occupancy a training datasct;
We generate multi-step pairs from [Bo, B Br] in sliding-window fashion, i.e.
{(B,, B.
3. We train transition function po (B [B)) with (B,, B +T and the voxel-wise cross-entropy.
To decorrelate the time steps of training pairs a batch and shorten training time, we use a buffer throughout training lo store training pairs similar the work (Zhang et al. 2021). The detailed process is described in Algorithm 2
4.3 Inference for Sequential Brick Assembly
In an inference stage, we determine the next brick positions by following our aforementioned procedure, given Bo. We provide different form of Bg depending sequentially generate B, until terminal step T. For completion task that is designed to assemble bricks from a incomplete brick structure, we use an intermediate state, i.e., incomplete brick structure, Bo. For a generation task that is designed to assemble bricks from scratch, we sample an initial brick position from a discrete uniform distribution, i.c., (z, y. ~ u(f-2,2))) Then, we assemble bricks on a zoro-centerod voxel grid of size (64, 64, 64) and use the voxel occupancy of the initial brick position sampled as Bo-
task, i.c., completion and generation, and
4.4 Budget-Aware Sequential Brick Assembly
Suppose that we are given brick lypes. Shape of i-th brick lype different. the other brick type shapes, where the volume of i-th brick type is eg For the sake of brevity, we define that the volume of the largest brick type is U1 and the volume of the smallest brick type is eg. More concretely, Us fk-1 ... S v1- A budget of brick types is represented as [er,..... cu) and ||с|] assemble, which implies that we have c; bricks for i-th brick type for i [k]. Then, probability of the next brick placement over brick types is post-processed by the following:
is the total budget of bricks we can
p(a X,-1, cc-1) = ( C
Ct-1
@ p(a X--1)).
(11)
where X,-1 is a structure that has been assembled until iteration 1, Ct-1 the budget of brick types at iteration 1- 1, [fi,..., ux] is the volumes of brick types, and g is sum-to-one function. After
8

---

Published in Transactions on Machine Learning Research (09/2024)
choosing the brick type of the next brick and its placement, X,-1 and Ct-1 updated. The rationale behind Equation (11) is that larger and abundant bricks are assembled first. This helps to first build the skeleton of a brick structure with larger bricks and then express the fine parts of the structure. In addition, the consideration of abundance makes abundant bricks consume first.
5 Experimental Results
We demonstrate that our model generates diverse structures with high fidelity satisfying assembly constraints in the experiments on the completion and generation of brick structures with distinct brick types. Moreover, more elaborate studies are conducted in order to validate BrECS.
Dataset. To generate souund-tuuhh assembly sequences and the training pairs based the ground-truth sequences, we use the ModelNet40 dataset (Wu et al. 2015). In particular, the categories of airplane, table, and chair are used for assembly experiments. 3D meshes in the dataset are converted into (64, 64, 64)-sized voxel grids, and then they are scaled down to 1/4 of the original size to reduce the number of required bricks.
Mctrics. For the completion task, we use intersection over union (IoU) evaluate the performance:
E
k=
B
[
(B(2)
LoU(B(",
(12)
ligk
where B e Rexaxa Along with IoU, we measure the ratio of valid structures to all the structures assembled:
% valid
Myalid
(13)
where mealid is the number of brick structures that satisfy assembly constraints and m is the number of brick structures assembled. In addition, we utilize a class probability of target class, which is the softmax output the generation of brick structures. The probability of the target class
of the target class, in experiments is measured using pretrained classifier with the ModelNet40 dataset. We generate 100 samples and report averaged metrics over 100 samples for all experiments.
Baseline Methods. We compare the assembly performance of our method against a sequential assembly method with Bayesian optimization (Kim et al., )020), denoted as BayesOpt, Brick-by-Brick (Chung et al. 2021), denoted as BBB, and the deep generative model of LEGO graphs (Thompson et al. 2020). denoted DGMI.G, in Tables 2 and BayesOpt optimizes brick positions to maximize ToU between assembled shapes and target shapes. For the method by Kim et al. (2020), we provide exact target structures which belong to particular category. BBB learns to assemble bricks given multi-view images of target structures. Following its formulation, we also provide three images (top, left, and front) of target structures in a test datasot. DGMLG generates a structure by utilizing the graph representation of brick structures and a deep graph generative model. Note that our approach does not provide any guidance (image or target shape) to produce a new structure. It is noteworthy that such different formulation inevitable due to their respective assumptions. Importantly, we would claim that our method requires weaker guidance than other methods.
5.1 Completion of Brick Structures
We test our method on a complction task for sequential brick assembly where unseen partial structures are given. To establish the completion task for brick assembly problems, we first assemble LEGO bricks using brute-force approach to filling voxel occupancy in test dataset with LEGO bricks. Then, we remove fraction of bricks assembled without losing connectivity between bricks and provide it as an initial state Bo- Each model is trained with a training dataset and then complete brick structures from the initial states. We compare t the completion performance by measuring ToU bet ground-truth voxel occupancy and complete brick structure. In addition, we report valid assembly ratio and inference time.
As shown in Table our method outperforms the other three baseline methods terms of IoU. The results show that our method creates high-fidelity brick structures compared to other methods, despite exhaustive
9

---

Published in Transactions on Machine Learning Research (09/2024)
Table 2: Quantitative results of the completion of brick structures. An asterisk after a method name denotes that partial full ground-truth information is given to the corresponding model.
IoU (t)
% valid (1)
Inference time (sec., 4)
Method
airplane table chair average airplane table chair average airplane table chair average
BayesOpt*
0.145
0.206 0.233
0.194
100.0
100.0
100.0
100.0
1.20e6
1.1166 1.05e6 1.12e6
Brick-by-Brick*
0.455
0.440
0.434
0.443
12.0
7.0
16.0
11.7
305.6
1502.4
2785.2 1531.1
DGMLG
0.315
0.269
0.271
0.285
0.0
1.0
0.0
0.3
237.3
340.0
473.0
350.4
BrECS (2x4)
0.571
0.586
0.534
0.564
100.0
100.0
100.0
100.0
36.3
143.9
151.0
110.4
BrECS (2x4 + 2x
0.599
0.594 0.541
0.578
100.0
100.0
100.0
100.0
73.8
224.1
279.0 192.3
Table 3: Quantitative results of the generation of brick structures with distinct brick types. An asterisk denotes model with partial or full ground truth information.
Class probablity of target class (t)
% valid (t)
Method
airplane
lable
chair
average
airplane
table
chair
average
BayesOpt*
0.089
0.043
0.069
0.050
100.0
100.0
100.0
100.0
Srick-by-Brick'
0.430
0.042
0.032
0.168
6.0
3.0
2.0
3.7
DGMLG
0,228
0.023
0.027
0.093
0.0
0.0
0.0
0.0
BrECS (2x4)
0.415
0.250
0.401
0.356
100.0
100.0
100.0
100.0
BrECS (2x4 + 2x2)
0.447
0.229
0.419
0.365
100.0
100.0
100.0
100.0
constraint satisfaction. Moreover, our method performs best in validity ratio alongside BayesOpt, but ours is also the best in inference time. We additionally test our model with distinct brick types by appending 2x2 bricks after assembling x brick type first. The performance of method is further improved by using two brick types since different brick types can fill brick positions more densely and express the fine aspect of structures in consequence.
5.2 Generation of Brick Structures
As our method is a generative model, our brick assembly model can generate a brick structure that belongs to particular category. To compare the quality of generated structures semantically, train classifier over voxel grids with small number of 3D convolution layers using the ModelNet40 dataset; the detailed architecture of the classifier presented in Section F Given a pretrained classifier over voxel grids, we measure the class probability of generated brick structures for a target class. To feed the voxel grid of generated structure into the classifier, we match the voxel grid size of generated structure with the grid size of the training dataset for the classifier.
Quantitative results are presented in Tables and Our method achieves the best scores in terms of class probabilities and coverage. The results indicate that our method generates diverse and high-quality brick structures compared to the other methods. We also emphasize that the semantic generation quality can be improved using additional 2 2x brick lypes. Brick structures with distinct brick types are generated by assembling 2 4 bricks first and then 2 LEGO bricks. This performance gain led by the additional improvement on structure refinement that cannot be filled with a single brick type; see Figures and
5.3 Budget-Aware Generation
We further conduct experiments on budget-aware scenarios. In the budget-aware experiments, we measure generation performance on various scenarios and analyze how our framework helps to generate 3D structures closer target shape. To measure generation quality, we employ the target class probabilities predicted by the pretrained voxel classifier following the evaluation procedure for the generation task.
10

---

Published in Transactions on Machine Learning Research (09/2024)
Table 4: Results on the diversity of generated samples from our method and baselines different ob- ject classes. We generate 100 objects and then mcasure diversity using the coverage metric similar to the work (Zhang et al. 2021
Metric
Class
BayesOpt
Brick- BrickkBy--Brikk
DGMLG
BrECS
Airplane
0.11
0.33
0.24
0.39
Coverage
Table
0.21
0.11
0.08
0.39
Chair
0.34
0.26
0.22
0.44
BO
BBB
DGMLG
Ours
table
chair
Figure 3: Qualitative results of structure generation. Best viewed in color.
We examine four different scenarios on brick budgets: even, shortage, vany_big and many_smaal amall. To fairly compare them, the same numbers of voxels are provided across the scenarios excluding the shortage case; if four 2x4 4 bricks are given for one scenario, we provide eight 2x2 bricks for another scenario the numbers of voxels are all 32. We assume that we are given three brick types, i.e., 2x2, 2x4, and 2x8. For the even case, we evenly distribute the number of voxels for cach brick type; the total number of voxcls 400. For the shortage case, we reduce the total number of voxels and evenly distribute the number of voxels for each brick type that it can fill up to 240 voxels. For the many_ case, allot twice many voxels to the largest brick type, compared to the other brick types. On the contrary, the number of voxels for the smallest brick type is twice as many as the other brick types in many_small.
As shown in Table 5 even, shortage, and many_big outperform 2x4 4 only and amal_1mall. is because the use of diverse brick types can increase the number possible connections and helps express the fine parts of the structures. Notably, many_small small fails create structures since the number of attachable positions for 2x 2 bricks is less than the other brick types.
11

---

Published in Transactions on Machine Learning Research (09/2024)
chair
table
airplane
Figure 4: Qualitative results of BrECS with 2x2, 2x4, and 2 brick types for structure generation. Best viewed in color.
Table 5:
Quantitative result of budget-aware brick assembly. A budget is represented as (# 2x2 bricks, 2x4 bricks, 2x8 bricks).
Scenario
# bricks
Max # voxels
Class probability (t)
2x4 1 only
(0, 150, 0)
1200
0.195
(100, 50, 25)
1200
0.329
shortage
(60, 30, 15)
720
0.283
many_big
(50, 25, 50)
1200
0.317
many_small
(200, 25, 12)
1200
0.123
5.4 Analysis on Our Proposed Model
We analyze the components included in BrECS by verifying each of them in completion or generation tasks, as presented in Tables and
Firstly, we compare different model architectures for a score prediction model. Specifically, we show the comparisons between U-Net and fully convolutional networks. For fair comparisons, we use the same number of convolutional filters. We present the results of generation and completion in Table 6 We find that the U-Net performs better than the fully convolutional network in both generation and completion. We presume that the U-Net is capable of extracting features ures more robustly because of the pyramidal structure of U-Net.
Secondly, we carry out study on the impact of stochasticity in the selection process for brick positions by comparing them in terms of completion and generation performance. As presented in Table 7 stochasticity improves generation performance as expected. Interestingly, completion quality is also improved by stochas- ticity. In the completion task, we remove half of the bricks, and the model completes partially-aseembled results, which lose large amount of their information. Stochasticity may help infer its original shape by making multiple candidates. Wan et al. (2021) also report that stochasticity improves the FID scores of image completion tasks if they are masked out part of the original image.
Moreover, we compare our original model to models without validity check or sequential skipping in the completion task. As reported in Table each component in our model effective for improving the quality of brick assembly. Similar the previous completion experiments, we complete brick structures from the intermediate states of the unseen structures in a test dataset. According the results, the validity check using convolution filters plays critical role in constraint. satisfaction. Moreover, the performance of
12

---

Published in Transactions on Machine Learning Research (09/2024)
Table 6: Results of the study on model architectures. The U-Net architecture consistently outperforms the fully convolutional network with the same number of convolutional filters in both completion and generation scenarios.
IoU (t)
Class probability of target class (1)
Methods
airplane
table
chair
average
airplane
table chair
average
BrECS with U-Net BrECS with Fully convolutional network 0.510
0.571
0.586
0,534
0.564
0.415
0.250
0.404
0.356
0.399
0.450
0.453
0.208
0.075
0.186
0.156
Performance comparisons of BrECS with or without stochasticity. Stochasticity improves perfor- mance in both completion and gencration tasks.
Table 7:
IoU (1)
Class probability of target class (t)
Methods
airplane
table
chair
average
airplane
table
chair
average
BrECS with stochasticity 0.571
0,586
0.534
0.564
0.415
0,250
0.404
0.356
BrECS without stochasticity
0.515
0.533
0.509
0.519
0.238
0.104
0.217
0.186
Table 8: Results of the study on two components, i.e., validity check and sequence skipping, where we measure completion performance for the chair category. Ours without ablation performs better than ablated variants.
IoU
% valid
# bricks
Inference time (sec.)
Defanlt setup
0.534
100.0
96.7
151.0
w/o validity check
0.441
0.0
141.6
335.8
w/o sequence skipping
0.437
100.0
59.3
6.0
model degrades significantly without sequence skipping the number of bricks assembled decreases. Tt. implies that the sequence skipping encourages BrECS to predict diverse brick positions.
6 Conclusion
We have proposed brick assembly method to efficiently validate complex assembly constraints and effectively generale high-fidelity brick structures. To sequentially assemble LEGO bricks into 3D structures, our model checks the validity of brick positions using one-initialized brick-sized convolution filters and calculates brick scores utilizing the U-Net architecture. Finally, we showed that our method performs better than several existing methods, tested our method in both budget-free and budget-aware scenarios, and analyzed the components involved our method through diverse empirical studies.
Broader Impact Statement
From the perspective that our model tackles an instance of combinatorial optimization problems, which is an attractive problem in computer science, our work does not have any negative broader impact. However, our approach might be used generate unethical products, because ours can create novel structures in a combinatorial manner. Thus, this negative ability should be carefully monitored and managed.
Acknowledgments
This work was supported by NRF grant (No. 2023RLAIC200781211 (65%)) and ПTT grants (RS-2021- IT212068: AI Innovation Hub (25%), RS-2021-I2211343 AI Graduate School Program at Scoul National University (5%), and R1-9919- AI Graduate School Program POSTECH (5%)) funded by the Korea government (MSIT).
13

---

Published in Transactions on Machine Learning Research (09/2024)
References
P. Achlioptas, O. Diamanti, 1. Mitliagkas, and L. Guibas. Learning representations and generative models for 3D point clouds. In Proceedings of the International Conference on Machine Learning (ICML), 2018.
Y.-C. Chen, H. Li, D. Turpin, A. Jacobson, and A. Garg. Neural shape mating: Sclf-supervised object assembly with adversarial shape priors. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
C.
Choy, J. Gwak, and S. Savarese. 4D spatio-temporal ConvNets: Minkowski convolutional neural net- works. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recogrition (CVPR), 2019.
Н. Chung, J. Kim, B. Knyazev, J. Lee, G. W. Taylor, J. Park, and M. Cho. Brick-by-Brick: Combinatorial construction with deep reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
R. Coulom. Efficient selectivity and backup operators in Monte-Carlo tree search. In Proceedings of the International Conference on Computer and Games, 2006.
P. Ertl, R. Lewis, E. Martin, and V. Polyakov. In silico generation of novel, drug-like chemical matter using the LSTM neural network. Xixiv preprint urXiv::712.07744. 2017.
M. Gadelha, R. Wang, and S. Maji. Multiresolution tree networks for 3D point cloud processing. In Proceedings of the European Conference on Compuler Vision (ECCV), 2018.
S. K. S. Ghasemipour, D. Freeman, B. David, S. S. Gu, S. Kataoka, and I. Mordatch. Blocks assemble! Learning to assemble with large-scale structured reinforcement learning, In Proceedings of the International Conference on Machine Learning (ICML), 2022.
R. Hu, J. Xu, B. Chen, M. Gong, H. Zhhang, and H. Huang. TAP-Net: Transport-and-pack using reinforce- ment lcarning. ACM Transactions on Graphics, 2020.
B. Jones, D. Hildreth, D. Chen, I. Baran, V. G. Kim, and A. Schulz. AutoMate: A dataset and learning approach for automatic mating of CAD assemblies. ACM Transactions Graphics, 2021a.
R. K. Jones, D. Charatan, P. Guerrero, N. J. Mitra, and D. Ritchie. ShapeMOD: Macro operation discovery for 3D shape programs. ACM Transactions on Graphics, 2021b.
J. Kim, H. Chung, J. Lee, M. Cho, and J. Park. Combinatorial 3D shape generation via sequential assembly. In Newral Information Processing Systems Workshop on Machine Learning for Engineering Modeling, Simalation, and Design (ML4Eng), 2020.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In Proceedings of the International Conference Learning Representations (ICLR), 2015.
J. Lee, J. Kim, H. Chung, J. Park, and M. Cho. Learning to assemble geometric shapes. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCA1), 2022.
Y. Lee, E. S. Hu, and J. J. Lim. IKEA furniture assembly environment for long- horizon complex manipulation tasks. In Proceedings of the International Conference on Robotics and Automation (ICRA), 2021.
Y. Li, T. Kong, L. Li, Y. Li, and Y. Wu. Learning to design and construct bridge without blueprint. In Proceedings of the IEEE/RS. ERESJJJ International Conference on Intelligent Robots and Systems (IROS), 2021.
R. Liu, Y. Sun, and C. Liu. Robotic LEGO assembly and disassembly from human demonstration. arXiv preprinl ar
2023.
R. Liu, K. Deng, Z. Wang, and C. Liu. StableLego: Stability analysis of block stacking assembly. JEEE Robotáes and Automation Letters, 2024.
14

---

Published in Transactions on Machine Learning Research (09/2024)
S-J. Luo, Y. Yue, C-K. Huang, Y-H. Chung, S. Imai, T. Nishita, and B-Y. Chen. Legolization: Optimizing LEGO designs. ACM Transactions on Graphics, 34(6):222:1 -222:12, 2015.
A. Martinovic and L. Van Gool. Bayesian grammar learning for inverse procedural modeling. In Proceedings of the IEEE International Conference on Computer Vision and Pottern Recognition (CciiinmCCPP (CVPR), 2013.
T. Mikolov, M. Karafiát, L. Burget, Cernocký, and S. Khudanpur. Recurrent neural network based language model. In Proceedings of the Conference of the International Speech Communication Association (Interspeech); 2010.
L. Nägele, A. Hoffmann, A. Schierl, and W. Reif. LegoBot: Automated planning for coordinated multi-robot assembly of LEGO structures. In Proceedings of the IEEE/RSI International Conference on Intelligent Robols and Systems (IROS), 2020.
D. Neil, M. Segler, L. Guasch, M. Ahmed, D. Plumbley, M. Sellwood, and N. Brown. Exploring deep recurrent models with reinforcement learning for molecule design. In International Conference on Learning Representations Workshop, 2018.
D. Ritchie, B. Mildenhall, N. D. Goodman, and P. Hanrahan. Controlling procedural modeling programs with stochastiealll--oddeee sequential Monte Carlo. ACM Transactions Graphics, 2015.
D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, 1. Sutskever, T. Lil- licrap, M. Leach, K. Kavukcuoglu, T. Gracpel, and D. Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 2016.
M. Sung, H. Su, V. G. Kim, S. Chaudhuri, and L. Guibas. ComplementMe: Weakly-supervised component suggestions for 3D modcling. ACM Transactions Graphics, 2017.
1. Sutskever, O. Vinyals, and Q, V. Le. Sequence to sequence learning with neural networks. In Advances in Newral Information Processing Systems (NewrIPS), 2014.
R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
J. O. Talton, Y. Lou, Lesser, J. Duke, R. Měch, and V. Koltun. Metropolis procedural modeling. ACM Transactions on Graphics, 2011.
R. Thompson, G. Elahe, T. DeVries, and G. W. Taylor. Building LEGO using deep generative models of graphs. Neural Information Processing Systems Workshop Machine Learning for Engineering Modeling, Simulation, and Design (ML4Eng), 2020.
E. P. K. Tsang. Foundations of constraint satisfaction. Academic Press, 1993.
Z. Wan, J. Zhang, D. Chen, and J. Liao. High-fidelity pluralistic image completion with transformers. In Proceedings of the International Conference on Computer Vision (ICCV), 2021.
D. D. Willis, P. K. Jayaraman, H. Chu, Y. Tian, Y. Li, D. Grandi, A. Sanghi, L. Tran, G. Lambourne, A. Solar-Lezanae and W. Matusik. JoinABLe: Learning bottom-up assembly of parametric CAD joints. In Proceedings of the IEEE International Conference Computer Vision and Pattern Recognition (CVPR), 2022.
J. Wu, C. Zhang, T. Xue, B. Freeman, and J. Tenenbaum. Learning a probabilistic latent space of object shapes via 3D generative-ad veesariial modeling. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
Z. Wu, Song, A. Khosla, Yu, L. Zhang, X. Tang, and J. Xiao. 3D ShapeNets: A deep representation for volumetric shapes. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), 2015.
15

---

Published in Transactions on Machine Learning Research (09/2024)
G. Yang, X. Huang, Z. Hao, M.-Y. Liu, S. Belongie, and B. Hariharan. PointFlow: 3D point cloud generation with continuous normalizing flows. In Proceedings of the Internalional Conference on Computer Vision (ICCV), 2019.
J. You, B. Liu, Z. Ying, V. Pande, and J. Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. In Advances in Neural Information Processing Systems (NeurIPS). 2018.
Zhang, Choi, J. Kim, and Y. M. Kim. Learning to generate 3D shapes with generative cellular automata, In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
16

---

Published in Transactions on Machine Learning Research (09/2024)
A Overall Procedure of Our Method
Brick Score
Budget-Aware Score Adjustment
Brick Position Determination
Calculation
Figure 5: Overall procedure our method.
Figure presents the overall procedure of our method BrECS. Our method starts from brick score caleu- lation step with current brick structure. Then, adjust brick scores to assemble within given budget. Finally, we determine a brick position using brick scores from the previous steps. These steps are repeated for assembling a fixed number of bricks into brick structure.
B Details of Implementation
We present the implementation details of baseline methods and our proposed method.
B.1 Bayesian Optimization
We employ Bayesian optimization to tackle sequential brick assembly problem. We follow the setup proposed by Kim al. (2020). The number of bricks is limited 160 bricks most. Every brick position is optimized by maximizing IoU between current and ground-truth structures. Note that have to provide ground-truth voxel information for this strategy.
B.2 Brick-by-Brick
We use Brick-by-Brig as baseline method and compare it to our method in terms of the performance of brick assembly. We follow the model architecture and training setup of the model described in the work (Chung et al. 202T Also, we would like emphasize that partial ground-truth voxel information have be provided for this strategy, the method requires three images of ground-truth shapes to create target shapes. The number of bricks is limited to 75 bricks most, which is the samne as the original setup, due to the excessively increasing memory requirements of the model. In an inference stage, generation sequence is halted when the newly placed brick violates the constraints, following the environment reset condition of the method.
B.3 Deep Generative Model of LEGO Graphs
We solve the problem of brick assembly generation using the deep generative model LEGO Graphs and compare against ours. We follow the model architecture and training setup described the work (Thomp- son ct al. 2020). To train the graph generation model, we need the graph representations of target shapes. We therefore create (arget shapes with ground-truth voxel shapes. Then convert brick structures into graphs by representing bricks nodes and direct connections between bricks as edges, following the previous work (Thompson et al. 2020) We train this model for 200 epochs.
B.4 BrECS
To efficiently train a model for 3D voxel generation, we utilize Minkowski Engine (Choy et al. 2019 and its 3D sparse convolution operation. We train our model with a fixed learning rate of 5e-4, Adam optimizer (Kingma & Ba (2015). batch size of 32, sequence skipping with stop size & 8, buffer size of 1024, and the maximum number of bricks of 150. The input size of our model is (64, 64, 64), and the output size is also (64, 64, 64). We train the model until reaching 100k steps.
17

---

Published in Transactions on Machine Learning Research (09/2024)
C
Training
We train model on server with four NVIDIA GeForce RTX 2080 Ti GPUs.
Details of Hyperparameters D
We train our model using the Adamn optimizer with a learning rale of 0.0005 and weight decay of 0.0. We set batch size to 32, internal buffer size to 1024, the number of steps skip to 8, and voxel size to 64. The numbers of convolution kernels in the score prediction model are 7, 5, 5, 3, 3, 3, 3, 3, 3, and 3 from top to bottom. The number of output channels for the score prediction model is 1.
E Detailed Architecture of U-Net
3xc3e3, 128
Cony DownDlooBlll, 256
ClacBlack/6) 3x.3x, 256
Conv 3x3x3, 128
ComvBlock 3x3x,, 256
Sparse Conv 3x3x3, 256
Sparse 3x.3 64
ConyDowaBBledt 128
32
ConyDown 64
Cony ConyDewaBlock 128
ConyBlock() 3x3x3, 128
CameCCnnTiin 3x003 96
32
Sparee onvy 5x585,
SparseConvi
ConnDown
96
Cons Hon-DowaBBoock 96
Sparse Coun 7x7x7, 32
Sparas Cone S15w5,
ConvBlack be.dd,
Conv ConvBBlock22 3x3x33
Sparse Conv 3x3x33
96
Coev Dew.DowwBllc 96
ConvBBlock() 3A3A3,
SparseC Cony IF 3x333,
Cony
Figure 6: Model architecture of U-Net.
We design our score prediction network inspired by Choy et al. 2019 Detailed model architecture is
illustrated Figure G
F Detailed Architecture of Voxel Classifier
AugPool
Spane Come Sx3k.3 64
SparseCons Conv 3,3x3, 128
SporeCCom Cony bclx 256
SparseCom's 363t3, 512
SparseCons 3x3r3, 1024
ceee 3rchec,
Sparse Cony Sa3a3,
Max Pool
Mox Pool
Max Pool
Mix Pool
Cancall
F1,
FCNN
wollmax
MaxPool
Figure 7: Model architecture of voxel classifier.
18

---

Published in Transactions on Machine Learning Research (09/2024)
We train shallow voxel classification network to compare several models in terms of generation quality semantically. We add softmax layer at the end of the network. The detailed network structure is described in Figure
G Limitations
Our model can process any rectangular bricks with a small amount of modification. However, it is difficult to deal with more diverse brick lypes such as a brick with a slope and circular brick. Assembling more general brick types and even free-form brick types left for future work; since non-rectangular materials are common in real-world scenarios, it would make our work more effective. addition, our model does not consider the inefficiency that occurs when the next brick is attached to multiple bricks previously assembled. More precisely, while different pivot bricks and the corresponding relative positions are selected, the same structure can be produced. In future work, it will be considered to improve assembly efficiency by avoiding such a possibility.
19


Reviews:
[{"review_id": "OwiEm6O5tt", "reviewer": "Reviewer_VkFp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ The paper is very well-written, all the concepts are explained clearly, and the proposed method implementation is also described in detail.\n+ The general idea of the proposed method seems to be reasonable (although I have various concerns below regarding the detailed implementation of the proposed method).\n+ The experiments show the proposed method outperforms existing techniques by a very high margin, and across different aspects.\n\nWeaknesses:\n+ I think the motivation of the components of the proposed method could be elaborated much more. For example, when predicting the next brick position, the use of U-shaped sparse 3D convolutional neural network needs to be explained in more detail. The paper only said it is inspired by Choy et al. (2019) but no clear rationale is given. Why don’t we use another type of convolutional neural network? What makes U-shaped one work well in this case? For the filtering invalid brick positions, why do we just apply a convolution filter? Why don’t we use a U-shaped sparse 3D CNN as in the 1st component?\n+ For the experimental evaluation, I’m wondering why only one dataset (ModelNet40) is used. Is there only one dataset for this type of problem? And for the metrics, in the beginning of Section 4, the paper only describes the IoU metric, but then later, the paper also evaluates all the methods with other metrics like coverage, but the description of the coverage metric is not described in detail. And furthermore, because we have multiple metrics, what metrics are more important in this type of problem?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper aims to solve the problem of sequential assembly of brick to create combinatorial 3D structures. In particular, the paper proposes to new method that first, predict the scores of the next brick position using a U-shaped sparse 3D convolutional neural network, second, use a convolution filter to validate physical constraints between bricks, and finally, use a sampling strategy to determine the next brick position based on the physical constraints. The proposed method is evaluated on the ModelNet40 dataset, and was compared various baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "[1] More motivation for the components in the proposed method (e.g., the use of U-shaped sparse 3D convolutional neural network or the convolution filter)\n\n[2] Explanations of why only one dataset is used to evaluate all the methods (if there are more datasets available, need to evaluate with more datasets). Descriptions of all the metrics used in the experimental section.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "u3mhNNZq06", "reviewer": "Reviewer_kiQa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n**Would at least some individuals in TMLR's audience be interested in knowing the findings of this paper? YES.**\n\nThe main insight of the BrECS algorithm is that convolutions are very efficient on GPUs, and that they have a natural interpretation for overlap checking. This is a genuinely interesting connection, which yields a fast sequential assembly algorithm.\nNumerical results are compelling in some regards, especially the adequation of the generated structure to the target class (which can be assessed visually).\n\n## Weaknesses\n\n**Are the claims made in the submission supported by accurate, convincing and clear evidence? NOT YET.**\n\nMy main issue with the paper is that is lacks clarity. The task of \"sequential brick assembly\" is never properly defined, in particular with respect to a possible target shape. On page 8, the authors state\n\n> Note that our approach does not provide any guidance (image or target shape) to produce a new structure.\n\nBut then how do you enforce the generation of something that looks like a chair, or an airplane? How can you compare your method against predecessors in a fair way, when these predecessors work from an exact (Kim et al. 2020) or approximate (Chung et al. 2021) target shape?\n\nIt is also unclear to me what the interpretation of the U-shaped neural net should be, and why the convolutional filter $\\mathbf{K}$ is a necessary postprocessing step.\n\nAs a result of these gray areas, I couldn't assess the experimental results properly. I hope that the authors will be able to explain both points properly in the discussion phase.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a novel method (BrECS) for sequential LEGO brick assembly in 3 dimensions. BrECS leverages a U-shaped neural network to suggest positions for the next brick, and relies on a convolution operation to efficiently avoid overlaps (the most crucial constraint). It can accommodate different brick types, as well as brick budget constraints. Performance is evaluated on the ModelNet40 dataset and compared to previous algorithms.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Most of the remarks below are caused by lack of clarity on the fundamental goal of sequential brick assembly. They are ordered by the page I refer to.\n\n- “Supposing that we are given many bricks to assemble” (p. 1) And a target shape?\n- “an auxiliary neural network that fails to predict legitimate moves perfectly.” (p. 2) Does your method succeed in perfect prediction?\n- “We will release our source code upon publication.” (p. 2) Can you submit it for review?\n- “feature” (p. 3) typo\n- “Sequential Brick Assembly.” (p. 3) Define the problem more precisely: what is the objective? Matching a given 3d volume?\n- “Given a voxel representation of a structure at step t,” (p. 4) Explain what this is\n- “Moreover, we expect that our neural network produces a likely complete or potentially next-step 3D structure, which is represented by a probability of voxel occupancy” (p. 5) How do you train it? What is the loss? How does it handle voxels that are already occupied?\n- “scores for next brick positions $A_{t+1} \\in \\mathbb{R}^{a×a×a}$ is computed by sliding a convolution filter $K \\in \\mathbb{R}^{w_b \\times d_b \\times 1}$ across $B_t$:” (p. 5) Why is the filter needed here too, and not just for validity?\n- “is” (p. 5) typo\n- “the size of the convolution filter is the same as the brick size we assemble” (p. 5) Do we need to know ahead of time which brick shape we'll use next?\n- “Input: Voxels of structure at current time step $B$, a list of assembled brick positions $P$, and brick size $w_b \\times d_b$” (p. 6) What if we don't know which brick will be used next? Does this adapt to heterogenous bricks, possibly with some normalization?\n- “$p_{ijk}$” (p. 6) What is this quantity $p_{ijk}$ in Equation (6)?\n- “bricks” (p. 6) typo\n- “By replacing $B_t$ with ground-truth voxel occupancy, we generate an assembly sequence $[B_0, B_1, \\dots , B_{T−1}]$ following the procedure in this section.” (p. 7) This is not clear: how do you recover the intermediate states? How do you ensure that the final ground truth is reached?\n- “For a completion task, we use an intermediate state” (p. 7) What is a completion task?\n- “For a generation task, we sample an initial brick position” (p. 7) What is a generation task?\n- “a probability of the next brick placement is post-processed by the following” (p. 8) What is $\\mathbf{a}_t$ in equation (10)?\n- “$c_{t−1} \\odot v$” (p. 8) In Equation (10), we put more weight on bricks which 1/ are abundant and 2/ have large volume? What is the rationale?\n- “Along with IoU, we measure the ratio of valid bricks in structures of interest.” (p. 8) What is the ratio of valid bricks?\n- “BayesOpt optimizes brick positions to maximize IoU between assembled shapes and target shapes. BBB learns to assemble bricks given multi-view images of target structures. Following its formulation, we also provide three images (top, left, and front) of target structures in a test dataset.” (p. 8) How can you compare these methods if they use different input data?\n- “Note that our approach does not provide any guidance (image or target shape) to produce a new structure.” (p. 8) So it can do whatever it wants?\n- “We test our method on a completion task for sequential brick assembly where unseen partial structures are given.” (p. 8) I thought your method didn't require / accept any guidance?\n- “Each model is trained with a training dataset and then complete brick structures from the initial states.” (p. 9) What does that mean?\n- “Given a pretrained classifier over voxel grids, we measure the class probability of generated brick structures for a target class.” (p. 9) How do you impose the target class on your model?", "broader_impact_concerns": "There are no broader impact concerns to address here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9ZE16geu9C", "reviewer": "Reviewer_Tbgf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The proposed method is a novel one for sequential brick assembly. The main innovation is training a k-step voxel predictor whose predictions are used as scores in selecting the next location to place a brick. \n\n2. There are several other smaller innovations in pivot brick selection and relative brick position determination that are also reasonable. Ablation studies also validated their contribution to BrECS.\n\n3. Empirical evaluations show a decent improvement over baselines in terms of the intersection over union metric.\n\nWeaknesses:\nThere are several places where the paper is not very clear. The authors should provide more details on BrECS and their experimental setting.\n\n1. In training the k-step look-ahead model, I do not fully understand the data generation method. On page 7 in describing generation for $\\tilde{\\textbf{B}}_i$, they use ground-truth voxel occupancy to replace $\\textbf{B}’$. Does it mean at each step $\\textbf{B}’$ stays the same? This is a bit strange.\n\n2. It is unclear to me how this training process provides class information to the model. The empirical evaluations show BrECS is able to construct structures more closely satisfying class labels but I do not see how the model learns to do this.\n\n3. Experimental details are missing the sequence skipping value used for the results. In addition, ablation results on removing sequence skipping show degradation but a more interesting ablation is to measure performances over a range of skipping values. \n\n4. What is the definition of valid bricks in the metric “ratio of valid bricks”?\n\n5. In section 4.2, the authors trained a classifier to measure class probability. How accurate is the classifier?\n\n6. The dataset description could use more details. It seems like the authors used a subset of the ModelNet40 dataset so it would be helpful to provide details on them.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors study the problem of sequential brick assembly with LEGO bricks to create 3D structures. They propose to train a predictor to predict 3D voxels after k steps of placing bricks and use it as a score function to determine where to place each brick. They named their method BrECS. They also present a budget-aware version of BrECS that takes remaining brick types and the number of bricks into consideration during construction. Empirical evaluations on the ModelNet40 dataset demonstrate that BrECS achieves higher intersection with the ground truth. BrECS is also better at constructing specific shapes according to a voxel classifier. Finally, the budge-aware version of BrECS is able to adapt to different types of available bricks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See my questions in the section above. The first 3 weakness points are critical and the next three are relatively minor.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two of the three reviewers indicated that this initial submission already met the TMLR criteria. The reviewers had some suggestions and questions, which the authors addressed in their response and updates to the paper.

The third reviewer also recommended acceptance after a comprehensive discussion with the authors. What came out of the discussion is that there are aspects of the paper that the authors might wish to expand upon to improve the paper's reproducibility and make it more accessible, especially to researchers somewhat outside this subfield. In particular, based on the reviewer's suggestions here are the minor modifications I suggest:

-   Exposition. The reviewer asks "to clarify how the training dataset is generated: how a ground truth volume is decomposed into individual brick additions" My understanding from the paper is that this is already provided in Section 4.2. If this is the case, no additional modification is required.
- Exposition. Your new Section 3 is helpful, but I support the reviewer's suggestion to also specify/discuss the objective of sequential brick assembly for readers. 
-  Reproducibility. You write "We will release our source code upon publication." Providing the method code and the code to generate the datasets would be most helpful.

I am happy to recommend acceptance, congratulations!
Decision: Accept (poster)