Motion Planning for Autonomous Vehicles using Optimization over Graphs of Convex Sets

• URL: http://arxiv.org/abs/2605.14199v1
• Date: Wed, 13 May 2026 23:29:54 GMT
• Title: Motion Planning for Autonomous Vehicles using Optimization over Graphs of Convex Sets
• Abstract summary: Motion planning for autonomous vehicles requires generating collision-free and dynamically feasible trajectories under real-time constraints.<n>In this paper, we introduce a new geometric control method to approximate nonlinear motion planning problems.<n>The method provides a structured approximation of nonlinear motion planning problems, capturing dominant geometric dynamic effects while preserving convexity in the continuous relaxation.
• Score: 0.6445605125467574
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Motion planning for autonomous vehicles requires generating collision-free and dynamically feasible trajectories in complex environments under real-time constraints. While nonlinear optimal control formulations provide high-fidelity solutions, they are computationally demanding and sensitive to initialization, whereas geometric planning methods scale well but often decouple path selection from trajectory optimization. This paper studies the extent to which optimization over Graphs of Convex Sets (GCS) can approximate solutions of nonlinear optimal control problems in the context of autonomous driving. The free space is represented as a finite union of convex regions organized as a directed graph, allowing nonconvex geometry to be handled through discrete connectivity decisions while maintaining convex trajectory constraints within each region. Vehicle motion is parameterized using Bezier curves for the spatial path and a polynomial time-scaling function for temporal evolution. Under small-slip and linear tire assumptions, a simplified dynamic bicycle model enables approximate enforcement of dynamic feasibility through convex constraints on trajectory derivatives. The approach is evaluated in CommonRoad scenarios involving static obstacle avoidance and lane-changing maneuvers, and is compared against a nonlinear discrete-time optimal control formulation. The results indicate that the GCS-based method generates collision-free and dynamically consistent trajectories that closely match those obtained from the nonlinear program, while exhibiting improved computational efficiency and reduced sensitivity to initialization. These findings suggest that GCS provides a structured approximation of nonlinear motion planning problems, capturing dominant geometric and dynamic effects while preserving convexity in the continuous relaxation.

Related papers

• Integrated Graph Search and Model Predictive Control for Smooth and Efficient Path Planning in Autonomous Vehicles [1.228397872697275]
  A rough path is first obtained via Dijkstra search on a discretized grid.<n>A Model Predictive Control problem is formulated to refine the path.<n>The proposed algorithm is evaluated in multiple overtaking scenarios on both straight and curved roads.
  arXiv  Detail & Related papers  (2026-07-05T12:14:33Z)
• Saturation-Aware Robust Trajectory Optimization for Reusable Launch Vehicles via Differentiable Physics [9.011250637911248]
  High-angle-of-attack flip maneuver of reusable launch vehicles presents challenges for robust trajectory optimization.<n>This paper presents a differentiable physics framework for saturation-aware robust trajectory optimization.
  arXiv  Detail & Related papers  (2026-07-02T14:30:37Z)
• Adaptive Smooth Tchebycheff Attention for Multi-Objective Policy Optimization [55.338784037660474]
  Multi- curvature reinforcement learning in domains requires balancing complex, non-fragile interference trade-offs between conflicting objectives.<n>In this paper we introduce a novel based real-time based real-time optimization on a robotic visual -- a proxy for monitoring ecosystems.
  arXiv  Detail & Related papers  (2026-05-12T21:32:57Z)
• Iterative Convex Optimization with Control Barrier Functions for Obstacle Avoidance among Polytopes [3.8436274588467696]
  Obstacle avoidance by polytopic robots is a challenging problem in optimization-based control and trajectory planning.<n>Existing methods rely on hyperiable distance approximations, such as ellipsoids, which distort geometric dynamics.<n>In this paper, we propose a novel iterative convexity- finite-horizon optimization framework for safety-critical navigation programs.
  arXiv  Detail & Related papers  (2026-03-06T05:10:44Z)
