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 collision constraints for irregularly shaped objects. Current heuristic and learning-based methods mainly assume a limited spatial discretization resolution of space, and computation becomes extremely inefficient as discretization accuracy increases. In this work, we eliminate this assumption by introducing SOPO-CD, which frames sequential object placement as a differentiable nonlinear optimization problem with hard constraints in a decomposed free space. We formulate the constraints of placing a convex object inside a convex hull as constraining the vertices of the object to lie inside the convex hull. The constraints and their derivatives can be written in closed form and calculated efficiently. We implement a custom solver that achieves local-optimal placements within tightly constrained space in milliseconds; a 50× speedup compared to a fine-grained grid search method. We evaluate our framework on 2D Tangram, 2D Tetris, and 3D Bin Packing, and have demonstrated strong computational performance and packing utility. We also demonstrate its real-world applicability for solving the Tangram puzzle using a robot equipped with a dexterous hand.
Figures & tables
Fig. 2: Visualization of the Tangram puzzle with the given object sequence and cost functions. The first two rows show the free-space decomposition using Delaunay Triangulation [ 22 ] and merged convex polygons. At each iteration, we select the largest convex hull, and SQP will calculate the best placement in this convex hull, as shown in the third row.
Fig. 3: Illustration of hull assignment for placing an L-shaped object. The free-space convex hulls can be grouped into 5 pairs of adjacent hulls. We sort the pairs by height and select the top k=2 hull pairs. Each convex body of the object is assigned to each hull, resulting in 4 combinations of constraint pairs, and we will solve these 4 problems separately.
scenario
gradient ( ns )
Jacobian ( ns )
Hessian ( ns )
Analytic
2D
16.29
24.96
41.45
3D
85.64
188.70
368.59
ForwardDiff
2D
21.16
45.70
311.65
3D
167.82
345.27
7652.00
TABLE I: Computation time for calculating gradient, Jacobian, and Hessian.
obj 1
obj 2
obj 3
obj 4
obj 5
obj 6
obj 7
SOPO-CD
preprocess ( \SIUnitSymbolMicros )
35.34
60.35
25.05
75.44
49.64
39.94
31.78
SQP time ( ms )
0.31
0.21
0.16
0.32
0.88
0.20
0.26
SQP iters
9.40
4.11
5.43
7.72
11.70
2.99
5.99
solved rate (%)
100.00
100.00
99.89
99.89
99.18
100.00
99.99
DCOL
SQP time ( ms )
0.31
1.01
1.00
2.25
6.13
20.13
23.19
SQP iters
9.15
7.72
6.46
10.43
27.80
49.63
50.00
TABLE II: Computation time for Tangram on a single thread.
n_threads
total time ( ms )
successful placements
memory estimate (MiB)
SOPO-CD
2
9.02
4.35
2.53
4
9.31
5.62
4.66
8
10.02
6.63
9.44
16
12.98
6.96
17.67
DCOL
2
27.48
2.63
3.26
4
46.34
3.54
6.76
TABLE III: Performance for full sequence Tangram.
Fig. 4: SQP convergence for a single object in Tangram.
n_threads
total time ( ms )
successful placements
success rate (%)
5-Tetris
2
3.14
4.75
74.95
4
3.46
4.94
93.71
8
4.62
4.99
99.84
8-Tetris
2
10.45
7.28
35.13
4
6.90
7.80
81.05
8
8.22
7.99
98.71
TABLE IV: Performance for mini Tetris using SOPO-CD.
Fig. 5: An intermediate screenshot of convex hull generation and placed objects for 2D Tetris.
grid size
compute time per obj ( ms )
successful placements
occupancy rate (%)
Grid-Search
8 × 8
0.03
14.10
84.86
80 × 80
1.69
13.97
83.92
800 × 800
1455.24
13.67
82.29
TABLE V: Performance for full Tetris using grid search.
top- k
preprocess per obj ( \SIUnitSymbolMicros )
compute time per obj ( ms )
successful placements
occupancy rate (%)
SOPO-CD (n_threads=2)
1
5.40
9.05
9.95
59.46
2
5.59
13.52
10.88
65.13
3
5.83
18.70
11.06
66.23
SOPO-CD (n_threads=4)
1
5.73
12.39
12.06
72.28
2
6.09
19.06
12.28
73.62
3
5.84
26.05
12.32
73.94
TABLE VI: Performance for full Tetris.
Fig. 6: An intermediate screenshot of convex hull generation and placed objects for 3D Bin Packing.
Most existing approaches either fix the container in advance or optimize only a single container dimension through an outer search loop, leaving the remaining dimensions as a manual tuning problem. We present a differentiable packing framework that jointly optimizes all 6N object pose parameters and all three container side lengths inside a single gradient-based loop. The formulation combines six physics-inspired, differentiable loss terms computed directly on triangle meshes through axis-aligned bounding-box proxies. An adaptive squeezing mechanism periodically tightens the container whenever the overlap loss falls below a pair-count-scaled threshold, producing a large initial drop in container volume, followed by small refinements. All pairwise computations are written in tensor-broadcasting form, giving a 3.4 to 54 times speedup over a reference loop-based implementation. The pipeline is implemented in Python and PyTorch, with no physics engine, FFT library, or convex decomposition. On multiple object categories, the method produces containers that are 11 to 32 percent smaller than time-matched DBLF and simulated-annealing baselines at N =100, while running in under 4 minutes per instance on a single consumer GPU.
3D bin packing rectangular items into standardised containers to maximise space utilisation under geometric shipping automation. Loading a furniture purchase into a personal vehicle is the same task, but under more complex conditions that standard container loading algorithms ignore. This paper addresses the physically stable placement under these realistic conditions with heterogeneous boxes (e.g. varying dimensions and weights) and occupied containers (e.g. groceries). This paper provides a real-world benchmark dataset and baseline model for the Heterogeneous furniture-in-vehicle packing task. The dataset uses real furniture company flat-pack packaging data covering a large number of catalogue products via family-level extrapolation with diversity length, widths, heights, and weights. We also propose a PackingGPT framework for packing as a sequential placement inspired by the Lego assembly process, where heterogeneous boxes of varying dimensions (bricks) are placed step-by-step into the irregular remaining cargo space (creations). Five baseline packing methods were tested on our dataset without considering the Centre-of- Mass (CoM) constraints. In sedan car simulations, 10-40% of placed boxes failed the stability check on average. When the LLP model was trained on packing sequences with CoM constraints enforced during placement, the failure rate dropped to 0.67% (SUV-500).
Yi You, Hui Li
Faculty of Technology, Policy and Management Technische Universiteit Delft, Delft, Netherlands · Department of Industrial and Systems Engineering The Hong Kong Polytechnic University, Hong Kong, China
We study semidefinite relaxations for collision-free motion planning. We focus on a point robot moving from start to goal through spherical obstacles in Rn, subject to path continuity constraints and squared derivative costs; a setting that is conceptually simple yet captures the hardness of collision-free motion planning. We formulate this problem exactly as a nonconvex problem over polynomial curves, and present a natural semidefinite relaxation. We contribute two key theoretical insights; to our knowledge this is the first theoretical analysis of semidefinite relaxations for collision-free motion planning. First, we show that solving the convex relaxation is equivalent to solving, to global optimality, a related motion planning problem in a potentially higher-dimensional space. This geometric interpretation yields necessary and sufficient conditions for tightness, and a clear intuition for when the relaxation is loose. Second, we show that the relaxation admits a symmetry reduction that makes it significantly smaller than one might expect, with positive semidefinite cone sizes that scale linearly with the polynomial degree and are independent of the ambient dimension. The resulting relaxation is 10 to 100 times faster than direct nonlinear programming transcriptions solved with SNOPT and IPOPT, exhibits significantly lower variance in solve times, and reliably finds a locally optimal path for the original problem. We demonstrate its effectiveness as a convex steering function in an RRT planner for minimum-snap quadrotor planning with C4 continuous trajectories.
Bernhard Paus Graesdal, Alexandre Amice, Pablo A. Parrilo +1
Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, USA.