{"id":"1b404586-e465-49b8-aa79-b45bb6585e71","arxiv_id":"2504.18978","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A biconvex alternating method computes near time-optimal, dynamically feasible trajectories through sequences of convex sets, with completeness and anytime guarantees.","lead":"This paper presents SCS, a fast optimization method that plans minimum-time robot trajectories through a fixed sequence of convex safe zones. It alternates between two convex subproblems so it always returns a usable trajectory quickly, and tests show it beats general-purpose solvers in speed with near-identical quality.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The completeness/an anytime guarantee depends on Assumption 1's strict positivity; if an optimal trajectory touches a safe set at a point, the S_i=1/T_i change of variables breaks and the proposed lower-bound workaround is unproven.","rationale":"The paper's central contribution is a complete, anytime, parameter-light biconvex method for the fixed-sequence minimum-time problem. Under Assumption 1, the argument is sound: both subproblems (11) and (15) are genuine convex restrictions (the acceleration linearizations underestimate T_i^2 and 1/S_i), the current trajectory is always feasible for the next subproblem, so costs are monotone non-increasing and feasibility is preserved. The initialization is feasible for K≥3, giving the anytime property. The experiments are extensive, honest about heuristic optimality, and the code is released. The only substantive caveat is Assumption 1. It is explicitly stated and echoed in §IX, but it is a real restriction: zero traversal times are allowed by the original problem (1) and are natural when a set is only touched at a point. The proposed lower-bound patch is not analyzed, so the completeness guarantee does not automatically extend to that regime. Because the authors clearly scope the method and disclose the limitation, this does not change the overall accept verdict; it does mean the abstract's unconditional phrasing should ideally carry the assumption. The reader's weakest-assumption analysis correctly captures this, so we agree.","tokens_in":17736,"tokens_out":17437,"duration_ms":178954,"concrete_test":"Build a minimal 2D instance with I=3 axis-aligned boxes where Q1∩Q2∩Q3 is nonempty and the straight line from qinit to qterm passes through that triple intersection, so the true time-optimal trajectory has T_2=0 (it only touches Q2 at one point). Run SCS with the suggested positive lower bound on T_2 and compare the resulting duration with SNOPT/IPOPT on the original problem (1). If SCS's duration is strictly larger, or the modified problem becomes infeasible, the completeness claim is confirmed to depend on Assumption 1 and the lower-bound workaround is not a free repair.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Assumption 1 (§II-B) is load-bearing. The method's core change of variables S_i=1/T_i in the fixed-transition-points subproblem (15) requires every traversal time T_i to be strictly positive. Assumption 1 (qinit∉Q2, qterm∉Q_{I-1}, and Qi∩Q_{i+1}∩Q_{i+2}=∅) is exactly what guarantees this for all feasible trajectories. If it fails, an optimal trajectory can touch a safe set at a single instant (T_i=0), S_i becomes infinite, and subproblem (15) is not well posed. The paper's proposed remedy—an artificial lower bound on traversal times (§IX)—is heuristic: no theorem shows the modified method remains complete or anytime, and no bound is given on the induced suboptimality. The abstract and the paper's headline claims state completeness and anytime behavior without this qualification, so the guarantee is narrower than advertised. All experiments satisfy Assumption 1, so the numerics do not probe this boundary; a practical instance with overlapping safe sets (common in corridor decompositions) could exhibit T_i=0 and fall outside the proven guarantees.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes SCS, an alternating convex-optimization algorithm for the minimum-time motion-planning problem of traversing an ordered sequence of convex sets while respecting convex velocity and acceleration constraints. The authors reformulate the nonconvex infinite-dimensional problem using per-set time scaling, derive two convex subproblems by fixing either transition velocities or transition points and underestimating the time-dependent terms with tangent lines, and initialize the method with a polygonal trajectory. The paper claims monotone convergence, anytime feasibility, no line-search or trust-region parameters, and empirically reports faster runtimes than SNOPT and IPOPT and lower-duration trajectories than trust-region and waypoint baselines, including a two-robot package-transfer benchmark.","tokens_in":17952,"tokens_out":18166,"duration_ms":179589,"significance":"The manuscript is a solid, clearly written contribution to a practical problem. Its strengths include a transparent derivation from elementary convex analysis, where every iterate is feasible by construction and no step-size tuning is required; a fully specified finite-dimensional Bezier implementation in Appendix A; reproducible code; and systematic experiments across problem size, facet count, dimension, and polynomial degree. If the claims hold, the method offers a parameter-light, anytime alternative to nonconvex trajectory optimization within its scope. The principal caveat is that the formal guarantees rely on Assumption 1, which rules out zero traversal times; this is acknowledged in the body but not in the abstract.","major_comments":[{"comment":"The completeness and anytime guarantees are proven only under Assumption 1, which ensures strictly positive traversal times T_i. The reformulation in (15) uses S_i = 1/T_i, so it is not well posed when some optimal traversal time is zero. The abstract states 'guaranteed to converge, returns a feasible trajectory even if stopped early' without this qualification, and the limitations paragraph in §IX proposes an artificial lower bound on traversal times without a proof that the modified method remains complete or anytime, or a bound on the induced suboptimality. I recommend qualifying the abstract (e.g., 'under a mild nondegeneracy assumption') and either analyzing the lower-bound variant or explicitly labeling it as a heuristic.","section":"§II-B, §IX, abstract"},{"comment":"The statement 'SCS is guaranteed to converge monotonically' is used to support the abstract's 'guaranteed to converge.' The proof in §VIII-A shows only that the objective values are nonincreasing and bounded below; it does not establish convergence of the trajectory iterates to a limit or to a stationary point. Since the stopping criterion is a relative-decrease tolerance, the sense of 'converge' should be stated precisely to avoid overstating the theoretical result.","section":"§VIII-A"}],"minor_comments":[{"comment":"The phrases 'runtimes increase by 3060', 'grows by 210', 'by 17.6', and 'by 9.9' are ambiguous; they should be written as 'by a factor of 30–60', 'by a factor of 2–10', etc.","section":"§X-B"},{"comment":"The variable r_i is used in (12) but defined only indirectly as ˙r_i = ˙q_i/T_i; please state explicitly that r_i = q_i/T_i before (12).","section":"§V"},{"comment":"The anytime claim should specify that feasibility is guaranteed at iteration boundaries, not during the solve of a convex subproblem, since stopping mid-solve does not necessarily provide a feasible trajectory.","section":"§VIII-A"},{"comment":"The phrase 'forces our trajectory to cover a nonzero distance within each safe set' is imprecise; Assumption 1 actually guarantees a positive traversal time, which is the property used in the change of variables.","section":"§II-B"}],"recommendation":"major_revision","confidential_remarks":"The manuscript fits the journal's scope and the technical development is sound. The main revision is to align the stated guarantees with the assumptions under which they are proven, particularly in the abstract and the discussion of the artificial lower-bound workaround."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is a solid, practical algorithm. The biconvex decomposition—fixing transition points, then transition velocities, with each subproblem a conservative convex restriction built from tangent underestimators—is new and works well. It avoids line search and trust-region parameters, the subproblems are banded, and the completeness/anytime claims follow directly from the construction. The math in the paper is transparent, the implementation is in the appendix, and the code is released. The benchmarks against SNOPT and IPOPT are honest: SCS is usually within 1–3% of the nonconvex solvers' cost, often an order of magnitude faster, and the runtime scaling plots are credible.\n\nNow the soft spot, which the stress-test note points to correctly. The change of variables Si = 1/Ti in subproblem (15) requires every traversal time to be strictly positive. Assumption 1 is exactly what guarantees that, and it is load-bearing. If an optimal trajectory touches a safe set at a single instant, Ti = 0, Si blows up, and the method as proven does not apply. The paper acknowledges this in §IX and suggests adding an artificial lower bound on traversal times, but gives no theorem that the modified method stays complete or any bound on the induced suboptimality. The abstract's unqualified \"guaranteed to converge\" should carry the positivity assumption, and all experiments satisfy Assumption 1, so the boundary case is untested. That is a genuine caveat, but it is disclosed, not hidden. Readers who encounter corridor decompositions with overlapping safe sets should be aware of it.\n\nThe convergence proof is informal—monotone decrease, no stationarity guarantee—but that is typical for a multi-convex method and the authors say so. The citation pattern is clean: self-citations to [28] are for a baseline and a feasibility construction reproduced in Proposition 1, and the benchmarks use external solvers. No circularity to worry about.\n\nWho is this for? Robotics researchers and practitioners wanting a CPU-only, reliable, near-optimal motion planner with no tuning knobs, and anyone interested in biconvex design templates for nonconvex trajectory optimization. It deserves a serious referee. A careful review should ask the authors to add the positivity condition to the abstract and to tighten the discussion of the lower-bound workaround. I would bring this to the reading group and would likely cite it in future work.","headline":"SCS is a genuinely useful biconvex planner with transparent math and honest limitations; the strict-positivity assumption is real but disclosed, and the paper deserves a serious referee.","tokens_in":18477,"tokens_out":2526,"would_cite":true,"duration_ms":25610,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A biconvex alternating scheme solves minimum-time motion planning through convex sets, returning complete, anytime, near-optimal trajectories without tuning.","keywords":["motion planning","minimum-time trajectory","biconvex optimization","convex restriction","Bézier curves","sequence of convex sets","anytime algorithm","trajectory optimization"],"falsifier":"Take a one-dimensional or two-dimensional corridor satisfying Assumption 1 whose true time-optimal trajectory is known from dynamic programming or bang-bang analysis; run SCS with high Bézier degree and a tight tolerance (for example $\\varepsilon=10^{-4}$) and measure the duration gap and whether every early-stopped iterate satisfies all constraints, since a gap clearly above the few percent reported, a non-monotone cost sequence, or an infeasible early iterate would contradict the central claims.","tokens_in":17557,"feed_emoji":"⏱","tokens_out":6538,"duration_ms":68237,"temperature":0.7,"pith_summary":"This paper aims to show that minimum-time motion planning through a fixed sequence of convex sets, a nonconvex problem because trajectory shape and timing are coupled, can be solved reliably by alternating two convex subproblems. The proposed method, SCS, keeps either the transition points or transition velocities fixed at each step, and each subproblem is a conservative convex approximation of the original problem, so every iteration produces a feasible trajectory whose duration is no worse than before. The authors claim this makes the algorithm complete (it always finds a feasible trajectory), anytime (a feasible trajectory is available if stopped early), and free of line-search or trust-region parameters. On benchmarks, SCS returns trajectories within roughly 1–3% of the duration found by state-of-the-art nonconvex solvers in a fraction of their runtime, and it designs lower-duration plans than waypoint and trust-region alternatives on a warehouse package-transfer task. If these claims hold, robot systems that need smooth, fast, reliable motions can avoid brittle solver tuning and feasibility failures in online operation.","feed_headline":"Biconvex method plans min-time robot motions in milliseconds","feed_subtitle":"Alternating two convex subproblems yields complete, anytime, near-optimal paths in a fraction of nonconvex-solver time.","key_machinery":"The carrying mechanism is a pair of convex restrictions of one nonconvex program. In the fixed-transition-velocity subproblem, velocity continuity becomes linear and the acceleration set $T_i^2\\mathcal{A}$ is replaced by the tangent underestimate $\\bar T_i(2T_i-\\bar T_i)\\mathcal{A}$ around the nominal traversal time. In the fixed-transition-point subproblem, the trajectory inside each set is reparameterized by reciprocals $S_i=1/T_i$ and scaled position functions $r_i=q_i/T_i$, which makes velocity constraints convex and leaves the acceleration constraint as the only nonconvexity; it is then relaxed by the analogous underestimate $\\bar T_i(2-\\bar T_i S_i)\\mathcal{A}$. Each subproblem is feasible whenever the current trajectory is feasible and yields a trajectory of no greater duration, which is what makes full-step alternation, monotone convergence, completeness, and the anytime property possible. Bézier curves with their convex-hull property supply the finite-dimensional implementation.","core_discovery":"The paper's central claim is that the minimum-time problem can be solved by biconvex alternation in a way that is complete and anytime, even though the full problem is nonconvex. The key fact is that fixing either the transition points $q(t_i)$ or the transition velocities $\\dot q(t_i)$ makes the remaining problem convex, up to a conservative linearization of the acceleration constraint that underestimates $T_i^2$ (or $1/S_i$) at the current traversal times. Because each convex subproblem is a restriction rather than an approximation that can leave feasibility, SCS can take full steps toward their optima without a line search or trust region; the duration decreases monotonically and any intermediate iterate is feasible. The authors report worst-case duration gaps of about 3.2% against nonconvex solvers on their test battery, with typical gaps near 0.1–1.2% when the stopping tolerance is tightened, and they show that the same package-transfer task completes 28% faster than the trust-region baseline and 50% faster than a waypoint planner.","pith_inferences":["The same convex-restriction pattern should carry over to fixed-final-time costs that penalize velocity and acceleration, as the paper hints; the reciprocal-time change of variables is not specific to minimizing total time.","A natural test of the completeness-versus-optimality distinction is to benchmark SCS against a certified global method in low dimensions; the paper only compares against local nonconvex solvers and heuristic baselines.","Because only convex geometry and convex derivative constraints are used, SCS should compose with any convex-corridor generator, including GPU-inflated sets; the package-transfer experiments suggest but do not establish this at scale.","The method could also be extended to jerk or higher-order derivative constraints by raising the Bézier degree, but convexity of the resulting constraints would need to be rechecked."],"forward_implications":["SCS can be used as an online motion planner for robots operating in convex corridors: planning completes in milliseconds and any interruption yields a usable trajectory.","Because no line-search or trust-region parameters are involved, deploying the method in production avoids algorithm-specific tuning; only the Bézier degree and stopping tolerance remain.","On the reported benchmark family, SCS scales nearly linearly with the number of safe sets, facets, space dimension, and trajectory degree, so the method should remain practical for large corridors and high-dimensional arms.","The small duration gap to nonconvex optimizers (0.1–3.2%) means SCS is appropriate where near-optimal, reliable, fast plans matter more than certified global optimality."],"supporting_citations":[{"why":"Defines the traversing-sequences-of-convex-sets problem and supplies the trust-region baseline SCS is compared against.","marker":"[28]"},{"why":"Introduces the Graphs of Convex Sets planning approach whose convex-parameterization limitations motivate the narrower continuous problem treated here.","marker":"[27]"},{"why":"Supplies the nonconvex sequential-quadratic-programming solver used as a baseline in the runtime and quality experiments.","marker":"[11]"},{"why":"Supplies the interior-point nonconvex solver used as a second baseline in the runtime and quality experiments.","marker":"[41]"},{"why":"Provides the multi-convex programming context that frames SCS as a heuristic method that can nevertheless be complete.","marker":"[34]"},{"why":"Supplies the Bernstein polynomial derivative, endpoint, and convex-hull properties underlying the finite-dimensional Bézier implementation.","marker":"[10]"}],"fun_headline_variants":["Biconvex split gives min-time paths in milliseconds, anytime","Min-time planning without line search: biconvex alternation","Biconvex method for min-time motion: fast and always feasible","Splitting nonconvexity: biconvex min-time planner beats solvers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole guarantee rests on every traversal time $T_i$ being strictly positive; Assumption 1 ensures this geometrically, and when an optimal trajectory merely grazes one set, the $S_i=1/T_i$ transformation used in the fixed-transition-point subproblem breaks down.","fun_headline_variants_meta":{"raw":{"variants":["Biconvex split gives min-time paths in milliseconds, anytime","Min-time planning without line search: biconvex alternation","Biconvex method for min-time motion: fast and always feasible","Splitting nonconvexity: biconvex min-time planner beats solvers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000926,"raw_usage":{"total_tokens":3950,"prompt_tokens":909,"completion_tokens":3041,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":525,"completion_tokens_details":{"reasoning_tokens":2964}},"tokens_in":525,"tokens_out":3041,"duration_ms":23145,"temperature":1.0,"reasoning_tokens":2964,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T10:04:41.280436+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a one-dimensional or two-dimensional corridor satisfying Assumption 1 whose true time-optimal trajectory is known from dynamic programming or bang-bang analysis; run SCS with high Bézier degree and a tight tolerance (for example $\\varepsilon=10^{-4}$) and measure the duration gap and whether every early-stopped iterate satisfies all constraints, since a gap clearly above the few percent reported, a non-monotone cost sequence, or an infeasible early iterate would contradict the central claims.","supporting_citations":[{"cited_title":"Fast path planning through large collections of safe boxes","cited_arxiv_id":null,"evidence_quote":"Defines the traversing-sequences-of-convex-sets problem and supplies the trust-region baseline SCS is compared against."},{"cited_title":"SNOPT: An SQP algorithm for large-scale constrained optimization","cited_arxiv_id":null,"evidence_quote":"Supplies the nonconvex sequential-quadratic-programming solver used as a baseline in the runtime and quality experiments."},{"cited_title":"On the imple- mentation of an interior-point filter line-search algorithm for large-scale nonlinear programming","cited_arxiv_id":null,"evidence_quote":"Supplies the interior-point nonconvex solver used as a second baseline in the runtime and quality experiments."},{"cited_title":"Disciplined multi-convex programming","cited_arxiv_id":null,"evidence_quote":"Provides the multi-convex programming context that frames SCS as a heuristic method that can nevertheless be complete."},{"cited_title":"Algorithms for polynomials in Bernstein form","cited_arxiv_id":null,"evidence_quote":"Supplies the Bernstein polynomial derivative, endpoint, and convex-hull properties underlying the finite-dimensional Bézier implementation."}],"review_version":1}