Search papers, labs, and topics across Lattice.
This study reveals that Dijkstra's algorithm can be effectively utilized as an exact planning engine for online stochastic shortest path navigation by relaxing the traditional causality condition to merely require nonnegativity of a reduced cost on a determinized map. The proposed DORA (Dijkstra Oracle Reduced-cost Algorithm) leverages this insight, allowing mobile robots to navigate efficiently without estimating transition kernels, while maintaining safety constraints against dynamic obstacles. Experimental results demonstrate that DORA significantly reduces planner workload and contact rates compared to traditional methods, achieving performance on par with optimistic value iteration while requiring substantially less computational effort.
Dijkstra's algorithm can be transformed into a powerful exact planner for stochastic navigation, achieving efficiency gains of up to 19 times less computational work than traditional methods.
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.
