# Reachability Verification Based Reliability Assessment for Deep
Reinforcement Learning Controlled Robotics and Autonomous Systems

Yi Dong1, Xingyu Zhao1, Sen Wang2 and Xiaowei Huang1 *This work is supported
by UK Dstl through Safety Argument for Learning-enabled Autonomous Underwater
Vehicles and UK EPSRC through End-to-End Conceptual Guarding of Neural
Architectures [EP/T026995/1]. This project has received funding from the
European Union’s Horizon 2020 research and innovation programme under grant
agreement No 956123.1Yi Dong, Xingyu Zhao and Xiaowei Huang are with the
Department of Computer Science, University of Liverpool, Liverpool, UK
<EMAIL_ADDRESS>Wang is with the
Department of Electrical and Electronic Engineering, Imperial College London,
London, UK<EMAIL_ADDRESS>
###### Abstract

Deep Reinforcement Learning (DRL) has achieved impressive performance in
robotics and autonomous systems (RASs). A key impediment to its deployment in
real-life operations is the spuriously unsafe DRL policies—unexplored states
may lead the agent to make wrong decisions that may cause hazards, especially
in applications where end-to-end controllers of the RAS were trained by DRL.
In this paper, we propose a novel quantitative reliability assessment
framework for DRL-controlled RASs, leveraging verification evidence generated
from formal reliability analysis of neural networks. A two-level verification
framework is introduced to check the safety property with respect to
inaccurate observations that are due to e.g., environmental noises and state
changes. Reachability verification tools are leveraged at the local level to
generate safety evidence of trajectories, while at the global level, we
quantify the overall reliability as an aggregated metric of local safety
evidence, according to an operational profile. The effectiveness of the
proposed verification framework is demonstrated and validated via experiments
on real RASs.

##  I INTRODUCTION

Deep Reinforcement Learning (DRL) has achieved impressive experimental results
in video game playing, in which DRL agents are deployed under a trial-error-
replay model. However, safety critical applications normally are not able to
trial and replay at will in the real-world, such as autonomous vehicles, power
systems, and humanoid robots.  A recent trend in autonomous navigation,
including ground and underwater vehicles, is to use end-to-end controllers
trained by reinforcement learning methods [1, 2, 3, 4]. For these applications
that require a high level of safety integrity, deploying unverified DRL
policies can lead to catastrophic consequences.  In the meantime, Deep Neural
Networks (DNN) in DRL algorithms are known to be unrobust to adversarial
examples, i.e., the output of a DNN may be subject to dramatic change under a
minor input disturbance. Such issues have motivated this work to formally
analyse the end-to-end DRL systems and assure their reliability before they
are deployed.

DRL verification and testing are emerging in recent years, including safe
exploration, run-time monitoring, adversarial training, etc.. Pattanaik et al.
first proposed adversarial attacks for DRL algorithms, which trains the DRL
with engineered adversarial attacks to improve the DRL performance and obtain
more robust DRL models [5]. However, these adversarial training methods cannot
guarantee the safety during the training process. To this end, Dalal et al.
designed a safety layer that solves an action correction formulation per state
[6]. Felix et al. used the Lyapunov function to calculate the region of
attraction for a specific policy, and applied statistical models to obtain
high-performance DRL policies [7]. These algorithms focus on the safety
property in the training process, but the testing environment may be different
from the training environment. Therefore, run-time monitors were proposed to
assure the safety during the operations. The shield structure is created to
prevent the agent from making unsafe decisions [8]—it bans all unsafe actions
for each state to achieve safe reinforcement learning.

Aforementioned methods answer the binary/worst-case question of whether there
exists any safety violation in the presence of extreme perturbations/attacks.
They do not, however, provide an overall understanding of how safe the DRL
policy is whenever a violation can be found locally (in line with the insight
gained from evaluating Deep Learning (DL) classifiers [9, 10]). In this
regard, we introduce a reliability metric based on the probabilistic notion of
proportions of safety violations in the global input space representing the
environment and formulated by the Operational Profile (OP). Furthermore, most
DRL algorithms are explored and learned in simulation environments for, e.g.,
efficiency and cost considerations. However, the gap between simulated and
real environments may lead to violation of the safety property set in
simulation. Observation in the simulation environment is assumed as an
accurate and unbiased signal, which is an unacceptably strong assumption in
safety critical context. To this end, we proposed a novel two-level
verification framework to assess the reliability of DRL algorithms: i) at the
local level of an initial state, reachability analysis tools are utilised to
generate safety verification evidence that are interval based trajectories
starting from an initial state; ii) at the global level, we borrow ideas from
software reliability engineering to model the distribution of initial states
as the OP (representing all possible operational scenarios), and then
aggregate local safety evidence according to the OP to statistically estimate
the overall reliability.

The main contributions of this paper include:

a) A two-level assessment framework is designed to assess the reliability of
DRL algorithms. Reachability analysis formally verifies the safety of
trajectories starting from an initial state at the local level, while overall
reliability claims are supported statistically at the global level across
initial states.

b) At the local level, the state-of-the-art reachability verification tool
POLAR [11] is integrated and optimised for faster computation and tighter
bounded results. Meanwhile, OP is introduced and approximated to support a
global level reliability claims.

c) A publicly accessible repository of our method with all source code,
datasets, experiments and a real-world case study based on BlueRov2 unmanned
underwater vehicles (UUVs).

The rest of this paper is organised as follows. The mathematical preliminaries
used in this paper are summarised in Section II. A detailed two-level
verification algorithm is demonstrated in Section III, including local-level
reachability analysis and global-level statistical analysis. Simulation
results and corresponding discussion are presented in Section IV. Finally,
Section V concludes this paper.

##  II PRELIMINARIES

###  II-A Deep Reinforcement Learning

We use discounted infinite-horizon Markov Decision Process (MDP) to model the
interaction of an agent with the environment $E$. An MDP is a 5-tuple ${\cal
M}^{E}=(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma)$, where
$\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space,
$\mathcal{P}(\textbf{x}^{\prime}|\textbf{x},\textbf{a})$ is a probabilistic
transition, $\mathcal{R}(\textbf{x},\textbf{a})\in{\mathbb{R}}_{\geq 0}$ is a
reward function, and $\gamma\in[0,1)$ is a discount factor. We use x to range
over the state space $\mathcal{S}$ because it not only is a state but also
will later be used as input to a policy neural network. We consider different
DRL algorithms, such as DDPG [12], TD3 [13], PPO [14], which return an optimal
policy $\pi^{*}$ includes a mapping $\mu:\mathcal{S}\rightarrow\mathcal{A}$
that maps from states to actions.

Based on $\mathcal{M}^{E}$, a policy $\pi$ induces a trajectory distribution
$\rho^{\pi,E}(\zeta)$ where
$\zeta=(\textbf{x}_{0},\textbf{a}_{0},\textbf{x}_{1},\textbf{a}_{1},...)$
denotes a random trajectory. The state-action value function of $\pi$ is
defined as

$\small
Q^{\pi}(\textbf{x},\textbf{a})=\mathbb{E}_{\zeta\sim\rho^{\pi,E}}[\sum_{t=0}^{\infty}\gamma^{t}\mathcal{R}(\textbf{x}_{t},\textbf{a}_{t})]$
(1)

and the state value function of $\pi$ is
$V^{\pi}(\textbf{x})=Q^{\pi}(\textbf{x},\pi(\textbf{x})).$

We consider a DRL driven robot that navigates, and avoids collisions, in a
complex environment where there are static and dynamic objects (or obstacles).
The interaction of the robot with the environment can be modelled as an MDP.
At each time $t$, the robot has its sensor observation from the environment,
namely state $\textbf{x}_{t}$, i.e.,
$\textbf{x}_{t}=(o^{1}_{t},o^{2}_{t},\cdots,o^{n}_{t})^{T}$ where
$o^{1}_{t},o^{2}_{t},\cdots,o^{n}_{t}$ are observable sensor signals at time
$t$. It is worth noting that the robot’s parameters are also formatted as
observations because these variables are relative to the environment, such as
the pose in the global coordinate system and the velocity relative to the
stationary ground. The sensors can only observe partial information of the
environment, e.g., by scanning the environment within a certain distance. For
example, the observation range is within 3.15 metres in Turtlebot Waffle Pi
[15] for a distance sensor.

An action $\textbf{a}_{t}\in\mathcal{A}$ consists of several decision
variables. With the Proportional-Integral-Derivative (PID) controller on the
robot, we consider two action variables, representing line velocity and angle
velocity, respectively, i.e.,
$\textbf{a}_{t}=(v^{line}_{t},v^{angle}_{t})^{T}.$ At each time $t$, the DRL
policy outputs an action $\textbf{a}_{t}$ from the action set $\mathcal{A}$.

A fundamental functionality of an autonomous robot is to avoid the obstacles
and reach a goal area. On every state $\textbf{x}_{t}$, the sensory input
$o^{i}_{t}$ can be utilised to e.g., predict the distance to the obstacles
when they are within the sensing range. To implement the functionality, the
environment may impose a reward function $\mathcal{R}$ on the states, the
actions or both. A reward on the states can be, e.g., with respect to the
distance to obstacles, and a reward on the actions can be, e.g., with respect
to the acceleration in linear or angular speeds.

###  II-B Reachability Analysis and Verification

Reachability analysis has been developed recently for the verification of
safety and robustness of DNNs [16, 17, 18, 19]. Adapted to the context
described in Section II-A, reachability analysis determines the set of states
that a system can reach, starting from a set of initial states and considering
the interaction between the DRL policy and the MDP. Safety verification, which
is to determine whether a given DRL policy may lead to any unsafe state over
an MDP, can be reduced to the reachability problem of whether an unsafe state
is reachable.

In this paper, we verify a safety property on a model-free DRL algorithm by
computing its reachable set over a full trajectory. Similar to POLAR [11], the
following two mathematics are employed to calculate the reachable set: Taylor
Arithmetic and Bernstein Polynomial.

####  II-B1 Taylor Arithmetic

Followed by [20, 11, 21], any interval could be transferred into a Taylor
model. A Taylor model is combined by a polynomial approximation $p$ and an
interval error bound $I$:

$\small TM=p(\textbf{x})+I,\textbf{x}\in D$ (2)

where $D$ is the input domain of the Taylor model. $I$ is the remainder of the
Taylor model.

Given two Taylor Models: $TM_{1}=(p_{1},I_{1})$ and $TM_{2}=(p_{2},I_{2})$,
the addition and multiplication are computed as:

$\displaystyle\small TM_{1}+TM_{2}=$ $\displaystyle(p_{1}+p_{2},I_{1}+I_{2})$
$\displaystyle TM_{1}\times TM_{2}=$ $\displaystyle(p_{1}\times
p_{2}-r_{k},I_{1}\times I_{2}+Int(p_{1})\times I_{2}$
$\displaystyle+Int(p_{2})\times I_{1}+Int(r_{k}))$

where $Int(\cdot)$ is the interval of the polynomials, $k$ is the maximum
order of the Taylor models, and $r_{k}$ is the truncated polynomial of the
Taylor models.

