ADMM-based Continuous Trajectory Optimization in Graphs of Convex Sets

arXiv:2603.11335 · cs.RO · Submitted 2026-03-11 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: Today's paper: "ADMM-based Continuous Trajectory Optimization in Graphs of Convex Sets".

Dev: This paper presents a numerical solver for computing continuous trajectories in non-convex environments, denoted as ACTOR (ADMM-based Continuous Trajectory OptimizeR).

Rosa: First, who's behind it and why it matters.

Title and authors: Rosa: So we're diving into the specifics of the paper now, focusing on what they actually wrote in the introduction regarding "ADMM-based Continuous Trajectory Optimization in Graphs of Convex Sets." The authors are Lukas Pries, Jon Arrizabalaga, Zachary Manchester, and Markus Ryll.

Dev: I see their names on there; it sounds like a solid team tackling a problem that requires both mathematical rigor and strong engineering insight to get the ADMM setup right for continuous trajectories.

Taro: I'm curious what they are aiming to solve beyond just finding *a* trajectory, Rosa; are they trying to solve problems where the environment itself is constantly changing, like in a dynamic scene?

Rosa: They aren't just looking for one path in a static space; the title suggests their goal is to compute continuous trajectories within environments that are non-convex, which means they can navigate around obstacles that don't form simple convex shapes.

Dev: That’s what we deal with constantly, but usually, those problems force us into very slow solvers or highly simplified models because the constraints become too messy for standard methods to handle efficiently.

Taro: So their approach seems geared toward taking a problem that is fundamentally non-convex and providing a numerical solver that can output a continuous path as the answer, rather than just a set of discrete waypoints.

Rosa: Right, they are aiming for continuity in the path itself, which is crucial for smooth physical motion, not just connectivity between points.

Dev: And the ADMM method suggests they're breaking down that complex optimization into smaller problems that are easier to handle sequentially, which is a good engineering strategy when dealing with high-dimensional problems.

Taro: I wonder if this structured approach offers any inherent advantage over methods that might just use approximations, or if it’s purely about finding a better numerical solution for the same underlying math.

Rosa: The paper suggests it does more than just improve the numerical accuracy of existing methods; it proposes a new way to structure the entire optimization process by incorporating spatial and temporal decisions together.

Dev: That combined approach is what I’m most interested in because it addresses the inherent difficulty of coupling continuous dynamics with discrete geometric constraints in one cohesive mathematical framework.

Taro: So, their main contribution seems to be this specific combination: polynomial parameterization paired with a spatio-temporal allocation graph for constraint handling.

Rosa: Exactly, they use the polynomial parameterization to get that closed-form update for the primal problem, and then they use the graph structure to manage how those segments map onto the safe regions defined by those convex sets.

Dev: That combination is what allows them to jump past some of the limitations where traditional methods struggle with formulating smooth constraints against complex environments.

Taro: It’s about providing a more complete optimization framework for motion planning in challenging settings, which is important when you consider autonomous agents operating in unstructured real-world areas.

The paper's summary: Rosa: Now we look at the actual summary of "ADMM-based Continuous Trajectory Optimization in Graphs of Convex Sets" to really nail down what the authors claim they’ve achieved in practice. Essentially, they're describing their two main building blocks again.

Dev: They summarize it by saying they are parameterizing trajectories as polynomials, which lets them get a closed-form primal update for the minimum-control-effort problem. That seems like a huge efficiency gain right off the bat.

Taro: And then they introduce the second block, which is this spatio-temporal allocation graph based on a mixed-integer formulation, where the slack update becomes a shortest-path search through that graph.

Rosa: Exactly; it's about jointly optimizing over both the discrete spatial and continuous temporal domains, allowing them to access a larger search space than existing decoupled approaches. That’s the key benefit they highlight regarding discovery of superior trajectories.

Dev: So, they are effectively using that graph structure to manage the safety constraints by modeling the non-convex obstacle-free space as a union of convex sets, which is a major mathematical trick for making those constraints tractable.

Taro: That trick is powerful because it allows them to define safety constraints over these unions of convex sets without needing an exact, continuous representation of every single obstacle boundary at once.

