{"id":"fd1aeef8-c14c-41b2-a827-6910618fccb3","arxiv_id":"2507.10878","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Shortest walks in graphs of convex sets, guided by SDP-computed cost-to-go lower bounds, provide a unified approximate planner for robot motion, skill chaining, and hybrid control.","lead":"The paper studies shortest walks in graphs of convex sets, where every node carries its own convex optimization problem and the walk may revisit nodes. It builds cost-to-go lower bounds with semidefinite programming and uses them to guide a fast greedy planner, then tests the idea on robot motion, skill chaining, and hybrid walkers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The SDP-generated lower bounds may not be admissible after the quadratic-cost approximations of Section IV-C, and the paper provides no check; a small exact-comparison test would settle this.","rationale":"The reader's weakest assumption correctly identifies the conservatism of the quadratic lower bounds in Section IV-C as the load-bearing risk. My independent reading of the argument confirms that the lower-bound property is the only mechanism that connects the SDP solution to the admissibility of the greedy lookahead in equation (5). If the cost approximations are not pointwise underestimators, then the synthesized J functions are not guaranteed to be lower bounds on the true cost-to-go, and the search may terminate with arbitrarily bad walks. The paper explicitly states that completeness and optimality are not guaranteed, so the correctness of the approximation is not protected by any other guarantee. This is not a disagreement with the community consensus; it is an internal correctness risk in the method's central pipeline. The reader also flagged the simulated parallel solve-times and absence of code/data; those are secondary to the theoretical validity of the lower bound. A small exact-comparison experiment is sufficient to determine whether the concern is real in practice, and if it is, the appropriate verdict would remain conditional pending a fix or an explicit limitation. Since the reader has already conditioned on this exact issue, no verdict change is needed.","tokens_in":533,"tokens_out":4497,"duration_ms":170768,"concrete_test":"Construct a small GCS where the true shortest-walk cost can be computed exactly, e.g., a chain of two vertices with self-loop edges and quadratic costs, and solve it by enumerating all walks up to a length where the cost exceeds an upper bound on J_s. Then run the Section IV-C SDP synthesis on the same GCS, first with exact quadratic costs and then with a non-quadratic cost (say l(x)=exp(x)) replaced by the paper's quadratic approximation. Compare the SDP-produced J_s(\\bar{x}_s) and J_v(x_v) against the exact values on a fine grid. If any J exceeds the exact value by more than solver tolerance, the lower-bound claim in Section IV-B is violated and equation (5) is non-admissible in that instance.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central numerical argument depends on the piecewise-quadratic J_v obtained from program (4) being a valid lower bound on the true cost-to-go, so that the lookahead objective (5) does not overestimate the remaining cost. Section IV-C restricts costs to convex quadratics by using \"quadratic approximations for non-quadratic l_v, l_e\" and sets to intersections of polyhedra and ellipsoids. The paper does not prove or verify that these approximations are conservative pointwise lower bounds on the true costs. If any approximating l_v or l_e overestimates the true cost on even one feasible point, constraint (4c) can permit J_u to exceed J*_u, making the heuristic non-admissible. Since the extraction stage uses J in greedy search with no completeness or optimality guarantee, solution quality can degrade silently; the reported 1-2% duration differences and 2.3x speedups could then be artifacts of favorable instances rather than a property of the method. The limitation statement acknowledges tightness loss but not this correctness condition. This is load-bearing because equation (5) is the only bridge from the SDP to the planned trajectories.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper introduces the Shortest-Walk Problem (SWP) in a Graph of Convex Sets (GCS), a generalization of the shortest-path problem in which vertex revisits are allowed and each visit selects a continuous point from a convex set. The authors derive a Bellman equation for the cost-to-go (Section IV-A), relax it to an infinite-dimensional LP (Section IV-B), and obtain finite-dimensional piecewise-quadratic lower bounds via semidefinite programming (Section IV-C). These lower bounds guide an incremental greedy search with multi-step lookahead (Section IV-D). The method is demonstrated on three robotics applications: collision-free motion planning with acceleration limits, skill chaining, and footstep planning for a hybrid ZMP walker. The central claim is that the SWP in GCS is a natural and computationally efficient unifying formulation for mixed discrete-continuous planning problems.","tokens_in":1409,"tokens_out":1713,"duration_ms":136952,"significance":"If the lower bounds remain valid after the restrictions in Section IV-C, the paper provides a reusable multi-query planning framework that extends the authors' earlier SPP-in-GCS work to the walk setting. The Bellman derivation in Section IV-A is clean, the SDP relaxation is well motivated, and the three application domains illustrate genuine breadth. The paper is also commendably explicit that the extraction search lacks completeness and optimality guarantees. However, the absence of a conservatism check for the quadratic cost and set approximations, together with unspecified hyperparameters and potentially unfair timing comparisons, leaves the central performance claims under-supported. The contribution is promising and within the scope of the journal, but it requires substantive additional verification and reporting before acceptance.","major_comments":[{"comment":"The paper replaces non-quadratic costs l_v, l_e with 'quadratic approximations' and restricts sets to intersections of polyhedra and ellipsoids, but it never proves or verifies that these replacements are conservative. For the SDP solution to be a valid lower bound, constraint (4c) must hold for the true costs and true feasible sets; if an approximating cost overestimates the true cost at any feasible point, the optimized J can exceed the true cost-to-go, making the heuristic in Eq. (5) non-admissible. Since the search in Section IV-D has no completeness or optimality guarantee, solution quality can degrade silently. Please add a proof of conservatism under the stated approximations, or a pointwise verification procedure (e.g., checking (4c) on the true costs and sets for the actual instances), and state how each quadratic approximation was constructed.","section":"IV-C (Eq. (4c))"},{"comment":"The reported performance depends on several unspecified or simulated choices. The lookahead horizon n in Eq. (5) is never given; the edge-cost offset epsilon from Section II-D is never quantified; and the SDP objective used in the experiments (e.g., 'maximizing the average value' in Sections V-B and V-C) differs from the single-source objective of program (4) without explanation. In addition, Section VI discloses that solve times assume solving up to 10 convex programs in parallel and are simulated rather than measured. Please specify all hyperparameters, give the exact SDP solved in each experiment, and report actual wall-clock times.","section":"IV-D, V-B, V-C"},{"comment":"The timing comparison in Figure 7 is not apples-to-apples. For the SWP, the 45-second cost-to-go synthesis is excluded from the reported 0.46-second average, while the SPP baselines include all their computation as single-query methods. Over the 100-query battery, amortizing the synthesis adds roughly 0.45 second per query, which is comparable to the reported speedup. The paper should report total time over the batch with and without amortization, include per-query variability (error bars or distributions), and provide statistical support for the 'within 1-2 percent' duration claim.","section":"V, Figure 7"}],"minor_comments":[{"comment":"The sentence 'the optimal solution to program (4) yields an exact solution to the Bellman equation' is only true for the infinite-dimensional LP; the finite-dimensional SDP of Section IV-C is a restricted problem, so this wording should be qualified to avoid implying that the numerical solution is exact.","section":"IV-B"},{"comment":"The statement 'we consider all candidate n-step decision sequences' can involve an exponential number of walks when the graph has high out-degree; a brief discussion of this complexity or a bound on the practical choice of n would help readers assess scalability.","section":"IV-D"},{"comment":"There is a typo in 'evolves evolves according to different affine dynamics'; also, the spacing in 'PW A' is inconsistent throughout the paper and should be normalized to 'PWA'.","section":"III-C"},{"comment":"The caveat that solve times are simulated parallelized times appears only in Section VI; it should be stated prominently where the timing results are first reported in Section V.","section":"V and VI"},{"comment":"The figure shows box-whisker-style plots, but the caption does not explain what the boxes, whiskers, and points represent; please add this information for clarity.","section":"Figure 7"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is from a strong group and builds directly on the authors' prior work [39]. The main risk is that the SDP lower bounds may not be admissible after the quadratic approximations, which would undermine the heuristic guiding the search. A focused verification experiment, such as comparing the SDP lower bounds against exact cost-to-go on small instances or checking constraint (4c) pointwise on the true costs, would substantially de-risk the contribution. The timing methodology also needs to be presented more transparently before the performance claims can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a credible, well-written extension of the GCS program from shortest paths to shortest walks. The Bellman derivation is clean, Example 1 makes the core point vividly (revisits can genuinely help), and the three application demos—motion planning with acceleration limits, skill chaining, and ZMP footstep planning—show the framework has real reach. The authors are also unusually honest about what is not guaranteed.\n\nThe new thing here is the problem formulation itself: SWP in GCS, with the observation that vertex revisits are not redundant when the continuous variables change the cost. The fixed-duration Bézier convexification for acceleration limits is a nice trick, and the multi-query reuse of cost-to-go bounds is practically sensible.\n\nThe soft spots, in order of weight. First, the SDP lower bounds: Section IV-C replaces non-quadratic costs with quadratic approximations and restricts sets to polyhedra and ellipsoids, but never shows the approximations are pointwise lower bounds on the true costs. If they are not, the inequality in (4c) can fail and the J used in the lookahead (5) is not admissible. The paper says 'sacrificing the tightness' but that is not the same as preserving conservatism. This is a real gap, though it may be fixable in practice by choosing approximations carefully or by adding a verification step. The stress-test note is right to flag this as load-bearing.\n\nSecond, the experiments are narrower than the abstract suggests: one warehouse scenario, one skill-chaining puzzle, two footstep maps. Solve times for the greedy search are simulated parallel (up to 10 solves), and no code or data are provided, so the 1.5–2.3x speedups are not independently reproducible yet.\n\nThird, the method explicitly lacks completeness and optimality guarantees; the authors say so. That is a limitation but not a flaw, provided the heuristic is understood to be approximate.\n\nOn balance, I think the paper deserves a serious referee. The formulation is a legitimate addition to the GCS literature, and the admissibility question can be settled with an exact comparison on small instances—that would be a natural request for revision.","headline":"A solid extension of GCS planning to walks, with a real admissibility gap in the SDP lower bounds that should be fixed before relying on the heuristic.","tokens_in":16457,"tokens_out":2739,"would_cite":false,"duration_ms":30379,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that allowing vertex revisits in graphs of convex sets yields a unified, fast approximate solver for mixed discrete-continuous planning problems.","keywords":["shortest-walk problem","graphs of convex sets","cost-to-go lower bounds","semidefinite programming","mixed discrete-continuous planning","motion planning","hybrid systems","incremental search"],"falsifier":"Solve the restricted SDP program (4) on a small GCS with a non-quadratic cost, such as $l_e = \\|x_u - x_v\\|^3$, then compute the true cost-to-go at many sampled points by solving the layered $K$-step SPP for growing $K$ or by exact enumeration; if any sampled point has $J_v(x)$ greater than the true cost-to-go, the heuristic is inadmissible and the paper's claim that the approximations sacrifice only tightness, not validity, is broken.","tokens_in":15471,"feed_emoji":"🤖","tokens_out":5176,"duration_ms":59789,"temperature":0.7,"pith_summary":"The paper introduces the Shortest-Walk Problem in a Graph of Convex Sets and argues that it is a natural, unified language for mixed discrete-continuous planning problems in robotics. Unlike shortest paths, walks may revisit vertices, which lets a fixed-duration trajectory piece be reused and lets contact or skill modes repeat in hybrid control. To solve the NP-hard walk problem, the paper synthesizes piecewise-quadratic lower bounds on the cost-to-go via semidefinite programming and uses those bounds to guide incremental greedy search. Experiments in collision-free motion planning, skill chaining, and footstep planning report faster solve times than path-based alternatives with comparable trajectory quality. A sympathetic reader would take this as evidence that one formulation can replace several specialized planners.","feed_headline":"Shortest walks beat shortest paths for hybrid robot planning","feed_subtitle":"One SDP-built lower bound guides all queries, unifying motion, manipulation, and hybrid control in one planner.","key_machinery":"The load-bearing object is the cost-to-go lower bound synthesized by the SDP relaxation of the Bellman equation. For each vertex $v$, $J_v(x_v)$ is a convex quadratic underestimator of the true cost-to-go to the target; the SDP maximizes $J_s$ at the source while enforcing $J_u(x_u) \\le l_u(x_u) + l_e(x_u,x_v) + J_v(x_v)$ on every edge. The search then uses these bounds in a greedy $n$-step lookahead: at each step it minimizes the cost of the next $n$ segments plus the residual bound, commits to the first segment, and repeats. The restrictions that make the SDP finite-dimensional, quadratic costs, sets that are intersections of polyhedra and ellipsoids, and convex quadratic $J_v$, are precisely what must hold for the bound to remain a true lower bound.","core_discovery":"The central discovery is that the Shortest-Walk Problem in a GCS, where a walk may repeat vertices and pick a new continuous point at each visit, has a practical approximate solution method, and that this formulation captures problems the Shortest-Path formulation does not handle naturally. The method computes, once per GCS, a piecewise-quadratic lower bound on the cost-to-go at each vertex by solving a single SDP over the whole graph, then runs greedy multi-step lookahead search guided by those bounds, re-optimizing the trajectory on the chosen walk and removing unnecessary cycles as post-processing. The paper claims this yields a natural language for motion planning with derivative constraints, skill chaining, and hybrid-system optimal control, and reports average query times 1.5 times faster than shortest-path planning with time-optimal path parameterization and 2.3 times faster than shortest-path planning with non-convex post-processing, with trajectory durations within 1-2 percent.","pith_inferences":["Beyond the paper: if the same SDP lower bounds are used inside a complete search such as a walk-version of A* rather than greedy lookahead, the precomputation could supply optimality guarantees instead of heuristic solutions.","Editorial extension: the fixed-duration, vertex-revisiting representation suggests a testable extension to changing environments, where only the affected vertex's bound would need to be recomputed and the SDP warm-started.","Editorial inference: the many-to-many cost-to-go variant mentioned in the paper could support receding-horizon replanning under disturbances, since a new target reuses the existing bound instead of requiring a fresh SDP solve.","Editorial extension: the formal connection between revisits and repeated skills points toward task-and-motion planning where the same manipulation primitive must be applied multiple times; the skill-chaining experiment is the first instance of that use."],"forward_implications":["A single GCS construction supports many queries after one cost-to-go synthesis step, so multi-query settings amortize the SDP cost: the motion-planning experiment spends about 45 seconds on synthesis and 0.46 seconds per query.","Acceleration limits and, in principle, higher-order derivative constraints can be enforced during search rather than in a separate post-processing stage.","Hybrid optimal control can be posed directly as a walk over contact-mode vertices, making the mode sequence and the continuous state and control trajectories jointly optimizable.","Because greedy search is heuristic, the quality of the returned walk depends on how tight the lower bounds are, and the paper's cycle-removal post-processing improves that quality in practice.","The formulation unifies collision-free motion planning, skill chaining, and footstep planning, problems that previously required specialized solution strategies."],"supporting_citations":[{"why":"Supplies the cost-to-go lower-bound synthesis via SDP and the greedy search strategy that this paper extends from paths to walks.","marker":"[39]"},{"why":"Defines the Shortest-Path Problem in GCS, the base formulation whose Bellman relaxation this work adapts.","marker":"[37]"},{"why":"Provides the motion-planning formulation with Bezier curves and durations that the walk formulation modifies to enforce acceleration limits.","marker":"[35]"},{"why":"Introduces Graphs of Convex Sets, proves NP-hardness of shortest paths in acyclic GCS, and describes the layered vertex-duplication construction for walks.","marker":"[34]"},{"why":"Time-optimal path parameterization is the first baseline post-processing method compared in the motion-planning experiments.","marker":"[56]"},{"why":"Non-convex post-processing is the second baseline compared in the motion-planning experiments.","marker":"[57]"},{"why":"Supplies the convex decomposition of the collision-free space that generates the GCS used in the motion-planning experiment.","marker":"[43]"},{"why":"GCS* incremental graph search motivates the lookahead-based walk extraction strategy.","marker":"[8]"}],"fun_headline_variants":["A single SDP bound guides all shortest-walk planning","Walk repeats allowed: unified planner for hybrid systems","From paths to walks: faster hybrid planning via SDP","Shortest-walk planner unifies motion and hybrid control","SDP lower bound speeds up hybrid planning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The SDP cost-to-go lower bounds remain true lower bounds after costs are replaced by quadratic approximations, sets are restricted to intersections of polyhedra and ellipsoids, and each $J_v$ is forced to be convex quadratic; if any of these restrictions makes $J$ overestimate the true cost-to-go, the greedy heuristic can be misled and solution quality degrades with no detection mechanism.","fun_headline_variants_meta":{"raw":{"variants":["A single SDP bound guides all shortest-walk planning","Walk repeats allowed: unified planner for hybrid systems","From paths to walks: faster hybrid planning via SDP","Shortest-walk planner unifies motion and hybrid control","SDP lower bound speeds up hybrid planning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000395,"raw_usage":{"total_tokens":2055,"prompt_tokens":915,"completion_tokens":1140,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":531,"completion_tokens_details":{"reasoning_tokens":1064}},"tokens_in":531,"tokens_out":1140,"duration_ms":10381,"temperature":1.0,"reasoning_tokens":1064,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:23:02.874801+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Solve the restricted SDP program (4) on a small GCS with a non-quadratic cost, such as $l_e = \\|x_u - x_v\\|^3$, then compute the true cost-to-go at many sampled points by solving the layered $K$-step SPP for growing $K$ or by exact enumeration; if any sampled point has $J_v(x)$ greater than the true cost-to-go, the heuristic is inadmissible and the paper's claim that the approximations sacrifice only tightness, not validity, is broken.","supporting_citations":[{"cited_title":"Shortest paths in graphs of convex sets","cited_arxiv_id":null,"evidence_quote":"Defines the Shortest-Path Problem in GCS, the base formulation whose Bellman relaxation this work adapts."},{"cited_title":"Motion planning around obstacles with convex optimization","cited_arxiv_id":null,"evidence_quote":"Provides the motion-planning formulation with Bezier curves and durations that the walk formulation modifies to enforce acceleration limits."},{"cited_title":"Graphs of Convex Sets with Applications to Optimal Control and Motion Planning","cited_arxiv_id":null,"evidence_quote":"Introduces Graphs of Convex Sets, proves NP-hardness of shortest paths in acyclic GCS, and describes the layered vertex-duplication construction for walks."},{"cited_title":"Time-optimal path tracking for robots: A convex optimization approach","cited_arxiv_id":null,"evidence_quote":"Time-optimal path parameterization is the first baseline post-processing method compared in the motion-planning experiments."},{"cited_title":"Using graphs of convex sets to guide nonconvex trajectory optimiza- tion","cited_arxiv_id":null,"evidence_quote":"Non-convex post-processing is the second baseline compared in the motion-planning experiments."}],"review_version":1}