{"id":"375d8f15-15b5-4f07-bf44-c400dc17f264","arxiv_id":"2509.08521","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"FMTX extends FMT* with a cost-based re-evaluation rule and local obstacle repair so the same sampled tree can be replanned efficiently after environment changes, with claimed asymptotic optimality.","lead":"FMTX is a reworked Fast Marching Tree planner that repairs its search tree when obstacles move instead of rebuilding it, and the paper reports that it replans faster than RRTX in simulated dynamic environments. The work matters because fast replanning under moving obstacles is a core need for autonomous vehicles and warehouse robots.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's superset claim is false: after obstacle removal, closed endpoints of newly unblocked edges are never reinserted into V_open, so FMTX can miss shortcuts that from-scratch FMT* finds, breaking the AO proof.","rationale":"The reader correctly identified Lemma 2's superset argument as the weakest assumption. My stress-test goes further and shows the assumption is not just insufficiently justified but actually false: the algorithm described in Algorithms 4 and 5 does not reinsert closed endpoints of newly unblocked edges into V_open, so FMTX can fail to perform updates that from-scratch FMT* would perform. The concrete counterexample (goal G, robot R, intermediate A, detour B) demonstrates that after removing an obstacle that opens a shortcut G-A-R, the closed root G is never re-expanded, A is never discovered with its true low cost, and the robot retains a suboptimal path. This invalidates Lemma 2 and Corollary 3, which are the entire basis for the paper's central claim of recovering asymptotic optimality. The experimental comparisons of replanning time may still be of interest as a heuristic evaluation, but the paper's stated theoretical guarantee is contradicted by its own pseudocode. Hence the verdict should move from CONDITIONAL to REJECT, since the main claim is not merely unproven but demonstrably incorrect for the algorithm as specified. The paper's own Section 5.2 acknowledgment that rewiring events are only 'expected to be negligible' without a formal bound is a related but secondary issue; the primary flaw is the failure to re-expand closed endpoints, which does not require any probabilistic argument to refute.","tokens_in":19174,"tokens_out":15415,"duration_ms":472707,"concrete_test":"Implement the two-phase counterexample exactly as described: a 100x100 workspace with goal G=(0,0), robot R=(10,0), intermediate A=(5,0), and a detour node B=(5,10); initially place an obstacle blocking segment G-A so FMT* builds G-B-R (cost 10). Run FMTX through the static phase, then remove the obstacle and invoke UpdateObstacles followed by FMT*Expand. Record the cost of the path to R. If the cost remains approximately 10 instead of decreasing to approximately 2 (the true G-A-R cost), Lemma 2 is refuted. As a supplementary check, instrument QueueNeighbors to log all insertions into V_open during the obstacle-removal step; verify whether G or A is ever reinserted (the pseudocode predicts they are not). If the published code is available, run the same scenario with the released implementation.","verdict_should_be":"REJECT","load_bearing_attack":"The central AO claim rests on Lemma 2, which asserts that FMTX's update rule is a superset of FMT*'s and therefore its path cost is no worse than a from-scratch FMT* run. This is not merely unproven; it is false for the algorithm as specified. In UpdateObstacles (Algorithm 4), when an obstacle is removed, the endpoints V+ of newly unblocked edges are passed to QueueNeighbors (Algorithm 5), which inserts only neighbors y of each endpoint u with c(y)<infinity and y not in V_open. It never reinserts u itself. Thus any closed endpoint that is not also a neighbor of another endpoint remains closed and is never expanded again. Consider a minimal graph with goal G=(0,0), robot R=(10,0), and intermediate A=(5,0), plus an off-path node B such that the initial obstacle blocks edge G-A, so FMT* builds path G-B-R with cost 10 and closes G, B, and R. When the obstacle is removed, edge G-A becomes free with cost 1, and A-R is free with cost 1, giving a new optimal path G-A-R of cost 2. UpdateObstacles sets E+={(G,A)} and calls QueueNeighbors({G,A}). For u=G, neighbors with finite cost (e.g., B) are inserted, but A has c(A)=infinity and is skipped; G itself is not inserted. For u=A, neighbors with finite cost include R (cost 10), which is inserted, but A itself is skipped. The subsequent FMT*Expand pops R (cost 10) and may discover A with cost 15 via R, but it never expands G, so it never computes c(A)=1 or the improved c(R)=2. The robot's final cost remains 10, exceeding c_FMT*=2. This directly contradicts Lemma 2 and the Corollary 3 AO guarantee. The root cause is that the inherited state contains closed nodes that standard FMT* would expand (G is the root, expanded first in a from-scratch run), and FMTX has no mechanism to reopen them. The paper's own Section 5.2 only discusses rewiring of already-connected nodes, not this failure to re-expand closed endpoints, and Section 5.3's superset argument ignores it.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes FMTX, an extension of the Fast Marching Tree (FMT*) algorithm for dynamic replanning. The main algorithmic changes are a cost-based re-evaluation condition in the expansion step and incremental repair routines (AddObstacles, RemoveObstacles, QueueNeighbors) that update the tree when obstacles appear or disappear. The central theoretical claim is that, during any static interval between environmental changes, FMTX recovers a path whose cost is no larger than a from-scratch FMT* run on the same graph, and hence inherits FMT*'s asymptotic optimality (Lemma 2, Corollary 3). The paper reports simulations in 2D geometric and kinodynamic settings, comparing median replanning times against RRTX and reporting lower times in most configurations.","tokens_in":19565,"tokens_out":12204,"duration_ms":114653,"significance":"If the main claim were established, FMTX would be a valuable contribution: an asymptotically optimal dynamic replanner that retains FMT*'s lazy, batch-oriented expansion while repairing only locally invalidated parts of the tree. The experimental study is a strength: it covers multiple sample sizes, obstacle counts, neighborhood radius multipliers, and three kinodynamic models, with 30 trials per condition and publicly available source code. However, the asymptotic-optimality proof is load-bearing for the paper's stated contribution, and the proof of Lemma 2 is not valid; the algorithm as specified can fail to improve an inherited path even when a strictly better path becomes available after an obstacle removal. The experimental results may still be useful as evidence that the heuristic repair strategy is fast, but the paper's central theoretical claim is not supported.","major_comments":[{"comment":"The superset argument in the proof of Lemma 2 is invalid because FMTX does not start from the same state as a from-scratch FMT* run after an environmental change. In the algorithm as specified, Algorithm 4 (RemoveObstacles) considers only edges in the current tree edge set E, and Algorithm 5 (QueueNeighbors) inserts only finite-cost neighbors y of an endpoint u with y not already in V_open; it never reinserts the endpoint u itself. Consequently, a closed endpoint of a newly unblocked edge is never expanded again, and a non-tree edge that becomes collision-free is not even considered. A concrete Euclidean counterexample is: G=(0,0), R=(10,0), A=(5,0), B=(5,4), with an obstacle configuration that initially forces the tree G-B-R and leaves A unvisited. After the obstacle is removed, the optimal path G-A-R has cost 10 while the inherited path G-B-R has cost about 12.8. RemoveObstacles does not place G-A in E+ because that edge is not in the current tree, and there is no open node from which A can be rediscovered. Thus FMTX returns a path of cost 12.8, violating the inequality c_FMTx,n(G_n^k) <= c_FMT*,n(G_n^k) and invalidating Corollary 3.","section":"Section 5.3, Lemma 2"},{"comment":"The manuscript states that the probability of a rewiring event near obstacles is 'expected to be negligible' without providing a formal bound. This is not a proof, and the subsequent appeal to Theorem 4.1 of FMT* does not fill the gap: asymptotic optimality of the final path cost in the from-scratch algorithm does not by itself bound the probability of persistent suboptimal connections in a repaired tree that starts from an inherited, pruned state. Because Lemma 2 relies on the claim that FMTX performs every update that FMT* would perform, this missing bound is load-bearing. The paper needs either a rigorous probabilistic argument that such rewiring events are negligible, or a different proof strategy for the static-segment path-quality claim.","section":"Section 5.2"},{"comment":"The proof of Lemma 1 invokes 'Invariant 1' and 'Invariant 2' of FMT* without stating them, and the case analysis assumes that open nodes' costs always satisfy a Bellman optimality condition. In the modified FMT*Expand, the cost-based condition can also trigger on open nodes with finite cost, causing priority updates and rewiring, so the equivalence claimed in Lemma 1 is not obviously maintained once such updates occur. The lemma is stated only for obstacle-free environments, but the proof should make the scope explicit, and the paper should explain how the invariants are re-established after UpdateObstacles before they are used in the dynamic-setting argument.","section":"Section 5.1, Lemma 1"}],"minor_comments":[{"comment":"Replace the phrase 'expected to be negligible' either with a formal probability bound or with an explicit statement that this is an unproven heuristic assumption.","section":"Section 5.2"},{"comment":"Several table entries lack whitespace between numbers, e.g., '103.32 1.60204.86 3.68'; the formatting should be corrected for readability.","section":"Table 1"},{"comment":"The notation is inconsistent: the title and abstract use FMT$^{x}$, while the body mostly uses FMTX; unify the notation.","section":"Throughout"},{"comment":"The while loop condition 'c(V_open.top()) < c(v_robot) or v_robot in V_open' is not explained; clarify what happens when v_robot is not in V_open and has infinite cost, and why the expansion terminates.","section":"Algorithm 7"},{"comment":"The claim that a minimal localized update costs O((log n)^2) depends on the assumption that each Near query returns O(log n) neighbors in expectation; this should be stated explicitly as an expected-case bound.","section":"Section 6.1"},{"comment":"The kinodynamic description introduces Near+ and Near- as distinct neighbor queries, but the pseudocode in Algorithms 5 and 7 only refers to Near; align the pseudocode with the kinodynamic definitions.","section":"Section 7.1.3"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the proof of Lemma 2, which is not merely incomplete but appears false for the algorithm as written: closed endpoints of newly valid edges are never reinserted into V_open, and RemoveObstacles only inspects current tree edges. If the author can repair the algorithm (for example, by reopening endpoints and considering non-tree candidate edges) and give a correct argument for Corollary 3, the paper could be publishable. If the theoretical guarantee cannot be repaired, the paper should be reframed as a heuristic dynamic replanner and the abstract and title should be revised accordingly. I recommend major revision rather than rejection because the experimental study and the general repair concept are potentially salvageable, but the central claim requires substantial rework."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, the core idea is genuinely new: adapting FMT*’s single-pass wavefront into a dynamic replanner via a cost-based re-evaluation condition and local repair of only the invalidated region. That is a sensible extension, and the experiments back up the speed claim: FMTX consistently beats RRTX across dozens of conditions, with larger gains in denser graphs and harder kinodynamic models. The empirical work is solid—30 trials, median-based statistics, clear reporting of parameters and hardware.\n\nSecond, the theoretical guarantee is not established. Lemma 2 claims that FMTX’s update rule is a superset of FMT*’s and therefore the path cost is no worse than from-scratch FMT*. The proof is a handwave: it asserts the superset property without carefully accounting for the inherited, pruned state or the fact that FMTX can revisit nodes in a different order. Section 5.2 openly admits that rewiring events near obstacles are “expected to be negligible” without a bound. So the paper’s central AO claim is, as written, an assertion rather than a proof.\n\nNow the stress-test note: its counterexample does not hold up. The note says closed endpoints of newly unblocked edges are never reinserted into V_open. But in the proposed graph, after the obstacle is removed, QueueNeighbors is called on {G,A}. Processing u=A, the neighbors of A include G, whose cost is finite (0) and who is not in V_open, so G is inserted into V_open. Then FMT*Expand pops G, discovers A with cost 1, and the path cost drops to 2. The algorithm actually repairs itself in that scenario. So the specific failure mode described is not a genuine counterexample.\n\nThat said, the proof gap is still real. The superset argument needs to be made precise: one must show that every node that could be part of a better path is either reinserted directly or becomes reachable through the wavefront. The current text does not do that. Given the algorithm is plausible and the experiments are strong, this is fixable—but it requires real work, not just a sentence patch.\n\nMinor issues: the code link is malformed (contains a space), and the experimental comparison reports only replanning time, not path quality or success rate. The AO claim is the thing that would make path quality unnecessary, but since that claim is unproven, the missing metrics matter.\n\nWho is this for? Robotics practitioners who need a fast, asymptotically-optimal-in-practice replanner and are willing to trust the empirical trends. Theorists should treat the AO guarantee as open. It deserves a serious referee—the idea is novel, the experiments are substantial, and the proof gap is patchable. I would send it to peer review, with the expectation of a major revision focusing on Lemma 2.","headline":"FMTX is a plausible, well-tested dynamic replanner, but the asymptotic optimality proof is not rigorous; the stress-test counterexample misfires, yet the proof gap remains real.","tokens_in":20207,"tokens_out":4850,"would_cite":false,"duration_ms":47412,"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":"The paper claims that a modified Fast Marching Tree, FMTx, can repair its tree after obstacle changes and still match FMT*'s asymptotic optimality.","keywords":["dynamic replanning","Fast Marching Tree","FMT*","asymptotic optimality","sampling-based motion planning","RRTX","kinodynamic planning","lazy collision checking"],"falsifier":"Run FMTx and a from-scratch FMT* on the same fixed set of $n$ samples in a static environment immediately after each obstacle insertion and removal, using identical connection radii; if across many trials FMTx's converged path cost ever exceeds FMT*'s, Lemma 2's superset claim is false. A cleaner version is to construct a small graph where a disappearing obstacle restores a shortcut whose endpoint was pruned and never requeued, then compare final path costs.","tokens_in":18960,"feed_emoji":"🤖","tokens_out":6414,"duration_ms":51348,"temperature":0.7,"pith_summary":"FMTx is presented as a dynamic replanner built by a single change to the Fast Marching Tree procedure: replace the one-pass unvisited check with a cost-based re-evaluation condition, so nodes whose cost can improve are revisited and rewired. The paper argues this preserves FMT*'s sampling efficiency and lazy collision checking while allowing local repair of only the branches invalidated by moving obstacles. Its main theoretical claim is that during any static interval between obstacle changes, FMTx produces a path no more costly than a from-scratch FMT* run, and therefore inherits FMT*'s asymptotic optimality in probability. The reported experiments compare median replanning times against RRTX and find FMTx faster in most tested geometric and kinodynamic scenarios, with the advantage growing as graphs get denser and dynamics get more complex. This matters because robots operating near people must revise plans quickly without giving up optimality guarantees.","feed_headline":"One change makes the Fast Marching Tree replan in dynamic worlds","feed_subtitle":"FMTx repairs only invalidated branches, keeps FMT*'s optimality guarantee, and beats RRTx in replanning speed.","key_machinery":"The load-bearing object is the cost-ordered min-heap open set together with the modified expansion condition $c(x)>c(z)+\\mathrm{Cost}(z,x)$ for a neighbor $x$ reached from an expanding node $z$. The condition acts as a certificate: when it is true, $x$'s current cost is provably not the best available, so it is worth the more expensive search for the optimal parent $y_{\\min}$ among $x$'s open neighbors. The dynamic-update subroutines (AddObstacles, RemoveObstacles, QueueNeighbors) feed this queue by pruning, resetting, and requeueing only the affected portions of the tree. In the proof, an equivalence lemma shows that the cost condition coincides with unvisited-ness in obstacle-free runs, and a superset lemma bounds FMTx's path cost by FMT*'s path cost in each static phase.","core_discovery":"The central discovery is that FMT*'s single-pass limitation is not essential to its wavefront structure. In obstacle-free space, the modified rule $c(x)>c(z)+\\mathrm{Cost}(z,x)$ selects exactly the same neighbor set as the original unvisited-set rule, so FMTx behaves like FMT* when nothing changes. When an obstacle appears or disappears, FMTx prunes the descendant subtree of any blocked edge, resets those costs to infinity, requeues affected neighbors, and lets the cost-ordered expansion rewire them. The paper argues that this update set is a superset of FMT*'s operations, so the converged path cost on a static phase is no larger than FMT*'s, and then transfers FMT*'s asymptotic optimality in probability to FMTx. The paper also reports simulations in which FMTx beats RRTX on median replanning time, especially as obstacle count, sample count, and neighborhood radius grow.","pith_inferences":["A consequence not stated in the paper is that the same cost-based re-evaluation could probably handle goal changes by treating the goal entering or leaving the tree as a cost perturbation, with no change to the algorithm's structure.","Because Lemma 2 compares converged path costs rather than repair time, a testable prediction is that FMTx's advantage over RRTX depends on the size of the invalidated region and may shrink when an obstacle change disrupts a large part of the tree.","The superset argument suggests a stronger, also unproven property: repeated repairs should make node costs monotonically non-increasing across consecutive environmental updates, which could be checked empirically on a fixed sample set."],"forward_implications":["On any static interval, FMTx converges in probability to an optimal path as the sample count grows, so a robot can reuse its tree across obstacle changes without sacrificing FMT*'s optimality guarantee.","Only the portions of the tree invalidated by an obstacle change are pruned and requeued; unaffected branches keep their costs and parents.","Because FMTx retains FMT*'s lazy collision checking, expensive edge validation is deferred until a promising parent is chosen, which pays off in kinodynamic planning.","The reported comparison predicts that FMTx's speed advantage over RRTX grows with sample count, obstacle density, and neighborhood radius, and is largest for high-dimensional dynamic models.","FMTx remains a persistent-sample, batch planner rather than an anytime planner; the paper identifies adding new samples continuously as future work."],"supporting_citations":[{"why":"It supplies the original FMT* algorithm and its asymptotic-optimality theorem, which Lemma 2 and Corollary 3 extend to dynamic settings.","marker":"Janson et al. (2015)"},{"why":"It defines the RRTX replanner used as the experimental baseline and supplies the time-varying obstacle problem model.","marker":"Otte and Frazzoli (2016)"},{"why":"It introduces LPA*'s incremental repair idea that motivates selectively updating only affected parts of a search structure.","marker":"Koenig et al. (2004)"},{"why":"It provides the D* Lite local-repair paradigm adapted into FMTx's queue-based subtree repair.","marker":"Koenig and Likhachev (2005)"},{"why":"It establishes the asymptotic-optimality framework and RRT* rewiring concepts that define the comparison class for sampling-based planners.","marker":"Karaman and Frazzoli (2011)"},{"why":"It gives the kinodynamic FMT* framework with forward and backward reachable sets used in the kinodynamic experiments.","marker":"Schmerling et al. (2014)"}],"fun_headline_variants":["FMTx: Fast, optimal replanning for changing worlds","One tweak to FMT* enables efficient dynamic replan","FMTx beats RRTx with minimal change to FMT*","Replan only what's needed: FMTx does it","FMTx: Update costs selectively, stay optimal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Lemma 2 rests on the claim that FMTx's update operations form a superset of standard FMT*'s, so starting from an inherited, pruned tree with revisited nodes cannot yield a worse path than a fresh FMT* run.","fun_headline_variants_meta":{"raw":{"variants":["FMTx: Fast, optimal replanning for changing worlds","One tweak to FMT* enables efficient dynamic replan","FMTx beats RRTx with minimal change to FMT*","Replan only what's needed: FMTx does it","FMTx: Update costs selectively, stay optimal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000292,"raw_usage":{"total_tokens":1754,"prompt_tokens":1044,"completion_tokens":710,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":660,"completion_tokens_details":{"reasoning_tokens":623}},"tokens_in":660,"tokens_out":710,"duration_ms":6085,"temperature":1.0,"reasoning_tokens":623,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:01:03.732367+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run FMTx and a from-scratch FMT* on the same fixed set of $n$ samples in a static environment immediately after each obstacle insertion and removal, using identical connection radii; if across many trials FMTx's converged path cost ever exceeds FMT*'s, Lemma 2's superset claim is false. A cleaner version is to construct a small graph where a disappearing obstacle restores a shortcut whose endpoint was pruned and never requeued, then compare final path costs.","supporting_citations":[{"cited_title":"The International Journal of Robotics Research 35(7): 797--822","cited_arxiv_id":null,"evidence_quote":"It defines the RRTX replanner used as the experimental baseline and supplies the time-varying obstacle problem model."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It introduces LPA*'s incremental repair idea that motivates selectively updating only affected parts of a search structure."},{"cited_title":"IEEE Transactions on Robotics 21: 354--363","cited_arxiv_id":null,"evidence_quote":"It provides the D* Lite local-repair paradigm adapted into FMTx's queue-based subtree repair."},{"cited_title":"2015 54th IEEE Conference on Decision and Control (CDC) : 2574--2581 ://api.semanticscholar.org/CorpusID:2267285","cited_arxiv_id":null,"evidence_quote":"It gives the kinodynamic FMT* framework with forward and backward reachable sets used in the kinodynamic experiments."}],"review_version":2}