Skip to content

A Biconvex Method for Minimum-Time Motion Planning Through Sequences of Convex Sets

Authors: Tobia Marcucci, Mathew Halm, William Yang, Dongchan Lee, Andrew Marchese

Published: 2025 (Conference Paper)

Source: Robotics: Science and Systems (RSS)

Algorithm: SCS

arXiv: 2504.18978

Summary

Addresses minimum-time trajectory design through a fixed sequence of convex sets subject to velocity and acceleration constraints - a problem that is natively nonconvex due to the coupling between time scaling and path shape. The proposed biconvex method alternates between two convex subproblems, quickly generating a feasible initial trajectory and iteratively refining it without line-search parameters.

Abstract

We consider the problem of designing a smooth trajectory that traverses a sequence of convex sets in minimum time, while satisfying given velocity and acceleration constraints. This problem is naturally formulated as a nonconvex program. To solve it, we propose a biconvex method that quickly produces an initial trajectory and iteratively refines it by solving two convex subproblems in alternation. This method is guaranteed to converge, returns a feasible trajectory even if stopped early, and does not require the selection of any line-search or trust-region parameter. Exhaustive experiments show that our method finds high-quality trajectories in a fraction of the time of state-of-the-art solvers for nonconvex optimization. In addition, it achieves runtimes comparable to industry-standard waypoint-based motion planners, while consistently designing lower-duration trajectories than existing optimization-based planners.

Primary

Paper arxiv.org

Standard

arXiv Abstract 2504.18978 arXiv PDF 2504.18978 arXiv HTML 2504.18978

Alternate

amazon.science amazon.science

Tags

  • Motion planning

  • Trajectory optimization

  • Convex optimization

  • Minimum-time planning

  • GCS

  • Bezier curves