Semidefinite Relaxations for Collision-Free Motion Planning

• URL: http://arxiv.org/abs/2606.14063v1
• Date: Fri, 12 Jun 2026 03:18:03 GMT
• Title: Semidefinite Relaxations for Collision-Free Motion Planning
• Abstract summary: We focus on a point robot moving from start to goal through inmathbbRn constraints in terms of $C4 trajectories.<n>We demonstrate its effectiveness as a planner for minimum-snap continuous planning with $C4 trajectories.
• Score: 53.160637667144876
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study semidefinite relaxations for collision-free motion planning. We focus on a point robot moving from start to goal through spherical obstacles in $\mathbb{R}^n$, 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 $C^4$ continuous trajectories.

Related papers

• CyclOT: Learning Quadratic Optimal Transport Maps via Synchronized Forward-Backward Interpolants [20.064386074670605]
  We introduce a bidirectional neural framework in which the learned maps induce forward and backward displacement interpolants.<n>Experiments on Swiss roll, MNIST, CelebA, single-cell data, and chest X-ray images evaluate endpoint fidelity, transport cost inverse, consistency, and the geometry of the induced inverts.
  arXiv  Detail & Related papers  (2026-09-12T11:31:53Z)
• 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)
• 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)
• Local LMO: Constrained Gradient Optimization via a Local Linear Minimization Oracle [51.714334316332476]
  Local L is a new projection-free type for constrained optimization.<n>Local LMO is perhaps best viewed as an oracle of Gradient Descent (GD)
  arXiv  Detail & Related papers  (2026-05-09T10:03:24Z)
• Sliced Wasserstein Steering between Gaussian Measures [2.1485350418225244]
  We develop a sliced feedback controller for distribution steering.<n>The evolving law is projected onto one-dimensional directions on the sphere.<n>We show that the developed controller steers the law to the prescribed target.
  arXiv  Detail & Related papers  (2026-04-14T08:03:17Z)
• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  This paper studies minimax optimization problems defined over infinite-dimensional function classes of overparametricized two-layer neural networks. We address (i) the convergence of the gradient descent-ascent algorithm and (ii) the representation learning of the neural networks. Results show that the feature representation induced by the neural networks is allowed to deviate from the initial one by the magnitude of $O(alpha-1)$, measured in terms of the Wasserstein distance.
  arXiv  Detail & Related papers  (2024-04-18T16:46:08Z)
• Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximation [26.277745106128197]
  We propose an algorithm to tackle long planning horizon problems in reinforcement learning with general function approximation. The derived regret bound is deemed emphsharp as it matches the minimax lower bound when specialized to linear mixture MDPs up to logarithmic factors. The achievement of such a horizon-free, instance-dependent, and sharp regret bound hinges upon (i) novel algorithm designs and (ii) fine-grained analyses.
  arXiv  Detail & Related papers  (2023-12-07T17:35:34Z)
• Projected Langevin dynamics and a gradient flow for entropic optimal transport [0.8057006406834466]
  We introduce analogous diffusion dynamics that sample from an entropy-regularized optimal transport. By studying the induced Wasserstein geometry of the submanifold $Pi(mu,nu)$, we argue that the SDE can be viewed as a Wasserstein gradient flow on this space of couplings.
  arXiv  Detail & Related papers  (2023-09-15T17:55:56Z)
• Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part I: Definitions & Basic Properties [6.355764634492975]
  For general quadratically-constrained computation, we propose a relaxation described with quadratic constraints. The relaxation can be made as strong as a semidefinite (SDP) relaxation. It can be effective in accelerating algorithms that require a sequence of surrogates.
  arXiv  Detail & Related papers  (2022-08-07T02:44:23Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• Competitive Mirror Descent [67.31015611281225]
  Constrained competitive optimization involves multiple agents trying to minimize conflicting objectives, subject to constraints. We propose competitive mirror descent (CMD): a general method for solving such problems based on first order information. As a special case we obtain a novel competitive multiplicative weights algorithm for problems on the positive cone.
  arXiv  Detail & Related papers  (2020-06-17T22:11:35Z)

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.