DORASolvers.jl

DORA (Dijkstra Oracle Reduced-cost Algorithm) is an online solver for stochastic shortest path (SSP) problems specified using the POMDPs.jl interface.

The idea

A one-pass label-setting method such as Dijkstra is usually dismissed for stochastic shortest path problems because it is only exact when the value function decreases along every positive-probability transition. The condition that actually matters is weaker: if the reduced costs

\[w^*(s,a) = Q^*(s,a) - V^*(\sigma(s,a))\]

are nonnegative, where $\sigma(s,a)$ is the intended successor of action $a$ in state $s$, then Dijkstra run with them as edge weights returns exactly the optimal value function and exactly the optimal policy. DORA estimates these weights online, using one confidence bound per state-action pair and a fixed number of Dijkstra oracle calls per episode, and never estimates a transition kernel.

Like MCTS.jl, DORA follows the online-solver pattern of POMDPs.jl: solve converts the MDP into a tabular SSP and returns a planner; the Dijkstra oracle calls run lazily at decision time inside action.

Installation

DORASolvers is in the General registry:

import Pkg
Pkg.add("DORASolvers")

For the unreleased development version:

Pkg.add(url="https://github.com/ai-vnv/DORASolvers.jl")

Quick start

using POMDPs
using DORASolvers
using POMDPModels
using POMDPTools

rewards = Dict(GWPos(4, 3) => -10.0, GWPos(4, 6) => -10.0,
               GWPos(9, 3) => 10.0)
mdp = SimpleGridWorld(size=(10, 10), rewards=rewards, tprob=0.7)

planner = solve(DORASolver(start=GWPos(1, 1)), mdp)

a = action(planner, GWPos(1, 1))    # plans on first query
v = value(planner, GWPos(1, 1))     # negated learned cost-to-goal

r = simulate(RolloutSimulator(max_steps=100), mdp, planner)

Manual outline

• Solver Guide
• • How a model becomes an SSP
  • Three ways to use the planner
  • Solver options
  • Value convention
  • The episode-level API
  • Exact evaluation
• Examples
• • 1. Gridworld quickstart
  • 2. Online cost learning
  • 3. Warehouse navigation benchmark
  • 4. Custom MDP with explicit SSP structure
  • 5. Duckietown: an online SSP over a continuous driving MDP
• API Reference
• • Solver interface
  • Model conversion
  • Learners and the episode-level API
  • Warehouse benchmark domain
  • Dijkstra oracle
  • Reproducible RNG

Citation

If you use this package, please cite the paper it implements:

Mansur M. Arief, Ali Akarma, Ahmad Alfan Alfian Irfan. Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guarantees. arXiv:2608.17703, 2026. https://arxiv.org/abs/2608.17703

@misc{arief2026dijkstraoracleonlinestochastic,
      title={Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guarantees},
      author={Mansur M. Arief and Ali Akarma and Ahmad Alfan Alfian Irfan},
      year={2026},
      eprint={2608.17703},
      archivePrefix={arXiv},
      primaryClass={cs.RO},
      url={https://arxiv.org/abs/2608.17703},
}