####  II-B2 Bernstein Polynomial

There are several different activation functions in DNN s, e.g., Sigmoid,
ReLU, and Tanh. The Taylor model can only propagate with continuous activation
functions, but DNNs may use piece-wise activation functions to fit the data,
such as the ReLU function. Inspired by [11], the Bernstein polynomial can be
applied to calculate the Taylor models with discrete activation functions.

To achieve over-approximation for safety, the conservative remainder for
Bernstein polynomial should be considered:

$\small
p_{\sigma}=\sum_{i=0}^{k}\left(\sigma(a+\frac{b-a}{k}i)C^{k}_{i}\frac{(y_{i}-a)^{k}(b-y_{i})^{k-i}}{(b-a)^{k}}\right)$
(3)

where $a,b$ are the infimum and supremum of the activation function input, $k$
is the maximum order of the Bernstein polynomial, $y$ is the sampled point
between $a$ and $b$.

$\displaystyle\small\epsilon=\max_{i=0,\cdots,m}$
$\displaystyle\left(\left|p_{\sigma}\left(\frac{b-a}{m}(i+\frac{1}{2})+a\right)\right.\right.$
$\displaystyle\left.\left.-\sigma\left(\frac{b-a}{m}(i+\frac{1}{2})+a\right)\right|+\frac{b-a}{m}\right)$
(4)

where $m$ is the sampling steps and $\epsilon$ is the conservative error bound
of the Bernstein polynomial $I_{\sigma}=[-\epsilon,+\epsilon]$.

###  II-C Operational Profile based Reliability Assessment

In real world scenarios, the agent can take different trajectories from
different initial states under a given policy and an operational environment.
To support reliability claims for DRL in safety critical applications, all
possible trajectories need to be considered. In real applications, the initial
state (and its trajectory) of the agent usually obeys some distribution that
can be approximated from data.

The OP has been widely modelled in reliability assessment, which is applied to
represent the occurrence probabilities of function calls and the distributions
of parameter values [22, 23]. In other words, the OP is a Probability Density
Function over the whole input domain $D$, and returns the probability of
$\textbf{x}\in D$ being selected as the next random input. Later, we formally
define the reliability metric of a DRL policy in a given environment,
considering the OP.

##  III ALGORITHM DESIGN

In this paper, we design a novel two-level framework for assessing the
reliability of DRL controlled Robotics and Autonomous Systems (RAS) based on
the reachability verification tools and statistical analysis technologies. At
the local-level, safety verification is reduced to a reachability problem of
checking whether an unsafe state is reachable from an initial state, while the
global-level claims on reliability can be obtained by OP-based statistical
methods.

###  III-A Local-level Safety Verification

At the local level, we introduce an interval based method to calculate the
reachable set of a DRL policy. DDPG algorithm is composed of an actor network
and a critic network. We reduce the verification problem to a reachability
problem, which is to calculate the overall reachable set of actor neural
network and environment, cf. Fig. 1.

Figure 1: Reachability verification framework.

The observation from the environment is normally noisy due to, e.g.,
inaccurate sensor signal and external disturbance. These noises could be
ignored under safe conditions and in wide spaces but will cause safety issues
in some corner cases, as illustrated in subfigures (A-D) of Fig. 2. It is
obvious that the UUV is safe in case A because the real paths and observable
path are safe. In cases B, C, and D, the UUV is unsafe since at least one
signal shows that a crash occurs. If the sensor did not observe the correct
distance perception in a corner case, the decision of the current policy will
lead to a crash with high probability. Consequently, these errors should also
be considered in safety verification. Following the recommendation from [24],
the interval methods are suitable to deal with the uncertain sensor noises.
Based on the reachability verification tools, we use an interval to bound the
real paths around the observable path. Subfigure (E) in Fig. 2 shows that all
the real paths are bounded in green intervals.

Figure 2: Different corner cases and illustration diagram.

Specifically, the robot’s initial states are over-approximated with a range
$\eta$ and all possible true states are theoretically bounded in this green
interval. Then we have

$\small\textbf{a}_{t}\in NN_{actor}(\textbf{x}),\ \ \ \ \textbf{x}\in\eta$ (5)

where $NN_{actor}$ is the actor neural network of DDPG. Transferring the
initial input domain into a Taylor model:

$\small TM^{0}_{i}=\left(p_{i}(x_{i}),I_{i}\right),\,\,x_{i}\in\eta_{i}$ (6)

where $x_{i}$ is the $i$th state value of the observation. There is no
activation function after the first layer of the neural network. The Taylor
model can be directly propagated to the next layer.

$\small tm^{j}_{i}=\sum_{k=1}^{N}\boldsymbol{w}_{k}\times
TM^{j-1}_{k}+\boldsymbol{b}_{i}$ (7)

where $tm^{j}_{i}$ is the temporary Taylor model that has not passed the
activation functions. $\boldsymbol{w},\boldsymbol{b}$ are the weights and
biases of $NN_{actor}$, respectively. $j,k$ are the indices of neural network
layers and neurons, $N$ is the total number of neurons.

For the rest layers of $NN_{actor}$, there are activation functions.
Meanwhile, Taylor arithmetic cannot process the interval input with the
noncontinuous activation functions. Therefore, we employ the Bernstein
polynomial to deal the activation functions. Although the transformation will
yield errors, we can summarise these errors into the remainder of the Taylor
models by equations (3) and (II-B2).

$\small TM_{i}^{j}=p_{\sigma}(\sum_{k=1}^{N}\boldsymbol{w}_{k}\times
TM^{j-1}_{k}+\boldsymbol{b}_{i})+Int(r_{k})+I_{\sigma},\ \ \ \ j>0$ (8)

It is noticed that the maximum order of the Taylor models will be increased
after the activation functions, and therefore we truncate the part polynomial
$r_{k}$ of the output Taylor model to maintain the complexity of the Taylor
models. After several layers propagation, the output Taylor model is

$\small TM^{out}_{i}=\sum_{k=1}^{N}\boldsymbol{w}_{k}\times
TM^{out-1}_{k}+\boldsymbol{b}_{i}$ (9)

Here, the output Taylor model could be reverse to the interval by calculating
the upper and lower bound of the Taylor model regarding to the input domain
$D$.

##### POLAR Algorithm Optimisation

In this paper, POLAR algorithm is selected to test DRL algorithm due to its
advantages of tighter remainder bounds [11]. Different from other interval
arithmetic methods, POLAR algorithm generate better performance in reachable
set calculation, especially for DNNs. The deeper neural network layers cost
POLAR longer time to do Bernstein polynomial sampling. In consideration of the
characteristics of ReLU activation function, the propagation law of the Taylor
models is separated into three parts, which depends on the interval ranges
$TM\in[a,b]$.

Furthermore, it is time consuming to calculate the accurate bound of the high
order Taylor models. Similar to [11, 25], we calculate the conservative bound
for the Taylor models with the Minkowski addition [26]:

$\small P\oplus Q=\\{\textbf{p}+\textbf{q}|\textbf{p}\in P,\textbf{q}\in Q\\}$
(10)

Consequently, to accelerate the testing speed and further enhance the testing
accuracy of ReLU activation functions, we define the following propagation law
for the Taylor models:

