Compositional Diffusion-Based Continuous Constraint Solvers
Authors: Zhutian Yang
Jiayuan Mao
Yilun Du
Jiajun Wu
Joshua B. Tenenbaum
Tomás Lozano-Pérez
Leslie Pack Kaelbling
Venue: CoRL 2023 Poster (2023)
Keywords: Diffusion Models
Constraint Satisfaction Problems
Task and Motion Planning

Abstract: This paper introduces an approach for learning to solve continuous constraint satisfaction problems (CCSP) in robotic reasoning and planning. Previous methods primarily rely on hand-engineering or learning generators for specific constraint types and then rejecting the value assignments when other constraints are violated. By contrast, our model, the compositional diffusion continuous constraint solver (Diffusion-CCSP) derives global solutions to CCSPs by representing them as factor graphs and combining the energies of diffusion models trained to sample for individual constraint types. Diffusion-CCSP exhibits strong generalization to novel combinations of known constraints, and it can be integrated into a task and motion planner to devise long-horizon plans that include actions with both discrete and continuous parameters.

Compositional Diffusion-Based Continuous Constraint Solvers
Zhutian Yang',
Jiayuan Mao! Yilun Du'
Jiajun Wu
Joshua B. Tenenbaum
Tomás Lozano-Pérez' Leslie Pack Kaelbling'
Masssachusetts Institute of Technology, "Stanford University
Abstract:
This paper introduces an approach for learning solve continuous con- straint satisfaction problems (CCSP) robotic reasoning and planning, Previous methods primarily rely on hand-engineering learning generators for specific constraint types and then rejecting the value assignments when other constraints are violated. By contrast, our model, the compositional diffiusion continuous constraint solver (Diffusion-CCs) as factor graphs and combining the energies of diffusion models trained to sample for individual constraint types. Diffusion-CCSPP exhibits strong generalization novel combinations of known constraints, and can be integrated into task and motion planner devise long-horizon plans that include actions with both discrete and continuous parameters. Project site: https:/ddiffusion-cssy cos.iiinnccsss.gggbiii.....
derives global solutions to CCSPs by representing them
Keywords: Diffusion Models, Constraint Satisfaction Problems, Task and Motion Planning
Introduction
Robotic manipulation planning relies critically on the ability to select continuous values, such as grasps and object placements, that satisfy complex geometric and physical constraints, such stability and lack of collision. Existing approaches have used separale samplers, obtained through learning or optimization, for each constraint type. For instance, GraspNet [1] focuses on generating valid grasps, and StructFormer [2] specializes in generating semantically meaningful object placements. However, complex problems require general-purpose solver produce values that conform to multiple constraints simultaneously. Consider the task of 3D object packing with robot arm, as depicted in Figure 1. Given the geometric and physical properties of the objects, our objective is to generate the target pose and motion trajectories that fulfill three essential criteria. First, all objects must be contained within the container and satisfy qualitative user requirements (e.g., bowls should be placed next to each other). Second, collisions among objects and the robot, during their movement and when stationary, must be avoided, Finally, the final configuration should be physically stable.
Constructing training monolithic model capable of solving every possible combination of goals and constraints can be challenging due to limited data. Therefore, it is essential for general-purpose robot planners to reuse and to compose individual solvers for overall tasks. A common strategy is to combine specialized methods for solving individual problems in a sequential manner via rejection sampling, which is widely used by state-of-the-ar planners for object rearrangement and general task and motion planning (TAMP) problems [3, 4, 5, 6, 7]. The of solvers is applied in a predetermined order guided by heuristies (e.g., first sampling object poses and then grasps and trajectories). If previously sampled value violates later constraint (e.g., the sampled pose in the box does not leave enough space for the gripper during object placement), backtracking is performed. This rejection- sampling-basee based approach can be highly inefficient when faced with many constraints. An alternative approach is to formulate the entire constraint satisfaction problem using differentiable objective function and solve it using local optimization methods [8, 9]. However, these methods usually require manually manually-specified differentiable constraint formulas, but many important constraints, such as those corresponding to human directives like 'next to', need to be learned from data.
7th Conference Robot Learning (CoRL. 2023), Atlanta, USA.

---

(4) The dispenser is constrained be grusp- od only from sides.
(b) The gripper pose when grasping the bowl should be reachable.
(c) The gripper grasp poses shouldn't 't collide with other objects.
(d) All arm trajectories shouldn's collide with the object the tray.
(e) The two bowls are constrained next each other.
Figure I: Solving Continuous Constraint Satisfaction Problems by Composing Diffusion Models. Our approach combines diffusion models, representing individual constraints, to generate object placement poses. The choice of an object's placement depends on both qualitative constraints about object placement and collision avoidance constraints on the object and the robot gripper.
We propose to use constraint graphs as unified framework for specifying problems as novel combinations of learned constraint types and apply diffusion- www---ooooo-ssseee con- straint solvers to find solutions that jointly satisfy the constraints. constraint graph consists of nodes representing decision variables (e.g., grasping poses, placement poses, and robot trajectories) and nodes representing constraints among these decision variables. Our method, the compositional diffusion constraint solver (Diffusion-CCSP), Iearns collection of diffusion models for individual types of constraints and recombines them to address novel problem instances, finding satisfying assignments via a diffusion process that generates diverse samples from the feasible region. In partic- ular, each diffusion model learns to generate distribution feasible solutions for one particular type of constraint (e.g., collision-free placements). Since the diffusion models are generative models of the set of solutions, at inference time we can condition on an arbitrary subset of the variables and solve for the rest. Furthermore, the diffusion process is compositional: since each diffusion model is be cast
trained minimize implicit energy function, the task of global constraint satisfaction as minimizing the global energy of solutions (in this case, simply the summation of individual energy functions). These two features introduce notable flexibility in both training and inference. Component diffusion models can be trained independently or simultaneously based on paired compositional problems and solutions. At test time, Diffusion-CCSS generalizes to novel combinations known constraint types and graphs with more variables than those seen during training.
We evaluate Diffusion-CCS. arrangement with qualitative constraints, 3D shape stacking with stability constraints, and 3D object packing with robots. Compared with baselines, our method exhibits efficient inference time and strong generalization to novel combinations of constraints and problems with more constraints.
four challenging domains: 2D triangle dense- sanse-pccking 2D shape
2
Related Work
Geometric rearrangement. A large body of work has studied geometric rearrangement of objects in robotics subject to conditions specified in natural language [10, 11, 2, 12, 13, 14] via formal speci- fication or demonstration [15, 16, 17, 18, 19, 20]. Similar to our work, StructDiffusion [14] also uses diffusion models to solve for geometric rearrangements of objects. It employs a transformer based diffusion model architecture to generate object placement poses that satisfy language-conditteg scene-level constraints, such as positioning all objects to form circle. In comparison, our work provides a framework for solving arbitrary CCSPs that involve different constraints among objects.
Compositional generative modeling. Our work relates to existing work on compositional generative modeling, where individual generative models are combined to generate joint outputs [21, 22, 23, 24, 25, 26, 27, 12], primarily in the setting of image generation. Most similar to our work. Gkanatsios al. [12] compose EBMs to represent different subgoals in compositions of object scenes. They currently only address object placements, whereas our method is generic and can combine constraints involving object poses, grasps, and robot configurations in the optimization-bait poses; this is generally more efficient than backtracking over values generated by pose-only sampler.
sampling of object

---

