analiza aiqbench
FMT$^{\mathrm{X}}$ introduces a lazy wavefront search algorithm that enables efficient dynamic replanning by allowing node revisits when cost improvements are detected, addressing limitations in static-world planners like FMT$^{*}$. By deferring eager neighborhood rewiring to the expansion process, the method preserves lazy collision checking while maintaining asymptotic optimality and improving path consistency in changing environments. This advancement is significant for robotics applications requiring real-time trajectory updates under partial observability and dynamic obstacles.
FMT$^{\mathrm{X}}$: Lazy Wavefront Search for Dynamic Replanning
arXiv:2509.08521v2 Announce Type: replace 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.
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.
52 pages, 15 figures. Substantially revised version with strengthened asymptotic-optimality analysis, revised complexity analysis, expanded dynamic-replanning experiments, and updated presentation
Robotics (cs.RO); Artificial Intelligence (cs.AI); Systems and Control (eess.SY)
arXiv:2509.08521 [cs.RO]
(or arXiv:2509.08521v2 [cs.RO] for this version)
Text integral sub licența deschisă a publicației · 257 cuvinte
Subiecte conexe
Efficient World Action Model Inference with Adaptive Intermediate States
arXiv · 29 sept. 2026
When a Verified World Model Still Loses: Play-Adequacy vs Prediction-Accuracy in LLM-Synthesized Code World Models
arXiv · 21 iul. 2026
Schema-Adaptive Action-Conditioned JEPA for Cross-Machine CNC Transfer under Partial Sensor Overlap
arXiv · 16 sept. 2026
Trap-Quenched Matter-Wave Optics in Space
arXiv · 30 iul. 2026