$\footnotesize TM^{o}=\left\\{\begin{aligned} &0,&if\ \ \ \ b\leq 0,\\\
p_{\sigma}(TM^{i})+&Int(r_{k})+I_{\sigma},&if\ \ a\leq 0\ \ \&\ \ b\geq 0,\\\
&TM^{i},&if\ \ \ \ a\geq 0,\end{aligned}\right.$ (11)

where $TM^{i}$ and $TM^{o}$ are the Taylor models before and after the Relu
activation function, respectively.

We enhance the original POLAR algorithm by first splitting the polynomial fit
on each neuron into three piecewise functions based on the characteristics of
the ReLU function, and then using the Bernstein polynomial to calculate the
TMs if and only the interval of TMs contains $0$. It is obvious that the
proposed approach (11) is much faster than the original POLAR algorithm since
the sampling steps of the Bernstein polynomial are excused when the lower and
upper bounds of TMs are positive or negative simultaneously. Nevertheless, the
proposed method (11) can get the results without error (when the interval is
positive-definite) or even eradicate the errors passed from the previous layer
to zero (when the interval is negative-definite). Therefore, this optimisation
step can reduce the computation time and increase accuracy.

TABLE I: Connections between reliability assessment for traditional software, DL classifiers and DRL controllers. | Traditional safety critical software | DL classifiers | DRL controllers
---|---|---|---
Metric |  | Probability of failure
---
per random demand ($\mathit{pfd}$)
| Probability of misclassification
---
per random image ($pmi$)
| Probability of crash per
---
random initial state
OP |  | Distribution of
---
independent demands
| Distribution of
---
independent images
| Distribution of
---
independent initialisations
| Event of
---
interest
| Failure that has
---
safety impact
| Misclassification that
---
has safety impact
| Failure that leads to
---
hazards, e.g., crash
Partitions |  | Classes of input demands (“bins”)
---
based on functionalities
| Norm-balls in the input space
---
with certain radius
(e.g., the $r$-separation distance [27])
| Norm-balls in the input space with certain
---
radius representing a set of initial states
(e.g., a specified bound of errors)
| V&V in
---
each partition
| Estimation on conditional
---
$\mathit{pfd}$ of each bin (e.g., by stress
testing of a “bin”)
| Local robustness estimation
---
within a given norm-ball
| Reachability verification
---
(a “strip” of bounded trajectories in the input
space starting with a norm-ball)
| Oracle of
---
each partition
| By observation or given
---
by the specification
| Label of the central-point
---
(seed) of the norm-ball
| Emptiness of the intersection of
---
the “strip” and predefined unsafe-areas

###  III-B Global-level Reliability Assessment

The execution of a DRL-driven RAS in an environment leads to a trajectory
distribution (modelled as a Discrete-Time Markov Chain, discussed later),
where the uncertainty (modelled with probability distribution) is from the
environment111For simplicity and without loss of generality, we assume DRL
policy is deterministic, while our method can be adapted for probabilistic
policies.. Formally, given an environment $E$, a policy $\pi$, and an initial
state $\textbf{x}_{0}$, we can construct a model ${\cal
M}^{E}(\pi,\textbf{x}_{0})$ representing the probability distribution of a set
of trajectories. Assume that we have a verification technique $g$, as
discussed in Sections III-A.

###### Definition 1

The verification problem is, given a constructed model ${\cal
M}^{E}(\pi,\textbf{x}_{0})$ and a verification tool $g$, to determine whether
the model is safe with respect to certain property $\phi$, written as ${\cal
M}^{E}(\pi,\textbf{x}_{0})\models^{g}\phi$. We may omit the superscript $g$
and write ${\cal M}^{E}(\pi,\textbf{x}_{0})\models\phi$, if it is clear from
the context. We can also assume that $g$ returns a probability value – a
Boolean answer can be converted into a Dirac probability. Then, the
verification problem is to compute $Pr({\cal
M}^{E}(\pi,\textbf{x}_{0}),\phi)$, i.e., the probability of safety.

In the following, we discuss how the above verification problem may contribute
to the computation of the reliability. Similar as [28, 29], we partition the
space of initial states into $m$ sets, each of which is represented as a
constraint $\mathcal{C}_{i}$, for $i=1..m$. Then, we can also define the
empirical distribution $p_{op}$ over the partitions, and find a model
$G_{\theta}$ that is as close as possible to $p_{op}$. Formally, assume that
$G_{\theta}$ is a generative model over parameters $\theta$, we have

$\small\theta^{*}=\operatorname*{arg\,min}_{\theta}\text{KL}(G_{\theta},p_{op})$
(12)

where $\text{KL}(\cdot,\cdot)$ is the KL divergence between two distributions.

Based on these, we can estimate the reliability (defined as the probability of
failure in satisfying $\phi$ with the policy $\pi$ in the environment $E$) as

$\small\text{Reliability}(E,\pi,\phi)=\sum_{i=1}^{m}G_{\theta}(\mathcal{C}_{i})(1-Pr({\cal
M}^{E}(\pi,\textbf{x}_{\mathcal{C}_{i}}),\phi))$ (13)

where $G_{\theta}(\mathcal{C}_{i})$ returns the probability density of the
partition $i$ that is represented as the constraint $\mathcal{C}_{i}$,
$\textbf{x}_{\mathcal{C}_{i}}$ denotes the central point (i.e., a
representative) of $\mathcal{C}_{i}$, and $1-Pr({\cal
M}^{E}(\pi,\textbf{x}_{\mathcal{C}_{i}}),\phi)$ returns the failure rate of
the DRL agent $\pi$ working on inputs satisfying the constraint
$\mathcal{C}_{i}$ under the environment $E$. Note that, $G_{\theta}$ can be
estimated in the same way as the data distribution in [28, 29].

To better position the scope of our work, we summarise our approach for DRL,
compared with reliability assessment methods designed for traditional software
and DL classifiers, in Table I, where the proposed method is written in bold
font.

##  IV EXPERIMENT RESULTS

This section presents experimental results regarding the following research
questions (RQs):
RQ1: How effective the proposed local-level reliability assessment is of a
single trajectory (reachability verification)?
RQ2: How accurate the proposed method is compared to original POLAR algorithm?
RQ3: How conservative it is between our interval-based method and traditional
sampled point-based method?
In the following, we will first introduce our experimental environment, and
then address the RQs individually.

###  IV-A Experiment Setup

The mission of this experiment example is to automatically dock the UUV based
on DRL algorithm. We have both simulation and physical experiments for
Bluerov2 UUVs222All source code, DRL models, datasets, and experiment results
are available at solitude website https://github.com/Solitude-SAMR. For the
simulation environment, we use ROS [30] and Gazebo [31] as shown in the left
side of Fig. 3.

Figure 3: Simulation and physical experiment environments.

For the physical experiment environment, the training process is conducted on
a real-world water tank with a docking cage as shown in the right side of Fig.
3. In the real-world experiment environment, we randomly initialise the UUV
from different start points, which naturally generate the OP in our
reliability assessment framework. Theoretically, we will accurately estimate
the model’s safety if the verified all initial intervals can cover whole
initial space. Due to the limitation of computing power and the scalability
problem, we use the sampling method to estimate the safety of the entire input
space in this paper. It can be obtained from Fig. 4, the distribution of the
approximated OP converges as the number of samples increases.

Figure 4: Approximating the OP as more data is sampled. Multivariate
distribution is projected to a 2D space for visualisation.

###  IV-B Verification of an Initial State

In this subsection, we show the local-level reachability verification process
of an initial interval. In this paper, we use POLAR [11] as the reachability
verification tool to over-approximate the reliability of an initial state.
Here, we set a deadzone ([-0.1, +0.1]) around the target to accelerate the
UUV’s stability and improve the missions’ success rate. It can significantly
solve the scalability problem of the verification tool and the over-
conservative problem caused by the error accumulation. The verification
results are shown in Fig. 5.

Figure 5: The reachable set of six state variables (Top 3 figures: x, y, z
velocity; Bottom 3 figures: roll, pitch, yaw velocity). Each plot shows a
“strip” of bounded trajectories.

From the figure, the reachable sets of the robot converges to $0$, which means
the robot from that initial state interval will reach its destination. Due to
the existence of the deadzone, if the variables tend to the target value, then
all the variables will eventually converge to the deadzone, that is, the UUV
will eventually be parallel to the dock frame. Note that state variables 3
(roll velocity) and 4 (pitch velocity) are not changed ideally since they are
uncontrollable by the DRL policy in this experiment.

###  IV-C Comparison with Original POLAR Algorithm

Here, we show the over-approximated range between our method and POLAR [11] to
illustrate the advantages of the proposed algorithm. The experiments are
performed using Python on a same computer equipped with a AMD core $EPYC\
7452$. The initial states, system dynamics, neural network models and weights
are same. In the experiment, we found that the POLAR algorithm is too loose
after iterating 50 steps. To better show the performance, we update the input
state interval on every single steps. The output Q ranges of each step in a
trajectory are compared in Fig. 6.

Figure 6: Comparisons between the original POLAR and our optimised POLAR—the
latter yields tighter bounds.

In Fig. 6, our optimisation for the original POLAR greatly improves its
performance. Although both algorithms can obtain the reachable set of the
DNNs, the proposed approach yields tighter thus more accurate results.

###  IV-D Comparison with Point-based Assessment

After the local-level verification, we show the reliability assessment of
different DRL policies to validate the effectiveness of the proposed framework
in this subsection. For a given DRL policy and a set of initial spaces, we can
estimate the reliability of the system based on equation (13) and reachability
verification tools. In this paper, we collected the data from the real world
water tank environment and trained a DRL model to finish the mission task.
After we sampled 500 initial states in the real-world environment, we
calculate the reachable set by the proposed method and estimate the
reliability of the UUV system between our interval-based method and
traditional point-based methods, where we use the same OP on the global-level
assessment. The comparison results are summarised in Fig. 7:

Figure 7: Comparisons between point-based and our two-level interval-based
assessments—the latter yields more conservative results.

As can be seen from the Fig.7, the proposed interval-based approach is more
conservative than the point-based testing method. This is because the point-
based method is equivalent to a sample from our interval. Therefore, the
proposed local-level reachability verification algorithm considers the entire
environment and is an over-approximation of all possible points. The result of
original POLAR algorithm is not shown here, because the result is too
conservative, where the reachable set covers all safe and unsafe area.

It can be seen from the Fig. 7, as the number of sampled initial states
(representing trajectories starting from them) increases, the predicted
reliability of UUV system converges. We found that the reliability of the
system tested here is not very high. This is mainly due to the fact that
safety factors are not considered in the training of the DRL model. It is
conceivable that the goal of the reinforcement learning model is to dock the
UUV at the harbour, which will cause the UUV always attempt to approach the
destination in a straightforward route to achieve maximum reward and speed.

##  V CONCLUSION

This paper studies the probability of failures that can cause hazards in DRL
controlled RASs. A two-level reliability assessment framework is proposed,
using reachability verifications at the local-level and statistically
supporting a probabilistic reliability claims based on the OP at the global-
level. An optimisation on the local-level reachability analysis algorithm is
applied to enhance the verification speed and accuracy. The results in the
simulation and the real world manifest the effectiveness of the proposed
framework.

## ACKNOWLEDGMENT

We thank Vibhav Bharti for his support in the experiments.

## References

  * [1] B. R. Kiran, I. Sobh, V. Talpaert, P. Mannion, A. A. Al Sallab, S. Yogamani, and P. Pérez, “Deep reinforcement learning for autonomous driving: A survey,” _IEEE Transactions on Intelligent Transportation Systems_ , 2021\.
  * [2] J. Chen, S. E. Li, and M. Tomizuka, “Interpretable end-to-end urban autonomous driving with latent deep reinforcement learning,” _IEEE Transactions on Intelligent Transportation Systems_ , 2021.
  * [3] S. Levine, C. Finn, T. Darrell, and P. Abbeel, “End-to-end training of deep visuomotor policies,” _The Journal of Machine Learning Research_ , vol. 17, no. 1, pp. 1334–1373, 2016.
  * [4] F. Ye, S. Zhang, P. Wang, and C.-Y. Chan, “A survey of deep reinforcement learning algorithms for motion planning and control of autonomous vehicles,” in _2021 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2021, pp. 1073–1080.
  * [5] A. Pattanaik, Z. Tang, S. Liu, G. Bommannan, and G. Chowdhary, “Robust deep reinforcement learning with adversarial attacks,” in _Proceedings of the 17th International Conference on Autonomous Agents and Multi-Agent Systems_ , ser. AAMAS ’18. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2018, p. 2040–2042.
  * [6] G. Dalal, K. Dvijotham, M. Vecerik, T. Hester, C. Paduraru, and Y. Tassa, “Safe exploration in continuous action spaces,” _arXiv preprint arXiv:1801.08757_ , 2018.
  * [7] F. Berkenkamp, “Safe exploration in reinforcement learning: Theory and applications in robotics,” Ph.D. dissertation, ETH Zurich, 2019.
  * [8] M. Alshiekh, R. Bloem, R. Ehlers, B. Könighofer, S. Niekum, and U. Topcu, “Safe reinforcement learning via shielding,” in _Thirty-Second AAAI Conference on Artificial Intelligence_ , 2018.
  * [9] S. Webb, T. Rainforth, Y. W. Teh, and M. P. Kumar, “A statistical approach to assessing neural network robustness,” in _7th Int. Conf. on Learning Representations (ICLR’19)_. OpenReview.net, 2019.
  * [10] B. Wang, S. Webb, and T. Rainforth, “Statistically robust neural network classification,” in _Proc. of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence_ , ser. PMLR, vol. 161 of UAI’21, 2021, pp. 1735–1745.
  * [11] C. Huang, J. Fan, X. Chen, W. Li, and Q. Zhu, “Polar: A polynomial arithmetic framework for verifying neural-network controlled systems,” in _the 20th Int. Symp. on Automated Technology for Verification and Analysis_ , 2022.
  * [12] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra, “Continuous control with deep reinforcement learning,” in _ICLR’16_ , 2016.
  * [13] S. Fujimoto, H. Hoof, and D. Meger, “Addressing function approximation error in actor-critic methods,” in _International conference on machine learning_. PMLR, 2018, pp. 1587–1596.
  * [14] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _arXiv preprint arXiv:1707.06347_ , 2017\.
  * [15] Robotis, “Robotis(2019) turtlebot3 – e-manual, waffle pi,” [Online] https://emanual.robotis.com/docs/en/platform/turtlebot3/overview/. (Accessed on 02 August 2021).
  * [16] W. Ruan, X. Huang, and M. Kwiatkowska, “Reachability analysis of deep neural networks with provable guarantees,” in _Proceedings of the 27th International Joint Conference on Artificial Intelligence_ , ser. IJCAI’18. AAAI Press, 2018, p. 2651–2659.
  * [17] C. Huang, J. Fan, W. Li, X. Chen, and Q. Zhu, “Reachnn: Reachability analysis of neural-network controlled systems,” _ACM Transactions on Embedded Computing Systems (TECS)_ , vol. 18, no. 5s, pp. 1–22, 2019.
  * [18] X. Huang, D. Kroening, W. Ruan, J. Sharp, Y. Sun, E. Thamo, M. Wu, and X. Yi, “A survey of safety and trustworthiness of deep neural networks: Verification, testing, adversarial attack and defence, and interpretability,” _Computer Science Review_ , vol. 37, p. 100270, 2020.
  * [19] M. Althoff, “Reachability analysis and its application to the safety assessment of autonomous cars,” Ph.D. dissertation, Technische Universität München, 2010.
  * [20] K. Makino and M. Berz, “Taylor models and other validated functional inclusion methods,” _International Journal of Pure and Applied Mathematics_ , vol. 6, pp. 239–316, 2003.
  * [21] R. Ivanov, T. Carpenter, J. Weimer, R. Alur, G. Pappas, and I. Lee, “Verisig 2.0: Verification of neural network controllers using taylor model preconditioning,” in _Int. Conf. on Computer Aided Verification_. Springer, 2021, pp. 249–262.
  * [22] J. D. Musa, “Operational profiles in software-reliability engineering,” _IEEE Software_ , vol. 10, no. 2, pp. 14–32, 1993.
  * [23] C. Smidts, C. Mutha, M. Rodriguez, and M. J. Gerber, “Software testing with an operational profile: Op definition,” _ACM Comput. Surv._ , vol. 46, no. 3, 2014.
  * [24] R. Agarwal, M. Schwarzer, P. S. Castro, A. C. Courville, and M. Bellemare, “Deep reinforcement learning at the edge of the statistical precipice,” _Advances in neural information processing systems_ , vol. 34, pp. 29 304–29 320, 2021.
  * [25] G. Yang, G. Qian, P. Lv, and H. Li, “Efficient verification of control systems with neural network controllers,” in _Proceedings of the 3rd International Conference on Vision, Image and Signal Processing_ , 2019, pp. 1–7.
  * [26] P. Gritzmann and B. Sturmfels, “Minkowski addition of polytopes: computational complexity and applications to gröbner bases,” _SIAM Journal on Discrete Mathematics_ , vol. 6, no. 2, pp. 246–269, 1993.
  * [27] Y.-Y. Yang, C. Rashtchian, H. Zhang, R. R. Salakhutdinov, and K. Chaudhuri, “A closer look at accuracy vs. robustness,” _Advances in neural information processing systems_ , vol. 33, pp. 8588–8601, 2020.
  * [28] Y. Dong, W. Huang, V. Bharti, V. Cox, A. Banks, S. Wang, X. Zhao, S. Schewe, and X. Huang, “Reliability assessment and safety arguments for machine learning components in system assurance,” _ACM Tran. on Embedded Computing Systems_ , 2022.
  * [29] X. Zhao, W. Huang, A. Banks, V. Cox, D. Flynn, S. Schewe, and X. Huang, “Assessing the Reliability of Deep Learning Classifiers Through Robustness Evaluation and Operational Profiles,” in _AISafety’21 Workshop at IJCAI’21_ , 2021.
  * [30] M. Quigley, K. Conley, B. Gerkey, J. Faust, T. Foote, J. Leibs, R. Wheeler, A. Y. Ng _et al._ , “Ros: an open-source robot operating system,” in _ICRA workshop on open source software_ , vol. 3, no. 3.2. Kobe, Japan, 2009, p. 5.
  * [31] N. Koenig and A. Howard, “Design and use paradigms for gazebo, an open-source multi-robot simulator,” in _IEEE/RSJ Int. Conf. on Intelligent Robots and Systems_ , vol. 3. IEEE, 2004, pp. 2149–2154.


# Hierarchical Neural Coding for Controllable CAD Model Generation

Xiang Xu  Pradeep Kumar Jayaraman  Joseph G. Lambourne  Karl D.D. Willis
Yasutaka Furukawa

###### Abstract

This paper presents a novel generative model for Computer Aided Design (CAD)
that 1) represents high-level design concepts of a CAD model as a three-level
hierarchical tree of neural codes, from global part arrangement down to local
curve geometry; and 2) controls the generation or completion of CAD models by
specifying the target design using a code tree. Concretely, a novel variant of
a vector quantized VAE with “masked skip connection” extracts design
variations as neural codebooks at three levels. Two-stage cascaded auto-
regressive transformers learn to generate code trees from incomplete CAD
models and then complete CAD models following the intended design. Extensive
experiments demonstrate superior performance on conventional tasks such as
unconditional generation while enabling novel interaction capabilities on
conditional generation tasks. The code is available at
https://github.com/samxuxiang/hnc-cad.