Rosa: The paper emphasizes that this method also has structural robustness, which means they found that the solver converges reliably even from naive initializations, cutting out the need for complex warm starting procedures common in other solvers.

Dev: So they’ve essentially designed a system where the mathematical structure of the problem guides it toward a solution, making it less dependent on getting lucky with a good starting guess.

Taro: If that robustness is real, it means we might be able to deploy this solver in scenarios where we can't afford the heavy upfront computational cost of developing complex initialization routines for every new mission profile.

Rosa: That’s the practical implication: a more reliable and potentially faster way to generate feasible paths in non-convex spaces than what we have now.

The paper's improvements: Dev: Moving into the specific improvements they suggest, they focus on making two main building blocks work together effectively, particularly how they handle the constraints.

Taro: They detail how piecewise polynomial parameterization allows for expressing derivatives recursively, showing that you can construct the next segment's dynamics based on the previous one using a scaled Bernstein basis. That level of mathematical detail is impressive for ensuring smoothness across segment boundaries.

Rosa: And they enforce continuity constraints on those derivatives at the segment junctions, which ensures that when you stitch all these polynomial pieces together, the continuity requirement is met perfectly across the transition points.

Dev: Beyond that, they constrain the control points of each segment to stay within convex sets k, which directly enforces safety by ensuring each piece adheres to a certain geometric boundary.

Taro: They also introduce dynamic feasibility constraints by bounding each derivative control point based on the convex hull property of Bezier curves, effectively bounding velocity and acceleration bounds in a way that is tightly coupled with the trajectory segments.

Rosa: So they aren't just imposing safety constraints; they are actively enforcing physical limits on how fast the trajectory can change, which addresses a common issue in high-speed planning.

Dev: This coupling between segment definition and dynamic feasibility constraints is what makes this approach much stronger than methods where those dynamic limits are just tacked on afterwards.

Taro: I think this integrated way of handling safety and dynamics means that the solver inherently respects the physical limitations of the system as it searches for a solution, rather than treating them as external checks.

Rosa: That integration is what separates this work from previous attempts; they're not just adding features; they are weaving the physics directly into the optimization structure.

Conclusion: Dev: Wrapping up, it seems like the main conclusion of "ADMM-based Continuous Trajectory Optimization in Graphs of Convex Sets" is that this ADMM-based approach provides a solver for continuous trajectory optimization in non-convex environments by combining polynomial parameterization with a spatio-temporal allocation graph.

Taro: I think the biggest implication is that it gives us a structured way to tackle complex, non-convex path planning problems where standard methods get stuck in local minima by allowing joint optimization over spatial and temporal variables.

Rosa: And structurally, the solver’s robustness from naive initializations means we can plan trajectories in arbitrarily complex spaces without needing extensive warm starting information.

Dev: From an engineering standpoint, the closed-form primal update and structured iterations make it significantly faster than general nonlinear solvers for real-time applications where low latency is paramount.

Taro: I think the real impact will be seen as a more reliable tool for deploying AI systems in areas that were previously too geometrically intricate to plan safely.

Rosa: So, we’ve explored how this paper structures trajectory optimization using ADMM, and it seems like a solid piece of work for moving towards more robust path planning solutions.

Dev: And I think the ability to handle the dynamic feasibility constraints tightly coupled with segment definitions is a key feature that will make it very useful for our high-speed control loops.

Taro: Exactly; this method moves us closer to having AI systems that can navigate environments where geometry is highly complex without being limited by overly simplistic assumptions about the environment.

Rosa: It’s exciting to see this kind of work being published, and I think we have a lot more to discuss as we look at what comes next in the field.

Lukas Pries, Jon Arrizabalaga, Zachary Manchester, Markus Ryll

Autonomous Aerial Systems Lab at TU Munich · Department of Aeronautics and Astronautics at Massachusetts Institute of Technology

cs.RO

Submitted: 2026-03-11

Updated: 2026-09-29

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 83/100

The gist: This paper presents a numerical solver for computing continuous trajectories in non-convex environments, denoted as ACTOR (ADMM-based Continuous Trajectory OptimizeR).

Key concepts

