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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.
MethodRegret ↓\downarrowWork ↓\downarrowSR ↑\uparrowCR ↓\downarrowContacts ↓\downarrow
DORA203±74\mathbf{203\pm 74}15,08415{,}0840.984\mathbf{0.984}0.016\mathbf{0.016}12.7\mathbf{12.7}
DORA-04,806±8664{,}806\pm 866772\mathbf{772}0.7270.7270.2730.273219.4219.4
CED4,751±8414{,}751\pm 841772\mathbf{772}0.7270.7270.2730.273218.7218.7
EGD7,753±7407{,}753\pm 740772\mathbf{772}0.7090.7090.2910.291232.6232.6
OVI-U1,906±1,6661{,}906\pm 1{,}666196,094196{,}0940.9830.9830.0170.01720.520.5
OVI-K203±47203\pm 47164,801164{,}8010.984\mathbf{0.984}0.016\mathbf{0.016}12.7\mathbf{12.7}
TABLE I: Online navigation metric comparison over 800800 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.0110.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.
DomainMethodRegret ↓\downarrowWork ↓\downarrowSR ↑\uparrowCR ↓\downarrowContacts ↓\downarrow
GridDORA35±5\mathbf{35\pm 5}5,9165{,}9160.939\mathbf{0.939}0.061\mathbf{0.061}25.1\mathbf{25.1}
worldDORA-01,187±2221{,}187\pm 222388\mathbf{388}0.8740.8740.1260.12657.257.2
 CED891±388891\pm 388388\mathbf{388}0.8830.8830.1170.11743.243.2
 OVI-K31±631\pm 631,16631{,}1660.939\mathbf{0.939}0.061\mathbf{0.061}24.924.9
GeosteeringDORA5,625±1,318\mathbf{5{,}625\pm 1{,}318}5,6345{,}6341.000\mathbf{1.000}0.0000.0000.00.0
 DORA-07,095±2,3587{,}095\pm 2{,}358465\mathbf{465}1.000\mathbf{1.000}0.0000.0000.00.0
TABLE II: Online navigation metric comparison on the three navigation benchmarks tasks over 400400 episodes
Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

ParameterExp. 1Exp. 2Exp. 3
Map size20×2020\times 2020×2020\times 2020×2020\times 20
States ∣S∣|\mathcal{S}|266266266266266266
Slip probability ε\varepsilon0.100.1000 to 0.450.450.100.10
Picking zone contact prob.0.140.14000.160.16
Terrain roughness0.50.51.61.60.50.5
Cost bounds [cmin⁡,cmax⁡][c_{\min},c_{\max}][0.25, 2.2][0.25,\,2.2]
Appendix
TABLE III: Parameters of the warehouse experiments.
ParameterGrid worldGeosteeringDrone surv.
Grid size10×1010\times 1015×1515\times 157×77\times 7
States ∣S∣|\mathcal{S}|999915715722112211
Actions443355
Motion noiseslip 0.30.3drift 0.30.3agent walk
Start(1,1)(1,1)(1,10)(1,10)(1,1)(1,1) , agent (4,4)(4,4)
Goal(9,3)(9,3)right edge(7,7)(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.
More in this topic

Robot Navigation

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

See all 554 papers

Explore similar work

CardsList
Apr 2, 2026

Efficient Constraint Generation for Stochastic Shortest Path Problems

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.

Johannes Schmalz, Felipe Trevizan

Australian National University, Australia · Saarland University, Germany

Markov Decision Processes
AskPDF
Sep 17, 2026

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

With the widespread use of online navigation and ride-hailing services, achieving optimal route planning for diverse user preferences has recently attracted increasing attention. Classic graph algorithms for pathfinding use heuristic cost functions to define edge weight, thus providing no optimality guarantee of route quality. Prior data-driven approaches equating ground truth of the optimal route with user trajectory, which is however moderately influenced by the navigation service, suffers from the feedback loop problem. To address these issues, we propose a deep architecture that is able to jointly optimize cost functions and route-ranking model towards any route preference. First, we run a multi-objective Dijkstra algorithm offline to collect the set of Pareto optimal routes, deeming it as the complete candidate set. Exploiting the property of such a set, we design a neural network structure that emulates shortest-path search and route ranking in an end-to-end differentiable manner. Second, we define route preference as a task of constrained optimization of route attributes, and propose a novel loss function that optimizes a single-objective variable, with other variables strictly under constraints. We conduct extensive experiments on real-world datasets. The results show that our architecture significantly outperforms state-of-the-art methods in route quality and customizability.

Rui Zhao, Chao Chen, Longfei Xu +4

Alibaba Group Beijing, China · Alibaba Group Hangzhou, China

Graph-Based PlanningDifferentiable OptimizationMulti-Objective Optimization
AskPDF
Oct 8, 2026

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

We study real-time motion planning in dynamic hazard fields through a controlled comparison between classical planning and learning-based methods. Rather than introducing a new planner, we construct a unified benchmark in which representative classical and learning-based methods face the same environments, motion constraints, information assumptions, and evaluation metrics. The test environment consists of planar domains populated with rotating sprinkler-like hazards that generate time-varying forbidden regions via sweeping angular sectors. Our results show a clear regime shift. In deterministic environments, classical planners achieve near-perfect success and higher-quality paths, though sometimes at the cost of substantial planning or replanning time. Under stochastic obstacle dynamics, however, online search becomes strongly budget-sensitive: low budgets lead to frequent failure, while high budgets improve success at the cost of latency and longer trajectories. PPO-based policies, trained under the same scenario distribution, consistently outperform in latency, success rate, and path quality in these stochastic regimes. Overall, the results indicate that uncertainty in obstacle evolution, more than partial observability, is the dominant factor determining which planning paradigm is practically effective for the problem at hand.

Eran Iceland, Alexander Tuisov, Oren Gal +2

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

Motion PlanningDynamic Obstacle AvoidanceRobot Policy Learning
AskPDF