ナビゲーション2026/8/18arXiv:2608.17703v1

確率的保証付きオンライン確率的最短路ナビゲーションのためのオラクルとしてのダイクストラ法

Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guarantees

ダイクストラ法が確率的遷移下でも正確な計画エンジンとして機能する条件を示し、それを利用したオンライン学習アルゴリズムDORAを提案。動的障害物との接触確率を予算内に抑えつつ、計算量を大幅に削減する。

詳しい要約

1. どんなもの？

本研究は、移動ロボットのオンライン経路計画問題を扱う。地図の真の遷移コストが未知で、動作が確率的である環境下で、ロボットが低コストかつ安全に目的地へ到達することを目指す。提案手法DORA (Dijkstra Oracle Reduced-cost Algorithm)は、Dijkstraアルゴリズムをオラクルとして固定回数呼び出し、遷移カーネルを推定せずに学習を行う。

2. 先行研究と比べてどこがすごい？

従来、確率的な最短経路問題（Stochastic Shortest Path, SSP）を厳密に解くにはvalue iterationなどが必要で、計算量が地図の直径に依存する。一方、Dijkstraは高速だが確率的遷移には不正確とされてきた。本研究は、Dijkstraが厳密な計画エンジンとして機能するための条件を、文献でよく使われるcausality conditionよりも弱い条件（決定化マップ上のreduced costの非負性）で特徴づけた点が新しい。また、オンライン学習において遷移カーネルを推定せず、オラクル呼び出し回数を固定し、動的障害物との接触確率を予算内に抑えるための対数生存重みを導入した点も貢献である。

3. 技術・手法の肝は？

手法の核は、DijkstraアルゴリズムがSSPの厳密な解を与えるための条件を、決定化マップ上のreduced costの非負性として定式化したこと。この条件に基づき、DORAは各エピソードで最短経路オラクルを固定回数呼び出し、遷移カーネルを推定せずに学習する。さらに、動的障害物との接触確率を予算内に保つため、対数生存重みをコストに加える。

4. どうやって有効だと検証した？

数値実験では、グリッドワールドナビゲーション、方向性掘削、ドローン監視の3つのベンチマークを用いた。真の遷移カーネルを与えられた楽観的value iterationと比較し、計画計算量が4.5倍から19.3倍削減されることを示した。また、決定化して再計画する手法と比較して、学習中の接触回数を17分の1に削減し、接触率を2桁にわたる予算内に維持した。

5. 議論はある？

要旨からは、提案手法の理論的限界や、より複雑な環境での性能、実機での検証などについての議論は不明。また、reduced costの非負性条件が実際の環境でどの程度満たされるか、動的障害物のモデル化の仮定などについても要旨からは不明。

6. 次に読むべき論文は？

要旨で参照されている関連研究として、optimistic value iteration、determinize and replan、causality conditionに関する研究が挙げられる。具体的には、SSPを解くためのvalue iterationや、Dijkstraアルゴリズムの確率的設定への拡張に関する論文が次に読むべきであろう。

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Mansur M. Arief, Ali Akarma, Ahmad Alfan Alfian Irfan

分類: cs.RO, cs.AI, math.OC

原文アブストラクト

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.

arXivで原文を読む →arXiv概要ページ

← 論文一覧