动态环境中高效重规划路径,比传统方法更省计算且保持高精度。
FMT$^{\mathrm{X}}$: Lazy Wavefront Search for Dynamic Replanning
- 用成本改进测试替代未访问节点集,允许节点被重新访问优化路径。
- 在障碍物变化时快速重构路径,修复效率优于多数现有方法。
- 适合需要实时重规划的机器人导航与自动驾驶场景。
FMT$^{*}$ 通过代价有序波前和懒惰碰撞检测在静态环境中高效规划,但其单次遍历的未访问规则无法应对动态障碍物变化。本文提出 FMT$^{ ext{X}}$,一种任意时间、渐近最优的波前泛化方法,支持动态重规划。成本改进测试取代未访问集,使节点在发现更低代价连接时可被重新访问以选择最优父节点,从而在保留懒惰碰撞检查的同时实现隐式重连。FMT$^{ ext{X}}$ 保持 RRT$^{*}$ 的在线稠密化特性,但将主动邻域重连推迟至代价有序波前中,仅当波前扩展到该节点时才重新访问。障碍物更新会断开受影响子树并重新播种波前。从每个父节点直接向子节点传播成本改进,确保后代代价一致性,这是隐式重连无法保证的属性。我们在几何与运动学场景(包括部分可观测性)中对比了固定图批处理版本 D-FMT$^{*}$ 与 D$^{*}$ Lite、以及 FMT$^{ ext{X}}$ 与激进 RRT$^{ ext{X}}$ 及路径中心型 LLPT$^{*}$。D-FMT$^{*}$ 在路径质量接近的情况下显著减少碰撞检测次数。FMT$^{ ext{X}}$ 在修复开销上介于 LLPT$^{*}$ 与 RRT$^{ ext{X}}$ 之间,同时保持 RRT$^{ ext{X}}$ 的可靠性和轨迹质量。研究显示,碰撞检测策略影响中位修复延迟、尾部修复时间及执行轨迹质量。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。