ADMM-based Continuous Trajectory Optimization in Graphs of Convex Sets
This work addresses trajectory optimization for robotics or autonomous systems in complex environments, representing an incremental improvement over existing decoupled approaches.
The paper tackles the problem of computing continuous trajectories in non-convex environments by developing a numerical solver based on ADMM, which jointly optimizes over discrete spatial and continuous temporal domains to discover superior trajectories with reliable convergence from naive initializations.
This paper presents a numerical solver for computing continuous trajectories in non-convex environments. Our approach relies on a customized implementation of the Alternating Direction Method of Multipliers (ADMM) built upon two key components: First, we parameterize trajectories as polynomials, allowing the primal update to be computed in closed form as a minimum-control-effort problem. Second, we introduce the concept of a spatio-temporal allocation graph based on a mixed-integer formulation and pose the slack update as a shortest-path search. The combination of these ingredients results in a solver with several distinct advantages over the state of the art. By jointly optimizing over both discrete spatial and continuous temporal domains, our method accesses a larger search space than existing decoupled approaches, enabling the discovery of superior trajectories. Additionally, the solver's structural robustness ensures reliable convergence from naive initializations, removing the bottleneck of complex warm starting in non-convex environments.