Computer Vision, Generative 3D Modeling, Computer Aided Design, Self-
Supervised Learning, VQ-VAE, Controllable Generation, Transformer

##  1 Introduction

From automobiles to airplanes, excavators to elevators, man-made objects are
created using Computer Aided Design (CAD) software. Most modern CAD design
tools employ the “Sketch and Extrude” style workflow (Camba et al., 2016;
Shahin, 2008), where designers 1) draw loops of 2D curves as outer and inner
boundaries to create 2D profiles; 2) extrude the 2D profiles to 3D shapes; and
3) add or subtract 3D shapes to build complex CAD models.

Figure 1:  We propose three-level hierarchical neural coding for controllable
CAD model generation. Our system learns high-level design concepts as discrete
codes at different levels, enabling more diverse and higher-quality generation
(top); novel user controls while specifying design intent (bottom-left); and
autocompleting a partial CAD model under construction (bottom-right).

CAD models created in this way have a natural tree structure which supports
local edits. The curves at the leaves of the tree can be adjusted and the
extrusions regenerated to update the final shape. For designers, it is also
important that edits preserve “design intent”. Otey et al (Otey et al., 2018)
defines design intent as “a CAD model’s anticipated behavior when altered”
while Martin (Martin, 2023) describe it as “relationships between objects, so
that a change to one can propagate automatically to others”. Although “Sketch
and Extrude” allows local changes, it does not provide the relationships
required to give the anticipated behavior when the model is edited. A
computational system with understanding of design intent would revolutionize
the practice of CAD. The system would help designers in 1) generating a
diverse set of CAD models given high-level design concepts; 2) modifying
existing CAD models while constraining certain model properties or 3) auto-
completing designs interactively (See Figure 1).

Figure 2: Example failures of parametric CAD, editing a design (a) by
shortening or extending (green) the table. Inconsistent areas are highlighted
in red.

Unfortunately, such a system is not yet available for designers. A current
industry standard is to manually specify parameters and equations which define
the positions and sizes of profiles, and constraints to align geometry. This
process, known as Parametric CAD, requires specialized skills (Yares, 2013)
and easily breaks with unanticipated edits. Figure 2 illustrates examples,
where editing the geometry of a poorly constrained CAD model breaks the
original design intent. State-of-the-art research employs machine learning
techniques to automatically generate CAD models, e.g. Wu et al. (2021).
However, existing works do not make use of the hierarchical nature of CAD
designs to provide effective design control.

This paper presents a novel generative network that captures the design intent
of a CAD model as a three-level tree of neural codes, from local geometric
features to global part arrangement; and controls the generation or completion
of CAD models subject to the design intent specified by the code tree or an
incomplete CAD model. CAD models are generated as sequences of modeling
operations, then converted into the industry standard boundary representation
(B-Rep) format for editing in mechanical CAD software.

Concretely, a novel variant of the vector quantized VAE (Van Den Oord et al.,
2017) with “masked skip connection” learns design variations as three neural
codebooks from a large-scale sketch-and-extrude CAD dataset (Wu et al., 2021).
The masked skip connection is simple yet effective at extracting well-
abstracted codebooks, making the relationships of codes and generated geometry
intuitive. Then, two-stage cascaded auto-regressive transformers learn to
generate 1) three-level code trees given an incomplete CAD model, 2) complete
CAD model given the code tree and the incomplete data. Designers can also
directly provide a code tree for model generation.

Qualitative and quantitative evaluations against other generative baselines
show that our system generates more realistic and complicated models in a
random generation task. In user-controlled conditional generation tasks, our
system demonstrates flexible and superior geometry control, enabled by the
hierarchical code tree representation, over the current state-of-the-art deep
learning-based generative models (i.e., SkexGen (Xu et al., 2022), DeepCAD (Wu
et al., 2021)). In summary, we make the following contributions:

$\bullet$ A neural code tree representation encoding hierarchical design
concepts that enables generation of high quality and complex models, design
intent aware user editing, and design auto-completion.

$\bullet$ A novel variant of VQ-VAE with a masked skip connection for enhanced
codebook learning.

$\bullet$ State-of-the-art performance in CAD model generation over the
previous SOTA methods.

##  2 Related Work

Constructive Solid Geometry (CSG): CSG builds complex shapes as Boolean
combinations of simple primitives. Recent works utilized this representation
for reconstructing CAD shapes with program synthesis (Du et al., 2018; Nandi
et al., 2017, 2018; Sharma et al., 2018; Ellis et al., 2019; Tian et al.,
2019), and unsupervised learning (Kania et al., 2020; Ren et al., 2021; Chen
et al., 2020; Yu et al., 2022, 2023). Although a CSG tree can be converted
into B-rep by building equivalent primitives and applying Boolean operations
with solid modeling kernel, parametric CAD (Camba et al., 2016), where a
sequence of 2D sketches are built and extruded to 3D, is the dominant paradigm
for designing mechanical parts and supports easy parametric editing.

Direct CAD Generation: Some recent works focused on directly generating CAD
models without any supervision from CAD modeling sequences, by building the
geometry of parametric curves (Wang et al., 2020) and surfaces (Sharma et al.,
2020) with fixed (Smirnov et al., 2021) or arbitrary topology for sketches
(Willis et al., 2021a) and solid models(Wang et al., 2022; Guo et al., 2022;
Jayaraman et al., 2022). We focus more on controllable generation of
parametric CAD in the form of sketch and extrude sequences.

Sketch and Extrude CAD Generation: Recent availability of large-scale datasets
for parametric CAD has enabled learning based methods to leverage the CAD
modeling sequence history (Willis et al., 2021b; Wu et al., 2021; Xu et al.,
2022) and sketch constraints (Seff et al., 2020) to generate engineering
sketches and solid models. The generated sequences can be parsed with a solid
modeling kernel to obtain editable parametric CAD files containing 2D
engineering sketches (Willis et al., 2021a; Para et al., 2021; Ganin et al.,
2021; Seff et al., 2021) or 3D CAD shapes (Wu et al., 2021; Xu et al., 2022).
Additionally, the generation can be influenced by a target B-rep (Willis et
al., 2021b; Xu et al., 2021), sketches (Li et al., 2020; Seff et al., 2021),
images (Ganin et al., 2021), voxel grids (Lambourne et al., 2022) or point
clouds with (Uy et al., 2021) and without sequence guidance (Ren et al., 2022;
Li et al., 2023). But this kind of control is on a global level, while we aim
for hierarchical control on both global and local levels to support
applications like design preserved edits and autocomplete.