ACTOR: ADMM-based Continuous Trajectory OptimizeR is the numerical solver presented in the paper. It computes continuous trajectories in non-convex environments by combining polynomial parameterization with a spatio-temporal allocation graph.
Polynomial Parameterization: This technique allows trajectories to be expressed as polynomials. This enables a closed-form update for the minimum-control-effort problem, which provides significant computational efficiency for trajectory optimization.
Spatio-temporal Allocation Graph: This graph structure is used based on a mixed-integer formulation. It manages safety constraints by modeling the non-convex obstacle-free space as a union of convex sets, allowing joint optimization over spatial and temporal domains.

Terminology

Actor — 18× in this paper · explained in 3 episodes
Robustness — 6× in this paper · explained in 5 episodes
Alternating Direction Method of Multipliers — 3× in this paper
Alternating Direction Method of Multipliers (ADMM) — 3× in this paper · explained in 2 episodes
Decoupling — 2× in this paper · explained in 2 episodes
Graph of Convex Sets — 2× in this paper
Higher-order derivatives — 2× in this paper · explained in 2 episodes
Accuracy — 1× in this paper · explained in 1 episode
Augmented Lagrangian — 1× in this paper
Benchmark — 1× in this paper · explained in 2 episodes
Computational overhead — 1× in this paper · explained in 2 episodes
Consistency — 1× in this paper · explained in 3 episodes
Hybrid System — 1× in this paper · explained in 2 episodes
Optimization-based Collision Avoidance — 1× in this paper
Topological Order — 1× in this paper · explained in 2 episodes

Summary

This paper presents a numerical solver for computing continuous trajectories in non-convex environments, denoted as ACTOR (ADMM-based Continuous Trajectory OptimizeR). The approach relies on a customized implementation of the Alternating Direction Method of Multipliers (ADMM) built upon two key components: first, parameterizing trajectories as polynomials to compute the primal update in closed form as a minimum-control-effort problem, and second, introducing the concept of a spatio-temporal allocation graph based on a mixed-integer formulation and posing the slack update as a shortest-path search. The combination of these ingredients results in a solver with several distinct advantages over existing 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.

The problem addressed is formulated as:

min

J(q) (efficiency) (1a)

subject to q(t) ∈ S (safety) (1b)

q ∈ D (feasibility) (1c)

