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

Mansur M. Arief; Ali Akarma; Ahmad Alfan Alfian Irfan

cs.ROAug 18, 2026

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

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

Organizations: Industrial and Systems Engineering Department, IRC Smart Mobility and Logistics, King Fahd University of Petroleum and Minerals (KFUPM), Saudi Arabia · Faculty of Computer and Information Systems, Islamic University of Madinah, Saudi Arabia · Information Technology, Universitas Muhammadiyah Yogyakarta, Indonesia

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.

Figures & tables

Fig. 1: The warehouse benchmark. Dark blocks are shelves, the shading of free cells is the unknown traversal cost, and the red band is a picking zone where contact ends the episode. (a) The risk neutral route drives through the picking zone. (b) With a risk budget the same oracle call returns a detour that almost eliminates contact.

Method	Regret $\downarrow$	Work $\downarrow$	SR $\uparrow$	CR $\downarrow$	Contacts $\downarrow$
DORA	$\mathbf{203\pm 74}$	$15{,}084$	$\mathbf{0.984}$	$\mathbf{0.016}$	$\mathbf{12.7}$
DORA-0	$4{,}806\pm 866$	$\mathbf{772}$	$0.727$	$0.273$	$219.4$
CED	$4{,}751\pm 841$	$\mathbf{772}$	$0.727$	$0.273$	$218.7$
EGD	$7{,}753\pm 740$	$\mathbf{772}$	$0.709$	$0.291$	$232.6$
OVI-U	$1{,}906\pm 1{,}666$	$196{,}094$	$0.983$	$0.017$	$20.5$
OVI-K	$203\pm 47$	$164{,}801$	$\mathbf{0.984}$	$\mathbf{0.016}$	$\mathbf{12.7}$

TABLE I: Online navigation metric comparison over

800

episodes

Fig. 2: Online warehouse navigation results. (a) Cumulative regret, shaded by one standard deviation over ten instances. (b) Expected contacts accumulated during learning. (c) Planner work per episode as the map grows.

Fig. 3: Exactness of the Dijkstra policy class. (a) Causality collapses as soon as slip is introduced, while the reduced costs stay nonnegative. (b) The reduced cost weights are exactly optimal at every slip level, and the DORA fixed point stays within

0.011

percent of the optimum.

Fig. 4: Chance constrained navigation. (a) The contact rate of DORA-S tracks the budget across two orders of magnitude. (b) The cost paid for that safety. At intermediate budgets DORA-S beats the best deterministic policy because dual ascent mixes routes across episodes.

Fig. 5: Benchmark problems on navigation tasks. The top row shows each problem and the optimal determinized route. Hazard cells and the ground agent are red. In the geosteering problem the target zone is white, the shale margin is gray, and the terminal zone is green. The bottom row shows cumulative regret, shaded by one standard deviation over five seeds.

Domain	Method	Regret $\downarrow$	Work $\downarrow$	SR $\uparrow$	CR $\downarrow$	Contacts $\downarrow$
Grid	DORA	$\mathbf{35\pm 5}$	$5{,}916$	$\mathbf{0.939}$	$\mathbf{0.061}$	$\mathbf{25.1}$
world	DORA-0	$1{,}187\pm 222$	$\mathbf{388}$	$0.874$	$0.126$	$57.2$
	CED	$891\pm 388$	$\mathbf{388}$	$0.883$	$0.117$	$43.2$
	OVI-K	$31\pm 6$	$31{,}166$	$\mathbf{0.939}$	$\mathbf{0.061}$	$24.9$
Geosteering	DORA	$\mathbf{5{,}625\pm 1{,}318}$	$5{,}634$	$\mathbf{1.000}$	$0.000$	$0.0$
	DORA-0	$7{,}095\pm 2{,}358$	$\mathbf{465}$	$\mathbf{1.000}$	$0.000$	$0.0$

TABLE II: Online navigation metric comparison on the three navigation benchmarks tasks over

400

episodes

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Parameter	Exp. 1	Exp. 2	Exp. 3
Map size	$20\times 20$	$20\times 20$	$20\times 20$
States $\|\mathcal{S}\|$	$266$	$266$	$266$
Slip probability $\varepsilon$	$0.10$	$0$ to $0.45$	$0.10$
Picking zone contact prob.	$0.14$	$0$	$0.16$
Terrain roughness	$0.5$	$1.6$	$0.5$
Cost bounds $[c_{\min},c_{\max}]$	$[0.25,\,2.2]$

