{"id":"119ccb9c-072c-424e-95bd-9a396d4a0bbc","arxiv_id":"2411.19393","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Global Tensor Motion Planning is a layered, tensor-based sampling planner with value iteration that plans many paths in batch on GPUs and claims probabilistic completeness.","lead":"GTMP is a motion planning algorithm made entirely of tensor operations: it fixes a layered random graph of waypoints, checks all edges for collisions at once, and finds paths by value iteration. Because the whole pipeline is batchable, it plans thousands of paths on a GPU far faster than classical planners, which matters for robot learning datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's proof is invalid as written: Lemma 2 is false and the clearance inequality has the wrong sign, so the probabilistic-completeness guarantee is not established.","rationale":"The central claim of the paper is Theorem 1, which asserts probabilistic completeness for GTMP. The proof of this theorem contains a false lemma and a reversed inequality, so as written the claim is not established. This is more load-bearing than the reader's chosen weakest assumption (finite probing), because the finite-probe issue only concerns the gap between the abstract theorem and the implementation, whereas the proof flaw removes the guarantee even in the ideal case. The counterexample to Lemma 2 is decisive: linear interpolation of a line has zero error, so the claimed lower bound L/n cannot hold. The clearance inequality also has the wrong direction; the distance from the interpolant to the obstacle is at least the clearance of the original path minus the interpolation error, not at most. The correct PRM-style argument would use an upper bound on interpolation error and a positive clearance margin, and would likely yield a similar exponential concentration bound, so the theorem may be repairable. The empirical batch-speedup results are plausible and the algorithm is clearly described, but the theoretical guarantee is the stated novelty and must be corrected before the claim can be accepted. Since the reader already issued a CONDITIONAL verdict, the current recommendation is unchanged: the paper should be accepted only if the proof is repaired and the finite-probe gap is closed.","tokens_in":13943,"tokens_out":7217,"duration_ms":70580,"concrete_test":"Verify Lemma 2 directly: take f(t)=t on [0,1], n=1, so the piecewise-linear interpolant is g=f; then TV(f)=1 but ||f-g||_infty=0, contradicting ||f-g||_infty > L/n. Then re-derive Theorem 1 with the corrected clearance inequality r >= R - sup||g-f|| and with a genuine upper bound on the interpolation error; if Eq. (16) cannot be recovered under these corrections, the proof is not salvageable in its current form.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section VII, Lemma 2 asserts that a piecewise-linear interpolant g of f with n equal subintervals satisfies ||f-g||_infty > TV(f)/n. This is false: take f(t)=t, g=f with n=1; then TV(f)=1 but ||f-g||_infty=0, contradicting the claimed lower bound. The proof of Theorem 1 needs an upper bound on interpolation error to ensure the approximating path g stays inside the free space, not a lower bound. In the same proof, the displayed chain defines r as the clearance of g and claims r <= clearance(f) - sup||g-f|| < R - L/(M+1). The triangle inequality gives the reverse, r >= R - sup||g-f||; the asserted upper bound on r is generally false. Since the safe sampling radius around the waypoints g(t_m) must be no larger than r, the event whose probability is bounded in Eq. (16) is not established. Independently, Algorithm 1 checks edges by H=10 probe points (Section III-C), while Theorem 1 assumes the exact continuous integral cost in Eq. (3); a thin obstacle can pass between probe points, so the returned 'feasible' path may collide and the theorem does not apply to the algorithm as actually run. The probabilistic-completeness claim is therefore unsupported as written, although the PRM-style clearance argument is probably repairable.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes GTMP, a sampling-based motion planner in which the configuration space is discretized as a random multipartite graph with M layers of N uniformly sampled waypoints. All operations, including sampling, collision checking, and the Bellman updates used to find a shortest path from the start to a set of goals, are expressed as fixed-shape tensor operations and can be batch-vectorized over planning instances. The paper also introduces an Akima-spline variant that plans cubic-spline paths without gradient optimization. The central theoretical claim is Theorem 1, which asserts probabilistic completeness with a quantitative failure bound; the experimental section reports large wall-clock speedups for batch planning on planar occupancy maps and on MotionBenchMarker Panda tasks, together with an ablation over M and N.","tokens_in":14233,"tokens_out":8627,"duration_ms":75319,"significance":"The contribution is algorithmically appealing: the multipartite structured graph is a genuine departure from incremental tree/roadmap construction, the complexity analysis and implementation are clear, and the reported batch speedups (about 50x over VAMP/RRTC and orders of magnitude over OMPL baselines in the authors' setup) would be practically useful for generating training data. The derivation does not fit parameters to data, and the ablation heatmaps give useful evidence about the role of M and N. However, the paper's probabilistic-completeness guarantee is the main theoretical contribution, and as it stands the proof has a false lemma and an incorrect inequality; the theorem therefore does not yet support the claim. The empirical evaluation is not enough to substitute for the proof, because the reported collision-free percentages are produced by the same approximate collision checker whose gap with the theorem is unaddressed.","major_comments":[{"comment":"Lemma 2 is false as stated: for f(t)=t on [0,1] and g=f (n=1), TV(f)=1 while ||f-g||_∞=0, contradicting the claimed lower bound ||f-g||_∞ > L/n. More importantly, the proof of Theorem 1 needs an upper bound on the interpolation error, not a lower bound, because the clearance of the piecewise-linear approximant g satisfies r ≥ R - ||g-f||_∞ by the triangle inequality. The proof instead asserts r ≤ R - sup||g-f|| < R - L/(M+1), which reverses the triangle inequality. Consequently the event ||h-g||_∞ < r_h with r_h = R - L/(M+1) is not sufficient to guarantee the sampled path h is feasible, and the probability bound in Eq. (16) is not established. This is the load-bearing step of the probabilistic-completeness claim. A repair would replace Lemma 2 with a uniform-continuity or Lipschitz bound that makes ||g-f||_∞ < R/2 and then derive a lower bound on r; the constants in Theorem 1 would need to be re-derived accordingly.","section":"Section VII, Lemma 2 and Theorem 1 proof"},{"comment":"The implementation computes the collision term of Eq. (3) by evaluating the cost at H equidistant probe points per edge and averaging, rather than computing the exact continuous integral. Theorem 1 assumes the exact integral, so a thin obstacle lying strictly between two probe points is invisible to the algorithm; the returned 'feasible' path may collide, and the probability bound does not describe the algorithm as actually run. This is not a cosmetic mismatch: the experimental CF% metric is computed by the same approximate checker. The authors should either extend the analysis to a discretized/probed collision check, for example under an explicit clearance assumption relating obstacle thickness to the probe spacing, or state clearly that the guarantee applies only to an idealized continuous collision-checking oracle and adjust the empirical claims accordingly.","section":"Section III-C and Algorithm 1 vs. Eq. (3)"}],"minor_comments":[{"comment":"The line-integral notation is inconsistent: for a straight-line edge f(t)=q+t(q'-q), t∈[0,1], the arclength factor is ||f'(t)||=||q'-q||, not f'=1/||q'-q|| as stated. Please correct the definition or the parameterization.","section":"Section III, Eq. (3)"},{"comment":"The path tracing part sets P={i} and then appends Q[m,i] for m=1,...,M-1 and G[i]; the start q0 and the first-layer waypoint Q[0,i] are not both included. Please clarify the indexing so that the output is a sequence of configurations from q0 to a goal.","section":"Algorithm 1, Lines 8--13"},{"comment":"The symbol G is used both for the random multipartite graph and for the goal set in the problem statement; Theorem 1's 'G' is therefore ambiguous. Please use separate symbols, for example G_g for the goal set.","section":"Section VII and Definition 2"},{"comment":"The modified-Akima weights use m_{m,i,j}, m_{m-1,i,j}, etc., before the indices are fully defined, and the sums over i,j are not clear; a precise definition would help reproducibility.","section":"Appendix VI, Eq. (10)"}],"recommendation":"major_revision","confidential_remarks":"The paper has a serious but localized flaw in the proof of Theorem 1 and a gap between the theoretical collision model and the implementation. I believe both are repairable without changing the algorithm or the experimental design. If the authors fix the proof and explicitly scope the collision-checking assumption, the paper could be suitable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the core idea is real: fixed-shape random multipartite graph plus value iteration gives a fully tensorized planner, and the reported batch speedups are plausible. The Akima spline extension is a useful add-on. The ablations are informative. Second, the probabilistic completeness proof in Section VII is broken as written. Lemma 2 is false: the piecewise-linear interpolant of f(t)=t with one interval has zero error but total variation 1, contradicting the claimed lower bound. The proof of Theorem 1 then uses the triangle inequality in the wrong direction, claiming r <= R - L/(M+1) when the true bound is r >= R - sup||g-f||. That sign error is load-bearing. Additionally, Algorithm 1 checks edges with H=10 probe points while the theorem assumes exact continuous integration, so the guarantee does not apply to the implementation. A thin obstacle can slip between probes. These are serious but repairable. The algorithmic structure is sound; a corrected clearance argument with a real upper bound on interpolation error should restore a completeness guarantee for an idealized continuous checker. The probe gap requires either a conservative checker or a restated theorem. The paper honestly notes that Theorem 1 does not cover the Akima variant. Who should read this: anyone building batch planners or using vectorized planning for learning. It deserves a serious referee. My recommendation: send to peer review, condition acceptance on fixing the proof and aligning the theorem with the implementation.","headline":"GTMP's tensor multipartite-graph planner is a genuinely useful batch-planning contribution with plausible speedups, but the appendix's probabilistic completeness proof is broken as written and needs repair.","tokens_in":739,"tokens_out":1028,"would_cite":false,"duration_ms":25347,"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 motion planner that represents the discretized configuration space as a fixed-shape random multipartite graph can run entirely as tensor operations, vectorize over batches of planning instances, and carries a probabilistic-completeness…","keywords":["motion planning","batch planning","probabilistic completeness","tensor operations","random multipartite graph","value iteration","spline planning","GPU acceleration"],"falsifier":"Take a 2D occupancy map with a wall so thin that the straight line from start to goal crosses it only between two consecutive probe points of an $H$-point discretization, and run GTMP with the paper's default $H$; if the planner returns the crossing segment as collision-free, that shows the implemented collision check is not the integral assumed in Theorem 1.","tokens_in":13767,"feed_emoji":"🤖","tokens_out":13535,"duration_ms":107358,"temperature":0.7,"pith_summary":"GTMP is a sampling-based motion planner that replaces the usual incremental tree or roadmap with a fixed-shape random multipartite graph: a start layer, $M$ layers of $N$ uniformly sampled waypoints, and a goal layer, with all pairwise edges between consecutive layers. Because every layer has the same cardinality, the graph, its collision costs, and its value-iteration search are plain tensor operations, so an entire batch of planning instances can be vectorized on GPU/TPU hardware. The paper proves a probabilistic-completeness bound: for a feasible planning problem with $M$ at least the minimum number of segments, the probability that GTMP finds a finite-cost path is at least $1 - M\\exp(-a (R - L/(M+1))^d N)$, so success approaches certainty exponentially in the number of samples per layer. The practical payoff is batch planning that the authors report as roughly 50 times faster than a strong vectorized baseline and orders of magnitude faster than classical CPU planners, with a spline extension that returns smooth paths without gradient optimization. The authors position GTMP as a fast, parallel, provably complete way to generate diverse training trajectories for robot learning.","feed_headline":"50x faster batch robot planning via tensor graph","feed_subtitle":"By sampling waypoint layers as tensors, GTMP vectorizes collision checks and search with a completeness guarantee.","key_machinery":"The central object is the random multipartite graph: a directed graph whose node set is organized into fixed layers (start, $M$ sampled waypoint layers, goals), with all pairwise forward edges between consecutive layers. Because every layer holds exactly $N$ nodes, the graph is stored as tensors, and all operations—uniform sampling, probing collision costs along edges, and the dynamic-programming update as a matrix-reduced min—are tensor reductions that can be broadcast over a batch dimension. The search is finite value iteration: with $M+1$ iterations the value function converges exactly on this acyclic layered graph, and path tracing returns a path of exactly $M+1$ segments. The spline variant builds the same layered graph but replaces straight-line edges with local piecewise-cubic splines, so the returned path is already $C^1$ smooth without a separate optimization step.","core_discovery":"The central claim is that a planning problem can be discretized as a complete multipartite graph with a fixed number of layers, and that this fixed shape is exactly what makes planning batchable. Let layer $m$ contain $N$ waypoints sampled uniformly in configuration space; connect every waypoint in layer $m$ to every waypoint in layer $m+1$, with the start connected to layer 1 and the last layer to the goal set. GTMP computes the straight-line collision-and-length cost of every edge, stores all costs in tensors, and runs $M+1$ dynamic-programming value iterations to extract the least-cost path. Theorem 1 states that when $M$ is at least a problem-dependent minimum $M_m$, the probability that this procedure terminates with a finite path cost is at least $1 - M\\exp(-a (R - L/(M+1))^d N)$, where $R$ is the clearance of the true feasible path, $L$ its arc length, and $a$ a constant from the uniform measure; hence the planner is probabilistically complete and the per-batch work scales as tensor operations. The same tensor graph, with edges replaced by local piecewise-cubic splines, produces $C^1$ smooth paths without any gradient-based refinement, at the cost of not carrying the same completeness guarantee.","pith_inferences":["Going beyond the paper: the exponential bound suggests an anytime outer loop that grows $M$ and $N$ until at least one path in the batch is feasible; the paper mentions this direction but does not prove its behavior.","Going beyond the paper: the completeness theorem is explicitly not extended to spline edges, so a user relying on the smooth variant for execution should treat collision-freeness of those edges as an empirical matter, not a guaranteed one.","Going beyond the paper: the finite-probe collision check means the practical guarantee depends on obstacle geometry; environments with thin walls can evade the theorem, and adaptive or continuous collision checking would close that gap.","Going beyond the paper: because the graph is fixed-shape and acyclic, the same tensor construction could serve as a differentiable cost-to-go oracle for policy learning, not only as a batch planner; this is a natural extension of the paper's stated direction rather than an evaluated result."],"forward_implications":["For any feasible problem with $M \\ge M_m$, the failure probability decays exponentially in $N$, so a modest number of samples per layer already gives high success probability and the bound quantifies the trade-off between more layers and more samples.","Since every path has exactly $M+1$ segments, planning time and path length are predictable, and no simplification routines are needed after search.","The entire algorithm is vectorized over a batch dimension, so the authors report amortized batch planning roughly 50 times faster than a strong vectorized baseline and orders of magnitude faster than standard CPU sampling planners on the tested tasks.","With the spline construction, GTMP returns $C^1$ smooth paths directly, matching the smoothness of optimization-based planners without requiring gradient information.","Because the value iteration is a composition of differentiable tensor operations, GTMP can act as a differentiable global planner or as a warm-starter for local trajectory optimizers."],"supporting_citations":[{"why":"Introduces the classic probabilistic roadmap and the completeness notion that Theorem 1 extends to a tensorized layered graph.","marker":"[1]"},{"why":"Serves as the single-query sampling baseline whose incremental tree structure GTMP contrasts with fixed-layer tensor search.","marker":"[2]"},{"why":"GPU-parallel optimization-based planner used as a smoothness and speed baseline for the spline variant.","marker":"[11]"},{"why":"The vectorized sampling baseline whose batch performance GTMP is measured against in the headline speed comparison.","marker":"[22]"},{"why":"Provides the local piecewise-cubic interpolation used to give graph edges smoothness in the spline variant.","marker":"[34]"},{"why":"Supplies the state-machine and value-iteration formulation used for search on the multipartite graph.","marker":"[35]"},{"why":"Establishes convergence of the asynchronous value iterations that the algorithm runs.","marker":"[37]"}],"fun_headline_variants":["Tensor-only planner achieves probabilistic completeness","Batch motion planning with tensor graphs and GPU speed","Smooth splines from tensor planning, no gradient needed","GTMP: vectorized planning with completeness and splines","Tensor graph planning: 50x faster batch robot paths"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that the edge collision cost is the exact continuous integral of the occupancy function along the edge, but the implementation approximates it with $H$ discrete probe points; a thin obstacle lying between two probe points can therefore be missed, and the completeness guarantee as proven does not apply to the algorithm as actually run.","fun_headline_variants_meta":{"raw":{"variants":["Tensor-only planner achieves probabilistic completeness","Batch motion planning with tensor graphs and GPU speed","Smooth splines from tensor planning, no gradient needed","GTMP: vectorized planning with completeness and splines","Tensor graph planning: 50x faster batch robot paths"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000506,"raw_usage":{"total_tokens":2472,"prompt_tokens":950,"completion_tokens":1522,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":566,"completion_tokens_details":{"reasoning_tokens":1448}},"tokens_in":566,"tokens_out":1522,"duration_ms":11137,"temperature":1.0,"reasoning_tokens":1448,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:13:18.759136+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a 2D occupancy map with a wall so thin that the straight line from start to goal crosses it only between two consecutive probe points of an $H$-point discretization, and run GTMP with the paper's default $H$; if the planner returns the crossing segment as collision-free, that shows the implemented collision check is not the integral assumed in Theorem 1.","supporting_citations":[{"cited_title":"Prob- abilistic roadmaps for path planning in high-dimensional configuration spaces,","cited_arxiv_id":null,"evidence_quote":"Introduces the classic probabilistic roadmap and the completeness notion that Theorem 1 extends to a tensorized layered graph."},{"cited_title":"Rrt-connect: An efficient approach to single-query path planning,","cited_arxiv_id":null,"evidence_quote":"Serves as the single-query sampling baseline whose incremental tree structure GTMP contrasts with fixed-layer tensor search."},{"cited_title":"Curobo: Parallelized collision-free robot motion generation,","cited_arxiv_id":null,"evidence_quote":"GPU-parallel optimization-based planner used as a smoothness and speed baseline for the spline variant."},{"cited_title":"Motions in microsec- onds via vectorized sampling-based planning,","cited_arxiv_id":null,"evidence_quote":"The vectorized sampling baseline whose batch performance GTMP is measured against in the headline speed comparison."},{"cited_title":"A method of bivariate interpolation and smooth surface fitting based on local procedures,","cited_arxiv_id":null,"evidence_quote":"Provides the local piecewise-cubic interpolation used to give graph edges smoothness in the spline variant."}],"review_version":1}