FMT$^{x}$: An Efficient and Asymptotically Optimal Extension of the Fast Marching Tree for Dynamic Replanning

• URL: http://arxiv.org/abs/2509.08521v1
• Date: Wed, 10 Sep 2025 11:57:56 GMT
• Title: FMT$^{x}$: An Efficient and Asymptotically Optimal Extension of the Fast Marching Tree for Dynamic Replanning
• Abstract summary: This paper introduces FMT$x$, an extension of the Fast Marching Tree algorithm that enables efficient and consistent replanning in dynamic environments.<n>By maintaining a cost-ordered priority queue and applying a selective update condition, FMT$x$ ensures that suboptimal routes are efficiently repaired as the environment evolves.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Path planning in dynamic environments remains a core challenge in robotics, especially as autonomous systems are deployed in unpredictable spaces such as warehouses and public roads. While algorithms like Fast Marching Tree (FMT$^{*}$) offer asymptotically optimal solutions in static settings, their single-pass design prevents path revisions which are essential for real-time adaptation. On the other hand, full replanning is often too computationally expensive. This paper introduces FMT$^{x}$, an extension of the Fast Marching Tree algorithm that enables efficient and consistent replanning in dynamic environments. We revisit the neighbor selection rule of FMT$^{*}$ and demonstrate that a minimal change overcomes its single-pass limitation, enabling the algorithm to update cost-to-come values upon discovering better connections without sacrificing asymptotic optimality or computational efficiency. By maintaining a cost-ordered priority queue and applying a selective update condition that uses an expanding neighbor to identify and trigger the re-evaluation of any node with a potentially suboptimal path, FMT$^{x}$ ensures that suboptimal routes are efficiently repaired as the environment evolves. This targeted strategy preserves the inherent efficiency of FMT$^{*}$ while enabling robust adaptation to changes in obstacle configuration. FMT$^{x}$ is proven to recover an asymptotically optimal solution after environmental changes. Experimental results demonstrate that FMT$^{x}$ outperforms the influential replanner RRT$^{x}$, reacting more swiftly to dynamic events with lower computational overhead and thus offering a more effective solution for real-time robotic navigation in unpredictable worlds.

Related papers

• Dynamic Important Example Mining for Reinforcement Finetuning [53.98969373888718]
  Reinforcement fine-tuning (RFT) is increasingly used to strengthen the reasoning abilities of large models.<n>Most data-centric RFT methods rely on static or sample selection, implicitly assuming a sample's value is fixed over training.<n>We propose Dynamic Important Example Mining (DIEM), a principled and fully automated framework that makes data utilization adaptive throughout RFT.
  arXiv  Detail & Related papers  (2026-08-29T13:12:25Z)
• When Descent Is Too Stable: Event-Triggered Hamiltonian Learning to Optimize [4.395018007457715]
  Fixed-budget non optimization can fail because local descent is too stable.<n>We introduce structured adaptiveHamiltonian task-family for event-triggered minima hunting.
  arXiv  Detail & Related papers  (2026-05-07T19:10:48Z)
• Universally Empowering Zeroth-Order Optimization via Adaptive Layer-wise Sampling [43.822941944402544]
  Zeroth-Order optimization presents a promising memory-efficient paradigm for fine-tuning Large Language Models.<n>However, its practical adoption is severely constrained by slow wall-clock convergence and high estimation variance.<n>We propose AdaLeZO, an Adaptive Layer-wise ZO optimization framework.
  arXiv  Detail & Related papers  (2026-04-20T13:37:31Z)
• Neural Nonmyopic Bayesian Optimization in Dynamic Cost Settings [73.44599934855067]
  LookaHES is a nonmyopic BO framework designed for dynamic, history-dependent cost environments.<n>LookaHES combines a multi-step variant of $H$-Entropy Search with pathwise sampling and neural policy optimization.<n>Our innovation is the integration of neural policies, including large language models, to effectively navigate structured, domain-specific action spaces.
  arXiv  Detail & Related papers  (2026-01-10T09:49:45Z)
• Cost-Sensitive Freeze-thaw Bayesian Optimization for Efficient Hyperparameter Tuning [51.6191275658441]
  We introduce emphutility in the freeze-thaw framework, a function describing the trade-off between the cost and performance.<n>We validate our algorithm on established multi-fidelity HPO benchmarks and show that it outperforms all the previous freeze-thaw BO and transfer-BO baselines.
  arXiv  Detail & Related papers  (2025-10-24T12:03:57Z)
