FMT$^{\mathrm{X}}$: Lazy Wavefront Search for Dynamic Replanning

Soheil Espahbodi Nia

FMT$^{\mathrm{X}}$: Lazy Wavefront Search for Dynamic Replanning

T0 review · 3 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that a modified Fast Marching Tree, FMTx, can repair its tree after obstacle changes and still match FMT*'s asymptotic optimality.

desk verdict 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. read the letter →

arxiv 2509.08521 v2 pith:CLORXR3N submitted 2025-09-10 cs.RO cs.AIcs.SYeess.SY

Soheil Espahbodi Nia This is my paper · ORCID

classification cs.ROcs.AIcs.SYeess.SY

keywords dynamicreplanningFastMarchingTreeFMT*asymptoticoptimalitysampling-basedmotionplanningRRTXkinodynamiclazycollisionchecking

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

Second, 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.

Now 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.

That 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.

Minor 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.

Who 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.

Referee Report

3 major / 6 minor

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.

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 (3)

[Section 5.3, Lemma 2] 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 5.2] 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 5.1, Lemma 1] 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.

minor comments (6)

[Section 5.2] 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.
[Table 1] Several table entries lack whitespace between numbers, e.g., '103.32 1.60204.86 3.68'; the formatting should be corrected for readability.
[Throughout] The notation is inconsistent: the title and abstract use FMT$^{x}$, while the body mostly uses FMTX; unify the notation.
[Algorithm 7] 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 6.1] 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 7.1.3] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper imports FMT* as an external baseline and its derivations do not reduce to their own inputs.

full rationale

The paper's central claim is that FMTX inherits FMT*'s asymptotic optimality during static intervals. That claim rests on two lemmas. Lemma 1 is a genuine equivalence proof between the cost-based neighbor-selection criterion and FMT*'s unvisited-set criterion; it invokes FMT* invariants from Janson et al. (2015), which is an external, independently established result, and the equivalence is not assumed as the conclusion. Lemma 2 attempts to show that FMTX's update operations form a superset of FMT*'s, so its path cost cannot be worse; this is a claimed property of the algorithm's execution, not a redefinition of the target quantity, and it is argued from the algorithm's stated rules rather than from the conclusion being proved. The known weakness of Lemma 2 is that the superset assertion appears false after obstacle removals because closed endpoints of newly unblocked edges are never reinserted into V_open; that is a soundness gap in the proof, not a circularity. Section 5.2's statement that rewiring events are 'expected to be negligible' is an unformalized heuristic, but it is not presented as a theorem that defines the result into existence. The experimental section compares FMTX against RRTX using externally defined metrics and does not fit parameters to produce the claimed optimality guarantee. There are no self-citations, no fitted quantity renamed as a prediction, and no imported uniqueness theorem used to force a choice. Accordingly, no circular step can be exhibited, and the appropriate score is 0.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central proof imports FMT*'s asymptotic optimality theorem, sampling assumptions, and invariants as external results. The algorithm introduces no new physical entities. The only experimental free parameter is the radius multiplier C. The weakest part of the ledger is the assumption that FMT*'s invariants transfer to the modified expansion, which is exactly where the proof in Section 5.3 becomes hand-wavy.

free parameters (1)

Neighborhood radius multiplier C = C in {1.0, 1.5, 2.0} (experimental choices)
Scales the theoretical radius constant gamma* from FMT*/RRT* theory. It is chosen for experiments, not fitted to data, and the asymptotic optimality claim treats any sufficiently large gamma as valid.

assumptions (4)

domain assumption FMT* is asymptotically optimal (Theorem 4.1 in Janson et al. 2015)
Used directly in Corollary 3 and used to argue that rare suboptimal connections disappear in the limit. The paper does not rederive this theorem.
domain assumption FMT* Invariants 1 and 2 hold in the modified FMTX expansion
Lemma 1's equivalence proof relies on these invariants from FMT*. The modified algorithm allows priority updates and node revisits, so the invariants require re-verification rather than simple import.
domain assumption Sampling and connection-radius assumptions for asymptotic optimality
Imported from FMT*/RRT* theory, including uniform i.i.d. samples and a connection radius r_n = gamma * (log n / n)^(1/d). These assumptions are needed for convergence in probability in Corollary 3.
standard math Cost obeys the triangle inequality on the r_n-disk graph
Used in Lemma 1, Case B, and in the cost-comparison argument in Lemma 2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of FMT$^{\mathrm{X}}$: Lazy Wavefront Search for Dynamic Replanning." pith.science (2026). https://pith.science/paper/CLORXR3N

@misc{pith2026250908521,
  author       = {Pith},
  title        = {Pith review of: FMT$^\mathrmX$: Lazy Wavefront Search for Dynamic Replanning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CLORXR3N}},
  note         = {Machine review of arXiv:2509.08521}
}

abstract

FMT$^{*}$ plans efficiently in static worlds by expanding a cost-ordered wavefront and collision-checking lazily, but its single-pass unvisited rule cannot revise paths when obstacles change. We present FMT$^{\mathrm{X}}$, an anytime, asymptotically optimal generalization of that wavefront for dynamic replanning. A cost-improvement test replaces the unvisited set, allowing a node to be revisited for best-parent selection whenever a lower-cost potential connection is found. This induces implicit rewiring within the wavefront while preserving lazy collision checking. FMT$^{\mathrm{X}}$ retains the online densification of RRT$^{*}$ but defers its eager neighborhood rewiring to the cost-ordered wavefront, so a node is revisited only when the expansion reaches it. Obstacle updates orphan the affected subtree and reseed the wavefront. A direct cost push from each parent to its children propagates cost improvements through validated tree edges, thereby preserving descendant cost consistency, a property not guaranteed by implicit rewiring alone. We compare a fixed-graph batch variant, Dynamic FMT$^{*}$ (D-FMT$^{*}$), with D$^{*}$ Lite on identical PRM$^{*}$ graphs, and FMT$^{\mathrm{X}}$ with eager RRT$^{\mathrm{X}}$ and path-centric LLPT$^{*}$ in geometric and kinodynamic scenes, including partial observability. D-FMT$^{*}$ stays close on path quality at far fewer collision checks. FMT$^{\mathrm{X}}$ lies between LLPT$^{*}$ and RRT$^{\mathrm{X}}$ on repair effort while tracking the reliability and trajectory quality of eager RRT$^{\mathrm{X}}$. The study shows that collision-checking policy affects median repair latency, repair-time tails, and executed trajectory quality.