Appendix

TABLE III: Parameters of the warehouse experiments.

Parameter	Grid world	Geosteering	Drone surv.
Grid size	$10\times 10$	$15\times 15$	$7\times 7$
States $\|\mathcal{S}\|$	$99$	$157$	$2211$
Actions	$4$	$3$	$5$
Motion noise	slip $0.3$	drift $0.3$	agent walk
Start	$(1,1)$	$(1,10)$	$(1,1)$ , agent $(4,4)$
Goal	$(9,3)$	right edge	$(7,7)$

Appendix

TABLE IV: Parameters of the benchmark domains of experiment 4.

Fig. 6: Rollout of the final DORA policy (top) and the final OVI-K policy (bottom) on the warehouse instance of experiment 1.

Fig. 7: Rollout of the final policies on the grid world benchmark. Red cells are the hazard cells.

Fig. 8: Rollout of the final policies on the geosteering benchmark. The target zone is white, the shale margin is gray, and the terminal zone is green.

Fig. 9: Rollout of the final policies on the drone surveillance benchmark. The dashed red line is the path of the ground agent.

Robot Navigation

Robot navigation studies how robots perceive, localize, plan, and move safely toward goals in static or changing environments.

See all 554 papers

Efficient Constraint Generation for Stochastic Shortest Path Problems
Apr 2, 2026Johannes Schmalz, Felipe TrevizanMarkov Decision Processes
Australian National University, Australia · Saarland University, Germany
Customizable and Jointly Optimized Route Planning: A Deep Architecture Enabling Differentiable Shortest-Path Search
Sep 17, 2026Rui Zhao, Chao Chen, Longfei Xu +4Graph-Based Planning Differentiable Optimization
Alibaba Group Beijing, China · Alibaba Group Hangzhou, China
Real-Time Motion Planning with Dynamic Hazards: Classical vs. Learning-Based Methods
Oct 8, 2026Eran Iceland, Alexander Tuisov, Oren Gal +2Motion Planning Dynamic Obstacle Avoidance
School of Engineering and Computer Science, The Hebrew University of Jerusalem, Jerusalem, Israel · Faculty of Data and Decision Science, Technion Israeli Institute of Technology, Haifa, Israel · Hatter Department of Marine Technologies, University of Haifa, Haifa, Israel +1

Apr 2, 2026J/K move · Enter open · S save

Efficient Constraint Generation for Stochastic Shortest Path Problems

Johannes Schmalz, Felipe Trevizan

Australian National University, Australia · Saarland University, Germany

Markov Decision Processes

Open paper AskPDF arXiv

Stochastic Shortest Path problems (SSPs) are traditionally solved by computing each state's cost-to-go by applying Bellman backups. A Bellman backup updates a state's cost-to-go by iterating through every applicable action, computing the cost-to-go after applying each one, and selecting a minimal action's cost-to-go. State-of-the-art algorithms use heuristic functions; these give an initial estimate of costs-to-go, and lets the algorithm apply Bellman backups only to promising states, determined by low estimated costs-to-go. However, each Bellman backup still considers all applicable actions, even if the heuristic tells us that some of these actions are too expensive, with the effect that such algorithms waste time on unhelpful actions. To address this gap we present a technique that uses the heuristic to avoid expensive actions, by reframing heuristic search in terms of linear programming and introducing an efficient implementation of constraint generation for SSPs. We present CG-iLAO*, a new algorithm that adapts iLAO* with our novel technique, and considers only 40% of iLAO*'s actions on many problems, and as few as 1% on some. Consequently, CG-iLAO* computes on average 3.5x fewer costs-to-go for actions than the state-of-the-art iLAO* and LRTDP, enabling it to solve problems faster an average of 2.8x and 3.7x faster, respectively.

Abstract

Robot Navigation

Explore similar work

Efficient Constraint Generation for Stochastic Shortest Path Problems

Customizable and Jointly Optimized Route Planning: A Deep Architecture Enabling Differentiable Shortest-Path Search

Real-Time Motion Planning with Dynamic Hazards: Classical vs. Learning-Based Methods