User-Controlled CAD Generation: Providing user control over the generation
process, while preserving design intent, is key for adoption of generative
models in real world CAD software. Although previous approaches can produce
diverse shapes based on high level guidance, enabling user control over the
generation process is more challenging. In the Sketch2CAD framework (Li et
al., 2020), a network is trained to predict CAD operations that correspond
with segmented sketch strokes, enabling a user interface for sketch based CAD
modeling. Free2CAD (Li et al., 2022) generalizes this system by additionally
learning how to segment a complete sketch into groups that can be mapped to
CAD operations. These works focus on localized control over the design
process, and require significant user input. Recent works also leverage text
prompts (Wu et al., 2023; Kodnongbua et al., 2023) and user-specified
guidelines (Cheng et al., 2023). SkexGen (Xu et al., 2022) allows users to
explore design variations with disentangled global control over over the
topology and geometry of CAD shapes. However, their approach simply aids in
creating a new design from scratch and cannot be easily modified to provide an
interactive experience that users expect for smartly editing CAD models or
autocompleting their next steps to save effort. Different from existing works,
our method leverages the natural hierarchies which exist inside the CAD models
to provide both global and local control over the generation process.

##  3 Hierarchical CAD Properties

Figure 3: Our hierarchical tree representation of a CAD model, with which a
novel VQ-VAE learns codebooks at the levels of solid, profile, and loop.

A sketch and extrude CAD model is naturally hierarchical (see Figure 3) with a
loop defining a closed path of connected curves, a profile defining a closed
area in the sketch plane bounded by one outer loop and some inner loops, and a
solid representing a set of extruded profiles that are combined to form the
entire model. Our goal is to enable local and global control in the generation
of CAD models where users edit any of these entities and expect the rest to be
updated sensibly automatically. To achieve this, we capture this hierarchy in
the latent space of our neural networks. At higher levels of the hierarchy,
the network learns the relative positions of lower level geometric entities,
that is, the bounding boxes of the profiles and extrusions which make up the
model. Concretely, we consider a CAD model as a (S)olid-(P)rofile-(L)oop tree:

Loop ($L$): At the leaf of the tree, we have loops. Each loop consists of a
set of lines and arcs or a circle. The properties of a loop ($L$) is defined
as a series of x-y coordinates separated by special <SEP> tokens:

$L=\\{(x_{1},y_{1}),(x_{2},y_{2}),{\small\texttt{<SEP>}},(x_{3},y_{3}),\
\ldots\\}.$ (1)

Lines are represented by the xy-coordinates of two points. Here we use the
start and end of the curve. Arcs are represented by three points including
start, middle and end point. Circles are represented by four equally spaced
points lying on the curve. With this representation, the curve types can be
identified by the number of points as in (Willis et al., 2021a). We sort the
curves in a loop so that the initial curve is the one with the smallest
starting point coordinate, and the next one is its connected curve in
counterclockwise order.

Profile ($P$): The profile is above the leaf level. Since the loop geometry is
captured at the leaf level, the properties of a profile node is defined as a
series of 2D bounding box parameters of the loops within the sketch plane:

$P=\\{(x_{i},y_{i},w_{i},h_{i})\\}_{i=1}^{N_{i}^{\text{loop}}}.$ (2)

$i$ is the index of the $N_{i}^{\text{loop}}$ loops within a profile.
$(x_{i},y_{i})$ is the bottom-left corner of the bounding box. $(w_{i},h_{i})$
is the width and height. We determine the order of bounding box parameters in
profile $P$ by sorting the bottom-left corner of all the 2D bounding boxes in
ascending order.

Solid ($S$): Above the profile level, we have the 3D solid model formed by
extruding one or more profiles. The properties of a solid node captures the
arrangement of extruded profiles using a series of 3D bounding box parameters:

$S=\\{(x_{j},y_{j},z_{j},w_{j},h_{j},d_{j})\\}_{j=1}^{N_{j}^{\text{profile}}}.$
(3)

$j$ is the index of the $N_{j}^{\text{profile}}$ extruded profiles within a
model. $(x_{j},y_{j},z_{j})$ is the bottom-left corner of the bounding box and
$(w_{j},h_{j},d_{j}$) is its dimension. Likewise, the parameters in $S$ is
sorted by the bottom-left corner of all the extruded 3D bounding boxes in
ascending order.

Figure 4: Left: VQ-VAE with masked skip connection for codebook learning.
Given a CAD model as a construction sequence (e.g., x, y, S), an MLP and a
Transformer encoder convert the input to latent codes ( $T^{E}_{t}$), and a
vector quantization extracts a code ($\mathbf{c}$) after average pooling. A
Transformer decoder recovers the input sequence, conditioned on the vector-
quantized code ($\mathbf{c}$) and the masked input sequence ( $T^{D}_{t}$).
Grey color represents input tokens that were masked out. Right: Controllable
CAD generation module with two-stage auto-regressive generators. Given a
partial CAD model, a model encoder converts it to latent embeddings
($T^{E}_{t}$). The first auto-regressive Transformer generates hierarchical
neural codes ($T^{C}_{t}$) conditioned on the encoded embeddings. The second
auto-regressive Transformer generates a new CAD model.

##  4 Three-Level Codebook Learning

Given a dataset of sketch and extrude CAD models in the
(S)olid-(P)rofile-(L)oop tree format, a novel variant of the vector quantized
VAE (VQ-VAE) (Van Den Oord et al., 2017; Razavi et al., 2019) learns their
latent patterns as three discrete codebooks, which encode a CAD model into a
tree of neural codes for downstream applications.

Following SkexGen (Xu et al., 2022), the foundation of our architecture for
learning codebooks is a VQ-VAE, consisting of a Transformer encoder $E$ and
decoder $D$ (see Figure 4). We learn (L)oop, (P)rofile, and (S)olid codebooks
independently. Different from SkexGen and previous work on masked learning (He
et al., 2022), we apply masking on a skip-connection from the encoder input to
the decoder input. Intuitively, a standard VQ-VAE (i.e., without skip
connection) is trained to recover instance-specific input details, which would
be a challenge for the quantized code if it is learning instance-agnostic
design patterns. A naïve skip connection allows the decoder to cheat by
directly copying the input. Masking the skip connection forces the decoder to
relate partial details from unmasked elements and fill-in missing ones, where
the relation is guided by design patterns encoded in the code.

Encoder: Consider a (L)oop node $L$ (Equation 1), containing a series of x-y
coordinates and special <SEP> tokens. We use a $65$D one-hot vector to
represent a token, where a coordinate is quantized to a 6 bit (i.e., 64D) (Xu
et al., 2022; Seff et al., 2021) and <SEP> requires one extra dimension. Let
$T^{E}_{t}$ denote the 256D embedding of the $t^{\text{th}}$ token for the
Transformer encoder. The embedding is initialized as:

$\displaystyle
T^{E}_{t}\leftarrow\begin{cases}\text{MLP}(W_{\text{emb}}x_{t}\mathbin{\|}W_{\text{emb}}y_{t})+\gamma_{t}\
\ \text{ (for x-y)},\\\
\text{MLP}(W_{\text{emb}}\texttt{<SEP>}\mathbin{\|}W_{\text{emb}}\texttt{<SEP>})+\gamma_{t}.\\\
\end{cases}$ (4)

$W_{\text{emb}}$ is a $65\times 32$ token embedding matrix. $\mathbin{\|}$ is
the concatenation operator. MLP is a 2-layer multilayer perception.
$\gamma_{t}$ is a learnable 256D positional embedding. Second case is for
<SEP> where value is repeated twice. For (P)rofile and (S)olid codebooks, we
process each of the 2D or 3D bounding box parameters the same way as $x_{t}$,
$y_{t}$ coordinates, except with no <SEP> tokens.

Vector Quantization: The outputs of the encoder ($E$), with sequence length
$T$, are first average pooled, forming $\overline{E}(T^{E})$. The standard
vector quantization procedure is then applied to obtain a 256D codebook vector
$\mathbf{c}$. More specifically, we compare the Euclidean distance between
codebook vector $\mathbf{b}$ and encoded $\overline{E}(T^{E})$ and perform a
nearest neighbor lookup.

$\displaystyle\mathbf{c}\leftarrow\mathbf{b}_{k},\quad\text{where}\hskip
2.84544ptk=\mbox{argmin}_{i}\left|\left|\overline{E}(T^{E})-\mathbf{b}_{i}\right|\right|^{2}.$
(5)

Decoder with Masked Skip Connection: The decoder takes the quantized code
$\mathbf{c}$ and the input series of x-y coordinates and <SEP> tokens with
masking, and predicts the masked tokens. For example, in the case of a loop
node, any of the $x_{t}$, $y_{t}$ and <SEP> tokens could be masked (concretely
30% to 70% of the tokens per model randomly). Let $T^{D}_{t}$ denote the
embedding of the $t_{\text{th}}$ token as an input to the decoder. Each token
is embedded exactly as in Equation 4, except that embeddings of masked tokens
are replaced with a learnable shared 32D mask token embedding $m$.

The 256D codebook vector $\mathbf{c}$ from the encoder is concatenated
together with $\\{T^{D}_{t}\\}$ and passed to the decoder ($D$), which has 4
self-attention layers. The idea here is to force the encoder to learn useful
latent features that can help the decoder to predict the masked tokens.
Finally, an MLP is applied to each token embedding (except the codebook
vector) after the decoder to produce $(2\times 65)$D logits, a pair of
probability values over the 65 class labels for predicting the xy-coordinates
or the <SEP> token.

Loss Function: The training loss consists of three terms:

$\displaystyle\sum_{t}\text{EMD}\Big{(}D(\mathbf{c},\\{T^{D}_{t}\\}),\text{
}\mathbbm{1}_{T_{t}}\Big{)}+$
$\displaystyle\left|\left|sg[\overline{E}(T^{E})]-\mathbf{c}\right|\right|^{2}_{2}+\beta\left|\left|\overline{E}(T^{E})-sg[\mathbf{c}]\right|\right|^{2}_{2}.$
(6)

The first term is the squared Earth Mover’s Distance Loss between the decoder
output probability and the corresponding data property’s one hot encoding
$\mathbbm{1}_{T_{t}}$. The loss is only applied at masked tokens. We use the
EMD loss function from (Hou et al., 2016) which assumes ordinal class labels
and penalizes predictions closer to the ground-truth less than those far away.
This works better than a cross-entropy loss since x-y coordinates carry
distance relations, allowing the loss to focus on predictions far away from
the ground-truth. Note that we treat the <SEP> token in loop data properties
differently by applying the standard cross-entropy loss on it as this is not
an ordinal class label.

The second and third terms are the codebook and commitment losses used in VQ-
VAE (Van Den Oord et al., 2017; Razavi et al., 2019). $sg$ denotes the stop-
gradient operation, which is the identity function in forward pass but blocks
gradients in backward pass. $\beta$ scales the commitment loss and is set to
0.25. We use the exponential moving average updates with a decay rate of 0.99
(Razavi et al., 2019).