• Parametrized Multi-Agent Routing via Deep Attention Models [1.0377683220196872]
  We propose a scalable deep learning framework for parametrized sequential decision-making (ParaSDM)<n>A key subclass of this setting is Facility-Location and Pathity (FLPO), where multi-agent systems must simultaneously determine optimal routes and locations.<n>To address this, we integrate Maximum Entropy Principle (MEP) with a neural policy model called the Shortest Path Network (SPN)
  arXiv  Detail & Related papers  (2025-07-30T02:46:45Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization.<n>We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution.<n>Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Efficient Distributed Optimization under Heavy-Tailed Noise [32.96984712007111]
  TailOPT is designed to address heavy-tailed noise with potentially gradient variance and local updates.<n>$Bi2Clip$ performs coordinate-wise clipping at both the inner and outers, achieving adaptive-like performance.<n>$Bi2Clip$ demonstrates superior performance on several language tasks and models, outperforming state-of-the-art methods.
  arXiv  Detail & Related papers  (2025-02-06T15:47:18Z)
• FRUGAL: Memory-Efficient Optimization by Reducing State Overhead for Scalable Training [51.39495282347475]
  We introduce $textttFRUGAL$ ($textbfF$ull-$textbfR$ank $textbfU$pdates with $textbfG$r$textbfA$dient sp$textbfL$itting, a new memory-efficient optimization framework.<n>Our framework can be integrated with various low-rank update selection techniques, including GaLore and BAdam.
  arXiv  Detail & Related papers  (2024-11-12T14:41:07Z)
• Biased Pareto Optimization for Subset Selection with Dynamic Cost Constraints [23.67466377818849]
  Subset selection with cost constraints aims to select a subset from a ground set to maximize a monotone objective function without exceeding a given budget. We propose BPODC, enhancing POMC with biased selection and warm-up strategies tailored for dynamic environments.
  arXiv  Detail & Related papers  (2024-06-18T08:14:51Z)
• Fine-Tuning Adaptive Stochastic Optimizers: Determining the Optimal Hyperparameter $ε$ via Gradient Magnitude Histogram Analysis [0.7366405857677226]
  We introduce a new framework based on the empirical probability density function of the loss's magnitude, termed the "gradient magnitude histogram" We propose a novel algorithm using gradient magnitude histograms to automatically estimate a refined and accurate search space for the optimal safeguard.
  arXiv  Detail & Related papers  (2023-11-20T04:34:19Z)
• Neural Quantile Optimization for Edge-Cloud Networking [13.509945075582447]
  We seek the best traffic allocation scheme for the edge-cloud computing network that satisfies constraints and minimizes the cost based on burstable billing. We introduce the Gumbel-softmax sampling network to solve the optimization problems via unsupervised learning. The trained network works as an efficient traffic allocation scheme sampler, remarkably outperforming the random strategy in feasibility and cost function value.
  arXiv  Detail & Related papers  (2023-07-11T11:05:10Z)
• Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
  This paper investigates the delayed online convex optimization (OCO) in non-stationary environments. We first propose a simple algorithm, namely DOGD, which performs a gradient descent step for each delayed gradient according to their arrival order. We develop an improved algorithm, which reduces those dynamic regret bounds achieved by DOGD to $O(sqrtbardT(P_T+1))$.
  arXiv  Detail & Related papers  (2023-05-20T07:54:07Z)
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs [113.8752163061151]
  We study episodic reinforcement learning (RL) in non-stationary linear kernel Markov decision processes (MDPs)<n>We propose the underlineperiodically underlinerestarted underlineoptimistic underlinepolicy underlineoptimization algorithm (PROPO)<n>PROPO features two mechanisms: sliding-window-based policy evaluation and periodic-restart-based policy improvement.
  arXiv  Detail & Related papers  (2021-10-18T02:33:20Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Robust Value Iteration for Continuous Control Tasks [99.00362538261972]
  When transferring a control policy from simulation to a physical system, the policy needs to be robust to variations in the dynamics to perform well. We present Robust Fitted Value Iteration, which uses dynamic programming to compute the optimal value function on the compact state domain. We show that robust value is more robust compared to deep reinforcement learning algorithm and the non-robust version of the algorithm.
  arXiv  Detail & Related papers  (2021-05-25T19:48:35Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  We present techniques that produce optimal decision trees over a variety of objectives. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables.
  arXiv  Detail & Related papers  (2020-06-15T19:00:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.