Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guarantees
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...
| Authors | Mansur M. Arief, Ali Akarma, Ahmad Alfan Alfian Irfan |
|---|---|
| Primary category | cs.RO |
| Published | 18 August 2026 |
| Last updated at source | 18 August 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.