論文の概要: FMT$^{x}$: An Efficient and Asymptotically Optimal Extension of the Fast Marching Tree for Dynamic Replanning
- arxiv url: http://arxiv.org/abs/2509.08521v1
- Date: Wed, 10 Sep 2025 11:57:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-11 15:16:52.413643
- Title: FMT$^{x}$: An Efficient and Asymptotically Optimal Extension of the Fast Marching Tree for Dynamic Replanning
- Title（参考訳）: FMT$^{x}$:動的計画のための高速マーキングツリーの効率的かつ漸近的拡張
- Authors: Soheil Espahbodini Nia,
- Abstract要約: 本稿では,動的環境における効率的な一貫した再計画を可能にするFMT$x$を提案する。
FMT$x$は、コスト順序の優先度待ち行列を維持し、選択的な更新条件を適用することにより、環境が進化するにつれて、最適なルートを効率よく修復することを保証する。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 動的環境における経路計画は、特に自律システムは倉庫や公道のような予測不可能な空間に展開されるため、ロボット工学における中核的な課題である。
Fast Marching Tree (FMT$^{*}$)のようなアルゴリズムは、静的設定において漸近的に最適なソリューションを提供するが、そのシングルパス設計は、リアルタイム適応に不可欠なパス修正を防ぐ。
一方、完全な再設計は計算コストが大きすぎる場合が多い。
本稿では,FMT$^{x}$について紹介する。FMT$^{x}$は動的環境における効率的な一貫した再計画を可能にするFast Marching Treeアルゴリズムの拡張である。
我々は、FMT$^{*}$の隣接選択規則を再検討し、最小限の変更がシングルパス制限を克服し、漸近的最適性や計算効率を犠牲にすることなく、より良い接続を発見する際にコスト・ツー・カム値の更新を可能にすることを実証する。
FMT$^{x}$は、コスト順序の優先度待ち行列を維持し、拡張隣人を使用して、潜在的に最適以下の経路を持つ任意のノードの再評価をトリガーする選択的な更新条件を適用することにより、環境が進化するにつれて、最適以下のルートを効率的に修復することを保証する。
このターゲット戦略は、FMT$^{*}$の固有の効率を維持しつつ、障害物構成の変化に対して堅牢な適応を可能にする。
FMT$^{x}$は、環境変化後に漸近的に最適な解を回復することが証明されている。
FMT$^{x}$は、計算オーバーヘッドの少ない動的事象に対してより迅速に反応し、予測不可能な世界におけるリアルタイムロボットナビゲーションのためのより効果的なソリューションを提供する。
関連論文リスト
- Parametrized Multi-Agent Routing via Deep Attention Models [1.0377683220196872]
パラメタライズドシーケンシャル意思決定のためのスケーラブルなディープラーニングフレームワーク(ParaSDM)を提案する。
この設定の重要なサブクラスは、複数のエージェントシステムが最適なルートと位置を同時に決定する必要がある施設と場所(FLPO)である。
これを解決するために、最大エントロピー原理(MEP)と、最短経路ネットワーク(SPN)と呼ばれるニューラルポリシーモデルを統合する。
論文 参考訳（メタデータ） (2025-07-30T02:46:45Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Efficient Distributed Optimization under Heavy-Tailed Noise [32.96984712007111]
TailOPTは、潜在的に勾配のばらつきと局所的な更新を伴うヘビーテールノイズに対処するように設計されている。
Bi2Clip$は、インナーとアウターの両方でコーディネートワイドクリッピングを行い、アダプティブライクなパフォーマンスを実現する。
この$Bi2Clip$は、いくつかの言語タスクやモデルにおいて優れたパフォーマンスを示し、最先端のメソッドよりも優れています。
論文 参考訳（メタデータ） (2025-02-06T15:47:18Z) - Biased Pareto Optimization for Subset Selection with Dynamic Cost Constraints [23.67466377818849]
コスト制約付きサブセット選択は、与えられた予算を超えることなく、単調な目的関数を最大化するための基底セットからサブセットを選択することを目的としている。
我々は、動的環境に適した偏り選択とウォームアップ戦略でPOMCを強化したBPODCを提案する。
論文 参考訳（メタデータ） (2024-06-18T08:14:51Z) - Fine-Tuning Adaptive Stochastic Optimizers: Determining the Optimal Hyperparameter $ε$ via Gradient Magnitude Histogram Analysis [0.7366405857677226]
我々は、損失の大きさの経験的確率密度関数に基づく新しい枠組みを導入し、これを「緩やかな等級ヒストグラム」と呼ぶ。
そこで本稿では, 最適安全のための精密かつ高精度な探索空間を自動推定するために, 勾配等級ヒストグラムを用いた新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-11-20T04:34:19Z) - Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。
まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。
DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs [113.8752163061151]
非定常線形カーネルマルコフ決定過程(MDP)におけるエピソード強化学習(RL)の研究
線形最適化アンダーライン最適化アルゴリズム(PROPO)を提案する。
PROPOはスライディングウィンドウベースのポリシー評価と周期的リスタートベースのポリシー改善の2つのメカニズムを特徴としている。
論文 参考訳（メタデータ） (2021-10-18T02:33:20Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Robust Value Iteration for Continuous Control Tasks [99.00362538261972]
シミュレーションから物理システムへ制御ポリシを転送する場合、そのポリシは、動作の変動に対して堅牢でなければならない。
本稿では、動的プログラミングを用いて、コンパクトな状態領域上での最適値関数を計算するRobust Fitted Value Iterationを提案する。
より深い強化学習アルゴリズムや非ロバストなアルゴリズムと比較して、ロバストな値の方が頑健であることを示す。
論文 参考訳（メタデータ） (2021-05-25T19:48:35Z) - Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
様々な目的に対して最適な決定木を生成する手法を提案する。
また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
論文 参考訳（メタデータ） (2020-06-15T19:00:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。