{"id":"67ffcb0d-6c46-44db-9ce9-0b03a4035b72","arxiv_id":"1908.08493","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A hybrid planner that builds a convex, guaranteed-feasible trajectory optimization around a sampling-based obstacle-free path, demonstrated online on a quadcopter.","lead":"This paper combines a sampling-based path planner with a convex quadratic program to generate collision-free trajectories for mobile robots in cluttered spaces. It claims the optimization problem is always feasible, removing the need for slow iterative replanning, and demonstrates the method on a quadcopter in dense obstacle fields.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Discretized kinematics in Problem 4 are algebraically wrong (coefficient (k-i+3/2) vs correct (k-i-1/2)), so QP solutions need not satisfy the claimed waypoint constraints or collision-free bound.","rationale":"The paper presents a hybrid planner with a convex QP formulation and provides lemmas to show feasibility and a collision-free guarantee. The reader's conditional verdict focuses on the missing inequality between the path clearance 𝓁_m and the deviation bound (3/2)𝓁√d, which is a genuine gap. However, a more immediate correctness issue appears in Problem 4: the discrete-time kinematics equation for p[k] is algebraically inconsistent with the stated constant-acceleration model. Deriving the recurrence from p[k+1]=p[k]+h v[k]+0.5 h^2 a[k] and v[k+1]=v[k]+h a[k] gives p[k]=p[0]+h k v[0]+h^2 Σ_{i=0}^{k-1}(k-i-1/2)a[i], whereas the paper uses (h^2/2)(2(k-i)+3) = h^2(k-i+3/2) as the coefficient. The discrepancy is not a typo in one boundary term; it affects every summand and changes the reachable set of the QP. If the implementation in the experiments uses the correct dynamics, then the paper's written formulation is wrong and the theoretical guarantees do not apply to the solved problem; if the implementation uses the written formula, then the executed trajectories would not satisfy the waypoint constraints and the collision-free bound would be void. Either way, the central claim is not supported as stated. This concern, together with the reader's clearance inequality, makes clear that the manuscript requires revision. I do not conclude rejection because the method may be salvageable by correcting the kinematics equation and adding the missing inequality, and the experimental results suggest the approach is promising. Thus the conditional verdict stands, but with an additional, more fundamental condition.","tokens_in":14591,"tokens_out":16515,"duration_ms":144377,"concrete_test":"Re-derive the discretized position update in Problem 4 from the stated constant-acceleration dynamics p[k+1]=p[k]+h v[k]+(h^2/2)a[k], v[k+1]=v[k]+h a[k]. For a single interval with p[0]=0, v[0]=0, h=1, a[0]=1, compute p[1] using the paper's expression (2.5) and the recurrence (0.5); a mismatch confirms the kinematics error, which invalidates the QP constraints and the collision-free guarantee unless the implementation uses different dynamics.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Problem 4 the authors define p[k] = p[0] + h k v[0] + (h^2/2) Σ_{i=0}^{k-1} (2(k-i)+3) a[i]. Under the stated constant-acceleration kinematics (acceleration a[i] held constant on (ih,(i+1)h]), the exact recurrence p[k+1]=p[k]+h v[k]+(h^2/2)a[k], v[k+1]=v[k]+h a[k] yields p[k]=p[0]+h k v[0]+h^2 Σ_{i=0}^{k-1}(k-i-1/2) a[i]. The paper's coefficient is larger by 2 for each term, e.g., for k=1 it gives p[1]=p[0]+h v[0]+2.5 h^2 a[0] instead of p[0]+h v[0]+0.5 h^2 a[0]. Since the QP constraints ‖ϖ[k]-p[k]‖∞≤𝓁 are written in terms of this erroneous p[k], an optimizer can return an acceleration sequence that satisfies the constraints as defined but violates them under the true dynamics. Consequently the guarantees of Theorem 3 (|b(t)| ≤ 3/2 𝓁√d and hence p(t)∈χFree) do not apply to the solution that would actually be executed. This is a fundamental correctness issue in the central formulation, independent of the clearance-inequality gap noted by the reader.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a hybrid online trajectory planning method: an IRRT* sampling-based planner generates an obstacle-free path, and a single convex QP computes a time-parameterized trajectory that is claimed to be guaranteed feasible and collision-free. The QP uses waypoints placed along the path with associated hypercube regions, and the time step and velocity bound are derived from a design parameter 𝓁 and the maximum acceleration. The central theoretical claims are that the QP is always feasible and that the continuous trajectory remains within (3/2)𝓁√d of the path, hence collision-free given sufficient path clearance. The method is compared with iSCP and CHOMP in simulation and demonstrated on a Crazyflie quadcopter in cluttered environments with up to 200 obstacles.","tokens_in":14945,"tokens_out":15747,"duration_ms":132506,"significance":"If the theoretical claims were correct, the paper would make a valuable contribution: replacing iterative or sequential convex programs with a single QP that has formal feasibility and collision-avoidance guarantees is an important step for online planning. The experimental work is substantial, including 500-trial benchmarks across varying obstacle densities and real quadcopter flights, and the algorithm is clearly described with parameter choices. However, the correctness of the central guarantees is not established by the manuscript. The algebraic error in the discrete kinematics of Problem 4 and the invalid coordinate-wise arguments in the Appendix undermine the proof of the main theorem. The empirical results, while promising, cannot compensate for these theoretical gaps.","major_comments":[{"comment":"The discrete-time kinematics used in Problem 4 are algebraically incorrect. Under the stated constant-acceleration model, where a[i] is held constant on (ih,(i+1)h], the exact recurrence p[k+1]=p[k]+h v[k]+(h^2/2)a[k], v[k+1]=v[k]+h a[k] yields p[k] = p[0] + h k v[0] + h^2 Σ_{i=0}^{k-1} (k-i-1/2) a[i]. The paper instead defines the coefficient as (2(k-i)+3)/2 = k-i+3/2, which is larger by 2 for every term. Consequently, the constraints ‖ϖ[k]-p[k]‖∞ ≤ 𝓁 in Problem 4 are evaluated at positions that do not equal the actual positions produced by the acceleration sequence under the stated dynamics. A QP solution can therefore satisfy all constraints as written while the executed trajectory violates the waypoint constraints and the separation bound of Theorem 3. This error is load-bearing because the paper's central claim is that the posed QP is guaranteed feasible and that its solution is collision-free; the appendix lemmas construct accelerations using the correct recurrence, so the QP as stated is not the problem those lemmas solve.","section":"Section IV, Problem 4"},{"comment":"The proof of Lemma 5, and similarly Lemma 6, uses a rotation of coordinates so that the path segment lies on the x-axis, and then performs the construction coordinate-wise under assumptions such as vx[k] ∈ [0,Vmax], vy[k] ∈ [-Vmax,Vmax], and Ω[k+1] = Ω[k] + [𝓁,0,...]^T. These assertions are not valid for the ∞-norm constraints used in the paper. The ∞-norm is not invariant under rotation: for v with ‖v‖∞ ≤ Vmax, a rotated component can be as large as √d Vmax. Moreover, the rotation of an axis-aligned hypercube Ω[k] is generally not an axis-aligned hypercube in the rotated frame, so the coordinate-wise bounds on p[k] and the shifted-cube relation do not hold. Thus the constructed acceleration may violate the original acceleration bound and may not drive p[k+1] into Ω[k+1]. This invalidates the derivation of the feasibility conditions in Problem 2 and the proof of Theorem 3.","section":"Appendix, Lemma 5"},{"comment":"The feasibility proof assumes that consecutive waypoints are exactly 𝓁 apart (Problem 2, condition (i)), but the construction in Section IV-A sets κ_s = ceil(‖η[s+1]-η[s]‖/𝓁), giving spacing δ ≤ 𝓁, and adds duplicate waypoints at path nodes. The control designed in Lemma 5 produces a displacement of exactly 𝓁 along the path direction; when δ < 𝓁, a robot starting at the maximal allowable position in Ω[k] can be sent beyond Ω[k+1], so the proof does not cover the actual waypoint sequence generated by the algorithm. The paper does not explain how Problem 2's conditions are satisfied by the construction with non-uniform spacing and duplicate waypoints; Lemma 6 addresses duplicate waypoints but inherits the same rotation issues.","section":"Section IV-A and Lemma 5"},{"comment":"The claim that the bound |b(t)| ≤ (3/2)𝓁√d implies p(t) ∈ χFree requires a quantitative relationship between the path clearance 𝓁_m and the design parameter 𝓁. The paper asserts that 'Since there is a minimum clearance of 𝓁_m, this property guarantees a collision-free trajectory,' but it never states the required inequality 𝓁_m ≥ (3/2)𝓁√d. In the simulation benchmarks, 𝓁 = 0.05 is used in three dimensions, giving a deviation bound of approximately 0.13 m, while the reported clearance values are not shown to satisfy this inequality. In the experiments, 𝓁 = 0.02 yields a deviation bound of approximately 0.052 m, yet the stated maximum allowable 𝓁 derived from the robot radius, string diameter, and tracking error is 0.035 m, which would not satisfy the inequality if 𝓁_m = 0.035 m. Without this condition, Theorem 3 does not establish collision avoidance.","section":"Section IV, Theorem 3"}],"minor_comments":[{"comment":"There are several minor typographical issues: 'assumme' appears in Problem 2; the subscripts in the waypoint definition are inconsistently typeset (ϖs versus ϖ_s); and the dimension of the optimization variable in Problem 4 is written as R^{dK} although there are K+1 acceleration vectors, so the dimension should be d(K+1).","section":"Section IV, Problem 2 and Problem 4"},{"comment":"The caption of Figure 4 states that the separation is 'bounded by 2/3 𝓁√d', while the text and Theorem 3 give the bound as (3/2)𝓁√d. The fraction appears inverted in the caption.","section":"Figure 4 caption"},{"comment":"The definition of b(t) as a minimum of distances is nonnegative by construction, so the notation |b(t)| used in Lemma 7 and Theorem 3 is inconsistent; if b(t) is intended to be signed, its definition and the bound should be clarified.","section":"Section II and Lemma 7"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is the accepted version of a paper published in IEEE RA-L in 2017. The issues identified in this report concern the arXiv version as submitted. If the published version contains a corrected kinematics formula and a corrected proof, this report should be read accordingly; based on the present text, the central theoretical guarantees are not supported. The experimental work is strong, but the theoretical claims require substantial revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the paper has a nice, potentially useful idea—construct time-indexed waypoints along a sampling-based path and derive explicit Vmax and h so that a single convex QP is guaranteed feasible, avoiding iterative SCP. The experimental work is real: a Crazyflie flying through dense 3D obstacle fields, with comparisons to iSCP and CHOMP that show a clear edge in success rate and time. If the theory matched the implementation, this would be a solid RA-L contribution.\n\nUnfortunately, it doesn't match. The kinematics in Problem 4 are algebraically wrong. Under the stated constant-acceleration dynamics, the correct expansion is p[k] = p[0] + h k v[0] + h^2 Σ_{i=0}^{k-1} (k - i - 1/2) a[i]. The paper instead uses (h^2/2) Σ (2(k-i)+3) a[i], which is off by a factor of 5 for k=1 and inconsistent for every term. That's not a typo; the QP constraints are written with this erroneous p[k], so a feasible solution of the QP as posed does not satisfy the claimed waypoint constraints under the actual dynamics. Theorem 3, which is supposed to bound the trajectory deviation, therefore does not apply to the trajectory the robot would execute. This is load-bearing.\n\nTwo smaller gaps are worth noting. Lemma 5 assumes consecutive waypoints are exactly 𝓁 apart, but the construction uses ceil(‖η[s+1]−η[s]‖/𝓁), giving spacing ≤ 𝓁 plus duplicate waypoints at path nodes; this needs rework. And the collision-free guarantee silently requires a clearance inequality, 𝓁_m ≥ (3/2)𝓁√d, that is never stated; the benchmark uses 𝓁=0.05 in 3D, which would need about 0.13m clearance while they mention 0.05m. The authors may have inflated obstacles separately, but the paper should say so explicitly.\n\nThe empirical results are suggestive but don't rescue the theory: the QP solver is finding trajectories that work in practice, but the paper's central claim—guaranteed feasibility and collision-freedom—is not established. I don't see evidence of bad faith; the references are relevant and the approach is clearly a serious attempt. I just think the main theorem is broken as written.\n\nWho should read it: robotics people interested in hybrid sampling+optimization planning, and anyone who wants to see how a small algebraic slip can undermine a guarantee. I would not cite it as a correctness result until fixed.\n\nIf this were submitted fresh, I'd send it out—the idea deserves a serious referee and the errors look repairable. But I would expect major revision: fix the kinematics, redo Lemma 5 with the actual waypoint spacing, and state the clearance inequality. As it stands, it's not acceptable.","headline":"The paper's core promise of a guaranteed-feasible single-shot QP is undercut by an algebraic error in the kinematics that breaks the central theorem, though the idea and experiments are worth a serious revision.","tokens_in":15473,"tokens_out":6084,"would_cite":false,"duration_ms":55420,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that a sampling-based path can be turned into a dynamically feasible, collision-free trajectory by a single convex quadratic program, with a worst-case deviation bound that makes iterative optimization unnecessary.","keywords":["trajectory planning","sampling-based path planning","quadratic programming","convex optimization","collision avoidance","online planning","quadcopter navigation","cluttered environments"],"falsifier":"Run the planner in an environment where the true minimum clearance of the sampled path is measured, set $\\ell$ so that $\\ell_m < \\frac{3}{2}\\ell\\sqrt{d}$, solve the QP, and check whether the executed continuous trajectory enters the inflated obstacle region. If it does in any such case, the unconditional collision-free claim is false; if it never does for $\\ell=0.05$ with nominal clearance $0.05$ m in 3D, the bound is conservative or the realized clearance exceeds the nominal one.","tokens_in":14387,"feed_emoji":"🚁","tokens_out":8042,"duration_ms":77683,"temperature":0.7,"pith_summary":"This paper claims that online trajectory planning in a known cluttered environment can be split into two stages: a sampling-based planner finds an obstacle-free piecewise-linear path, and a single convex quadratic program turns that path into a time-parameterized trajectory respecting velocity and acceleration limits. The central guarantee is that the QP is always feasible, so no iterative or sequential convex programming is needed, and that the resulting continuous trajectory stays within $\\frac{3}{2}\\ell\\sqrt{d}$ of the guiding path, making it collision-free at every instant and not just at sampled waypoints. If this claim holds, dense-environment navigation can combine the reliability of sampling-based planners with the speed of convex optimization, which is why the authors report very high success rates and planning times of a fraction of a second on quadcopter experiments.","feed_headline":"One convex solve yields collision-free quadcopter trajectories","feed_subtitle":"Sampling plans the path; a single quadratic program adds dynamics and time, with a proven safety margin","key_machinery":"The load-bearing construction is the sequence of time-indexed waypoints $\\varpi[k]$ with hypercube soft constraints $\\Omega[k]$. Each waypoint sits on the sampled path, consecutive waypoints are separated by $\\ell$, and two identical waypoints are placed at every path vertex. The dynamical constants $V_{\\max}=\\sqrt{\\ell A_{\\max}}$ and $h=2\\sqrt{\\ell/A_{\\max}}$ are chosen so that crossing one hypercube in one time step is always possible with bounded acceleration; the duplicated vertex waypoints provide the extra time step needed to reverse direction safely. These choices make the QP's constraint set nonempty by construction, and the separation argument in Lemma 7 turns that into a continuous-time collision-free guarantee.","core_discovery":"The paper's core discovery is a constructive choice of waypoint spacing and time step that makes the feasibility problem trivial to satisfy. Along the sampled path it places waypoints $\\varpi[k]$ at Euclidean spacing $\\ell$, with duplicate waypoints at every vertex to handle sharp turns, and associates each with a hypercube $\\Omega[k]=\\{\\rho : \\|\\rho-\\varpi[k]\\|_\\infty\\le \\ell\\}$. Choosing $V_{\\max}^2=\\ell A_{\\max}$ and $h^2=4\\ell/A_{\\max}$, the authors prove through Lemmas 5-7 that a piecewise-constant acceleration exists moving the robot from any state in one hypercube to the next while respecting velocity and acceleration bounds, and that between samples the trajectory cannot depart more than $\\frac{3}{2}\\ell\\sqrt{d}$ from the guiding path. The QP then only has to minimize a cost such as jerk subject to these hypercube and bound constraints, and by Theorem 3 it is guaranteed feasible. This converts trajectory planning from a search over time durations and waypoint counts into a one-shot convex solve.","pith_inferences":["An implied tuning rule, not written in the paper, is to cap the deviation budget at about $0.38$ times the path's minimum clearance in three dimensions; this follows directly from the stated separation bound and gives a concrete safety-margin recipe for users.","Because the QP constraints only involve velocity and acceleration bounds, the same waypoint-hypercube construction should transfer to other differentially flat vehicles, not just quadcopters, by substituting the vehicle's acceleration limit.","The paper's table showing solve time decreasing as $\\ell$ grows suggests an online planner could adapt $\\ell$ during replanning, starting with a large margin for a fast initial solve and shrinking it later to shorten the trajectory."],"forward_implications":["A trajectory for a robot with bounded acceleration can be computed by solving one convex QP, so planning can run at the few-hundred-millisecond scale even in environments with hundreds of obstacles.","Because the QP is guaranteed feasible whenever the sampling planner finds a path with the required clearance, the overall success rate is essentially inherited from the sampling planner and is not degraded by the optimization stage.","The continuous trajectory, not just the discrete samples, is collision-free, so no post-hoc interpolation check or iterative time adjustment is needed.","The design parameter $\\ell$ controls a clear trade-off: smaller $\\ell$ gives shorter trajectories but longer solve times, while larger $\\ell$ produces faster solves and larger clearance margins.","Replanning can be triggered online while the robot executes a committed segment, supporting goal changes in obstacle-dense environments without restarting the whole pipeline."],"supporting_citations":[{"why":"Supplies the anytime sampling-based planner used to generate the obstacle-free path with high clearance.","marker":"[22]"},{"why":"Provides the asymptotic optimality and rewiring guarantees underlying the sampling-based path generation.","marker":"[3]"},{"why":"The free-space corridor QP whose waypoint-time assumption motivates the non-iterative feasibility guarantee.","marker":"[15]"},{"why":"A prior RRT* plus iterative-QP pipeline that the paper avoids by determining the trajectory time in closed form.","marker":"[11]"},{"why":"A sequential convex programming precursor whose required iterative solves motivate the one-shot formulation.","marker":"[12]"},{"why":"Motion planning with sequential convex optimization and convex collision checking; used as a comparison method.","marker":"[14]"},{"why":"Provides the incremental sequential convex programming baseline used in the benchmark comparisons.","marker":"[13]"},{"why":"CHOMP serves as a benchmark baseline and represents gradient-based trajectory optimization approaches.","marker":"[16]"},{"why":"Generates the Poisson forest benchmark environments used in the simulations.","marker":"[26]"},{"why":"Supplies the numerical solver used to solve the QP in the implementation.","marker":"[25]"}],"fun_headline_variants":["One convex QP yields guaranteed-feasible quadcopter paths","Sampling path, one QP: fast quadcopter planning","Guaranteed-feasible trajectories from a single convex optimization","One-shot convex solve for cluttered quadcopter navigation","Sampling finds a path; a single QP makes it a safe trajectory"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The collision-free guarantee assumes the sampled path truly keeps a minimum distance from obstacles of at least $\\frac{3}{2}\\ell\\sqrt{d}$, an inequality the paper never writes out; its benchmarks use $\\ell=0.05$ in 3D, which allows about $0.13$ m of deviation against a nominal clearance of $0.05$ m.","fun_headline_variants_meta":{"raw":{"variants":["One convex QP yields guaranteed-feasible quadcopter paths","Sampling path, one QP: fast quadcopter planning","Guaranteed-feasible trajectories from a single convex optimization","One-shot convex solve for cluttered quadcopter navigation","Sampling finds a path; a single QP makes it a safe trajectory"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000436,"raw_usage":{"total_tokens":2218,"prompt_tokens":945,"completion_tokens":1273,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":561,"completion_tokens_details":{"reasoning_tokens":1183}},"tokens_in":561,"tokens_out":1273,"duration_ms":9394,"temperature":1.0,"reasoning_tokens":1183,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:39:56.114926+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the planner in an environment where the true minimum clearance of the sampled path is measured, set $\\ell$ so that $\\ell_m < \\frac{3}{2}\\ell\\sqrt{d}$, solve the QP, and check whether the executed continuous trajectory enters the inflated obstacle region. If it does in any such case, the unconditional collision-free claim is false; if it never does for $\\ell=0.05$ with nominal clearance $0.05$ m in 3D, the bound is conservative or the realized clearance exceeds the nominal one.","supporting_citations":[{"cited_title":"Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic,","cited_arxiv_id":null,"evidence_quote":"Supplies the anytime sampling-based planner used to generate the obstacle-free path with high clearance."},{"cited_title":"Sampling-based algorithms for optimal motion planning,","cited_arxiv_id":null,"evidence_quote":"Provides the asymptotic optimality and rewiring guarantees underlying the sampling-based path generation."},{"cited_title":"Online generation of collision-free trajectories for quadrotor flight in unknown cluttered environments,","cited_arxiv_id":null,"evidence_quote":"The free-space corridor QP whose waypoint-time assumption motivates the non-iterative feasibility guarantee."},{"cited_title":"Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments,","cited_arxiv_id":null,"evidence_quote":"A prior RRT* plus iterative-QP pipeline that the paper avoids by determining the trajectory time in closed form."},{"cited_title":"Generation of collision-free trajectories for a quadrocopter fleet: A sequential convex programming approach,","cited_arxiv_id":null,"evidence_quote":"A sequential convex programming precursor whose required iterative solves motivate the one-shot formulation."},{"cited_title":"Motion planning with sequential convex optimization and convex collision checking,","cited_arxiv_id":null,"evidence_quote":"Motion planning with sequential convex optimization and convex collision checking; used as a comparison method."},{"cited_title":"Decoupled multiagent path planning via incremental sequential convex programming,","cited_arxiv_id":null,"evidence_quote":"Provides the incremental sequential convex programming baseline used in the benchmark comparisons."},{"cited_title":"CHOMP: Covariant hamiltonian optimization for motion planning,","cited_arxiv_id":null,"evidence_quote":"CHOMP serves as a benchmark baseline and represents gradient-based trajectory optimization approaches."},{"cited_title":"High-speed flight in an ergodic forest,","cited_arxiv_id":null,"evidence_quote":"Generates the Poisson forest benchmark environments used in the simulations."},{"cited_title":"[Online]","cited_arxiv_id":null,"evidence_quote":"Supplies the numerical solver used to solve the QP in the implementation."}],"review_version":1}