q(0) = q0, q(T) = qT (boundary), (1d

where:

(a)

J(q): Minimum Control Effort, defined as a weighted sum of quadratic energy integrals that penalize the derivatives of the trajectory: J(q) = Xno i=1 αi Z T 0 q(i) (t)2 dt (2).

(b)

D: Dynamic Feasibility, requiring the trajectory q to be continuously differentiable and bounded up to a sufficiently high order nc, nb: D:= n q(t) q ∈ Cnc, q[nb] (t) ∈ B, ∀t ∈ [0, T] (3), where B is a convex bounded set.

(c)

S: Safety Constraints, represented as the union of convex sets: S:= (q(t) q(t) ∈ [k∈K Qk, ∀t ∈ [0, T]) (4), where Qk refers to a convex set k.

The method is structured around two main building blocks:

A. Trajectories as Piecewise Polynomials:

The trajectory q(t) is parameterized using a finite number of decision variables by dividing the trajectory into consecutive segments, each parameterized by an individual polynomial. A general M-segment polynomial trajectory p: [0, Ttot] 7→ R d with Ttot = PM m=1 Ti is defined as:

p(t) =



Pn i=0 c i 1 β i n (t/T1), t ∈ [0, T1], Pn i=0 c i 2 β i n (t/T2), t ∈ [0, T2],.... Pn i=0 c i M βi n (t/TM), t ∈ [TM].

where βi n(τ) = n i τ(1 − τ) n denotes the Bernstein basis of order n and t is scaled by the duration Tm to yield a standard Bezier curve with ´ τ ∈ [0, 1]. The i-th control point of the m-th segment of the Bezier curve is parameterized by ´ c i m ∈ R d.

Derivatives are expressed recursively:

p˙m(t) = nTm X−1 i=0 c i+1 m − c i m βi n−1 (t/Tm), for t ∈ [0, Tm], which itself represents a Bezier curve with ´ n control points c i m′ = n/Tm c i+1 m − c i m / βi n−1 (t/Tm) and basis βi n−1 (τ).

Continuity and Boundary Constraints are enforced by imposing continuity constraints on the derivatives at segment boundaries: p(j)m (Tm) = p(j)m+1(0), for all j ∈ 0,..., nc and m ∈ 0,..., M − 1.

Safety Constraints are enforced by constraining the control points of each segment to lie within a convex set k: pm(t) ∈ Qk → c i m i∈[0,n] ∈ Qk.

Dynamic Feasibility Constraints are enforced by bounding each derivative control point: p(j)m (t) ∈ Bj → bj ≤ (c i m) (j) ≤ bj, for all i ∈ 0,..., n − j and j ∈ 0,..., n, effectively constraining each derivative control point to remain in the bounded set B j:= x ∈ R d bj ≤ x ≤ bj.

Improvements for AI systems

Here are the specific improvements that can be made to AI systems by implementing the ACTOR solver, and what these improved systems can achieve:

The implementation of the ACTOR solver enables a transition from decoupled, locally optimal planning methods to a unified framework capable of finding globally superior trajectories in highly constrained, non-convex environments.

Here are the specific improvements and capabilities:

mathbfRobustness to Naive Initialization (Elimination of Local Minima Bottleneck):

ACTOR's structural robustness ensures reliable convergence from naive initializations, removing the bottleneck of complex warm starting required by traditional Newton-type methods (like IPOPT or SNOPT).

The improved AI system can plan trajectories in arbitrarily complex, non-convex spaces (e.g., cluttered mazes) without requiring prior knowledge of a feasible corridor or a good starting guess.

mathbfGlobal Optimality through Joint Discrete and Continuous Search:

By jointly optimizing over both the discrete spatial allocation (which segment belongs to which convex set) and the continuous temporal domain, ACTOR accesses a larger search space than existing decoupled approaches.

The improved AI system can discover globally superior trajectories that avoid holistically suboptimal performance resulting from partitioning the search space (e.g., finding paths that require non-intuitive sequence of spatial maneuvers).

mathbfEfficient Computation via Closed-Form Primal Updates:

The formulation parameterizing trajectories as piecewise polynomials allows the primal update to be computed in closed form as a minimum-control-effort problem, which is factorization-free.

The improved AI system achieves significantly reduced per-iteration computational overhead compared to general NLP solvers, enabling real-time or near real-time trajectory optimization for complex systems.

mathbf Scalability and Efficiency for Large Problems:

ACTOR exhibits per-iteration complexity linear in the number of sets and trajectory segments, scaling substantially better than existing methods where runtimes grow combinatorially or exponentially (as seen in comparison with MIQP/NLP solvers).

The improved AI system can handle large-scale navigation tasks involving numerous obstacles or high-order dynamic constraints (e.g., quadrotor minimum-snap planning under strict acceleration limits) that would be intractable for current state-of-the-art trajectory optimization pipelines.

mathbf Flexibility in Constraint Encoding (Handling Non-Convex Geometry):

The method leverages a mixed-integer formulation and a spatio-temporal allocation graph to model the non-convex safety constraints as a union of convex sets, allowing for flexible assignment of segments to safe regions.

The improved AI system can operate effectively on naive or simple decompositions of free space (point clouds) without needing an additional, often inaccurate, optimization step for free-space decomposition around an initial path.

mathbf Integration of Higher-Order Dynamic Feasibility:

ACTOR explicitly incorporates higher-order dynamic feasibility constraints (bounded velocity and acceleration) directly into the control point bounds derived from the convex hull property of Bezier curves.

The improved AI system can plan for aggressive, high-speed maneuvers (like minimum-snap trajectories) while guaranteeing that the resulting trajectory respects strict physical limits on its derivatives, a capability often lacking in methods relying solely on corridor selection.

In summary, the improved AI systems powered by ACTOR can perform:

High-fidelity motion planning in cluttered 3D environments (e.g., drone navigation).
Discovery of globally optimal flight paths that are physically feasible and dynamically smooth under strict acceleration/velocity limits.
Rapid deployment of trajectory optimization for autonomous systems by leveraging fast, structured ADMM iterations instead of slow general-purpose NLP solvers.