##  5 Controllable CAD Generation

Loop, profile, and solid codebooks allow us to express the design concepts of
a CAD model as hierarchical neural codes, enabling diverse and high-quality
generation, novel user controls specifying design intent, and autocompletion
of incomplete CAD models. Concretely, given an incomplete CAD model as a
sketch and extrude construction sequence: 1) A model encoder turns the input
sequence into latent embeddings; 2) An auto-regressive Transformer generates a
code tree, conditioned on the embedded input sequence; and 3) The second auto-
regressive Transformer generates the full CAD models, conditioned on the
embedded input sequence and a code tree.

Model Encoder: The model encoder backbone is the standard Transformer encoder
module with 6 self-attention layers. We borrow the format used in SkexGen (Xu
et al., 2022) and represent a model as a sequence of tokens, each of which is
a one-hot vector, uniquely determining a curve type, quantized curve parameter
and quantized extrusion parameter. The encoder converts the one-hot vectors
into a series of 256D latent embeddings $\\{T^{E}_{t}\\}$. 111As in SkexGen,
we encode “geometry” and “extrusion” sequence separately and concatenate the
embeddings to get $T^{E}_{t}$. For experiments with 2D sketches, only the
geometry encoder is used.

Code Tree Generator: $G_{\text{code}}$ is an autoregressive decoder which
generates a hierarchy of codes $\\{T^{C}_{t}\\}$. A code is assigned to each
(S)olid, (P)rofile, or (L)oop from a corresponding codebook, conditioned on
the encoded embeddings $\\{T^{E}_{t}\\}$. Similar to the hierarchical property
representation (section 3), hierarchical codes are represented as a series of
feature vectors indicating either a code or a separator token. Concretely, a
feature is a one-hot vector whose size is the total number of codes in the
three codebooks plus one for the separator. For example, consider the code
tree in Figure 3, consisting of a model with one solid, two profiles, and two
or four loops. This tree is represented as features in the following order [S,
$<$SEP$>$, P, L, L, $<$SEP$>$, P, L, L, L, L]. Here we perform depth-first
traversal of the neural code tree and the boundary command $<$SEP$>$ is used
to indicate a new grouping of profile and loop codes.

$G_{\text{code}}$ has 6 self-attention (SA) layers interleaved with 6 cross-
attention (CA) layers. The first SA layer is over the query tokens
$\\{T^{\tilde{C}}_{t}\\}$, each of which is initialized by a position encoding
$\gamma_{t}$ and autoregressively estimated. The input to each of the CA
layers is $\\{T^{E}_{t}\\}$. Each SA or CA layer has 8-heads attentions,
followed by an Add-Norm layer. A query token $\\{T^{\tilde{C}}_{t}\\}$ will
have a generated code index, which is converted to a code $T^{C}_{t}$. A
separator is replaced by a learnable embedding.

$\displaystyle
T^{C}_{t}\leftarrow\begin{cases}\text{Codebook}(T^{\tilde{C}}_{t})+\gamma_{t}&\text{(for
code)},\\\ W_{\text{emb}}\texttt{<SEP>}\hskip 12.51927pt+\gamma_{t}&\text{(for
{<SEP>})}.\end{cases}$ (7)

Codebook denotes the mapping from a code index to the code. We train
$G_{\text{code}}$ with the standard cross-entropy loss. Note that for
unconditional generation, we remove the partial CAD model encoder and train SA
layers with query tokens ($\\{T^{\tilde{C}}_{t}\\}$) only, without cross-
attention layers and $\\{T^{E}_{t}\\}$.

Model Generator: The model generator is the second auto-regressive decoder
$G_{\text{cad}}$, generating a sketch-and-extrude CAD model. $G_{\text{cad}}$
is the same as the SkexGen decoder (Xu et al., 2022) except that partial CAD
model embeddings $\\{T^{E}_{t}\\}$ and the hierarchical neural codes
$\\{T^{C}_{t}\\}$ control the generation via the cross-attention layers, while
SkexGen only allows the specification of global codes. The architecture
specification is the same as the first decoder. The query tokens
($T^{out}_{t}$) contain the generated CAD command sequences as one-hot vectors
(Xu et al., 2022), where we use the same standard cross entropy loss.

##  6 Evaluation

(b) SkexGen (c) Ours Figure 5: Unconditional generation results by (a)
DeepCAD, (b) SkexGen and (c) our method. The bottom three rows (red color)
show complex samples with three or more sketch-extrude steps.

(a) DeepCAD

This section presents unconditional and conditional generation results, which
demonstrate 1) Higher quality, diversity, and complexity compared to current
state-of-the-art; 2) Controllable generation via hierarchical neural codes;
and 3) Two important applications, user-edit and auto-completion.

###  6.1 Experiment Setup

Dataset: We use the large-scale DeepCAD dataset (Wu et al., 2021) with ground-
truth sketch-and-extrude models. DeepCAD contains 178,238 sketch-and-extrude
models with a split of $90\%$ train, $5\%$ validation, and $5\%$ test samples.
We detect and remove duplicate models from the training set as in prior works
(Willis et al., 2021a; Xu et al., 2022). After extracting the hierarchical
properties for (L)oop, (P)rofile, and (S)olid (section 3), we also remove
duplicate properties for each level. Lastly, we use a CAD model for training
only when the number of solids is at most 5, the number of loops is at most 20
for every profile, the number of curves is at most 60 for every loop, and the
total number of commands in the sketch-and-extrude sequence is at most 200.
After the duplicate removal and filtering, the training set contains 102,114
solids, 60,584 profiles, 150,158 loops for codebook learning, and 124,451
sketch-and-extrude sequences for CAD model generation training. For CAD
engineering drawings, we follow SkexGen (Xu et al., 2022) and extract sketches
from DeepCAD. A total of 99,650 sketches are used for training after duplicate
removal.

Implementation Details: Models are trained on an Nvidia RTX A6000 GPU with a
batch size of 256. The codebook module and the generation module are trained
for 250 and 350 epochs, respectively. We use the improved Transformer backbone
with pre-layer normalization as in (Wu et al., 2021; Xu et al., 2022). Input
embedding dimension is $256$. Feed-forward dimension is $512$. Dropout rate is
$0.1$. Each Transformer network in the generation module has 6 layers with 8
attention heads. The codebook learning networks have 4 layers. We use the
AdamW (Loshchilov & Hutter, 2018) optimizer with a learning rate of $0.001$
after linear warm-up for 2000 steps. At test time, we use nucleus sampling
(Holtzman et al., 2020) to autoregressively generate the codes and CAD tokens.
To reduce overfitting, we follow (Xu et al., 2022) and augment the training
data by adding a small random noise to the input curve coordinates.

VQ-VAEs suffer from codebook collapse and we employ an approach from Jukebox
(Dhariwal et al., 2020) that reinitializes under-utilized codes (less than 7
mapped samples). To identify the optimal codebook size, we trained our model
using different codebook sizes and evaluated the unconditional generation
results using the $5\%$ validation set in DeepCAD. Our analysis revealed that
the model performance was best for codebook size ranging from 2,000 to 4,000,
with larger codebook not providing noticeable improvement. Our final codebook
size is around 3,500 for profile and solid, and 2,500 for loop. The
compression ratio of dividing the number of unique data by the codebook size
is approximately 60x for loop, 17x for profile, and 29x for solid.

###  6.2 Metrics

Five established metrics quantitatively evaluate random generation. Three
metrics are based on point clouds sampled on the model surfaces. Two metrics
are based on generated tokens of sketch and extrude construction sequence.

Point-cloud metrics measure generation diversity and quality by sampling 2,000
points on each generated or ground-truth data and compare two sets of point
clouds (Achlioptas et al., 2018; Wu et al., 2021; Xu et al., 2022).

$\bullet$ Coverage (COV) is the percentage of ground-truth models that have at
least one matched generated sample. The matching process assigns every
generated sample to its closest neighbor in the ground-truth set based on
Chamfer Distance (CD) or Earth Mover’s Distance (EMD). COV measures the
diversity of generated shapes. If CAD generation suffers from mode collapse,
generated shapes would only match a few ground-truth models, leading to low
coverage scores.

$\bullet$ Minimum Matching Distance (MMD) reports the average minimum matching
distance between the ground-truth set and the generated set.

$\bullet$ Jensen-Shannon Divergence (JSD) is the similarity between two
probability distributions, measuring how often the ground-truth points clouds
occupied similar locations as the generated point clouds. We voxelize the 3D
space and count the number of points in each voxel. This gives us occupancy
distributions for computing the JSD score.

Token metrics measure uniqueness (Willis et al., 2021a). Numeric fields are
quantized to 6-bit.

$\bullet$ Novel is the percentage of generated CAD sequence that does not
appear in the training set.

$\bullet$ Unique is the percentage of generated data that appears once in the
generated set.

Table 1: Quantitative evaluations on the CAD generation task based on the Coverage (COV) percentage, Minimum Matching Distance (MMD), Jensen-Shannon Divergence (JSD), the percentage of Unique and Novel scores and Realism as perceived by human evaluators.  Method | COV | MMD | JSD | Novel | Unique | Realism
---|---|---|---|---|---|---
|  % $\uparrow$ | $\downarrow$ | $\downarrow$ |  % $\uparrow$ |  % $\uparrow$ |  % $\uparrow$
DeepCAD | 80.62 | 1.10 | 3.29 | 91.7 | 85.8 | 38.7
SkexGen | 84.74 | 1.02 | 0.90 | 99.1 | 99.8 | 46.9
Ours | 87.73 | 0.96 | 0.68 | 93.9 | 99.7 | 49.2

###  6.3 Unconditional Generation

We compare with two sketch-and-extrude baselines, DeepCAD (Wu et al., 2021)
and SkexGen (Xu et al., 2022), for the unconditional generation task. Our
cascaded auto-regressive system generates a code tree and then a CAD model.
Each method generates 10,000 CAD models, which are compared with randomly
selected 2,500 ground truth models from the test set.

Quantitative Evaluation: Table 1 reports the average scores across 3 different
runs. Our method outperforms baselines on all three point cloud evaluation
metrics, demonstrating great improvements in quality and diversity. The Unique
score of our method matches SkexGen and is significantly better than DeepCAD.
For the Novel score, our method is slightly worse than SkexGen, while still
significantly better than DeepCAD, which is caused by the smaller training set
that lacks diversity and has only a few complex shapes. SkexGen suffers less
from this issue since it fails to generate very complex CAD models (see Figure
5).

Qualitative Evaluation: Figure 5 provides side-by-side qualitative comparisons
at different steps of sketch-and-extrude. The figure shows that our approach
generates well-structured CAD models, reminiscent of real-world examples.
Generated solids have more complicated shape geometries and part arrangements.
Additional qualitative results are available in Figure 15 and Figure 16. Also
see Appendix C for the sketch generation results.

Figure 6: Distribution of votes by 7 human evaluators comparing the realism of
complex samples produced by the three methods with the training set. Figure 7:
Generated results from hierarchical code tree editing. Code is edited in the
(L)oop level of the tree in the first row, the (P)rofile level of the tree in
the second row, and the (S)olid level of the tree in the third row. The code
tree corresponding to each result is inset below.