• FACTO: Function-space Adaptive Constrained Trajectory Optimization for Robotic Manipulators [4.0407133618465005]
  This paper introduces Function-space Adaptive Constrained Trajectory Optimization (FACTO) for single- and multi-arm manipulators.<n>To address nonlinearity, FACTO uses a Gauss-Newton approximation with exponential moving averaging, yielding a smoothed quadratic subproblem.<n>The experimental evaluation of FACTO on Franka robots verifies the feasibility of deployment.
  arXiv  Detail & Related papers  (2026-02-23T16:38:13Z)
• Spatially-Aware Adaptive Trajectory Optimization with Controller-Guided Feedback for Autonomous Racing [74.83272587893508]
  We present a framework for autonomous raceline optimization that combines NURBS-based trajectory representation, CMA-ES global trajectory optimization, and controller-guided spatial feedback.<n>In simulation, our approach achieves a 17.38% lap time reduction compared to a controller parametrized with maximum static acceleration.<n>On real hardware, tested with different tire compounds ranging from high to low friction, we obtain a 7.60% lap time improvement without explicitly parametrizing friction.
  arXiv  Detail & Related papers  (2026-02-17T15:10:44Z)
• Fast Near Time-Optimal Motion Planning for Holonomic Vehicles in Structured Environments [8.195916347194315]
  The approach aims to solve the problem of motion planning for planar motion systems using magnetic levitation.<n>The presented approach encodes the environment representation using free-space corridors and represents the motion of the vehicle through such a corridor using a motion primitive.<n>The method achieves significantly lower times compared to the state-of-the-art and is validated on a real-world Beckhoff XPlanar system.
  arXiv  Detail & Related papers  (2026-02-02T21:26:30Z)
• A Fast Semidefinite Convex Relaxation for Optimal Control Problems With Spatio-Temporal Constraints [22.24436694865408]
  Solving optimal control problems (OCs) of autonomous agents is essential in applications ranging from driving autonomous vehicles to self-driving cars.<n>Most of the OCPs are nonpointing due to the coupling between the event timing and the trajectory.<n>We propose a time-scaling direct multiple shooting scheme that partitions the horizon into segments with time constraints.
  arXiv  Detail & Related papers  (2026-01-06T14:38:19Z)
• Integrating Higher-Order Dynamics and Roadway-Compliance into Constrained ILQR-based Trajectory Planning for Autonomous Vehicles [3.200238632208686]
  Trajectory planning aims to produce a globally optimal route for Autonomous Passenger Vehicles. Existing implementations utilizing the vehicle bicycle kinematic model may not guarantee controllable trajectories. We augment this model by higher-order terms, including the first and second-order derivatives of curvature and longitudinal jerk.
  arXiv  Detail & Related papers  (2023-09-25T22:30:18Z)
• 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)
• Stochastic Nonlinear Control via Finite-dimensional Spectral Dynamic Embedding [20.43835169613882]
  This paper proposes an approach, Spectral Dynamics Embedding Control (SDEC), to optimal control for nonlinear systems.<n>It reveals an infinite-dimensional feature representation induced by the system's nonlinear dynamics, enabling a linear representation of the state-action value function.<n>For practical implementation, this representation is approximated using finite-dimensional truncations.
  arXiv  Detail & Related papers  (2023-04-08T04:23:46Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms.<n>An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  We propose a dissipative extension of Dirac's theory of constrained Hamiltonian systems as a general framework for solving optimization problems. Our class of (accelerated) algorithms are not only simple and efficient but also applicable to a broad range of contexts.
  arXiv  Detail & Related papers  (2021-07-23T13:43:34Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  We introduce a class of first-order methods for smooth constrained optimization. Two distinctive features of our approach are that projections or optimizations over the entire feasible set are avoided. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear.
  arXiv  Detail & Related papers  (2021-07-17T11:45:13Z)

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.