REVIEW 4 major objections 6 minor 22 references
TOP: Trajectory Optimization via Parallel Optimization towards Constant Time Complexity
T0 review · 4 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read The paper claims that splitting a trajectory into independently optimized segments under consensus constraints reduces the per-iteration cost of trajectory optimization from $O(N)$ to $O(1)$ in the number of segments.
desk verdict Solid per-iteration O(1) decomposition, but the constant-time total claim is oversold and the stopping criterion scaling is the main load-bearing gap. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the Consensus Alternating Direction Method of Multipliers (CADMM) applied per segment. Each segment keeps its own polynomial coefficients as local variables; a consensus variable $z_i$ at each boundary is updated as the average of neighboring segment boundary derivatives (Eq. 20b), and the dual variables $u_i$, $v_i$, $w_i$ pull the local solutions toward consensus. The per-segment update of coefficients in Eq. (20a) inverts a matrix whose size depends only on the local polynomial degree and the local constraint count, not on the global number of segments $N$; this is what makes the per-iteration cost independent of $N$. Inequality constraints are converted into indicator-function terms and resolved by closed-form projections: a non-negativity projection for linear constraints and a Euclidean-ball projection for quadratic constraints, with a scalar rescaling of the projected vector.
What would settle it
Run the proposed algorithm with a fixed stopping tolerance that is not scaled by $N$, and measure the number of iterations to convergence for $N = 100$, $1000$, and $10000$ segments; if the iteration count grows with $N$, the total time complexity is not constant even though each iteration is $O(1)$.
Extended reading notes
Core claim
The central claim is that the constrained minimum-control-effort trajectory optimization problem, traditionally solved with methods whose per-iteration cost grows linearly (or worse) with the number of trajectory pieces, can be reformulated so that each iteration costs $O(1)$ per piece and $O(1)$ total with respect to $N$ on parallel hardware. The reformulation introduces a consensus variable at each shared boundary, so that continuity up to derivative order $d-1$ is enforced by averaging adjacent boundary states rather than by a global linear system. Every segment then solves a small local quadratic program, and inequality constraints are handled either by closed-form projections (linear and quadratic constraints) or by an L-BFGS numerical solve (general convex constraints). The authors demonstrate in simulation and on a real quadrotor that a trajectory with roughly one hundred segments can be optimized more than ten times faster than the GCOPTER baseline, and that on a GPU a one-thousand-segment trajectory can be optimized in tens of milliseconds.
Load-bearing premise
The claim of constant total time rests on the assumption that the number of CADMM iterations needed to converge does not grow with the number of segments; the paper does not measure this, and its stopping tolerance is relaxed proportionally to $N$, which could mask such growth.
Editorial extensions
If this is right
- Per-iteration cost becomes independent of the number of trajectory segments, so the bottleneck in large-scale planning shifts to memory bandwidth and parallel core count rather than to the optimization problem size.
- On GPU hardware, trajectories with thousands of segments can be optimized in well under a second, enabling online re-planning of long-horizon paths for aerial robots.
- High-order continuity up to derivative order $d-1$ is preserved at segment boundaries, so the method remains usable for agile multicopter control where smoothness is critical.
- The closed-form projection for quadratic constraints gives a fast way to enforce velocity or acceleration limits without adding auxiliary optimization variables.
Reading between the lines
- Editorial inference: The $O(1)$ claim is per-iteration; the total runtime is only constant if the number of iterations to the stopping tolerance does not grow with $N$, a condition the paper does not establish.
- Editorial inference: The closed-form projection for quadratic constraints (Eq. 14) could be reused for any convex set with a known Euclidean projection, so the approach may extend to ellipsoidal or polytopic safety regions without extra solver machinery.
- Editorial inference: Because the stopping tolerance in Eq. (23) is scaled by $N$, a fair constant-time test would fix the tolerance and report iteration counts across $N$; otherwise a looser tolerance can hide linear growth in iterations.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes TOP, a trajectory optimization framework that splits a differentially flat trajectory into N polynomial segments and solves the resulting consensus problem with the Consensus ADMM algorithm. Each segment is updated in parallel by solving a local dense linear system whose dimension depends only on the local polynomial degree and the local constraint count, not on N, which gives an O(1) per-iteration parallel complexity. The paper provides closed-form updates for linear and quadratic inequality constraints, a numerical L-BFGS variant for general convex constraints, CPU and GPU implementations, benchmark comparisons with GCOPTER, and a real-world quadrotor experiment with a 1000-segment trajectory. The central claims are a reduction from O(N) to O(1) per iteration and, in the conclusion and title, a move toward constant total time complexity.
Significance. The per-iteration complexity contribution is real and well supported by the update equations: Eq. (20a) is a local dense solve of size m(d+1), and the consensus, slack, projection, and dual updates are all local and parallelizable. If the total iteration count is independent of N, the GPU deployment would be a practically important step for long-horizon trajectory optimization. The paper also ships explicit closed-form projection rules and reports real-world validation, which are strengths. However, the total-complexity claim is not established, and the central update equation as printed contains a factor error relative to the augmented Lagrangian, so the manuscript needs substantive revision before the claims can be accepted.
major comments (4)
- [Sec. III-D3, Eq. (23), and Fig. 5] The O(1)-per-iteration claim is supported by the local update structure, but the paper's stronger conclusion of "constant time complexity" requires the number of CADMM iterations K to be independent of N. This is not shown: Sec. III-D2 only states convergence as k goes to infinity, with no bound or empirical study of K versus N. The stopping criterion in Eq. (23) is also problematic for the experimental evidence: Er = Ed = N E, while the residuals in Eqs. (21)-(22) are norms of vectors with O(N) components. For bounded per-boundary error, those norms grow as sqrt(N), so the N-scaled tolerance allows the per-boundary error to grow as sqrt(N) as N increases. The flat GPU runtime in Fig. 5 may therefore reflect progressively looser convergence rather than constant iteration count. The authors should report iteration counts, final per-boundary residuals, and wall-clock time under a fixed per-boundary tolerance, and should soften the conclusion if K grows with N.
- [Sec. III-D1, Eq. (20a)] Equation (20a) is not the minimizer of the augmented Lagrangian in Eq. (5). Minimizing L_i with respect to c_i gives (2 eQ + ρ fM^T fM + ρ A^T A + ρ Σ Av^T Av)c = ρ fM^T(z - u) + ρ A^T(b - s - v) + ρ Σ Av^T(φ - w). As printed, the right-hand side of Eq. (20a) omits the factor ρ multiplying fM^T(z-u), A^T(b-s-v), and Av^T(φ-w). If the implementation follows the printed formula, the algorithm is not the advertised ADMM and the fixed-point equations do not match the optimality conditions; if the implementation includes ρ, the formula is a typo. This issue is load-bearing because Eq. (20a) is the core local update used in all experiments, and the authors should correct the formula and verify the implemented version against the derivation.
- [Sec. III-D1 and Sec. III-D2] The local update in Eq. (20a) is an overdetermined least-squares problem: for polynomial degree 5 and d = 5 in the consensus notation, the matrix fM imposes m * 2d = 10m continuity constraints on m(d+1) = 6m coefficients. The statement in Sec. III-D1 that "a solution exists due to the relaxation of the constraints in the augmented Lagrangian term" is too vague: the linear solve always has a least-squares solution, but it does not necessarily satisfy the consensus constraints exactly at any finite iteration, and the fixed-point feasibility depends on the convergence of the ADMM iterations. In addition, the paper conflates two uses of the symbol d: the polynomial degree in Eq. (18) is set to 5, while eβ and fM include derivatives up to order d-1 = 4. The claim in Sec. III-D2 that continuity is enforced up to order 2p-1 = 5 for p = 3 is therefore not consistent with the published definitions; the authors should clarify the continuity order actually enforced and provide a precise solution-existence argument.
- [Sec. IV-A1, Table I] The benchmark comparison in Table I reports objective costs that differ by roughly a factor of five between the proposed method (about 34-64) and GCOPTER (about 179-297), even though the authors state that both methods use the same constraints and initial values. If both methods converge to the same constrained minimum-control-effort problem, this discrepancy is surprising and suggests that either the problems are not identical or one of the methods has not converged to the reported tolerance. The paper should report constraint violations, stopping criteria, and iteration counts for both methods, not only time and objective cost, so that the claimed superiority in both efficiency and smoothness can be assessed fairly.
minor comments (6)
- [Algorithm 1, line 3] The while condition is written as "while ||r_p||_2 < E_r^2 and ||r_d||_2 < E_d^2", which would exit immediately when residuals are small, i.e., it stops in the desired terminal region; the condition should be the negation, typically "while ||r_p||_2 >= E_r^2 or ||r_d||_2 >= E_d^2".
- [Table II] The row for Fixedρ(100) contains the value "237789.0375e−13", which appears to be a formatting error; the number of iterations for this row should be reported clearly.
- [Sec. IV-A2] The similarity metric uses M for the number of evaluation samples, while M is also used in Sec. III-D1 for the number of sample points per segment; this reuse of notation is confusing and should be disambiguated.
- [References] References [10] and [14] are the same LaValle technical report and should be consolidated to avoid duplication.
- [Sec. III-C3, Eq. (15)] The definition g(x) = max{0, g0(x)}^2 should be written with braces as max{0, g0(x)}^2 to avoid ambiguity in the order of operations.
- [Sec. II-B] The sentence "the running speed of the algorithm framework has not been fully explored" is vague; specify whether this refers to theoretical complexity, wall-clock time, or both.
Circularity Check
No circular derivation: the O(1)-per-iteration update is local by construction; self-citations are not load-bearing. The N-scaled stopping tolerance is a correctness risk for the total-time claim, not a circular reduction.
full rationale
The central per-iteration complexity claim is self-contained and follows directly from the update equations. In Eq. (20a), the matrix being inverted has fixed size m(d+1), depending only on the local polynomial degree and local constraint count, not on the number of segments N. Equations (20b)-(20g) are local updates for consensus, dual, slack, and projection variables, so each CADMM iteration costs O(1) per segment in parallel. There is no hidden equivalence to an input here: the O(1) property is read off the algorithm structure, not assumed into existence. The paper's occasional references to the authors' prior GCOPTER [6] and FIRI [22] are not load-bearing for this claim: the QP subproblem is strongly convex because of the positive quadratic terms in Eq. (20a), and convergence relies on the external ADMM framework of Boyd et al. [8]. The self-citations are therefore minor and contextual. The one substantive concern is the stopping criterion in Section III-D3, Eq. (23), where Er = Ed = N E. Since the primal residual in Eq. (21) concatenates N-1 per-boundary gaps, its Euclidean norm grows like sqrt(N) for a fixed per-gap error, so an N E threshold allows per-boundary errors to grow like sqrt(N) as N increases. This means the flat GPU runtime in Fig. 5 may partly reflect an increasingly loose stopping tolerance rather than an N-independent number of iterations. However, this is a missing-support issue for the total-constant-time conclusion, not a circular reduction: the per-iteration O(1) claim remains valid regardless of how many iterations are needed. The paper also honestly notes in Section IV-A1 that CPU time increases with N, 'which does not show the constant time complexity.' Overall, no derivation step is equivalent to its own input by construction.
Assumptions & free parameters
free parameters (5)
- Initial penalty parameter rho0 =
1
- Adaptive rho schedule constants (mu, tau_incr, tau_decr) =
mu=10, tau_incr=1.1, tau_decr=1.1
- Stopping tolerance E =
0.05
- Number of sample points per segment M for velocity constraints =
not specified
- Polynomial degree d =
5
assumptions (5)
- domain assumption Multicopter dynamics are differentially flat in the flat output sigma(t).
- domain assumption All inequality constraints used in the closed-form variant are convex (linear or quadratic).
- standard math ADMM converges for convex consensus problems.
- domain assumption The GCOPTER optimality conditions [6] guarantee existence of an optimal solution in the enlarged piecewise-polynomial solution space.
- domain assumption The O(1) per-iteration complexity is measured under a parallel model with at least N processing units and O(1) neighbor communication.
Cite this review
Pith. "Pith review of TOP: Trajectory Optimization via Parallel Optimization towards Constant Time Complexity." pith.science (2026). https://pith.science/paper/3PEOJ62L
@misc{pith2026250710290,
author = {Pith},
title = {Pith review of: TOP: Trajectory Optimization via Parallel Optimization towards Constant Time Complexity},
year = {2026},
howpublished = {\url{https://pith.science/paper/3PEOJ62L}},
note = {Machine review of arXiv:2507.10290}
}
read the original abstract
Optimization has been widely used to generate smooth trajectories for motion planning. However, existing trajectory optimization methods show weakness when dealing with large-scale long trajectories. Recent advances in parallel computing have accelerated optimization in some fields, but how to efficiently solve trajectory optimization via parallelism remains an open question. In this paper, we propose a novel trajectory optimization framework based on the Consensus Alternating Direction Method of Multipliers (CADMM) algorithm, which decomposes the trajectory into multiple segments and solves the subproblems in parallel. The proposed framework reduces the time complexity to O(1) per iteration to the number of segments, compared to O(N) of the state-of-the-art (SOTA) approaches. Furthermore, we introduce a closed-form solution that integrates convex linear and quadratic constraints to speed up the optimization, and we also present numerical solutions for general inequality constraints. A series of simulations and experiments demonstrate that our approach outperforms the SOTA approach in terms of efficiency and smoothness. Especially for a large-scale trajectory, with one hundred segments, achieving over a tenfold speedup. To fully explore the potential of our algorithm on modern parallel computing architectures, we deploy our framework on a GPU and show high performance with thousands of segments.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
J. T. Betts, Practical methods for optimal control and estimation using nonlinear programming. SIAM, 2010
work page 2010
-
[2]
Flatness and defect of non-linear systems: introductory theory and examples,
M. Fliess, J. L ´evine, P. Martin, and P. Rouchon, “Flatness and defect of non-linear systems: introductory theory and examples,” International journal of control , vol. 61, no. 6, pp. 1327–1361, 1995
1995
-
[3]
Minimum snap trajectory generation and control for quadrotors,
D. Mellinger and V . Kumar, “Minimum snap trajectory generation and control for quadrotors,” in IEEE international conference on robotics and automation. IEEE, 2011, pp. 2520–2525
work page 2011
-
[4]
B. Mu and P. Chirarattananon, “Trajectory generation for underactuated multirotor vehicles with tilted propellers via a flatness-based method,” in 2019 IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM). IEEE, 2019, pp. 1365–1370
work page 2019
-
[5]
Finding locally optimal, collision-free trajectories with sequential con- vex optimization
J. Schulman, J. Ho, A. X. Lee, I. Awwal, H. Bradlow, and P. Abbeel, “Finding locally optimal, collision-free trajectories with sequential con- vex optimization.” in Robotics: science and systems , vol. 9, no. 1. Berlin, Germany, 2013, pp. 1–10
work page 2013
-
[6]
Geometrically constrained tra- jectory optimization for multicopters,
Z. Wang, X. Zhou, C. Xu, and F. Gao, “Geometrically constrained tra- jectory optimization for multicopters,” IEEE Transactions on Robotics , vol. 38, no. 5, pp. 3259–3278, 2022
2022
-
[7]
Trajectory splitting: A distributed formulation for collision avoiding trajectory optimization,
C. Wang, J. Bingham, and M. Tomizuka, “Trajectory splitting: A distributed formulation for collision avoiding trajectory optimization,” in 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2021, pp. 8113–8120
work page 2021
-
[8]
Distributed optimization and statistical learning via the alternating direction method of multipliers,
S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein et al., “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Foundations and Trends® in Machine learning , vol. 3, no. 1, pp. 1–122, 2011
2011
Show all 22 references
-
[9]
Ara*: Anytime a* with provable bounds on sub-optimality,
M. Likhachev, G. J. Gordon, and S. Thrun, “Ara*: Anytime a* with provable bounds on sub-optimality,” Advances in neural information processing systems, vol. 16, 2003
2003
-
[11]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms. MIT press, 2022
2022
-
[12]
Online graph pruning for pathfinding on grid maps,
D. Harabor and A. Grastien, “Online graph pruning for pathfinding on grid maps,” in Proceedings of the AAAI conference on artificial intelligence, vol. 25, no. 1, 2011, pp. 1114–1119
2011
-
[13]
Prob- abilistic roadmaps for path planning in high-dimensional configuration spaces,
L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Prob- abilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Transactions on Robotics and Automation , vol. 12, no. 4, pp. 566–580, 1996
1996
-
[14]
Rapidly-exploring random trees: A new tool for path planning,
S. LaValle, “Rapidly-exploring random trees: A new tool for path planning,” Research Report 9811 , 1998
1998
-
[15]
S. M. LaValle, Planning algorithms. Cambridge university press, 2006
2006
-
[16]
Gpops-ii: A matlab software for solving multiple-phase optimal control problems using hp-adaptive gaussian quadrature collocation methods and sparse nonlinear programming,
M. A. Patterson and A. V . Rao, “Gpops-ii: A matlab software for solving multiple-phase optimal control problems using hp-adaptive gaussian quadrature collocation methods and sparse nonlinear programming,” ACM Transactions on Mathematical Software (TOMS) , vol. 41, no. 1, pp. ...
2014
-
[17]
d{2} slam: Decentralized and distributed collaborative visual-inertial slam system for aerial swarm,
H. Xu, P. Liu, X. Chen, and S. Shen, “ d{2} slam: Decentralized and distributed collaborative visual-inertial slam system for aerial swarm,” IEEE Transactions on Robotics , 2024
2024
-
[18]
Introducing multi-convexity in path constrained trajectory optimization for mobile manipulators,
A. K. Singh, A. Ahonen, R. Ghabcheloo, and A. Mueller, “Introducing multi-convexity in path constrained trajectory optimization for mobile manipulators,” in 2020 European Control Conference (ECC) . IEEE, 2020, pp. 1178–1185
2020
-
[19]
Long-horizon motion planning via sampling and segmented trajectory optimization,
J. Leu, M. Wang, and M. Tomizuka, “Long-horizon motion planning via sampling and segmented trajectory optimization,” in 2022 European Control Conference (ECC). IEEE, 2022, pp. 538–545
2022
-
[20]
Distributed convex optimization with many convex constraints,
J. Giesen and S. Laue, “Distributed convex optimization with many convex constraints,” arXiv preprint arXiv:1610.02967 , 2016
2016 arXiv
-
[21]
On the limited memory bfgs method for large scale optimization,
D. C. Liu and J. Nocedal, “On the limited memory bfgs method for large scale optimization,” Mathematical programming, vol. 45, no. 1, pp. 503–528, 1989
1989
-
[22]
Fast iterative region inflation for computing large 2-d/3-d convex regions of obstacle-free space,
Q. Wang, Z. Wang, M. Wang, J. Ji, Z. Han, T. Wu, R. Jin, Y . Gao, C. Xu, and F. Gao, “Fast iterative region inflation for computing large 2-d/3-d convex regions of obstacle-free space,” arXiv preprint arXiv:2403.02977, 2024
2024 arXiv
-
[23]
Fast-lio2: Fast direct lidar- inertial odometry,
W. Xu, Y . Cai, D. He, J. Lin, and F. Zhang, “Fast-lio2: Fast direct lidar- inertial odometry,” IEEE Transactions on Robotics , vol. 38, no. 4, pp. 2053–2073, 2022
2022
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.