Human Evaluation: To evaluate the perceived quality of our generation results,
we run a human evaluation following the methodology in (Jayaraman et al.,
2022). As our hierarchical technique excels at generating complex models, we
choose to perform the human evaluation on models with three or more
extrusions. For the DeepCAD and SkexGen benchmarks, where control over the
complexity of the generated models is not possible, we randomly sample models
that have three or more extrusions from a larger pool of unconditional
generation results. For each model created by a generative method, we randomly
select another ground-truth model from DeepCAD and display renderings of the
two side by side. The image pairs were presented to crowd workers from the
Amazon Mechanical Turk workforce (Mishra, 2019), who were asked to evaluate
which of the two is more “realistic”. To assist the crowd workers with this
task, we provide carefully chosen examples of complex CAD models and low
quality generations. See Appendix A for details.

Each image pair was rated independently by 7 crowd workers and we record the
number of times generated data was selected as more realistic than training
data, giving us a “realism” score from 0 to 7. Figure 6 shows the distribution
of the“realism” scores. We see that for our method the distribution is
symmetric, indicating the crowd workers are unable to distinguish the
generated models from the training. DeepCAD and SkexGen distributions are
skewed towards ”less realistic”, indicating crowd workers were able to
identify models generated by them as simplistic or malformed. We consider a
generated model as more “realistic” than the training data if 4 or more of the
7 raters selected it. For our method, 49.2% of the generated models were more
“realistic” than complex examples from the training data compared to 46.9% for
SkexGen and 38.7% for DeepCAD.

Figure 8: CAD parameter edits with fixed code trees. Red arrows indicate the
individual parts edited by the user. Other parts automatically got modified.
Figure 9: Autocompleted sketches (column 2 $\sim$ 4) from partial loops
(column 1).

###  6.4 Controllable Generation

We demonstrate controllable generation in two “editing”, and one “auto-
completion” application scenarios.

Code Tree Editing: Given a code tree, a user can edit the code nodes at three
different levels, achieving local and global modifications across the CAD
hierarchy. This hierarchical control over the generation is unavailable in
previous methods (Wu et al., 2021; Xu et al., 2022). Figure 7 illustrates the
diverse and well-controlled generated results from editing of the code tree.
We see that loop codes control the shape geometry, profile codes control the
loop dimension and positioning in 2D, and finally solid code controls the
height of extruded sketches and their 3D combination.

Figure 10: Autocompleted CAD models (blue) from partial extruded profiles
(gray).

Design-Preserving Editing: With the code tree fixed, a user can preserve the
current design while making local edits to the model parameters to iteratively
refine it. Treating user edited parameters as partial input and reuse the
previous neural codes, the model generator outputs a new CAD model following
both the current design and the user edited values. Figure 8 demonstrates that
after a user edit to the horizontal length of a local part, the bottom part in
the left and the two supporting arms in the right adjusted their size
accordingly to accommodate the user edit. This automatic process is the result
of keeping the code tree that encodes the part connectivity and dimension
relations.

Figure 11: Qualitative comparison between our method (center) and the nearest
neighbor search baseline (right). Given the same partial user input (left),
our method autocompletes the CAD model with better diversity and fidelity.

Autocompletion from User Input: We consider partial user input in the format
of one or multiple extruded profiles or loops. Our code tree generator can
predict a set of likely codes from partial input and use the generated code
together with the partial input to autocomplete the full CAD model. Figure 9
shows the sketch autocomplete results when a user provide partial loops and
model completes the full sketch. Likewise, Figure 10 shows the CAD
autocomplete results from partial extruded profiles. Each row contains
multiple generated results from different generated codes. Here we use top-1
sampling in the model generator to limit the generation diversity to code
only. See Appendix B and Appendix C for additional results.

For comparison, we also implemented a nearest-neighbor search baseline.
Partial CAD solids built from intermediate steps of the sketch-and-extrude
formed a ground-truth incomplete CAD database. User input is the query and we
compute its Chamfer distance to all shapes in the database. The k-nearest
shapes are considered to be geometrically similar and we retrieve their
corresponding ground-truth complete CAD models as the completed result. Figure
11 compares our generated results with the top-3 nearest neighbor results.
Nearest-neighbor results have less diversity and fail to closely match the
user input. In contrast, our results correctly auto-complete the user input
with high diversity.

###  6.5 Instance-Agnostic Design Pattern

To better understand the unsupervised features learned by the codebook, Figure
12 shows the data and code mapping after encoding. We see that data assigned
to the same code share similar instance-agnostic design patterns, such as the
oscillating pattern in the first row, while effectively ignoring data-specific
details like the exact number of curves or its type. More visualization is in
Appendix D.

Figure 12: Loops (row 1,2) and profiles (row 3) encoded to the same code.
Profiles shown as bounding boxes.

##  7 Limitations

A primary failure mode of our current system is the lack of validity in the
generated CAD models with self-intersecting edges or solids. Our loss
functions do not explicitly penalize invalid geometries; future work is the
addition of a loss function that explicitly penalizes the CAD model invalidity
with domain knowledge. Another direction is to learn to recover from such
failures, which currently poses a challenge due to the lack of an “invalid CAD
model dataset”. Lastly, another limitation of our approach is the use of the
sketch-and-extrude CAD format that excludes other popular modeling operations
such as revolve, mirror, and sweep.

##  8 Conclusion

We introduce a novel generative model for controllable CAD generation. A key
to our approach is a three-level neural coding that captures design patterns
and intent at different levels of the modeling hierarchy. This paper makes
another step towards intelligent generative design with users in the loop.
Extensive evaluations demonstrate major boosts in generation quality and
promising applications of our hierarchical neural coding such as intent-aware
editing or auto-completion.

## Acknowledgements

This research is partially supported by NSERC Discovery Grants with
Accelerator Supplements and DND/NSERC Discovery Grant Supplement, NSERC
Alliance Grants, and John R. Evans Leaders Fund (JELF).

