論文の概要: Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guarantees
- arxiv url: http://arxiv.org/abs/2608.17703v1
- Date: Tue, 18 Aug 2026 12:26:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-19 21:40:53.332767
- Title: Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guarantees
- Title（参考訳）: 確率的最短経路ナビゲーションのためのOracleとしてのDijkstra
- Abstract要約: この研究は、ダイクストラのアルゴリズムが、文献でしばしば呼び出される因果性条件よりもはるかに弱い条件の下で、正確な計画エンジンを維持できることを示している。
この特徴に基づいて,ロボットナビゲーションにおいて,最短経路を1回に一定回数の時間で呼び出すオンライン学習者DORAを提案する。
- 参考スコア（独自算出の注目度）: 0.5735035463793009
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Mobile robots that operate in side by side with humans and critical facilities must reach their goals at low cost, despite often unknown true traversal costs of the map apriori and imperfect actuation. Planners that solve the underlying stochastic shortest path problem exactly, such as value iteration, require computation that grows with the diameter of the map, whereas Dijkstra's algorithm is fast but is usually considered inexact once transitions are stochastic. This study shows that Dijkstra's algorithm can remain an exact planning engine under a condition that is much weaker than the causality condition often invoked in the literature, namely nonnegativity of a reduced cost defined on the determinized map. Building on this characterization, an online learner DORA (Dijkstra Oracle Reduced-cost Algorithm) is proposed for robot navigation that calls a shortest path oracle a fixed number of times per episode, never estimates a transition kernel, and adds a logarithmic survival weight when the probability of contact with a dynamic obstacle must stay within a budget. In the numerical experiments involving three other benchmarks that cover grid world navigation, directional drilling, and drone surveillance, the learner matches optimistic value iteration that is given the true transition kernel while performing 4.5 to 19.3 times less planner work, reduces contacts during learning by a factor of seventeen relative to determinize and replan, and keeps the contact rate within budgets that span two orders of magnitude. These results indicate that shortest path search supports safe and efficient online navigation and path planning tasks.
- Abstract（参考訳）: 人間と並んで作業する移動ロボットは、地図アプリオリの真のトラバースコストや不完全な動きにもかかわらず、低コストで目標を達成する必要がある。
値反復のような基礎となる確率的最短経路問題を正確に解くプランナーは、写像の直径とともに成長する計算を必要とするが、ダイクストラのアルゴリズムは高速であるが、遷移が確率的であると通常不正確なと考えられる。
この研究は、ディクストラのアルゴリズムが、文献でしばしば呼び出される因果条件よりもはるかに弱い条件の下で正確な計画エンジンとして残ることを示し、すなわち、決定化された写像上で定義されたコスト削減の非負性である。
この特徴に基づいて、オンライン学習者DORA (Dijkstra Oracle Reduced-cost Algorithm) がロボットナビゲーションのために提案され、最短経路オークルを1回に一定回数呼び出し、遷移カーネルを見積もることなく、動的障害物に接触する確率が予算内に留まらなければならない場合に、対数生存重量を追加する。
グリッドワールドナビゲーション、指向性ドリル、ドローン監視をカバーする他の3つのベンチマークを含む数値実験では、学習者は真の遷移カーネルが与えられた楽観的な値反復と4.5から19.3倍のプランナー作業を実行し、学習中の接触を17の要因で減らし、決定および再計画し、接触率を2桁の予算内に保持する。
これらの結果は,最短経路探索が安全かつ効率的なオンラインナビゲーションと経路計画タスクをサポートすることを示している。
関連論文リスト
- Traffic-Aware Navigation in Road Networks [0.0]
本研究は,キングストンの道路網における交通認識ナビゲーションの課題に対する3つのグラフ探索手法を比較した。
Dijkstra と A* は、最小限の事前処理を必要とする最もトラフィック対応の最適ソリューションとなった。
フロイド=ワースホール=インガーマン(Floyd-Warshall-Ingerman)は、リアルタイムでは最速であったが、交通の注意を払わず、距離に基づく経路を提供した。
論文 参考訳（メタデータ） (2026-02-02T14:35:49Z) - Local Path Optimization in The Latent Space Using Learned Distance Gradient [14.220732305518583]
制約された運動計画は、ロボット操作において一般的な問題であるが難しい問題である。
本稿では,ロボットと障害物の最小距離を予測するためにニューラルネットワークを訓練する手法を提案する。
学習された距離勾配は、ロボットを障害物から遠ざけるために潜伏空間の移動方向を計算するために使用される。
論文 参考訳（メタデータ） (2025-12-30T14:56:09Z) - TransPath: Learning Heuristics For Grid-Based Pathfinding via
Transformers [64.88759709443819]
探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。
私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。
第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
論文 参考訳（メタデータ） (2022-12-22T14:26:11Z) - Learning Graph Search Heuristics [48.83557172525969]
本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。
我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。
実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
論文 参考訳（メタデータ） (2022-12-07T22:28:00Z) - Risk-Aware Off-Road Navigation via a Learned Speed Distribution Map [39.54575497596679]
本研究は,データから学習可能なロボットの速度のみに基づく,トラバーサビリティの新たな表現を提案する。
提案アルゴリズムは,ロボットが達成できる速度の分布を,環境セマンティクスと命令された速度に基づいて予測する。
数値シミュレーションにより,提案したリスク認識計画アルゴリズムが平均目標達成時間を短縮することを示した。
論文 参考訳（メタデータ） (2022-03-25T03:08:02Z) - Systematic Comparison of Path Planning Algorithms using PathBench [55.335463666037086]
パスプランニングはモバイルロボティクスの重要な構成要素である。
学習に基づく経路計画アルゴリズムの開発は、急速な成長を遂げている。
本稿では,パスプランニングアルゴリズムの開発,視覚化,トレーニング,テスト,ベンチマークを行うプラットフォームであるPathBenchについて述べる。
論文 参考訳（メタデータ） (2022-03-07T01:52:57Z) - Online estimation and control with optimal pathlength regret [52.28457815067461]
オンライン学習アルゴリズムを設計する際の自然なゴールは、入力シーケンスの時間的変動の観点から、アルゴリズムの後悔を束縛することである。
OCOや盗賊など、さまざまなオンライン学習問題に対して、データ依存の「病的」後悔境界が最近取得されている。
論文 参考訳（メタデータ） (2021-10-24T22:43:15Z) - PathBench: A Benchmarking Platform for Classical and Learned Path
Planning Algorithms [59.3879573040863]
パスプランニングは、モバイルロボティクスの重要なコンポーネントです。
アルゴリズムを全体的あるいは統一的にベンチマークする試みはほとんど行われていない。
本稿では,パスプランニングアルゴリズムの開発,視覚化,トレーニング,テスト,ベンチマークを行うプラットフォームであるPathBenchについて述べる。
論文 参考訳（メタデータ） (2021-05-04T21:48:18Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Performance Improvement of Path Planning algorithms with Deep Learning
Encoder Model [1.1995939891389429]
この状況を克服するために畳み込みニューラルネットワーク(CNN)が用いられた。
本稿では,このCNNモデルを用いて性能を詳細に解析し,無駄な経路を除去する。
論文 参考訳（メタデータ） (2020-08-05T17:34:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。