Source-linked AI summary
Sequential Object Placement Optimization with Convex Decomposition
Yuezhe Zhang, Xiangyu Lyu, Sohan Rudra, Davide Tateo, Georgia Chalvatzaki
TL;DR
Existing object-packing methods often rely on discretized position and orientation spaces whose size grows with accuracy, while collision checking and narrow-space planning remain challenging. SOPO-CD instead optimizes placements continuously in decomposed free space using differentiable constraints, and demonstrates millisecond solving across Tangram, Tetris, and 3D Bin Packing, including a real-world Tangram puzzle.
Problem
Existing object-packing algorithms often assume discretized position and orientation spaces whose size grows explosively with discretization accuracy, while collision checking and narrow-space planning for non-convex obstacles remain challenging.
Method
SOPO-CD decomposes collision-free space into convex hulls, assigns hulls to convex bodies, and formulates placement as differentiable nonlinear optimization with closed-form analytic derivatives.
Results
SOPO-CD demonstrates strong computational performance and packing utility across 2D Tangram, 2D Tetris, and 3D Bin Packing, with analytic derivatives almost 10–20 times faster than ForwardDiff and 50 times faster than grid search at the largest grid size.
Takeaways & Limitations
The framework solves optimal placements in milliseconds and supports a real-world Tangram puzzle demonstration using an Allegro Hand and an Xarm.
Takeaways & Limitations
Convex hull selection is not exhaustive, 3D decomposition generates axis-aligned cuboids, and the greedy algorithm does not look ahead to future placements.
Abstract
from arXiv · showhide
Robotic object packing has been a core challenge for robotic deployment in logistics, industry, etc., due to the curse of dimensionality in combinatorial search and the difficulty of dealing with dynamic and contact constraints for irregularly shaped objects. Current heuristic and learning-based methods assume a limited spatial discretization resolution of space, and computation becomes extremely inefficient as discretization accuracy increases. In this work, we eliminate these assumptions by introducing SOPO-CD, a sequential optimization framework that frames object placement as a differentiable nonlinear optimization problem in a decomposed free space. We prove that placing a convex object inside a convex hull is essentially constraining the vertices of the object inside the convex hull. The constraints and their derivatives can be written in closed form and calculated within $200$ns. We implement a custom solver that achieves optimal placement within tightly constrained space in milliseconds; a $100 \times$ speedup compared to a classical grid search method. We generalize our framework to 2D Tangram, 2D Tetris, and 3D Bin Packing, and have demonstrated strong computational performance and packing utility. We also demonstrate solving a real-world Tangram puzzle online using an Allegro Hand and an Xarm.
I. INTRODUCTION
SOPO-CD addresses inefficient discretized object placement by formulating packing in continuous free space as differentiable nonlinear optimization. It evaluates this framework across Tangram, Tetris, and 3D Bin Packing, with strong speed and packing results.
- Existing placement methods often discretize position and orientation, causing the action space to grow explosively as resolution increases.
- SOPO-CD decomposes free space into convex hulls and formulates object placement as a differentiable nonlinear optimization problem.The framework constrains convex-object vertices within selected convex hulls and uses a custom SQP solver.
- 10× speedup and higher success rates are achieved on Tangram compared with SQP using a differentiable collision checker.
- 77% packing utility and 50× speedup over grid search are achieved for 2D Tetris.
- SOPO-CD is evaluated on 2D Tangram, 2D Tetris, and 3D Bin Packing, including a real-world Tangram demonstration with an Allegro Hand and Xarm.
B. Convex Hull Definition
The paper represents convex hulls either through convex combinations of vertices or through finite halfspace inequalities. These representations support differentiable geometric constraints for collision and placement reasoning.
- A convex hull is the intersection of all convex sets containing a point set.
- V-representation expresses a convex hull as a convex combination of points in R^d.The coefficients ω_i are convex coefficients.
- H-representation defines a convex hull using a finite number of inequalities.The matrices A and vector b determine the hull’s halfspaces and can be computed from its vertices.
- For polytopes, differentiable collision-checking constraints can be expressed as halfspace constraints of the convex hull.
IV. METHODOLOGY
SOPO-CD decomposes collision-free space into convex regions, then places transformed object geometry inside those regions using explicit geometric constraints. A convex-hull theorem reduces containment to vertex constraints suitable for analytic optimization.
- A. Convex Decomposition: 2D free space is triangulated with constrained Delaunay Triangulation and greedily merged into larger convex polygons.Triangles are merged only when they share an edge, the merged polygon is convex, and its area is sufficiently large.
- A. Convex Decomposition: Fig. 2 shows Tangram free-space decomposition, largest-hull selection, and SQP-based placement across successive iterations.
- A. Convex Decomposition: 3D free space is partitioned into axis-aligned Maximal Empty Cuboids by scanning and expanding a 2D heightmap.
- B. Differentiable Collision Checking in Free Space: A convex hull A lies inside convex hull B if and only if every vertex of A lies inside B.This theorem converts convex containment into vertex-wise constraints.
- B. Differentiable Collision Checking in Free Space: Object vertices in world coordinates are r + t + QV_i, and each vertex is constrained by the free space’s halfspace representation.The optimization variables are translation t and orientation parameters q through Q(q).
C. Convex Hull Selection and Assignment
SOPO-CD uses heuristics to assign convex object bodies to candidate free-space hulls because exhaustive assignment is costly and some assignments are infeasible. Non-convex objects require testing adjacent-hull pairings.
- Assignment quality depends on matching each convex object body with a suitable free-space hull; undersized hulls make placement infeasible.
- Tangram selects the largest convex hull at each step, while 3D Bin Packing prioritizes low hulls by height and volume.
- The method solves placements for the top k candidate hulls and chooses the feasible solution with the best objective value.
- C. Convex Hull Selection and Assignment: Non-convex placement associates adjacent hulls and tests alternative assignments between the object’s convex bodies and the hull pair.For top k adjacent pairs, this produces 2k optimization problems.
D. Compute Analytic Derivative
SOPO-CD expresses placement constraints and their derivatives analytically for convex objects assigned to decomposed free-space hulls. For non-convex objects, adjacent hull assignments yield multiple constraint-pair problems solved separately.
- State and rotation: The placement state uses translation t and Euler-angle rotation q, with x = [t, q] ∈ R6.The rotation follows the ZYX convention: Q = Rz(γ)Ry(β)Rx(α).
- Analytic derivatives: The framework computes the cost gradient, constraint Jacobian, and Lagrangian Hessian directly in closed form.Kronecker products and vectorization remove loops during analytic derivative computation.
- Constraint formulation: Each convex-object placement constraint is written as gi = A(r + t + Q(q)Vi) − b for a hull halfspace.For each halfspace, Ai ∈ R1×3 and bi ∈ R define the scalar constraint gij.
- Non-convex assignment: For non-convex objects, adjacent free-space hulls are paired and the top k lowest pairs are solved separately because different object bodies may occupy different hulls.In the illustrated case, 5 adjacent hull pairs are ranked, the top k = 2 are selected, and 4 body-to-hull constraint combinations are solved.
E. Object Placement Optimization via SQP
SOPO-CD solves its nonlinear placement problems with Sequential Quadratic Programming, using regularization, line search, and randomized parallel starts to address numerical stability and local optimality.
- SQP solver: SQP models the placement problem at each iterate as a quadratic-programming subproblem and uses its solution to update the iterate.The subproblem uses the constraints cn and Jacobian Jn evaluated at the current state xn.
- Numerical stability: A scaled identity matrix is added to the Lagrangian Hessian to improve numerical stability.This addresses the possibility that the Hessian is indefinite.
- Step selection: Backtracking line search with the Armijo rule selects the step length while enforcing sufficient decrease in the merit function.The merit function combines the objective with penalized constraint violations.
- Termination: SQP terminates when the step norm and maximum constraint violation fall below tol = 1 × 10^-4, with at most 50 iterations.The penalty parameter is positive for constraints exceeding the tolerance threshold.
- Global-search heuristic: Randomized initial states are solved in parallel, and the placement with the best merit function is selected because SQP is locally optimal.A feasible local solution may still leave insufficient space for subsequent objects.
V. RESULTS
The experiments were implemented in Julia and benchmarked repeatedly on an AMD Ryzen 9 7950x3D 16-core CPU.
- Experimental setup: Experiments use Julia and BenchmarkTools on an AMD Ryzen 9 7950x3D 16-core CPU.BenchmarkTools runs modules multiple times to evaluate computational performance.
A. Analytic Derivatives vs. AutoDiff
Analytic derivatives are compared with ForwardDiff for randomized 2D and 3D object states. They are consistently faster while matching ForwardDiff values.
- Performance comparison: Analytic derivatives are consistently faster than ForwardDiff in both 2D and 3D scenarios.The comparison covers the cost gradient, constraint Jacobian, and Lagrangian Hessian, with identical computed values checked at every run.
- Performance comparison: 10–20× faster computation is reported for the analytic solution, especially for the most time-consuming Hessian calculation.Median computation times are reported in Table I.
B. Solve Tangram Puzzle
SOPO-CD is evaluated on Tangram as a sequential placement optimizer against SQP with differentiable collision checking. It consistently improves full-sequence performance and places almost all seven objects in about 10 ms with eight threads.
- Tangram evaluation: SOPO-CD is compared with SQP using the differentiable collision checker DCOL for sequential Tangram placement.The evaluation reports median computation time and average converged SQP iterations per object.
- Tangram evaluation: 50 iterations is the maximum reached by SQP when placing the last two objects.
- Full-sequence performance: 8 threads allow SOPO-CD to place almost all 7 objects successfully in around 10 ms for the full Tangram sequence.
C. Solve 2D Tetris Puzzle
SOPO-CD is tested on constrained 2D Tetris benchmarks against SPaSM and grid search. It handles hard constraints and achieves 77% packing utility while remaining substantially faster than grid search as resolution increases.
- Mini Tetris: SOPO-CD evaluates feasible poses for 5- and 8-object Tetris instances inside constrained bounding boxes.The method is compared with SPaSM without trajectory optimization.
- Mini Tetris: 1 × 10^-4 tolerance allows SOPO-CD to handle hard constraints, whereas SPaSM exhibits wall and sphere penetration between 2×10^-4 and 3×10^-3.
- Full Tetris: 77% packing utility is reached for full 2D Tetris with eight threads and k = 1.
- Full Tetris: 50 times faster than grid search at the largest grid size, SOPO-CD maintains performant computation as grid-search time grows with resolution.
- Full Tetris: 10–20 ms are required to solve 2k placement optimization problems per object, after approximately 6µs of preprocessing.
D. Solve 3D Bin Packing
SOPO-CD evaluates continuous-space 3D bin packing against heightmap grid search using convex-hull decomposition and batched optimization. Across varying grid sizes, it maintains efficient computation while improving placement performance at the largest resolution.
- Evaluation setup: The grid-search baseline represents occupied objects with an M × M heightmap and has time complexity O(M^2).Both methods use the objective f(t, q) = tx+ty+5tz for each placement.
- Optimization procedure: SOPO-CD generates axis-aligned convex hulls, selects the 3 lowest, and runs a batched SQP solver on each selected hull.Its preprocessing includes convex-hull generation and constraint extraction.
- Results: At the largest grid size, SOPO-CD is more than 200 times faster than grid search, while successful placements and occupancy rate also increase significantly.SOPO-CD preprocessing remains within 1ms, and computation time grows linearly with solver batch size and selected convex hulls.