## References

  * Achlioptas et al. (2018) Achlioptas, P., Diamanti, O., Mitliagkas, I., and Guibas, L.  Learning representations and generative models for 3d point clouds.  In _International conference on machine learning_ , pp. 40–49. PMLR, 2018.
  * Camba et al. (2016) Camba, J. D., Contero, M., and Company, P.  Parametric cad modeling: An analysis of strategies for design reusability.  _Computer-Aided Design_ , 74:18–31, 2016.
  * Chen et al. (2020) Chen, Z., Tagliasacchi, A., and Zhang, H.  Bsp-net: Generating compact meshes via binary space partitioning.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 45–54, 2020.
  * Cheng et al. (2023) Cheng, C.-Y., Huang, F., Li, G., and Li, Y.  Play: Parametrically conditioned layout generation using latent diffusion.  _arXiv preprint arXiv:2301.11529_ , 2023.
  * Dhariwal et al. (2020) Dhariwal, P., Jun, H., Payne, C., Kim, J. W., Radford, A., and Sutskever, I.  Jukebox: A generative model for music.  _arXiv preprint arXiv:2005.00341_ , 2020.
  * Du et al. (2018) Du, T., Inala, J. P., Pu, Y., Spielberg, A., Schulz, A., Rus, D., Solar-Lezama, A., and Matusik, W.  Inversecsg: Automatic conversion of 3d models to csg trees.  _Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH)_ , 37(6):1–16, 2018.
  * Eitz et al. (2012) Eitz, M., Hays, J., and Alexa, M.  How do humans sketch objects?  _ACM Trans. Graph. (Proc. SIGGRAPH)_ , 31(4):44:1–44:10, 2012.
  * Ellis et al. (2019) Ellis, K., Nye, M., Pu, Y., Sosa, F., Tenenbaum, J., and Solar-Lezama, A.  Write, execute, assess: Program synthesis with a repl.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pp. 9169–9178, 2019.
  * Ganin et al. (2021) Ganin, Y., Bartunov, S., Li, Y., Keller, E., and Saliceti, S.  Computer-aided design as language.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Guo et al. (2022) Guo, H., Liu, S., Pan, H., Liu, Y., Tong, X., and Guo, B.  Complexgen: Cad reconstruction by b-rep chain complex generation.  _ACM Trans. Graph. (SIGGRAPH)_ , 41(4), July 2022.  doi: 10.1145/3528223.3530078.  URL https://doi.org/10.1145/3528223.3530078.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * He et al. (2022) He, K., Chen, X., Xie, S., Li, Y., Dollár, P., and Girshick, R.  Masked autoencoders are scalable vision learners.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 16000–16009, 2022.
  * Heusel et al. (2017) Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., and Hochreiter, S.  Gans trained by a two time-scale update rule converge to a local nash equilibrium.  _Advances in neural information processing systems_ , 30, 2017.
  * Holtzman et al. (2020) Holtzman, A., Buys, J., Du, L., Forbes, M., and Choi, Y.  The curious case of neural text degeneration.  In _International Conference on Learning Representations (ICLR)_ , 2020.
  * Hou et al. (2016) Hou, L., Yu, C.-P., and Samaras, D.  Squared earth mover’s distance-based loss for training deep neural networks.  _arXiv preprint arXiv:1611.05916_ , 2016.
  * Jayaraman et al. (2022) Jayaraman, P. K., Lambourne, J. G., Desai, N., Willis, K. D. D., Sanghi, A., and Morris, N. J. W.  Solidgen: An autoregressive model for direct b-rep synthesis.  _”arXiv Preprint”_ , 2022.  doi: 10.48550/ARXIV.2203.13944.  URL https://arxiv.org/abs/2203.13944.
  * Kania et al. (2020) Kania, K., Zieba, M., and Kajdanowicz, T.  Ucsg-net-unsupervised discovering of constructive solid geometry tree.  _Advances in Neural Information Processing Systems_ , 33:8776–8786, 2020.
  * Kodnongbua et al. (2023) Kodnongbua, M., Jones, B. T., Ahmad, M. B. S., Kim, V. G., and Schulz, A.  Zero-shot cad program re-parameterization for interactive manipulation.  _arXiv preprint arXiv:2306.03217_ , 2023.
  * Lambourne et al. (2022) Lambourne, J. G., Willis, K. D., Jayaraman, P. K., Zhang, L., Sanghi, A., and Malekshan, K. R.  Reconstructing editable prismatic cad from rounded voxel models.  In _SIGGRAPH Asia_ , December 2022.
  * Li et al. (2020) Li, C., Pan, H., Bousseau, A., and Mitra, N. J.  Sketch2cad: Sequential cad modeling by sketching in context.  _ACM Transactions on Graphics (TOG)_ , 39(6):1–14, 2020.
  * Li et al. (2022) Li, C., Pan, H., Bousseau, A., and Mitra, N. J.  Free2cad: Parsing freehand drawings into cad commands.  _ACM Trans. Graph. (Proceedings of SIGGRAPH 2022)_ , 41(4):93:1–93:16, 2022.
  * Li et al. (2023) Li, P., Guo, J., Zhang, X., and Yan, D.  Secad-net: Self-supervised cad reconstruction by learning sketch-extrude operations.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 16816–16826, 2023.
  * Loshchilov & Hutter (2018) Loshchilov, I. and Hutter, F.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_ , 2018.
  * Martin (2023) Martin, D.  What is design intent?, 2023.  Accessed: Janurary 19, 2023.
  * Mishra (2019) Mishra, A.  Machine learning in the aws cloud: Add intelligence to applications with amazon sagemaker and amazon rekognition, 2019.  URL https://aws.amazon.com/sagemaker/groundtruth/.
  * Nandi et al. (2017) Nandi, C., Caspi, A., Grossman, D., and Tatlock, Z.  Programming language tools and techniques for 3d printing.  In _2nd Summit on Advances in Programming Languages (SNAPL 2017)_. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
  * Nandi et al. (2018) Nandi, C., Wilcox, J. R., Panchekha, P., Blau, T., Grossman, D., and Tatlock, Z.  Functional programming for compiling and decompiling computer-aided design.  _Proceedings of the ACM on Programming Languages_ , 2(ICFP):1–31, 2018.
  * Otey et al. (2018) Otey, J., Company, P., Contero, M., and Camba, J. D.  Revisiting the design intent concept in the context of mechanical cad education.  _Computer-Aided Design and Applications_ , 15(1):47–60, 2018.  doi: 10.1080/16864360.2017.1353733.  URL https://doi.org/10.1080/16864360.2017.1353733.
  * Para et al. (2021) Para, W. R., Bhat, S. F., Guerrero, P., Kelly, T., Mitra, N., Guibas, L., and Wonka, P.  Sketchgen: Generating constrained cad sketches.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Razavi et al. (2019) Razavi, A., Van den Oord, A., and Vinyals, O.  Generating diverse high-fidelity images with vq-vae-2.  _Advances in neural information processing systems_ , 32, 2019.
  * Ren et al. (2021) Ren, D., Zheng, J., Cai, J., Li, J., Jiang, H., Cai, Z., Zhang, J., Pan, L., Zhang, M., Zhao, H., et al.  Csg-stump: A learning friendly csg-like representation for interpretable shape parsing.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 12478–12487, 2021.
  * Ren et al. (2022) Ren, D., Zheng, J., Cai, J., Li, J., and Zhang, J.  Extrudenet: Unsupervised inverse sketch-and-extrude for shape parsing.  In _ECCV_ , 2022.
  * Seff et al. (2020) Seff, A., Ovadia, Y., Zhou, W., and Adams, R. P.  SketchGraphs: A large-scale dataset for modeling relational geometry in computer-aided design.  In _ICML 2020 Workshop on Object-Oriented Learning_ , 2020.
  * Seff et al. (2021) Seff, A., Zhou, W., Richardson, N., and Adams, R. P.  Vitruvion: A generative model of parametric cad sketches.  _arXiv:2109.14124_ , 2021.
  * Shahin (2008) Shahin, T.  Feature-based design – an overview.  _Computer-aided Design and Applications_ , 5, 01 2008.  doi: 10.3722/cadaps.2008.639-653.
  * Sharma et al. (2018) Sharma, G., Goyal, R., Liu, D., Kalogerakis, E., and Maji, S.  Csgnet: Neural shape parser for constructive solid geometry.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * Sharma et al. (2020) Sharma, G., Liu, D., Maji, S., Kalogerakis, E., Chaudhuri, S., and Měch, R.  Parsenet: A parametric surface fitting network for 3d point clouds.  In _European Conference on Computer Vision (ECCV)_ , pp. 261–276. Springer, 2020.
  * Smirnov et al. (2021) Smirnov, D., Bessmeltsev, M., and Solomon, J.  Learning manifold patch-based representations of man-made shapes.  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Tian et al. (2019) Tian, Y., Luo, A., Sun, X., Ellis, K., Freeman, W. T., Tenenbaum, J. B., and Wu, J.  Learning to infer and execute 3d shape programs.  In _International Conference on Learning Representations (ICLR)_ , 2019.
  * Uy et al. (2021) Uy, M. A., Chang, Y., Sung, M., Goel, P., Lambourne, J., Birdal, T., and Guibas, L. J.  Point2cyl: Reverse engineering 3d objects from point clouds to extrusion cylinders.  _CoRR_ , abs/2112.09329, 2021.  URL https://arxiv.org/abs/2112.09329.
  * Van Den Oord et al. (2017) Van Den Oord, A., Vinyals, O., et al.  Neural discrete representation learning.  _Advances in neural information processing systems_ , 30, 2017.
  * Wang et al. (2022) Wang, K., Zheng, J., and Zhou, Z.  Neural face identification in a 2d wireframe projection of a manifold object.  In _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 1612–1621, 2022.  doi: 10.1109/CVPR52688.2022.00167.
  * Wang et al. (2020) Wang, X., Xu, Y., Xu, K., Tagliasacchi, A., Zhou, B., Mahdavi-Amiri, A., and Zhang, H.  Pie-net: Parametric inference of point cloud edges.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 20167–20178. Curran Associates, Inc., 2020.
  * Willis et al. (2021a) Willis, K. D., Jayaraman, P. K., Lambourne, J. G., Chu, H., and Pu, Y.  Engineering sketch generation for computer-aided design.  In _IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPR Workshop)_ , pp. 2105–2114, 2021a.
  * Willis et al. (2021b) Willis, K. D. D., Pu, Y., Luo, J., Chu, H., Du, T., Lambourne, J. G., Solar-Lezama, A., and Matusik, W.  Fusion 360 gallery: A dataset and environment for programmatic cad construction from human design sequences.  _ACM Transactions on Graphics (TOG)_ , 40(4), 2021b.
  * Wu et al. (2021) Wu, R., Xiao, C., and Zheng, C.  Deepcad: A deep generative network for computer-aided design models.  In _IEEE International Conference on Computer Vision (ICCV)_ , pp. 6772–6782, October 2021.
  * Wu et al. (2023) Wu, R., Su, W., Ma, K., and Liao, J.  Iconshop: Text-based vector icon synthesis with autoregressive transformers.  _arXiv preprint arXiv:2304.14400_ , 2023.
  * Xu et al. (2021) Xu, X., Peng, W., Cheng, C.-Y., Willis, K. D., and Ritchie, D.  Inferring cad modeling sequences using zone graphs.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 6062–6070, June 2021.
  * Xu et al. (2022) Xu, X., Willis, K. D., Lambourne, J. G., Cheng, C.-Y., Jayaraman, P. K., and Furukawa, Y.  Skexgen: Autoregressive generation of cad construction sequences with disentangled codebooks.  In _International Conference on Machine Learning_ , pp. 24698–24724. PMLR, 2022.
  * Yares (2013) Yares, E.  The failed promise of parametric cad, 2013.  Accessed: November 5, 2022.
  * Yu et al. (2022) Yu, F., Chen, Z., Li, M., Sanghi, A., Shayani, H., Mahdavi-Amiri, A., and Zhang, H.  Capri-net: Learning compact cad shapes with adaptive primitive assembly.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 11768–11778, 2022.
  * Yu et al. (2023) Yu, F., Chen, Q., Tanveer, M., Amiri, A. M., and Zhang, H.  Dualcsg: Learning dual csg trees for general and compact cad modeling.  _arXiv preprint arXiv:2301.11497_ , 2023.

##  Appendix A Human Evaluation Details

The perceived quality of our generation results was assessed using a “two-
alternative forced choice” task, in which crowd workers from the Amazon
Mechanical Turk workforce were asked to choose whether a generated model was
more “realistic” than a random model from training data. To assist the crowd
workers, we provide examples of six high quality models from the DeepCAD
training data and ten examples of bad quality generations. The example images
are shown in Figure 13. The high quality models are chosen to include
desirable properties like symmetry, complexity and a coherent design, while
the low quality examples include models which are very simple, not watertight
or incoherent jumbles of extrusions. The evaluation was conduced on 950 image
pairs for each generative method, with 7 crowd workers rating each pair,
resulting in a total of 19,950 human annotations.

|  |  |  |  |
---|---|---|---|---|---
Realistic models

|  |  |  |
---|---|---|---|---
|  |  |  |
Unrealistic models

Figure 13: Images shown to crowd workers of realistic and unrealistic models.

##  Appendix B Additional CAD Results

Figure 10 only shows the partial input and the final autocompleted CAD model.
Here, we provide more examples in Figure 14 with detailed steps of the sketch-
and-extrude from left to right. For every partial input, we show two
generation of sketch-and-extrude CAD construction sequences due to the
prediction of different code tree. Figure 15 and Figure 16 provide additional
randomly generated CAD models from our method.

Figure 14: Autocompleted CAD models from partial user input. The order of
sketch-and-extrude is from left to right. User provided extruded profiles are
colored in orange. We show two different autocompletion results from the same
input. In the second example, user input consists of multiple extruded
profiles at different steps of the construction sequence.

##  Appendix C Sketch Generation Results

This section provides additional 2D sketch generation results conditioned on
loop and profile codes. For random generation evaluation, we report the
Fréchet inception distance (FID) score (Heusel et al., 2017) which computes
the difference in mean and covariance for real and generated 2D data in a
network feature space. Following SkexGen, we use ResNet-18 (He et al., 2016)
pre-trained on human sketch classification (Eitz et al., 2012) for extracting
the features to compute the FID.

Quantitative numbers for our random sketch generation are reported in Table 2.
Compared to DeepCAD and SkexGen, our model achieves a similar FID score as
SkexGen but has slightly better Novel score. Qualitative result in Figure 17
contains samples of randomly generated sketches from our method.
Qualitatively, sketches from our method have complex shapes with few self-
intersections or broken curves.

We provide additional sketch autocompletion results in Figure 18. We also
trained our model to autocomplete the full sketch from partial curves, which
is a more general case for user interaction.

Table 2: Quantitative metrics for unconditional sketch generation with models trained on sketches from the DeepCAD dataset. Method |  FID ($\downarrow$) |  Unique (%,$\uparrow$) |  Novel (%,$\uparrow$)
---|---|---|---
DeepCAD | 75.47 | 98.79 | 97.45
SkexGen | 18.56 | 96.02 | 83.54
Ours | 18.14 | 97.11 | 85.62

##  Appendix D Additional Code and Data Mapping

Qualitative results from Figure 19 and Figure 20 contain more visualization of
profile and loop data encoded to the same code. We see that data assigned to
the same code also have similar design patterns, such as the circular layout
around a center or the shape geometry approximating an ’X’ shape. Those
patterns ignore instance-specific details like the number of the bounding
boxes, the number of curves, and the type of the curves.

Figure 15: Randomly generated CAD models from our method. Figure 16: Randomly
generated CAD models with three or more sketch-extrude steps from our method.
Figure 17: Randomly generated sketches from our method.  Figure 18: Left:
Autocompleted sketches (column 2 $\sim$ 4) from partial loops (column 1).
Right: Autocompleted sketches (column 6 $\sim$ 8) from partial curves (column
5). Figure 19: Profile data at each row are mapped to the same code. Figure
20: Loop data at each row are mapped to the same code.