{"id":"cf8a5850-718a-4ac7-9efb-9d063daf6747","arxiv_id":"2411.13507","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Reachable Bezier polytopes enable a real-time, layered path planner that produces dynamically feasible, collision-free paths, demonstrated on a 3D hopping robot.","lead":"This paper presents a planner that uses reachable Bezier polytopes to find robot paths that are both collision-free and compatible with the robot's dynamics, with GPU acceleration for real-time use. It was tested on a 3D hopping robot moving through cluttered rooms.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The graph is cut against raw obstacles O, while MPC constraint (7c) and the actual safety claim require O⊕E; a graph path can pass within E of an obstacle, so Theorem 2's warm-start and recursive-feasibility proof fails even granting Theorem 1 from [30].","rationale":"A good-faith reading of the paper shows the central claim is Theorem 2: graph feasibility plus MPC in closed loop should solve Problem 1. The reader identifies Theorem 1 from the companion preprint [30] as the weakest assumption, and that is indeed a major external dependency: the matrices F and G are asserted, not derived, and their conditions for the ARCHER Raibert-style controller are not checked. I agree that this alone warrants a conditional verdict. However, stress-testing the proof of Theorem 2 reveals a second, more internal gap that is independent of [30]: the graph cut and the MPC use inconsistent obstacle sets, differing exactly by the tracking-error bound E. Because Definition 1 only guarantees the full-order trajectory lies in a tube around the reference, avoiding raw O is insufficient; the MPC correctly encodes O ⊕ E, but Algorithm 2 and the Cut-QP do not. This breaks the claimed warm-start feasibility and the recursive-feasibility appeal before any question about the reachable oracle is even considered. The computational results, GPU acceleration, and hardware demonstrations appear plausible and are independent evidence that the architecture works in practice, and the gap is repairable by dilating obstacles before graph cutting. Therefore I do not move the verdict: the paper should remain CONDITIONAL, with the additional condition that the authors either prove the graph cut respects the E-dilation or clearly document that obstacle sets are pre-inflated, while also providing a self-contained derivation or external verification of Theorem 1.","tokens_in":10207,"tokens_out":12158,"duration_ms":146294,"concrete_test":"Open the released code and inspect the obstacle data passed to cutGraph/Cut-QP: check whether the O_i are inflated by the tracking-error bound E before constructing A_O and b_O. Then construct a simple two-node graph edge whose Bézier control-point hull is disjoint from a raw obstacle but whose reference curve passes within distance E of it (e.g., an obstacle side at distance E/2 from the hull); run Algorithm 1 and feed the graph path into MPC to see whether constraint (7c) is feasible. If the code checks raw O only, or if the warm start violates (7c), the concern lands. If the obstacles are already dilated by E, the issue is a documentation gap that can be resolved by stating the dilation explicitly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section III-B cuts an edge only if the convex hull of its Bézier control points avoids the raw obstacle set O: the Cut-QP in Algorithm 2 uses A_{O_i} P λ ≤ b_{O_i} + δ, so an edge survives when conv(P) ∩ O = ∅. But Section III-D imposes the MPC constraint (7c): D[x_k; x_{k+1}] ∈ X_d \\(O ⊕ E), i.e., the reference states must avoid the E-inflated obstacles. The proof of Theorem 2 says 'As v_k is in the collision-free graph C, it satisfies (7d) and (7c).' That implication is not valid: by Definition 1, the full-order projection satisfies Π(x(t)) ∈ x_d(t) ⊕ E, so collision avoidance for the full-order system requires the nominal reference to avoid O ⊕ E, not merely O. A graph edge whose control-point hull is disjoint from O can still pass within distance E of an obstacle, and the tracked closed-loop trajectory can then enter O. Consequently the graph path is not generally a feasible warm start for the MPC, and the recursive-feasibility argument in Theorem 2 collapses even if Theorem 1 from [30] is accepted. The repair is straightforward—run the graph cut against O ⊕ E, or an equivalent erosion of X_d, and state this explicitly—but the paper as written does neither.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a layered kinodynamic planning framework for nonlinear systems in cluttered environments. A graph is built by sampling reduced-order states and connecting them with Bézier curves whose dynamic feasibility is certified by reachable polytopes from a companion preprint [30]. The graph is pruned by checking whether the convex hull of each Bézier curve's control points intersects obstacles, a shortest path is found with Dijkstra, and the path is refined by an MPC that tracks the graph solution while enforcing a collision-free corridor. The main theoretical claim (Theorem 2) is that a feasible graph path guarantees that the closed-loop system under MPC solves the original constrained control problem. The approach is demonstrated on the ARCHER 3D hopping robot in simulation and on hardware, with GPU acceleration for real-time performance.","tokens_in":10517,"tokens_out":6706,"duration_ms":68794,"significance":"If the stated guarantees held, the architecture would be a valuable example of combining discrete graph search with continuous optimization while preserving feasibility for nonlinear systems. The hardware experiments and GPU implementation are significant engineering contributions, and the paper provides code and video links, which is commendable. However, the central theoretical guarantee has a substantial gap: the graph is cut against raw obstacles rather than the E-inflated obstacles required by the tracking-error bound, and the proof of Theorem 2 does not verify the conditions needed for the cited tube MPC theory. These issues undermine the closed-loop guarantee as stated and require a major revision.","major_comments":[{"comment":"The graph cut in Section III-B only removes edges whose Bézier control-point convex hull intersects the raw obstacle set O (conv(P) ∩ O = ∅), whereas the MPC constraint (7c) requires the nominal state sequence to lie in Xd \\(O ⊕ E) and Definition 1 implies the full-order state satisfies Π(x(t)) ∈ x_d(t) ⊕ E. Therefore, an edge surviving the graph cut can pass within distance E of an obstacle, and the closed-loop trajectory can enter O even though the nominal curve avoids O. The proof of Theorem 2 states 'As v_k is in the collision-free graph C, it satisfies (7d) and (7c),' but this implication is false: membership in C only guarantees that the convex hull avoids O, not O ⊕ E. Consequently, the graph path is not generally a feasible warm start for the MPC, and the recursive-feasibility argument collapses. The repair is to run the graph cut against O ⊕ E (or erode the free space accordingly) and to state this explicitly; this is a load-bearing fix, not a cosmetic one.","section":"III-B and III-D, Theorem 2 proof"},{"comment":"The proof appeals to 'standard Robust tube MPC theory [31]' to claim recursive feasibility and robust stability, but the MPC formulation (7) is not shown to satisfy the assumptions of that theory. In particular, the terminal equality constraint (7e) x_N = r_N is not accompanied by a terminal invariant set or a terminal controller, and no tube tightening is defined for the state and input constraints under the tracking error E. Without these ingredients, the cited reference does not by itself establish recursive feasibility or robust stability. The authors should either provide a self-contained proof of these properties for (7) or explicitly verify the hypotheses of the tube MPC result they invoke, including the role of the reachability oracle in providing a terminal controller.","section":"Theorem 2 proof"},{"comment":"The central feasibility oracle, Theorem 1 from the companion preprint [30], is imported without proof or numerical verification in this paper. The matrices F and G, the worst-case tracking error bound E, and the class of tracking controllers for which the theorem holds are not specified for the ARCHER system. Since every graph edge and the MPC constraint (7d) depend on this theorem, a failure of its assumptions would invalidate Theorem 2. The authors should make the companion result accessible (e.g., include the theorem statement with its assumptions, or provide the code/data that verifies the oracle for the specific controller), or state clearly that the main claim is conditional on an unverified external result.","section":"II-B, Theorem 1"},{"comment":"The set membership notation in D[x_k; x_{k+1}] ∈ Xd \\(O ⊕ E) is ambiguous because D[x_k; x_{k+1}] is a matrix of Bézier control points, not an element of R^n. If the intended meaning is that each control point lies in the eroded free space, this is still a different condition from the convex hull avoiding O ⊕ E, and the paper should specify which condition is used. This ambiguity matters because the proof of Theorem 2 relies on (7c) being satisfied by the graph path, and the current text does not make the precise constraint clear.","section":"III-D, Eq. (7c)"}],"minor_comments":[{"comment":"The word 'polyonmials' in the abstract is a typo and should be 'polynomials'.","section":"Abstract"},{"comment":"The statement 'there exists a unique matrix D' could benefit from a brief explanation of how uniqueness follows from the chosen Bézier degree p = 2γ−1, since this is not immediately obvious from the text.","section":"Section II-B, Lemma 1"},{"comment":"The text uses 'Dijkstra‘s algorithm' with a curly apostrophe; please use a standard apostrophe for consistency.","section":"Section III-C"},{"comment":"The table columns are not labeled; the reader cannot immediately tell which column corresponds to which function (cutHeuristic vs. adjacentHyperplane). Adding column headers would improve clarity.","section":"Table I"},{"comment":"The description of the projection map Π as 'the restriction of the full order state to the center of mass x and y positions and velocities' is clear, but the sentence immediately following it ('This desired quaternion is then tracked by a low-level controller...') switches to 'u(x,t)' without defining all variables; please define q, q_d, and ω_d in the text for completeness.","section":"Section IV"}],"recommendation":"major_revision","confidential_remarks":"The paper's main theoretical claim is conditional on the companion preprint [30], which is self-cited and not independently verified. If the authors can fix the obstacle-inflation gap and provide the missing tube MPC verification, the paper could become a solid contribution. The hardware demonstration is compelling, but the theoretical gaps are load-bearing and should be addressed before publication. I would also encourage the editor to seek an independent check of Theorem 1's validity, as it may be outside the scope of this manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper is a credible integration of the authors' reachable Bézier polytope primitive into a working real-time kinodynamic planner, with a GPU collision-cut heuristic and hardware demos on ARCHER hopping in cluttered scenes. The new thing is the layered architecture and the cut heuristic, not the primitive, which comes from a companion preprint. The engineering looks real; the theory behind the headline guarantee does not.\n\nCredit where due: the cut heuristic that removes >99% of edges before solving the QP, and its GPU implementation, are genuinely useful. The timing numbers are convincing, and the hardware replanning when obstacles move is a meaningful demonstration. Code and video are linked.\n\nThe soft spot is Theorem 2. The graph is cut against the raw obstacle set O, but constraint (7c) and the actual collision-free claim require avoiding O⊕E, the E-inflated obstacles, because the tracking error bound E means the full-order trajectory can deviate from the reference by up to E. The proof just asserts that a graph path satisfies (7c). It doesn't. An edge can pass within E of an obstacle and the tracked full-order trajectory can enter it. The fix is straightforward—run the cut against O⊕E and say so—but as written the guarantee fails. Also, the recursive feasibility step is a generic appeal to tube MPC [31] without checking terminal ingredients; the terminal equality constraint (7e) makes that non-automatic. Neither issue kills the architecture, but Theorem 2 is not established.\n\nThe other dependency is Theorem 1 from [30], an unpublished same-author preprint. The paper does not verify it or its conditions for the Raibert controller. That's a risk, not necessarily a flaw, but it means the whole guarantee rests on an oracle the reader cannot check here.\n\nWho should read this: people working on real-time kinodynamic planning for legged robots, and anyone building layered planners with reachable-set primitives. It deserves a serious referee; the framework is promising and the demo is strong, but the theory section needs major revision: inflate obstacles in the cut, prove or cite a verified condition for the reachable oracle, and spell out the recursive-feasibility argument. I'd engage with it.","headline":"Real-time kinodynamic planner with a strong GPU cut heuristic and hardware demo, but the headline safety theorem has a fixable gap: the graph is cut against raw obstacles, not the tracking-error-inflated ones.","tokens_in":11028,"tokens_out":3041,"would_cite":false,"duration_ms":33793,"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":"Reachable Bézier polytopes make graph paths provably safe to track","keywords":["reachable Bézier polytopes","kinodynamic path planning","layered control architecture","model predictive control","Bézier curves","real-time planning","GPU acceleration","legged robots"],"falsifier":"Take ARCHER's actual Raibert-style controller, compute (or measure) its worst-case tracking error bound E, and search one of the Bézier graphs built in the paper for a pair of vertices satisfying F[x1;x2] ≤ G whose connecting Bézier curve, when tracked in closed loop, leaves the widened corridor Xd\\O⊕E or violates an input limit; if such a pair exists, the oracle is too optimistic and Theorem 2's conclusion collapses.","tokens_in":10018,"feed_emoji":"🤖","tokens_out":6228,"duration_ms":59376,"temperature":0.7,"pith_summary":"The paper argues that a conventional two-step pipeline — plan a coarse path, then track it with a low-level controller — can be made to carry formal guarantees if the path is built from Bézier curves selected by a reachability oracle. The authors propose building a graph whose edges are Bézier curves that, when tracked, provably keep the full closed-loop system inside its state and input constraints, cutting edges that collide with obstacles and refining the surviving path with model predictive control. Their central result states that if such a graph path exists, the closed-loop MPC execution reaches a neighborhood of the goal while respecting constraints for all time. They demonstrate the architecture in real time on the 3D hopping robot ARCHER, using GPU acceleration to replan through cluttered environments at 10–50 Hz. This matters because it replaces the usual leap of faith that a low-level tracker will keep the robot safe with a check performed at planning time.","feed_headline":"Bézier polytopes guarantee feasible, collision-free robot motion","feed_subtitle":"A layered planner links coarse graph search to closed-loop safety, running in real time on a 3D hopping robot.","key_machinery":"The central object is the reachable Bézier polytope — a polytopic reachable set in the space of polynomial Bézier reference trajectories, encoded by matrices F and G (Theorem 1). For any two boundary states x1, x2 satisfying F[x1;x2] ≤ G, there exists a Bézier curve that, when tracked by the given feedback controller, keeps the closed-loop system within the specified state and input constraint sets. This oracle lets the planner treat dynamics as a graph edge check rather than a differential constraint. Around it, the paper assembles standard Bézier facts — the convex-hull property (which makes collision checking a linear program over control points), a path-length bound used as the edge cost, and subdivision used to discretize the curve into MPC references — and adds a three-stage heuristic that eliminates most collision checks and maps cleanly onto a GPU.","core_discovery":"The paper's central claim is Theorem 2: if the graph-search problem Problem 2 is feasible, then applying the MPC refinement (MPC) in closed loop solves Problem 1 — the full-order closed-loop system keeps its projected state inside the free space, respects input bounds for all time, and converges to a neighborhood of the goal. The proof works by showing that the graph path gives a feasible warm start for MPC, and that each MPC segment, connected to the next by a Bézier curve guaranteed by Theorem 1 from the companion paper, keeps the closed-loop trajectory inside the same constraint sets; standard robust tube MPC theory then supplies recursive feasibility and stability. The paper thereby claims that checking the pair of endpoint states against the reachable-polytope matrices F and G is sufficient to certify dynamic feasibility of an entire path through nonconvex space.","pith_inferences":["Editorial extension: the same reachable-polytope oracle could be dropped into sampling-based kinodynamic planners (e.g., RRT*) as a steering primitive, replacing two-point boundary value solves with a single matrix inequality check.","Editorial extension: the paper's guarantee is only as tight as the worst-case tracking error bound E; if an implementation cannot compute a trustworthy E for its controller, the practical safety margin is unknown, and an optimistic E could invalidate the collision-avoidance claim.","Editorial extension: because the cut heuristic returns 'indeterminate' for a small fraction of edges and the QP resolves those, the GPU speedup is preserved; a similar three-stage pruning pattern could accelerate collision checking for other convex-hull parameterized curves (B-splines, NURBS).","Editorial extension: the F,G oracle implicitly assumes the obstacle map is static between replans; with moving obstacles the graph must be rebuilt each cycle, and the 50 Hz replan rate shown here suggests the practical limit on obstacle dynamics the current architecture can tolerate."],"forward_implications":["Any graph edge that passes the F,G check is a provably trackable reference for the full-order system, so dynamic feasibility is certified at the planning layer rather than assumed of the tracker.","Because the graph path is a feasible warm start for MPC, the refined trajectory inherits the guarantee: if the graph problem is feasible at any replan instant, the closed-loop system stays inside Xd\\O and U for all time.","The architecture is agnostic to the specific robot: it needs only a tracking controller with a bounded error set E and the corresponding F,G matrices, so the same pipeline can be retargeted to other nonlinear systems.","Real-time replanning at 10–50 Hz with 50,000 edges is achievable by GPU offloading of the cut heuristic and the separating-hyperplane computations, enabling online response to moving obstacles.","The path-length upper bound from Property 2 gives an admissible cost for Dijkstra, so the coarse path is optimal with respect to that bound before MPC refines it."],"supporting_citations":[{"why":"Supplies Theorem 1, the reachable-polytope oracle (matrices F and G) on which graph edge feasibility and the proof of Theorem 2 depend.","marker":"[30]"},{"why":"Provides the robust tube MPC theory used in the proof of Theorem 2 to establish recursive feasibility and robust stability.","marker":"[31]"},{"why":"Motivates the use of Bézier basis polynomials for path planning in nonconvex spaces and supplies the path-length bound used as the edge cost.","marker":"[24]"},{"why":"Establishes the multi-rate planning and control abstraction (reduced-order model, tracking controller, error bound) that this paper builds on.","marker":"[25]"},{"why":"Supplies the convex-hull and subdivision properties of Bézier curves used for collision checking and MPC reference generation.","marker":"[29]"},{"why":"Describes the ARCHER 3D hopping robot on which the framework is demonstrated in simulation and hardware.","marker":"[26]"}],"fun_headline_variants":["Bézier polytopes certify dynamic feasibility in cluttered spaces","Real-time path planning via reachable Bézier polytopes","GPU-accelerated planner guarantees feasible motion in clutter","Layered Bézier-polytope planner enables real-time 3D hopping","Reachable polytopes ensure collision-free, dynamically feasible paths"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire guarantee rests on the companion-paper oracle (Theorem 1): that any pair of states passing the F,G check really can be connected by a Bézier curve whose closed-loop tracking stays inside the state and input constraints for the specific Raibert-style controller used on ARCHER — and this paper neither proves that theorem nor verifies its conditions or provides the worst-case tracking error bound E for that controller.","fun_headline_variants_meta":{"raw":{"variants":["Bézier polytopes certify dynamic feasibility in cluttered spaces","Real-time path planning via reachable Bézier polytopes","GPU-accelerated planner guarantees feasible motion in clutter","Layered Bézier-polytope planner enables real-time 3D hopping","Reachable polytopes ensure collision-free, dynamically feasible paths"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000725,"raw_usage":{"total_tokens":3207,"prompt_tokens":862,"completion_tokens":2345,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":478,"completion_tokens_details":{"reasoning_tokens":2257}},"tokens_in":478,"tokens_out":2345,"duration_ms":18507,"temperature":1.0,"reasoning_tokens":2257,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:20:14.976254+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take ARCHER's actual Raibert-style controller, compute (or measure) its worst-case tracking error bound E, and search one of the Bézier graphs built in the paper for a pair of vertices satisfying F[x1;x2] ≤ G whose connecting Bézier curve, when tracked in closed loop, leaves the widened corridor Xd\\O⊕E or violates an input limit; if such a pair exists, the oracle is too optimistic and Theorem 2's conclusion collapses.","supporting_citations":[{"cited_title":"Reachable bézier polytopes: A primitive for layered motion planning,","cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 1, the reachable-polytope oracle (matrices F and G) on which graph edge feasibility and the proof of Theorem 2 depend."},{"cited_title":"Rawlings, D","cited_arxiv_id":null,"evidence_quote":"Provides the robust tube MPC theory used in the proof of Theorem 2 to establish recursive feasibility and robust stability."},{"cited_title":"Multi-Rate Planning and Control of Uncertain Nonlinear Systems: Model Predictive Control and Control Lyapunov Functions,","cited_arxiv_id":null,"evidence_quote":"Establishes the multi-rate planning and control abstraction (reduced-order model, tracking controller, error bound) that this paper builds on."},{"cited_title":"Creating ARCHER: A 3D Hopping Robot with Flywheels for Attitude Control,","cited_arxiv_id":null,"evidence_quote":"Describes the ARCHER 3D hopping robot on which the framework is demonstrated in simulation and hardware."}],"review_version":1}