A Biconvex Method for Minimum-Time Motion Planning Through Sequences of Convex Sets
Tobia Marcucci, Mathew Halm, William Yang, Dongchan Lee, Andrew D. Marchese · 2025
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-theart 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.