Sequential Object Placement Optimization with Convex Decomposition
- URL: http://arxiv.org/abs/2608.25162v1
- Date: Tue, 25 Aug 2026 21:19:31 GMT
- Title: Sequential Object Placement Optimization with Convex Decomposition
- Abstract summary: We introduce SOPO-CD, a sequential optimization framework that frames object placement as a differentiable nonlinear optimization problem in a decomposed free space.<n>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.<n>We generalize our framework to 2D Tangram, 2D Tetris, and 3D Bin Packing, and have demonstrated strong computational performance and packing utility.
- Score: 12.039337956885467
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Stable and Scalable Bundle Adjustment of Holistic 3D Structures [99.03818732955783]
We present a new version of Bundle Adjustment (BA) for 3D computer vision.<n>BA is developed to jointly optimize cameras, poses and 3D points.<n>By group-induced measurements and cross-feature reprojection, we preserve the sparsity of classical point-only 3D regularization.
arXiv Detail & Related papers (2026-09-03T16:08:03Z) - Biconvex Optimization for Smooth Minimum-Time Trajectories around Convex Obstacles [49.315843050082925]
We present a bi approach for minimum-time motion planning convex obstacles that is guaranteed to converge.<n>We find that the proposed method produces high-quality trajectories with times to produce state-of-the-art decomposition of variables.
arXiv Detail & Related papers (2026-08-03T19:48:24Z) - GPU-Accelerated Polygonal Signed Distance Functions for Real-Time Collision Avoidance [2.1993185973565113]
In dense environments, where feasible space is limited, the computational workload often dominates the control-cycle runtime.<n>The proposed Polygonal Signed Distance Function (PSDF) is a geometry-exact signed distance function between a convex polygonal robot footprint and obstacles represented by their boundary edges.<n>PSDF is embedded into model predictive control by locally linearizing the stage-wise safety constraints within a sequential quadratic programming-based real-time iteration scheme.<n>PSDF-MPC maintains real-time feasibility and robust collision avoidance in dense polygonal environments.
arXiv Detail & Related papers (2026-07-05T13:46:59Z) - NoPA: Non-Parametric Online 3D Scene Graph Generation [57.15076373014265]
NoPA represents each object as a separate non-parametric distribution.<n>We leverage maximum mean discrepancy on kernel density estimates to enable robust merging of object candidates.<n>NoPA substantially outperforms current methods without sacrificing real-time inference speed.
arXiv Detail & Related papers (2026-07-01T07:18:07Z) - Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
arXiv Detail & Related papers (2026-05-27T14:02:20Z) - $\ell_0$-Regularized Quadratic Surface Support Vector Machines [0.0]
Kernel-free quadratic surface support vector machines have recently gained traction due to their flexibility in modeling nonlinear decision boundaries without relying on kernel functions.<n>We propose a sparse variant of the QSVM by enforcing a cardinality constraint on the model parameters.<n>We validate our approach on several real-world datasets, demonstrating its ability to reduce overfitting while maintaining strong classification performance.
arXiv Detail & Related papers (2025-01-20T04:26:34Z) - Decomposed Global Optimization for Robust Point Matching with Low-Dimensional Branching [41.05165517541873]
We introduce a novel global optimization method for align partially overlapping point sets.<n>Our method exhibits superior robustness to non-rigid deformations, positional noise and outliers.<n> Experiments on 2D and 3D synthetic and real-world data demonstrate that our method, compared to state-of-the-art approaches, exhibits superior robustness to outliers.
arXiv Detail & Related papers (2024-05-14T13:28:57Z) - Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems.
We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
arXiv Detail & Related papers (2023-05-28T06:33:37Z) - OPA-3D: Occlusion-Aware Pixel-Wise Aggregation for Monocular 3D Object
Detection [51.153003057515754]
OPA-3D is a single-stage, end-to-end, Occlusion-Aware Pixel-Wise Aggregation network.
It jointly estimates dense scene depth with depth-bounding box residuals and object bounding boxes.
It outperforms state-of-the-art methods on the main Car category.
arXiv Detail & Related papers (2022-11-02T14:19:13Z) - Approximate Convex Decomposition for 3D Meshes with Collision-Aware
Concavity and Tree Search [23.52274863244624]
Approximate convex decomposition aims to decompose a 3D shape into a set of almost convex components.
It has been widely used in game engines, physics simulations, and animation.
We propose a novel method that addresses the limitations of existing approaches from three perspectives.
arXiv Detail & Related papers (2022-05-05T23:40:15Z) - Localization and Tracking of User-Defined Points on Deformable Objects
for Robotic Manipulation [0.0]
This paper introduces an efficient procedure to localize user-defined points on the surface of deformable objects.
We propose a discretized deformation field, which is estimated during runtime using a multi-step non-linear solver pipeline.
Our approach is capable of solving the localization problem online in a data-parallel manner, making it ideally suitable for the perception of non-rigid objects in industrial manufacturing processes.
arXiv Detail & Related papers (2021-05-19T11:25:33Z) - Dense Non-Rigid Structure from Motion: A Manifold Viewpoint [162.88686222340962]
Non-Rigid Structure-from-Motion (NRSfM) problem aims to recover 3D geometry of a deforming object from its 2D feature correspondences across multiple frames.
We show that our approach significantly improves accuracy, scalability, and robustness against noise.
arXiv Detail & Related papers (2020-06-15T09:15:54Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.