Box
geomi
geomlg
geomic
intA, Bux
close-totA.
cfrectA,
cfrectA, C)
Box
D
pus
pose
poseg
poséc
The arm trajectiry ma/a A's initial pose pose and the targel pose pose,, given grasp.-
pose au
valid-arui
maj
gruspa
(a) Visualization the environment while placing object A.
(b) Visualization constraint graphs associated with the object placement. There three decision variables.
Figure 2: Continuous Constraint Satisfaction Problem (CCSP) in Robot Planning. It unifies geometric, physical, and qualitative constraints. To place A into the tray, we need generate the grasping pose grasp A placement pose pose A. and the robot arm trajectory. We omit collision-free constraints with robots in (b) for brevity.
Task and motion planning (TAMP). There special-purpose 3D object packing algorithms based heuristic-search simulation [28, 29, 30] for finding object poses that satisfy collision and stability constraints. They are again not directly comparable to Diffusion-CCSSP because they cannot address the same range and combinations of constraints.
3 Compositional Diffusion Constraint Solvers
Our goal is to develop a general algorithm capable of learning and solving diverse continuous constraint satisfaction problems (CCSPs) encountered robotic manipulation tasks. To achieve this, we adopt generic graph-basee based representation of CCSPs unifying various geometric, physical, and qualitative constraints".
3.1 Formulation and Representation of Constraint Satisfaction Problems
Formally, continnous constraint satisfaction problem (CCSP) can be represented as a graph G = (V, V,,,C). Each e E V is a decision variable (such as the pose of an object), while each u E 2f is conditioning variable (such as the geometry an object, which will be constant at performance time). Each is a constraint, formally a tuple of (te, ne), where te the type of the constraint (e.g.. collision-free), and nie (V=, 2(9) contains sets of variables in V and 21 which correspond the arguments to this constraint. For example, collision-free constraint between object A and B can be represented as (cfree, (poSe pose geom geomg)). Here, pose and poseg are decision variables that represent the target pose of objects A and B, while geom, and geomg are conditioning variables that represent the geometry of objects A and B.
Let V and U be assignments of values to the decision and conditioning variables V and U, respectively, and let Ve and U be the subsets of assigned values to variables in constraint For example, in the 3D packing task shown in Figure 2a, the assignment V to variables V is mapping from the variables pose, to an SE(3) pose of object i. The solution should satisfy that for all (tc, (V=, (P,) E C. test(L.: (Ve, U?)) = 1, where fest takes the constraint type and the assignments to each variable and returns if the constraint is satisfied and O otherwise. The function test can be implemented as human-specifted rules, learned classifiers, or outcome physics simulator.
Example. Figure 2 illustrates the constraint graph associated with the pick-and-plat of bowl (A) into box close to another bowl (B), while avoiding it and other obstacles. It includes three decision variables: grasp (transform between object and hand), pose, (target pose), and traj (robot trajectory). The scenario involves three constraint groups: 1) qualitative constraints, including in(A, Box) ensuring the bowl's placement within the box and close-to(A, B) asserting proximity between two bowls; 2) collision avoidance constraints such efree(A, B), which asserts that objects
'Throughout the paper, we use the word qualitative constraint to refer to constraints that can not be easily and accurately described analytically- in particular, spatial relationships such as "left" and "close-to." These constraints depend contexts and would ideally be learned from human annotations.

---

Algorithm Training
Algorithm 2 Sampling
repeat
I: Vy 00) for = T....: do
2: V.Vo ~
3: fo Uniform((1,... T (N0.1)
3: if then 2 NN(, else
4: Take gradient descent step
4: Vi-1 vas (Vs 1-mg
E co (V,, UV,, + oz aEC
Vole Σ (vaVV + +II + rEc
vi-ax
6: until converged
5: return Vo
and B do not collide in the final placement; 3) trajectory constraints, encapsulated by valid-traj. which assert that the trajectory IrajA is feasible robot path that connects the bowl's initial position pose Ao and the target pose given graspA. is important to note that these constraints are correlated: for example, the choice of pose requires the consideration of the robot trajectory ensure the existence of valid grasping pose and trajectory.
3.2 Compositional Diffusion Models
Given a set of constraints C, decision variables V, and conditioning values U, we wish to find assignment of Vo that satisfies C. We represent the conditional distribution of variable assignments given an individual constraint using diffusion model Pa(V= = V/e U U?) x 1[rest(te, (V', [. which is effectively uniform over the (bounded) region of V that satisfies the constraint. Finding a satisfactory assignment of variables Vo then corresponds to finding an assignment that maximizes the likelihood in the joint distribution constructed from the product of the individual constraint models. Each constraint diffusion model represents p(Vo (9) in the form of energy-based model, p(V= (45) x e E(V"(() through its score [24, 26], so the probability maximization problem corresponds to the energy minimization problem:
Vo arg max V
II (V 229)) arg min Σ
E(V" 24))
CEC
We solve this energy minimization problem by using sampler based on the annealed unadjusted Langevin algorithm (ULA) [31, 26). The ULA algorithm is special case of Langevin Monte Carlo it iteratively optimizes a noisy sample using the gradient of the energy function, with added noise at each step of optimization.
During training, we optimize a noise prediction model e for each constraint type t. Each é, takes conditioning variables U and a noisy version of V as input, and predicts the noise applied on Vo, Most simply, we could train the diffusion models independently for each constraint, and combine them prediction time. In our experiments, train multiple diffusion models simultaneously: since each training example corresponds to some constraint graph, it is natural to train all the constraints that are instantiated in that graph jointly from the example. Note that the constraint graphs within the training set and between training and testing need not be the same-they just need to be constructed from the same basic set of constraint types.
Specifically, our training dataset contains set of constraint graphs, each with conditioning values and a solution the decision variables: (g (V, U, C), U, Vo). For each type of constraint, randomly initialize a denoising function éz, and sum the denoising predictions over the constraints in the graph to denoise a noisy version of Vo:
LMSE
||e
Σ CEC
ct (VarVo - are, US,
(VV.V.C....VV (.....).--Umlmmm
where is random Gaussian noise applied Vo, a are predefined noise scheduling for training and sampling following Nichol and Dhariwal [32], a₂ II Ot, is randomly sampled diffusion step, and T is the total number of diffusion steps. The full pseudocode for training and sampling from our conditional diffusion models for constraints can be found in Algorithms and 2.
3.3 Geometric and Physical Constraint Solving with Diffusion-CCSP
Given the general formulation of Diffusion-CCCC CCSP, describe its concrete implementation in robot planning setting. Recall that for each type of constraint, we have defined a "denoise" function ep

---

geom
garon
490
B
geomn
Eposen
035
MI.
geotll
geoom
posel
Epose
-130
-135
pose
fywus
PONe
(b) The denoise neural network architecture. eposeg is ignored because posel fixed in case.
(c) Learned gradient field for efree constraint.
(4) The efree construint.
Figure 3: Illustration of the denoising neural network for satisfying constraint cfree (collision-free) and the gradient map learned by Diffusion CCCSp for the centroid of B at (z, y) when at (0, 0).
that takes the conditioning values and (the noisy version of) the decision values as inputs, and predicts the noise applied on the decision values. In our robotic domains, we focus on two variable types: geometry variables and pose/transformation variables. We illustrate the neural network architecture for collision-free constraints though the construction easily generalizes to other constraint types.
Recall that the argument to collision-free free constraint has four elements: 2 (geom A x. VE (posex.posep) We use pose' to denote the value of this variable at diffusion time step t. The output of Cafree is a tuple (cpose': (pose)) which corresponds to the noise applied on pose and poség at diffusion time step I. In our implementation, an object's shape is represented as a 3D axis-aligned bounding box, and its pose is represented as a 5-dimennional feature vector composed of the 3-DoF translation and rotation 7 about + axis, encoded using sin(1) and cos(1). We use multi-layer perceptron (MLP) feom to encode the object shapes (shared across all constraints) and constraint-speecfie MIP fesee encode poses. Both geometric features and pose encoders map input representations into fixed-length vector embedding. The function Eefree is implemented as
Cen (geom
Aeeommngeomgg...... gwwng.eoooooooo.oo pose poseg) Mefree (Srom @ fgeom (geom)) 1 fpose xpose)) ① fpuse (poseg) t),
where @ denotes vector concatenation, and Jetree is another MLP model that takes the concatenated feput-feature vectors and outputs vector of length 10. The first 5 entries correspond to the prediction of epose and the rest correspond to Epose,, where is the decoding time step.
Example. Figure illustrates the neural network architecture for one specific constraint and the corresponding gradient map learned by Diffusion-CCSS In this example, our objective to generate a pose for object A that avoids collisions with object B in its current position. The neural network encodes the four input features and predicts the noise for pose and poseg- As the pose of the object B remains unchanged, the noise (gradient) predicted by <efre for its pose is disregarded. Figure 3c visualizes the gradient map for the X and Y components of pose where the gradient points approximately outward from the current location of object B. It is important to note that the gradient over the pose variable pose will have contributions from multiple constraints in the constraint graph. See the gradient fields of all qualitative constraints in Appendix F.
Planning. So far, we have presented generic solution solving constraint satisfaction problems that involve geometric and physical constraints, assuming that the constraint graph is given input to the algorithm. This approach can be directly used to solve particular tasks such as the pose prediction task in object rearrangements. Our primary motivation is to solve subproblems that arise during general robot manipulation planning. In Appendix E, we illustrate how Diffusion-CCSP can be integrated with a search algorithm to solve general task and motion planning (TAMP) problems, where the constraint graphs are automatically constructed based on the sequence of actions that has been applied and the goal specification of the task.
4 Experiments
We evaluate Diffusion-CCS) through CCSP tasks incorporating geometric, physical, and qualitative constraints. We include all environmental details and sample complexity discussions in Appendix A. For implementation and training details and additional discussions model training and inference, Appendix B. For analysis of Diffusion-CCSP failure cases in each task, see Appendix C.
5

---

leff-ie
avayy
from top-oe
eyree
close-tt
awagy
from center-in
b-aligned
u-glined
(4) 2D Triangle Packing.
(b) 2D Shape Arrangement with Qualitative Constraints
(e) 3D Object Stacking with Stability Constraints.
(d) 3D Object Packing with Robots.
Figure 4: Illustration four domains. (a) Triangle packing. (b) Dense 2D packing with qualitative constraints. The figure shows a subset of 45 constraints of 13 types. (c) 3D object stacking. The arrww show the support relationships. (d) 3D object packing with a panda robot.
We compare our full model to model variant, sequential -saplling baseline, and StructDiffusion [14]. Diffusion-CCCS diffusion process to sample from composed diffusion models [24]. This method is faster at sampling than ULA, but is generally found to have worse generalization performance. We include detailed comparison between these two in Appendix D. Sequential Sampling: We sequentially sample each generic sampler (e-g., for 2D poses, we randomly sample location
Reverse Sampling: In this variant, we directly use the standard reverse
decision variable according that is within the tray and a random rotation) and check all geometric constraints (e.g., and cfree associated with the decision variable. For each variable, when successful samples can be produced within 50 samples. StructDiffusion: StructDiffusion is a transformer-basee diffusion model for predicting object placement poses based on object shapes and a single scene-level constraint. It takes a set of object shape representations, the noisy sample of their poses, and the diffusion time step, and predicts the noise on object poses. Since it can only handle a single global constraint, it is only applicable two of our tasks (Section 4. and Section 4.4).
sample 50 samples, and report failure
4.1
2D Triangle Packing
The first domain considers packing a set of random triangles into square tray, ensuring no overlap. Triangles can be rotated, and their shapes are encoded by their vertex coordinates in their zero poses. The model's output includes 2D translation vector and ID rotation. Training data consists of 30,000 solutions to problems with 2-4 triangles, and testing includes 100 problems with 2-5 triangles. We generate training solutions by randomly splitting the tray.
Fig. 5a shows the result, and Fig. shows a concrete testing problem and its solution found by Diffusion-CCSSI When the number triangles becomes large, becomes increasingly difficult for the drrection-sappligg baseline to succeed. The transformer architecture used in StruetDiffusion successfully models the relational structure among all pairs of objects. Therefore, it performs similarly to our method and has better generalization to out-of-distribuian CCSPs in this task.
4.2 2D Shape Arrangement with Qualitative Constraints
This domain involves packing rectangles into a 2D box, satisfying geometric and qualitative constraints resembling scenarios such as dining table settings and office desk arrangements. Qualitative constraints include center-in(A, Box), left-in(A, Box), left-o(A,, B), close-to A, B), vertically-aligneedAA B), etc., along with the geometric ones such as containment (in) and collision- free (efree). Different problem instances have different box sizes and constraints. The training dataset consists of 30,000 problems and solutions with 2 to 4 objects, while the testing set contains 100 problems with to 5 objects. Training examples are generated by randomly splitting the tray.
Fig. 5b shows the result, and Fig. 4b shows a concrete test problem that involves six objects and 45 constraints (including qualitative constraints shown in the figure and geometric constraints such in and cfree). The task is very challenging when the number of objects and the number of constraints becomes large. Therefore, the baseline rejection sampling method barely solves any problem instances with 6 objects. Diffusion-CCSP significantly outperforms the baselines. We also

---

(a) 2D Triangle Packing
DSCCSP (ULA)
DICCSP (Reverse)
SincDDifission
Sequenilal Sampling
Objjetts
Objects
Objects
Objects (OOD)
oat oohee
100
100
100
100
50
40
20
20
20
20
2
3
6
9
10
4
5
8
10
3
4
6
7
9
10
2
5
8
9
10
Number of somples
Namber samples
Number of semples
Number of samples
(b) 2D Shape Arrangement with Qualitative Constraints
AeTC sohve
1000
Objjett
100
Object
150
4 OBJjects
100
Objects (OOD)
60
60
40
40
40
20
Number samples
Namber samples
Number samples
samples
(c) 3D Object Stacking with Stability Constraints
100)
OOjjets
100
Objeets
100
7 Objject
1100
Objectt (OOD)
50
40
40
40
30
20
20
Number
Number
Number
Number
(d) 3D Object Packing with Robot Trajectory Constraints
Pa sohedd
(04)
Objjcts
100
Objerts
120
Objjects
100
Objjctts (OOD)
501
20
20
20
20
2
5
6
9 10
4
5
8
10
3
6
9
10
2
5
6
8
Number of samples
Number samples
Number of samplle
Number of samples
Figure 5: Quantitative Comparisons of Constraint Solvers. Accumulated number of problems solved in 10 runs of different models. OOD=Out of training distribution. The shaded area indicates the standard deviation of various models across five different seeds. The sequential sampling baseline completely failed for task (c) and hard tasks in (b) and (d). Our full model performs better than a variant without ULA sampling and better than StructDiffusion in more complex problems (d).
cfree
Seft-in
v-aligned
10)
03
25 00
10
105
-0.
-10
Figure 6: Visualization of learned energy functions of selected geometric and qualitative constraints.
visualized the learned energy landscape for a few constraints in Fig. 6 learned by our model, and more visualizations in Appendix F.
4.3 3D Object Stacking with Stability Constraints
The third domain considers arranging trapezoidal prisms onto a shelf to satisfy given support structure and stability. The goal is to generate sequence of object placement actions (including object names and their target poses). This reflects real-life tasks such as organizing storage containers, which often involve tilted boxes due to varying prism heights. All of our training and testing problems involve at least one "bridge-like" structure, i.e., there is at least one object supported by multiple objects simultancously. Furthermore, since the output of models is a sequence of object placements, a sequence successful only if the final stage and all intermediate states are physically stable. We randomly sample the sizes of the shelf region and the shapes. We use a physical simulator to generate training examples. The training dataset has 24,000 problem instances and solutions with 5 to 7 objects, and the testing set includes 100 problem instances with 4 to 7 objects.
7

---

Objects
N=4 N=5
Objects
N=2 N=3
N=4
N
N=6
# of Calls to Diflusion-CCSP 11.9 33.33
# of Calls to Diffusion-CCSP 1.33
1.97
2.96
4.37 7.26
(b) Task 3: 3D Object Packing with Robots. Table I: Average number of calls to Diffusion-CCSP in order to solve the full TAMP problem.
(a) 3D Object Stacking.
An example of the task is illustrated in Fig. 4c. Given that neither our algorithm nor the baselines specifically plan for object placement orders, we integrate them into a very simple task and motion planner, as detailed in Appendix E. This planner randomly samples object placement orders and box "support" structures (i.e., the arrangement of objects supporting other objects), then invokes the Diffusion-CCSP solver to find solutions. We assess two metries: first, the performance of Diffusion- CCSP with a fixed CCSP graph, illustrated in Fig. 5c; second, the number of calls to Diffusion-CCSS required to solve problems involving varying quantities of objects, as shown in Table la. For instance, packing boxes into a cabinet necessitates, on average, 25 different object placement and support structure samples. If CCSP is not solvable by Diffusion-CCSP, it might truly be infeasible due to incorrect sampled placement orders or support structures. Therefore, Table la shows the integrated system's 's overall performance. Notably, given that we can process multiple CCSPs and that generating object orders is inexpensive, the system does not have high latency overall. In batch of 100 CCSPs, it takes average 0.01-0.04 seconds for Diffusion- CCCS (Reverse) solve each CCSP, and 0.06-0.19 seconds for Diffusion-CCSPP (ULA).
GPU batch
4.4 Task 4: 3D Object Packing with Robot Trajectory Constraints
This domain involves packing 3D objects into box container in simulated environment using PyBullet, with Franka Emika Panda arm. The dataset includes 53 objects from the PartNet Mobility dataset and ShapeNet [33, 34], 15 of which only afford side grasps, while others can be grasped from the top. We pre-generate set of grasps for each object, and use motion planner to find robot trajectories. The task and motion planner and Diffusion-CCSP jointly solve for grasping choices, object poses, and arm motions. Although our model doesn't directly generate grasps or trajectories, reasons about object geometries and has learned to predict poses which is likely that there are collision-free trajectories (which is later verified with motion planner.) The training dataset has 10,000 problem instances and solutions with 3 to objects, and the testing set includes 100 problem instances with 3 to 6 objects. Eerfusion-CCSP successfully finds solutions to 60-80 percent of the problems in just 10 samples for the most challenging 6 6-triangle packing problems.
Fig. 5d illustrates the number of samples needed for tasks involving a different number of objects. Overall, Diffusion-CCSP significantly outperforms the rejection-sampeee -aasedii----eeddd based solver and Struct- Diffusion, especially for larger numbers of objects. Diffusion-CCSP can even generalize directly to six-object packing problems without additional training. Table 1b showcases the full pipeline's 's performance, which includes generating placement orders, grasps, poses, and trajectories.
Limitation and Conclusion
Limitations. All constraints we have explored in this paper have fixed arity (i.e., they involve a fixed number of objects). An interesting direction is to consider variable-arity constraints. Another future improvement to incorporate more sophisticated shape encoders and learning constraints from real-world data, such as online images, for wider range of applications.
Conclusion. In conclusion, this paper proposes a learning- based approach that leverages the com- positionality of continuous constraint satisfaction problems (CCSP) and uses diffusion models as compositional constraint solvers. The proposed algorithm, namely the compositional diffusion constraint solver (Diffusion-CCSPP), consists of modular diffusion models for different types of constraints. By conditioning these models on subsets of variables, solutions can generated for the entire CCSP. The model exhibits strong generalization capabilities and can handle novel combinations of known constraints, even with more objects and constraints than encountered during training. It can also be integrated with search algorithms to solve general task and motion planning problems.
8

---

Acknowledgements. This work is in part supported by NSF grant 2214177, AFOSR grant FA9550-22- 1-0249, FA9550-23-1-0127,, ONR MURI grant N00014-22-1-2740, ARO grant W911NF-23-1-0MM
the MIT-IBM Watson AI Lab, the MIT Quest for Intelligence, the Boston Dynamics Artificial Intelligence Institute, the Center for Brain, Minds, and Machines (CBMM, funded by NSF STC award CCF-12312166 the Stanford Institute for Human-Centered Artificial Intelligence (HAI), and Analog Devices, JPMC, and Salesforce. Any opinions, findings, and conclusions recommendations expressed in this material are those of the authors and do not necessarily reflect the views of our sponsors.
References
[1] A. Mousavian, C. Eppner, and D. Fox. 6-DOF GraspNet: Variational Grasp Generation for Object Manipulation. ICCV, 2019.
[2] W. Liu, C. Paxton, T. Hermans, and D. Fox. StruetFormer: Learning Spatial Structure for Language-Guide Guided Semantic Rearrangement of Novel Objects. In ICRA, 2022. 1,
[3] L. P. Kaelbling and T. Lozano-Pérez. Hierarchical Task and Motion Planning in the Now. In ICRA, 2011.
[4] C. R. Garrett, T. Lozano-Pérez, and L. P. Kaelbling. PDDL-trream: Integrating Symbolic Planners and Blackbox Samplers via Optimistic Adaptive Planning, In ICAPS, 2020. 1,
[5] J. Mao, T. Lozano-Pérez, J. B. Tenenbaum, and L.. Kaelbling. PDSketch: Integrated Domain Programming, Learning, and Planning. In NeurIPS, 2022.
[6] C. Paxton, C. Xie, T. Hermans, and D. Fox. Predicting Stable Configurations for Semantic Placement of Novel Objects. In CoRL, 2022.
[7] Z. Yang, C. R. Garrett, T. Lozeno-Pérez, L. Kaclbling, and D. Fox. Sequence- Feasibility Prediction for Efficient Task and Motion Planning. RSS, 2023.
Sequence-Based Based Plan
[8] M. Toussaint. Legic-Ge Programming: An Optimization-Bassed Approach to Combined Task and Motion Planning. In IJCAI, 2015.
[9] T. Pang, H. Suh, I.. Yang, and R. Tedrake. Global Planning for Contact-Rich Manipulation via Local Smoothing of Quasi-dynamic Contact Models. arXiv:2206. 10787, 2022.
[10] M. Shridhar, L. Manuelli, and D. Fox. CLIPort: What and Where Pathways for Robotic Manipulation. In CoRL, 2021. 2
[11] C. Lynch, M. Khansari, T. Xiao, V. Kumar, J. Tompson, S. Levine, and P. Sermanet. Learning Latent Plans from Play. In CoRL, 2020. 2
[12] N. Gkanatsios, A. Jain, Z. Xian, Y. Zhang, C. Atkeson, and K. Fragkiadaki. Energy-based Models as Zero-Shot Planners for Compositional Scene Rearrangement. In RSS, 2023. 2
[13] O. Mees, I. Hermann, and W. Burgard. What Matters in Language Conditioned Robotic
Imitation Learning over Unstructured Data. RA-L, 2022. 2
[14] W. Liu, Du. Hermans, Chernova, and C. Paxton. StructDiffusion: Language-Guided Creation of Physically- Valid Structures using Unseen Objects. In RSS, 2023. 2, 6, 12
[15] A. Simeonov, Du, B. Kim, F. R. Hogan, Tenenbaum, Agrawal, and A. Rodriguez. A
Long Horizon Planning Framework for Manipulating Rigid Pointcloud Objects. In CoRL, 2020.
2
[16] A. Curtis, X. Fang, L. Kaelbling, T. Lozano-Pérez, and C. R. Garrett. Long-Horizon Manipulation of Unknown Objects via Task and Motion Planning with Estimated Affordances. In ICRA, 2022. 2

---

[17] C. Paxton, C. Xie, T. Hermans, and D. Fox. Predicting Stable Configurations for Semantic Placement of Novel Objects. In CoRL., 2021. 2
[18] W. Yuan, C. Paxton, Desingh, and D. Fox. SORNet: Spatial Object-Centric Representations for Sequential Manipulation. In CoRL, 2021.
[19] A. Bobu, C. Paxton, W. Yang, B. Sundaralingam, Y.W. Chao, M. Cakmak, and D. Fox. Learning Perceptual Concepts by Bootstrapping from Human Queries. RA-L, 2022. 2
[20] A. Simeonov, Y. Du, L. Yen-Chen, A. Rodriguez, L. Kaelbling, T. Lozano-Pérez, and Agrawal. Squii--qui Relational Rearrangement with Neural Deseriptor Fields. In CoRL. 2022. 2
[21] Y. Du, S. Li, and I. Mordatch. Compositional Visual Generation with Energy Based Models. In NeurIPS, 2020. 2
[22] N. Liu, Li, Y. Du, J. Tenenbaum, and A. Torralba. Learning to Compose Visual Relations. In NeurlPS, 2021. 2
[23] W. Nie, A. Vahdat, and A. Anandkumar. Controllable and Compositional Generation with Latent-Space Energy-Based Models. In NeurlPS, 2021. 2
[24] N. Liu, Li, Du, Torralba, and B. Tenenbaum. Compositional Visual Generation with Composable Diffusion Models. In ECCV, 2022. 2, 4, 6, 15
[25] J. Urain, A. Li, P. Liu, C. D'Eramo, and J. Peters. Composable Energy Policies for Reactive Motion Generation and Reinforcement Learning. In RSS, 2021. 2
[26] Y. Du, C. Durkan, R. Strudel, J. B. Tenenbaum, Dieleman, R. Fergus, J. Sohl-Dickstein, A. Doucet, and W. Grathwohl. Reduce, Reuse, Recycle: Compositional Generation with Energy-Based Diffusion Models and MCMC. In ICML, 2023. 2,4
[27] T. Wu, M. Tjandrasuwita, Z. Wu, X. Yang, K. Liu, R. Sosic, and J. Leskovee. ZeroC: A Neuro-Symbolle Model for Zero-shot Concept Recognition and Acquisition at Inference Time. In NeurlPS, 2022. 2
[28] Egeblad, B. Niclsen, and A. Odgaard. Fast Neighborhood Search for Two- and Three- Dimensional Nesting Problems. European Journal of Operational Research, 183(3):1249-1266) 2007.
[29] X. Liu, J.-m Liu, A.-x. Cao, and Z.-I. Yao. HAPE3D-a new constructive algorithm for the 3D irregular packing problem. Frontiers of Information Technology Electronic Engineering, 16 (5):380-390. 2015.
[30] F. Wang and K. Hauser. Stable Bin Packing Of Non-Convex 3D Objects With A Robot Manipulator. In ICRA, 2019. 3
[31] G. O. Roberts and R. L. Tweedie. Exponential Convergence of Langevin Distributions and Their Discrete Approximations. Bernoulli, pages 341-363, 1996.
[32] A. Q. Nichol and Dhariwal. Improved Denoising Diffusion Probabilistic Models. In ICML,
2021.
[33] A. X. Chang. T. Funkhouser, L. Guibas, P. Hanrahan, Q. Huang, Z. Li, S. Savarese, M. Savva,
S. Song, H. Su, et al. ShapeNet: An Information- Rich 3D Model Repository. arXiv:1512.03012. 2015.
[34] F. Xiang, Y. Qin, K. Mo, Y. Xia, H. Zhu, F. Liu, M. Liu. H. Jiang, Y. Yuan, H. Wang, al. SAPIEN: A SimulAted Part-based Interactive ENvironment. In CVPR, 2020. 8
10

---

[35] J. Urain, N. Funk, G. Chalvatzaki, and J. Peters. Difuusiiffsssnfiillld Learning Cost Functions for Joint Grasp and Motion Optimization Through Diffusion. In ICRA, 2023. 15
[36] C. R. Garrett, R. Chitnis, R. Holladay, B. Kim, T. Silver, L.. P. Kaelbling, and T. Lozano-Pérez. Integrated Task And Motion Planning. Annual Review Of Control, Robotics, And Autonomous Systems,
2021. 21
[37] N. T. Dantam, Z. K. Kingston, Chaudhuri, and L. E. Kavraki. An Incremental Constraint- Based Framework for Task and Motion Planning. I/RR, 37(10): 134-1151, 2018. 21

---

Supplementary Material for Compositional Diffusion-Based Continuous Constraint Solvers
Appendix A describes how our datasets are collected for each task and how the inputs are encoded for diffusion models. We also provided discussions on sample efficiency of Diffusion-CCSP on the tasks studied. Appendix B details syper-parameter choices of our models, implementation details of StructDiffusion baseline [14], as well as training details for both. We have also included additional discussions on model training and fine-tuning, constraint weights, local optima in optimization, and partial observability. Appendix C discusses common failure cases in solutions generated by out Diffusion-CCSP. Appendix D includes detailed experiment the number of samples it takes for Diffusion-CCSSP to solve CCSP problems in each task. Appendix E discusses how to integrate Diffusion-CCSSP for CCSP solving with task and motion planning (TAMP) algorithms. Appendix F shows the learned energy landscapes for qualitative constraints in 2D shape arrangement tasks.
A Problem Domains and Data Generation
In all datasets, the number the examples involving different number of objects are the same.
A.1 2D Triangle Packing
Figure 7: Example collision-fres free configurations of triangles
Data. The data is generated by randomly sampling points in the square and, connecting them with each other and the edge points using the Bowyer-Watson Watson algorithm, then shrinking each triangle little make space among them.
Encoding, We define the resting pose of a triangle as the pose when the vertex A facing the shortest side BC at origin and its longest side AB aligned along + axis. Its geometry is encoded using three numbers, the length |AB) and the vector (x, 3) = AC. Its pose is encoded as the 2D coordinates of vertex A, along with the sin and cos values of the rotation from the testing pose.
A.2 2D Shape Arrangement with Qualitative Constraints
Figure 8: Example rearrangements of rectangles with 11 types of qualitative constraints.
Data. The data is generated by recursively splitting the tray different proportions until depth 3. For each resulting region, random padding added to each side. Regions whose side is too small
12

---

are discarded. Labels of qualitative constraints are created by hund-crafted rules, e.g. 'close-to' means the distance between two objects is smaller than the maximum width of two objects. All qualita- tive constraints include 'center-in', 'left-in', 'right-in', 'top-in', 'bottom-in', 'left-of', 'top-of', 'close-to', 'away-from', 'h-aligned', and 'v-aligned'.
Encoding. The resting pose of rectangle is when its longer side is oriented horizontally. Its geometry is encoded using its width and length at resting pose. Its pose is the 2D pose of the centroid, along with the sin and cos encoding of the object's yow rotation. Many problems require some objects to be at vertical positions in order for all the constraints to be satisfied.
A.3 3D Object Stacking with Stability Constraints
Figure 9: Example stable configurations of rectangles, with in, cfree, and supported-be straints. There is at least one object that's supported by multiple objects.
Data. The data is generated by randomly splitting a 2D vertical region, then shrinking and cutting each region. The resulting cuboids are initiated in PyBullet simulator and letting them drop until rest. We filter for configurations where the final state stable. Then all objects are removed one by one test that each intermediate configuration is also stable. An upper shelf is added to be just enough to fit the current configuration with little overhead space.
Encoding, The resting pose of a cuboid is when its longer side is oriented horizontally. The cuboid's geometry is encoded using its width and length. The cuboid's pose the 2D pose of the centroid, along with the sin and cos encoding of the cuboid's roll rotation.
A.4 3D Robot Packing with Robots
Figure 10: Example configuration of 3D shapes that enables the robot place each object in given sequence without colliding into other objects already placed. All the bottles, dispensers, and bowls affords only side grasps.
13

---

Data. The 10 categories of objects used in this dataset include 'Dispenser', 'Bowl', 'StaplerFlat', 'Eyeglasses', 'Pliers', 'Scissors', 'Camera', 'Bottle', 'BottleDpened', and 'Mug', contributing total 53 object assets. For each asset, a fixed number of grasps are generated beforehand that points directly to one of its five faces, e.g. +2. The problems are generated by randomly splitting the tray into rectangle regions, then fitting into each region object with random category, asset, and scale. An order to place the objects is sampled, then TAMP planner is called to check whether the corresponding grasps can be found (by enumerating all combinations of order and grasps) so that the gripper at each grasp pose won't I collide with any objects already in the goal region and all arm trajectories going to the grasp configurations can be found.
+2, -2. 1y..y.++ +.
Encoding. The objects' geometry is encoded using bounding box (e.g., width, length, height). An object's grasp is encoded using five-dimensional vector, indicating the face that the gripper points to. For example, [0, O, 0, 0, is top grasp. The object's pose is encoded using its 3D coordinate in the tray frame, along with the sin and cos encoding of the object's you rotation.
A.5 Discussion: Sample Complexity of Diffusion-CCSP
Our training datasets are the scale of 10k-30k for each task. It is always important to be aware of the amount of training data needed and the cost of obtaining it from various sources. We observed that we can train the models in simulation with abundant data and believe they can be applied to real-world robotic tasks. In our system, we learn two categories of constraints. First, geometric and physical constraints are independent both of the robot (and hence of perceptual and motor noise and irregularities that cause most tn-to--eal difficulties) and of any human input. Learning to check that object placements are collision free, or that robot configurations are kinematically feasible can be done entirely via data obtained in simulation and transfer without diffficulty the real world. Second, qualitative constraints corresponding to human input must be obtained from human annotation. Such annotations are costly obtain and, as matter of future work, we would like to leverage additional data sources, such as object relationship information in large vision/language models.
A.6 Discussion: Partial Observability
Across all experiments in the paper, we have been assuming fully-observed setting where we know object shapes (in particular, their bounding boxes) and their initial 3D poses. We think one possible way to handle at least some types of partial observability in our setting is through replanning. Taking object packing as a concrete example, given the segmented (partial) point clouds for objects, we use learning or heuristic methods to complete the object mesh and then run our solver compute plans. During execution, assuming we can sense object collisions while moving them, we can always replan for different placement in closed-loop manner.
B Implementation and Training Details
We used 1000 diffusion timesteps for all models, except for Diffusion-CCSP on Task 4 robot packing, which used 500 diffusion timesteps. In neural network input encoding, all object dimensions and poses are normalized with regard to that of the container or shelf region.
Diffusion- CCSp:: Given the geometry, pose, and grasp features, encoders to process them to the same hidden dimension of 256, which is the same dimension as time embedding. The outputs from individual diffusion models have the same dimension as input pose embedding. The output for each object's 's pose are composed by taking the average of all outputs of diffusion models that have the object as an argument. They are processed through pose decoder to get the output reconstructed noise value added to the poses. The encoders, pose decoder, and diffusion models are trained together using the L2 loss between reconstructed noise value and input noise value, as detailed in Section 3.2. For our ULA variant, we used sampling steps of 10 and step sizes of 2t((t) where 3 is cosine beta schedule for the diffusion model.
geometry, pose, and grasp
14

---

The objects are sampled in sequence inside the container (collision-fre) with the container guaranteed). For each object, its pose is sampled uniformly at random at most 50 times to find a placement that's collision-free to all objects already placed.
Rejjetion-Sampling:
StructDiffusion: We implemented the architecture of concatenating the geometry and pose embed- dings for each object one token (dimension 512 for each token) to the transformer encoder, plus positional encoding and time encoding. For task 4, we also concatenated the chosen grasp embedding to the object embedding (total dimension 768 for each token). We used four layers of residual attention blocks and two heads. We added normalization layers before and after the transformer layers. We used the same diffusion timesteps as our Diffusion- CCSP models. Because there is no language imput, we omitted the word embeddings from the architecture.
B.1 Discussion: Individual Constraint Diffusion Training and Finetuning
Our diffusion models for individual constraints can be trained either jointly independently: however they trained, they can be applied in novel combinations performance time. In experiments, we concurrently train all constraints since our data naturally encompasses multiple constraints in single scene, such as object collision-free constraints in a bin packing problem. It is also possible to finetune a pretrained constraint solver with new data. In some scenarios such as generalization to unseen object shapes this might very helpful.
B.2 Discussion: Weights for Energy Function Composition
In general, selecting appropriate weights for different constraints is important and challenging, which has been observed in Urain al. [35] and Liu et al. [24]. In our experiments, consistently use weight 1 for all constraints, and this setting has proven effective in our tasks. We postulate two reasons for this. First, visualizations of the learned energy functions (see Appendix F) indicate that the energy field is steep. The areas in the configuration space that meet the constraints exhibit considerably lower energy than areas that don't. As such, when constraints are combined, the solver tends to prioritize solutions that satisfy all constraints. Second, during training, our models are jointly trained explain data with various combined constraints. This implicitly forces the diffusion models to learn score functions that support combinations.
B.3 Discussion: Local Optima in Optimization
Bad local optima can be an issue for multi-constraint optimization problems. In this paper, partially address this problem by running multiple seeds in parallel. That is, given a CCSP problem, we run the reverse diffusion process with multiple randomly sampled initial noise values. For instance, in the 3D object stacking task, on average, 33.3 samples are needed for solving tasks involving objects. This does not significantly affect our runtime because different random seeds can be run in parallel. In two cases shown in the table (object packing and stable stacking), we have used the physical simulator to check solution validity-whethee objects are in collision-free poses and whether the system is physically stable. In other cases where solution checkers unavailable, can consider learning classifiers for conditions.
C Failure Case Analysis
Example failure cases for Task 2 involving qualitative constraints are shown in Figure 11. One insight we gained is that the failure rate to satisfy a qualitative constraint is inversely correlated with the area of its defining region. We ran a IiffussionCCSS) 4000 times to solve a test set of 400 CCSPs involving 2-4 shapes and counted the number of unsatisfied constraints in solutions generated by Diffusion-CCSS
From Figure 12a, we make two observations: (1) the failure rate is inversely correlated with the amount of data for each constraint, and (2) constraints with discontinuous regions harder to satisfy (e.g. v-aligned, close-to). Then, we look at problem with one object A (size 0.5 by 0.5) in the center of a container. We estimate the area of the detining region of each constraint
15

---

Failure Cases
The shapes collide with each other
The shapes don't satisfy all the qualitative constraints
Satisfying Solution(s)
CCSP example r (m==5, OOD)
All Constraints: [in, (. [t, 3. 4. 5]]: [(free, (. for range(i, for in range(1,6)]:
(away-from. 1, 3); (away-from, 4): (away-froom foonuy--ommmmm I, 5); (away--rom, 2, 5) haway-frome 3. 5): (away--rome 5); (left-in, o); (left-of: 3, 4); (right-in, 5, o); (top-in, 3, O); (top-in, o); (top-of. 3, 2); (top-of, 4, 2); where container
(bottom-in, 0); (h-aligned, 5, 2); (h-aligned,, 2, 5); (h-aaligned, 4, 3); (h-alligned,
solution,
solution,
solution,
solution,
solution,
Missing: (away-from, 4): (h-aligned 2, 5):
Missing:
(left-of. 3, 4);
All satisfied!
CCSP example 2 (n=55, OOD)
All Constraints: (in, for in [t, 2, 4. 5]]: [(ffree, i. for in range(t, 6) for j in range(t,6)]; (away--room, 3, (away from, 4, I); (awwyy from, 2); (awwyy from, 10: (away from, 2); (away from, 5, 4); (bottom-in. 1, O); (left-in, I, O); (left-of, of, 2); (left-of:2 3); (left-ol of, 3, (right-in, (right in, (right O); (top-in,
Missing: (away-from, 5);
Missing:
(away-from, 4
All satisfied!
Figure 11: Failure and success samples for Task 2: 2D Shape Rearrangement with Qualitative Constraints. All solutions are generated by Diffusion-CCon CCSP (ULA), trained on 30k data up to objects.
by doing rejection sampling the pose (x. of object B (size 0.5 by 0.5) that doesn't 't collide with A (except for center-in). From Figure 12b, the order is highly similar to the order in Figure 12a, supporting the hypothesis that the smaller the defining region of constraint, the harder it is to satisfy, Note that this experiment assumes two object. Therefore, although the area is large for efree in this estimate, doesn't represent the dataset where there are 5 shapes in each problem. So we exclude from further discussions.
Example failure cases for Task and are shown in Figure 13 and Figure 14.
16

---

of Falture
12500
2.5
10000
Extmated
5000
1.0
2500
0.5
tnalfgoodd cleaedo
cffer
conteeit
helignd
opeo
larbal
battagr-s
leffae
Jwayy Rom
rightiin
Fallgaed
topeat
letval
bollgnee
cloreto
contor ull
bostian
top
laft-i
right-ii
10
cffer
Qualitative Constraints
Qualtatiie Consiruiats
(a) Failure rate of qualitative constraints. The failure rate of each constraint is annotated the bars. The red bars denote the number of failures, while green bars denote success. Constraints are sorted by failure rate.
(b) Estimated area occupied by qualitative con- straints. The order is highly similar to the order in supporting the hypothesis that the smaller the defining region of constraint, harder to sat- isfy.
vallgnolA 16.11
1.0
tep-sfiA..o Oa y3
Telbvol Co.
0.75
3.75
0.75
230
-6.00
-3.00
-0.55
-079
-075
-110
-3.
-100
-35
1.5
2.55
0.0
2.30
0.00
0:5
325
025
0.00
-0.75
-0.75
-1.00
5.5
-1.0
-35
0/
1.5
-1.00
-.5
-1.6
-0.5
00
0.5
100
-1.00
-10
-35
0.9
1.5
1000
0.5
0.59
3.5
0.25
035
0.0
-6.50
-0.5
-075
-1.00
1.5
-1.0
40.5
8.0
1.0
E5
-1.00
1.5
-1.0
10.5
00
8.5
1.0
-100
1.50
away-francA.co (s.
1.00
0.75
2.7
0.50
000
-025
-025
-025
-.90
3
6.50
-0.5
10.55
-0.25
-1.0
(c) Training data distribution for each constraint, in the order of increasing of the defining region. Each point is the centroid for an object that appeared in one constraint(A, A, B) inside the training dataset.
Figure 12: Analysis of how failure rate of qualitative constraints correlates with area of its defining region.
17

---

Failure Cases
One Satisfying Solution
The shapes collide with each other
n=5 (out-of-distributtio))
solution,
satarion
sofation,
sotatton
CCSP,
CCSP,
n=6 (OOD)
CCSP
CCSP
CCSP,
Figure 13: Failure and success samples for Task 1: 2D Triangle Packing. All solutions generated by Diffusion-CCSP (ULA), trained on 30k data up to 4 objects.
18

---

Failure Cases
Satisfying Solution (s)"
The objects penetrate" into each other, resulting in objects exploding once sim is on
The stack isn't stable, resulting objects falling off when sim is on
The stack doesn't satisfy given support structure among shapes
in the Tst exumple, both solution (=O) and the final scene (sim t=600) are shown
"sigght penetration is allowed by Pybullet simulator
CCSP Example Given Support Structure; where o is the lower shelf [on, I, 0), (on, 0), (on, 3, I), (on, 3, 2). (on, 4. 3), (on, 5. 4), (on, o)]
solution,
solution,
solution,
solution,
correct
solution,
CCSP Example 2 Support Structure:
wrong structure
All correct
(on, I, 0), (on,) 3, 0), (on, 4, 0), (on, 2, I), (on, (on, 3), (on, 6, 4), 7, 6)
solution, exploded
solution, fallen off
Figure 14: Failure and success samples for Task 3: 3D Object Stacking with Stability Constraints.
All solutions are generated by Diffusion-CCSS (ULA), trained on 24k data up to objects.
19

---

D Additional Sampler Comparison
In the main experiment section, we let Diffusion- CCSP and baselines generate 10 samples for each CCSP and check if all constraints are satisfied. Here we let Diffusion-CCSPP generate 100 samples on 100 problems, and plot the number of problems it took Diffusion-CCSP to solve for each task. In a batch of 100 CCSPs, it takes on average 0.01-0.04 sec for Diffusion- (Reverse) to solve each CCSP while 0.06-0.19 see for Ciffussio-CCSS. (ULA) to solve each CCSP, as shown in Table 2.
DICCSP
DICCSP (Revise)
2 Objjects
3 Ohjjett
Objjects
5 OObject (OOB)
200
100
1000
100
40
40
00
20
20
20
Number samples
Number samples
Number somples
Number samppls
(a) Task 1: 2D Triangle Packing
DiOCSP(ULA)
DIC CSP (Rovees
200
Objjects
100
Olhjects
1000
ODbjects
100
(Ibjects (OOD)
50
50
50
20
20
20
20 40
70 Number samples
TO Number dEsamples
50
50
10 50
60 101
20
40 60
90
Number of sampls
Number of sEmamples
(b) Task 2: 2D Shape Arrangement with Qualitative Constraints
DICCSP (ULA)
DICEPP (Revew))
Objjerts
Oifjeets
Objectt
Dbjjects (OOB)
2001
1000
Pf CXSPs udovd
201
10
303
341
60
64
20
10 20 30 40 50 0
60
73
3D
90
70 50 90 0 20 20 30
40 50
30
10 20 30 40 50 60 70 1U 50
30 20 30 40 50 60 TU 8D 90
of of samples
Number of sasampies
Number of samples
Namber of samples
(c) Task 3: 3D Object Stacking with Stability Constraints
DICCSP (ULA)
DICCSP (Rev
Objjetts
Olbjects
Obbjects (OOD)
CirCCSPPaabaal
301
80
60
60
60
40
0 20 30 40 50 63
70
90
0 10 20 50
50 50 70 50 90 Number of oasapppes
10 20: 30 40
50
60 50 50
10 20 30 40 50 60 70 50 90
Number samples
Number of samplos
Number ofsamples
(d) Task 4: 3D Object Packing with Robots
Figure 15: Number of Diffusion-CCSP runs it takes solve 100 CCSPs. OOD means problems that are out of training distribution (i.e. include more objects than trained on). On the a-aaiss tick x means problems not solved within 100 samples.
E Integration with Task and Motion Planning Algorithms
So far, we have presented a generic solution to solving constraint satisfaction problems that involve geometric and physical constraints. However, assuming that the constraint graph is given input to
20

---

Objects
Objects
Objects
Objects
Diffusion- (ULA)
0.10
0.10
0.11
0.12
Diffusion-CCSP (Reverse)
0.01
0.01
0.01
0.01
StructDiffusion
0.08
0.08
0.08
0.08
(a) Task 1. Triangle Packing
Objects
Objects
Objects
Objects
Diffusion CCCSP (ULA)
0.17
0.18
0.19
0.19
Diffusion CCSP (Reverse)
0.04
0.04
0.04
0.04
(b) Task 2. 2D Shape Arrangement with Qualitative Constraints
Objects
Objects
Objects
Objects
Diffusion-CCSS (ULA)
0.15
0.16
0.17
0.19
Diffusion- CCSP (Reverse)
0.01
0.01
0.01
0.02
(c) Task 3D Object Stacking with Stability Constraints
Objects
4 Objects
Objects
Objects
Diffusion-CCC (ULA)
0.06
0.06
0.07
0.07
Diffusion CCSP (Reverse)
0.01
0.01
0.01
0.01
StructDiffusion
0.09
0.09
0.08
0.08
(d) Task Object Packing with Robots
Table 2: Average time (sec) of models in batch of 100 CCSPs.
the algorithm. This approach can be directly used to solve particular tasks such the pose prediction task in object rearrangements, Next, illustrate how the proposed method can be integrated with search algorithm to solve general task and motion planning (TAMP) problems, where the constraint graphs are automatically constructed based on the sequence of actions that has been applied and the goal specification of the task. For brevity, we will present a simplified formulation of TAMP problems, For more details, please refer to the recent survey [36].
Formally, given space S of world states, a problem the initial state (e.g., the geometry and poses of all objects), g C S is a goal specification (c.g.. as a logical expression that can be evaluated based on a state: in(A, Box) and in(B, Box)), A is set of continuously parameterized actions that the agent can execute (e.g., pick-and-place) and T is a partial environmental transition model T : S x A - S. Each action a is parameterized by two functions: precondition pre, and effect effa. The semantics this parameterization is that: vs E S.Va E A.pre, (s) = (T(s, a) eff, (s)).
tuple (S, 80; G,A,T; where 8o E S is
The goal of task and motion planning
output a sequence of actions à so that the terminal state sr induced by applying a; sequentially following T satisfies sT E G. The state space and action space are usually represented as STRIPS- like representations: the state is a collection of state variables and each action is parameterized by set of arguments. Figure 16 shows a simplified definition of the pick-and-plans place action in a table-top manipulation domain.
A characteristic feature of TAMP problems is that the decision variables (i.e., the arguments of actions) include both discrete variables (e.g., object names) and continuous variables (e.g., poses and trajectories). Therefore, one commonly used solution is to do a bi-level search [37, 4]: the algorithm first finds a plan that involves only discrete objects (called plan skeleton) and uses a subsequent CSP solver to find assignments of continuous variables, backtracking to try different high-level plan the CCSP is found to be infeasible. For example, consider the discrete task plan (also called plan skeleton): pick-and-place( ()), pick-and-place (B). There are six parameters decide: the grasps on A and B, the place locations of A and B, and the robot trajectory while transporting A and B. Based the preconditions of actions and the goal condition of the task, obtain the constraint
21

---

ii pick up x and and place x to action pick-place(x, B, P, t) pre: valid pose(xl,
is the grasp
valid-traj pose[x], 8, P. t) forall z. cfree(x, pase[x], t) eff: pose[x] :=
33 p is the target pose
the robot trajectory
13 object x will be moved
goal: in(A, pose[A], pose(c]) and in(8, C, pose[B], pose[C])
The precondition-effee definition of continuously parameterized action pick-place: pick and place object x.
Figure 16: Illustration of a simple task and motion planning problem. The domain contains only one action: pick-and-place objects. contains three preconditions: g should be a valid grasp pose on object / should be valid robot trajectory that moves from its current pose to the target pose p. and during the movement,
robot and the object e should not collide with any other objects y. successful, the object will be moved to the new location. The goal of the task is to pack both objects into the target box without any collisions.
pick- gA, pA, tA)
valid-grasp(A, pAo, gA) valid-traj(A, pAa, EA, pA, eAree(A, B, pee, tA) efree(A, pco, tA)
PAn
PBo
pick-place(B, gB, pB, tB) valid-grasp(B, pee, gB) valid-trai(B,, p8e, gB, p8, tB) ctree(B, A, pA, tB) efree(B, c, pñe, ta)
Pco
valid-g
valid-t
valid-g
valid-t
A
Aa
fA
Goal
in(A, C, PA, pca)
in
in(a, c, p8, pce)
(a) A partially specified plan skeleton and its corresponding constraints.
(b) The corresponding TAMP constraint graph derived from the plan skeleton. efree constraints and geometric features are omitted for brevity.
Figure 17:
Example of a partially specified plan skeleton in task and motion planning, together with the corresponding set of constraints. PAn- PBo- and pco corresponds the initial pose of objects.
graph. Therefore, each solution to the CCSP constructed based on the plan skeleton corresponds to a concrete plan the original planning problem. By combining the high-level search of plan skeletons and our constraint solver Diffusion-CCCC CCCS, the integrated algorithm capable of solving a wide range of task and motion planning problems that involves geometric, physical, and qualitative constraints.
F Learned Gradient Fields
We visualized the learned gradient functions for all qualitative constraints trained for Task 2 (Figure 18 column 3). The gradient functions for the first 6 constraints (from in to bottom-in) corresponds to the direction of changing the pose of a square shape of size 0.15 by 0.15 inside container of size by given different initial poses. The gradient functions for the later 7 constraints (from cfree to v-aligned Figure 19) corresponds to the direction of updating the pose a square shape of size 0.15 by 0.15 inside container of size by where another square shape of the same size has been fixed at pose (0, 0). We show a pose sampled by Diffusion-C&S CCSP for the target object in column 4. In column 5, we visualized the distribution of poses that satisfy each qualitative constraint in the training data. Note that the poses are normalized against the size of the container and the shapes of those objects are no longer 0.15 by 0.15.
We also computed the energy function as the difference between input noise and reconstructed output the final step of diffusion (Figure 18 column 2). Note that the energy field steep. Therefore the areas in the configuration space that meet the constraints exhibit considerably lower energy than areas that don't t. As such, when constraints are combined, the solver tends to prioritize solutions that satisfy all constraints.
22

---

Constraint
Energy (t=0)
Gradient (t=0)
Sampled Data
Data Distribution
1280) MAN
In
-11
-02
-11
122 1160
center-in
-03
163
-15
left-in
-65
right.in
-65
top-in
-03
bottom. in
-10
Figure 18: Visualization of energy and gradient functions of trained diffusion models for qualitative constraints (Part Constraints between a shape and the container). Column 2: Energy fields inside container of size 1 by 1. Column 3: Gradient functions that update poses in different time steps. Column 4: Poses sampled according to the given qualitative constraint. Column S: Poses in the training data set with the given constraint, for 30,000 CCSPs that involve 2 4 objects that have different sizes. The number of constraints that appeared the dataset is shown the top right corner.
23

---

Constraint
Energy (t=0)
Gradient (t=0)
Sampled Data
Data Distribution
cay
-12
-14
left.
-13
3812 SINT
top-of
48
-13
644
159
close-to
-12
away-from
ITU 200
-25
h-aligned
v-aligned
415
-05
-13
Figure 19: Visualization of energy and gradient functions of trained diffusion models for qualitative constraints (Part Constraints between two shapes).


Reviews:
[{"review_id": "fbhPI0aCBIZ", "reviewer": "Reviewer_drxW", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "The paper proposes a compositional diffusion continuous constraint solver, which learns to solve continuous constraint satisfaction problems. It uses constraint graphs as a unified view for different types of tasks and applies diffusion-model-based constraint solvers to find solutions. The proposed method is evaluated on four challenging domains and shows promising results.", "summary_of_recommendation": "The paper uses the compositional diffusion model to solve constraint satisfaction problems, which is novel and well-motivated. On four different domains, the proposed method shows strong performance compared to baselines. It generalizes well to novel combinations of known constraints. However, I am not very familiar with the topic and it is difficult for me to evaluate the significance of this work, so I give Weak Accept with low confidence considering the overall quality of the paper. I may change my score during the rebuttal.", "technical_quality": "Good: Generally convincing, but some additional experiments or analyses needed.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "Highly relevant to robotics but no hardware experiments", "quality_of_limitations": "Limitations are addressed clearly", "questions_for_rebuttal": "No.", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper uses the compositional diffusion model to solve constraint satisfaction problems, which is novel and well-motivated. On four different domains, the proposed method shows strong performance compared to baselines. It generalizes well to novel combinations of known constraints. Some questions: could you run more seeds in Figure 5? or are the results consistent among different runs? Also, do you have more baselines to compare with in Fig 5 since you only compare your method with sequential sampling?", "extra_scores": {"impact": "4: The work contains interesting new ideas that will potentially have major impact in robotics or machine learning."}, "extra_text": {}}, {"review_id": "fWcU-jYNrrk", "reviewer": "Reviewer_88cB", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "The paper tackles the problem of generating solutions for continuous constraint satisfaction problems (CCSP) in robotics. In particular, they focus in problems in which multiple modular constraints need to be satisfied jointly. This could be object-to-object constraints (such as two objects cannot place in the same place, due to collisions) or robot-to-object (plan trajectories collision-free)\n\nThis problem has been previously solved by learning generators for a single constraint and rejecting samples that do not solve previous constraints.\n\nThis paper proposes solving a joint-optimization problem. First, they represent the problem as a factor graph of constraints. Then, each constraint is represented with an energy-based model and learned with diffusion based techniques. \n\nThe authors claim generalization to novel combinations of known constraints and the application of the method for motion planning with both continuous and discrete actions.\n\n", "summary_of_recommendation": "I recommend an acceptance of the work. The paper tackles a very interesting problem for robotics and proposes and interesting solution.\nSolving a CCSP problem with composition of energies is novel and it seems a promising direction.", "technical_quality": "Very Good:  Convincing.", "clarity_of_presentation": "Excellent: Enjoyable to read.", "potential_impact": "", "robotics_focus": "Highly relevant to robotics but no hardware experiments", "quality_of_limitations": "Additional details required", "questions_for_rebuttal": "The questions are presented in the Weaknesses section. Main questions are:\n\n1. How do you deal with the weighting of different energy components?\n2. How do you choose your initial seed to tackle local minimas?", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper is very well written and easy to read. I personally was not familiar with the concept of CCSP and it was easy to understand thanks to the introduction. Framing the problem as the solution of the composition of multiple energy-based models is original and interesting and only few works [1,2] have explored this direction.\n\nThe problem they are tackling is an interesting one and it is properly introduced. The CCSP problem aims to solve a multi-constraint optimization problem. The solution should satisfy all the objectives at once. The authors have shown empirically the benefit of solving all the objectives jointly in contrast with sampling from a single constraint and trying to solve the rest of the constraints by rejection. This solution is in line with previous works [2] that have shown similar results for pick-and-place motion optimization problems.\n\n\n\n**Strenghts**\n\n1. The paper is very well written and easy to understand even for somebody that is not familiarized with CCSP, Composability in Energy Based Models or Diffusion Models.\n\n2. The problem they are tackling is an interesting and important problem for robotics. Multiple robot tasks aim to find solutions finding trade-offs between multiple different objectives. \n\n\n3. The paper presents an elegant and novel approach to CCSP, exploiting the composability of diffusion models. \n\n\n\n**Weaknesses**\n\n\n1. A known problem in EBM composition is the weighting of each energy in the optimization problem [2,3]. How did you tackle the problem of weighting the energy-based models? \n\n2. Another known problem is the possible multiple local minimas in the optimization. A badly chosen initial seed might led to bad solutions. How do you tackle this problem?\n\n3. The paper is not having any comparison with other methods that aim to solve similar problems. It would be interesting to observe if it possible with [1,4].\n\n\n\n[1] Gkanatsios, Nikolaos, et al. \"Energy-based models as zero-shot planners for compositional scene rearrangement.\" arXiv preprint arXiv:2304.14391 (2023).\n\n[2] Urain, Julen, et al. \"Se (3)-diffusionfields: Learning cost functions for joint grasp and motion optimization through diffusion.\" arXiv preprint arXiv:2209.03855 (2022).\n\n[3] Liu, Nan, et al. \"Compositional visual generation with composable diffusion models.\" European Conference on Computer Vision. Cham: Springer Nature Switzerland, 2022.\n\n[4] Liu, Weiyu, et al. \"Structdiffusion: Object-centric diffusion for semantic rearrangement of novel objects.\" arXiv preprint arXiv:2211.04604 (2022).\n", "extra_scores": {"impact": "4: The work contains interesting new ideas that will potentially have major impact in robotics or machine learning."}, "extra_text": {}}, {"review_id": "KXqhPzRA1V", "reviewer": "Reviewer_wq1w", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "This paper introduces a novel approach that leverages the compositional aspects of diffusion models to address robotics planning represented as continuous constraint satisfaction problems (CCSP). The fundamental idea revolves around representing a set of constraints as a computational graph, and employing modular diffusion models to handle various types of constraints. Leveraging the compositionality of these diffusion models, the approach can generate solutions by sampling from the joint model, ensuring satisfaction of the complete set of constraints. The authors showcase experimental results on simulated domains, demonstrating the model's generalization capabilities in handling novel combinations of constraints.", "summary_of_recommendation": "I fully understand the paper in terms of technical work and diffusion models in general, although I do not have a broad knowledge of the relevant work in space of robotic and control except for a few work. Having sad that, I would like to recommend for a weak accept to accept due to its relative novelty in robot planning, although I am concerned about sample complexity of this work when faced with real world robotics tasks.", "technical_quality": "Very Good:  Convincing.", "clarity_of_presentation": "Very Good:  Well organized and clear.", "potential_impact": "", "robotics_focus": "Highly relevant to robotics but no hardware experiments", "quality_of_limitations": "Additional details required", "questions_for_rebuttal": "1. Figures 1(c) and 1(d) do not really serve a purpose\n2. \".. which involve both discrete and continuous parameters\". Can you elaborate further on the \"discrete\" parameters?\n3. Assumes fixed conditions (e.g., object features). What happens when the problem involves partial observability? \n4. Sometimes collision is required for example when \"tight packing\" is required. How do we handle opposing constraints?\n4. In example Figure 2(b) why pose A0 is required once given some other graspA?\n5.  \"It is important to note that these constraints are interdependent\", I did not understand this point. The constraints could be in conflict.\n6. It cries out for adding attention to the architecture.\n7. Suggestion: \"As object B is fixed\" --> As pose of the object B remains unchanged\n8. There is no Figure 3.c\n9. What is \"Object rearrangements\"? (in introduction)\n10. Could you precisely describe ULA?\n11. Could you include any interesting failure cases? I am curious in what instances of the problem the model cannot generalize well.\n12. Rearrange figure 5(c) for OOD (move it to the last column like every other experiment)\n13. Could you address sample complexity issues when moving to real world robotic domains?\n14. Please discuss some future work int he conclusion section if any.", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper reads well and is presented well in general. Although there has been some work in the context of composable diffusion models, and also representing constraints using diffusion models (decision diffuser), to the best of my knowledge I find the approach presented in this paper novel in terms of combining constraints with different types of modalities in robotics domain. My main concerns about this work: (1) still there is a gap from the proposed solution to having it functional in real world robotic applications. The sample complexity is concerning (10k - 30k); (2) the fact that the full model needs to be trained jointly presents some limitation in a sense that we also acquire skills not always in the context of a well defined task and solely based on curiosity. It is less clear to me how individual skill acquisition could be achieved more following a \"divide and conquer\" approach; (3) related to the previous point, it would have been nice to demonstrate how to fine tune when pre-trained skills and constraints are given a priori. Overall, I like the approach and find it very relevant to current trend in robotics.", "extra_scores": {"impact": "3: The work is incremental and unlikely to have much impact, even though it may be technically correct and well executed."}, "extra_text": {}}]

Author rebuttal:

Meta-review: I would like to thank the reviewers and authors for the fruitful discussion during the review process. The work proposes a novel approach to solve continuous constraint satisfaction problems in robotics which are of key relevance to the community. The approach of utilizing a compositional diffusion based approach appears to be novel and an improvement over the state of the art. The reviewers in particular highlight the following strengths of the work:

- the work is well written and approachable also for audiences new to CCSP
- the approach taken was considered elegant and novel
- the problem of CCSP in robotics was appreciated as being of high relevance
- the approach appears to generalize well to novel combinations of known constraints

Among areas of potential further investigation, the reviewers in particular listed
- potential remaining gap to real world deployment on robots 
- sample complexity concerns
- questions around local vs global optimality during optimization
- investigation of fine-tuning of a pre-trained constraint solver

Overall the review consensus appears to indicate that this work may be a candidate for publication at CORL given in particular novelty and relevance to the community.
Decision: Accept (Poster)