Robotics: Science and Systems XXI

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

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

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.

Download:

Bibtex:

  
@INPROCEEDINGS{MarcucciT-RSS-25, 
    AUTHOR    = {Tobia Marcucci AND Mathew Halm AND William Yang AND Dongchan Lee AND Andrew Marchese}, 
    TITLE     = {{A Biconvex Method for Minimum-Time Motion Planning Through Sequences of Convex Sets}}, 
    BOOKTITLE = {Proceedings of Robotics: Science and Systems}, 
    YEAR      = {2025}, 
    ADDRESS   = {LosAngeles, CA, USA}, 
    MONTH     = {June}, 
    DOI       = {10.15607/RSS.2025.XXI.044} 
}