API Reference

DORASolver(; kwargs...)

POMDPs.jl solver for the Dijkstra Oracle Reduced-cost Algorithm. solve tabularizes a discrete MDP into a stochastic shortest path problem and returns a DORAPlanner that plans at decision time with a fixed number of reduced-cost Dijkstra calls, in the style of other online solvers such as MCTS.jl.

Learner hyperparameters (defaults are the paper values):

• iters = 3: Dijkstra oracle calls per (re)planning round
• alpha = 0.4: damping of the cost-to-goal update
• beta = 0.05: confidence radius scale for optimistic cost estimates
• optimistic = true, correct = true, explore_eps = 0.0: see DORALearner
• known_costs = true: seed the cost statistics from the model's expected step costs, so the first action call already yields the reduced-cost Dijkstra policy with no environment feedback. Set to false to learn the costs online through observe!.
• train_episodes = 0: number of self-simulated training episodes to run inside solve (the protocol of experiment 4 in the paper). The model's transition kernel is used as the generative simulator.
• episodes_budget = 500: the horizon K in the confidence radius schedule
• seed = 0: seed of the internal SplitMix64 stream

Tabularization controls (nothing means "derive a default from the MDP"):

• start: initial state; default samples initialstate(mdp)
• classify: function sp -> :goal | :crash | :normal. The default classifies a terminal state as :crash when its reward is negative and :goal otherwise, and a non-terminal state as :goal for positive reward, :crash for negative reward, and :normal for zero. The sign is taken from the largest expected immediate reward over actions.
• cost: function (s, a, sp) -> Float64; default max(c_min, step_cost - reward(mdp, s, a))
• key = identity: hashable identifier of a state (needed when the state type does not hash by value)
• step_cost = 1.0, c_min = 0.25, horizon = 200, cost_noise = 0.0
• c_to (default 2 * horizon * step_cost): timeout penalty
• c_crash (default horizon * step_cost): crash penalty
• name = "tabular": label stored on the resulting TabularSSP, used only to identify the model in reports and plots

DORA treats the model as an undiscounted stochastic shortest path problem; a warning is issued when discount(mdp) < 1.

DORAPlanner

Decision-time policy returned by solve(::DORASolver, ::MDP). Planning is lazy: the Dijkstra oracle calls run on the first action query and again whenever new cost observations arrive through observe!.

action(p, s) returns the planned action for s. States that were collapsed into the goal or crash sink during tabularization (absorbing reward cells) and states unreachable from the start fall back to the first action of the model, since no planning information exists for them.

value(p, s) returns the negated learned cost-to-goal, matching the POMDPs.jl convention that values are maximized. States outside the tabularization return 0.0.

replan!(p::DORAPlanner)

Run the learner's Dijkstra oracle calls and refresh the cached policy. Called automatically by action when observations have arrived since the last plan.

train!(p::DORAPlanner, episodes::Int)

Continue learning by running episodes self-simulated episodes on the tabularized model (the protocol of experiment 4). Uses the planner's internal SplitMix64 stream.

observe!(p::DORAPlanner, s, a, cost)

Report the observed traversal cost of taking action a in state s. Updates the learner's cost statistics and marks the planner for lazy replanning, so the Dijkstra oracle runs again on the next action query. This is the online interface for deployment-time cost learning (known_costs = false).

Generic tabular stochastic shortest path models built from POMDPs.jl problems.

tabularize enumerates the states of a discrete POMDPs.jl model that are reachable from a designated start state, converts the reward structure into positive traversal costs, and collapses every terminal state into a single goal index and a single crash index. The result exposes the same arrays as the warehouse model in NavSSP.jl, so the learners in Learners.jl run on it without modification.

The determinized graph is obtained by mapping each state action pair to its most likely successor. The self outcome and the crash outcome never define an edge, which matches the convention used for the warehouse map, where a blocked move has no determinized edge.

TabularSSP

Array based stochastic shortest path problem distilled from a POMDPs.jl model by tabularize. It is the representation the Dijkstra oracle and every learner in the package actually operate on, and it is what solve(::DORASolver, ::MDP) stores in planner.tab.

Relation to the original model. Ordinary states keep their identity and occupy indices 1:S, with states[i] giving the original model state of index i. Every state classified as a goal is collapsed into the single absorbing index goal = S + 1, and every state classified as a failure into crash = S + 2, so NS = S + 2. Rewards have already been converted into positive traversal costs, and the problem is undiscounted.

Fields that matter when reading or extending the code:

• succ[s, a]: the determinized successor, that is the most likely outcome that is neither a self loop nor the crash sink, or 0 when there is none. These edges are the graph the Dijkstra oracle searches.
• avail[s, a]: whether (s, a) has a determinized successor at all.
• out_s[s, a, k], out_p[s, a, k]: the k-th stochastic outcome and its probability; k runs to MAXOUT and unused slots hold probability zero.
• cout[s, a, k]: traversal cost of that outcome; cbar[s, a] is its expectation over k.
• c_min, c_to, c_crash: cost floor, timeout penalty and crash penalty.
• c_bump, out_bump: held at zero; present so that a TabularSSP and a NavSSP expose the same fields to the learners.

The exported evaluation helpers optimal_value, eval_policy, outcome_rates, causality_margin and reduced_costs accept a TabularSSP directly, and are the intended way to analyse a tabularized model exactly:

tab = planner.tab
V, pistar = optimal_value(tab)
gap = (eval_policy(tab, planner.pi)[tab.start] - V[tab.start]) / V[tab.start]

causality_margin(m::TabularSSP, V, pi) -> (worst, fraction)

Smallest decrease of V along a positive probability transition of pi, and the fraction of ordinary states at which every such transition decreases V. A nonnegative margin is the classical condition under which one pass label setting is exact; DORA does not need it, which is the point of the reduced cost weights.

eval_policy(m::TabularSSP, pi::Vector{Int}) -> Vector{Float64}

Expected horizon truncated cost of the stationary policy pi from every state index. The crash sink carries m.c_crash and the goal sink carries zero.

optimal_value(m::TabularSSP) -> (V, pi)

Horizon truncated optimal cost-to-goal V and its greedy stationary policy pi, computed exactly by value iteration on the tabularized model. This is the reference a DORA policy is compared against.

outcome_rates(m::TabularSSP, pi::Vector{Int}) -> (success, crash, timeout)

Exact probabilities, from m.start, that pi reaches the goal sink, reaches the crash sink, or exhausts the horizon. The three values sum to one.

reduced_costs(m::TabularSSP, V) -> Matrix{Float64}

Reduced costs w(s, a) = Q(s, a) - V(sigma(s, a)) on the determinized graph, where sigma(s, a) = m.succ[s, a] is the intended successor. Entries without a determinized successor are Inf. Nonnegativity of these weights is the condition under which the Dijkstra oracle is exact.

tabularize(mdp; start, classify, cost, c_min, c_to, c_crash, horizon,
           cost_noise, key=identity, name="tabular")

Build a TabularSSP from a POMDPs.jl model with discrete states and actions.

start is the initial state of the model. classify(sp) returns :goal, :crash, or :normal for a successor state. cost(s, a, sp) returns the traversal cost of the outcome and must be at least c_min. key(s) maps a state to a hashable identifier and is needed when the state type does not hash by value.

Online learners for the navigation SSP.

DORA is the proposed method. It keeps optimistic estimates of the SA traversal costs and calls Dijkstra a fixed number of times per episode on the known determinized map. The weight handed to the oracle is a reduced cost: the learned step cost plus the expected change in cost-to-goal caused by actuation slip. At the fixed point the weight equals Q(s,a) - d(sigma(s,a)), so the shortest path tree reproduces the greedy policy of the stochastic model.

Dijkstra Oracle Reduced cost Algorithm.

iters is the number of oracle calls per episode and alpha the damping of the cost-to-goal update. Setting correct = false recovers plain determinize and replan.

UCT planner that is given the true generative model, including the expected step costs. Nothing is learned, so the extracted policy is stationary and the search runs once. The reported work is the total number of generative model steps divided by the number of episodes, which is the amortized cost of the search.

DORA with an explicit risk weight. The additive term -log(1 - phat) makes the weight of a route equal to the negative log probability of traversing it without contact, so a shortest path under the combined weight trades distance against survival. The multiplier is updated by projected dual ascent on the realized contact indicator, which needs no extra planning sweep.

Tabular expected SARSA with an epsilon greedy behavior policy. The method is model free. It never plans, so its work per episode is one temporal difference update per step plus one greedy sweep to extract the policy.

Extra expected cost of a step relative to arriving at the intended successor.

Uniform random rollout to the depth cap.

Sample one generative model step. Returns the successor and the step cost.

Number of actions and maximum number of outcomes of a model.

Shrinkage estimate of the contact probability. Unvisited pairs are pulled to zero so that cost optimism, not risk pessimism, drives exploration.

run_episode!(L, pi, rng)

Simulate one episode and feed the observations back to the learner. Returns (cost, success, collided, timeout).

Expected SARSA update under the epsilon greedy behavior policy.

Warehouse episode. The observed step cost is the terrain sample plus a bump.

Tabular episode. The observed step cost is the outcome cost plus noise.

Projected dual ascent driven by the realized contact indicator.

Warehouse navigation as a stochastic shortest path problem, exposed through the POMDPs.jl MDP interface.

The map geometry is known. Traversal costs and contact risk are unknown and must be learned online. A commanded move succeeds with probability 1 - eps and slips laterally otherwise. A slip into a shelf is a soft failure that stops the robot in place. Entering a cell occupied by a dynamic obstacle is a hard failure that ends the episode at the absorbing crash state.

States are indexed 1:NS where NS = S + 1 and index NS is the crash state. POMDPs.jl maximizes reward, so reward returns the negative of the cost.

MAXOUT

Number of stochastic outcome slots per state-action pair of the warehouse domain: intended move, two lateral slips, and the crash sink. Exported for the same reason as NACT; a TabularSSP carries its own MAXOUT field, whose value depends on the model being tabularized.

NACT

Number of actions of the warehouse domain: the four commanded moves N, E, S, W. Exported because the arrays of a NavSSP are indexed with it; it is a constant of this domain, not of the package (a TabularSSP carries its own NA field instead).

NavSSP

The warehouse navigation benchmark, exposed through the POMDPs.jl MDP interface and constructed with build. States are integer indices 1:NS where NS = S + 1, the ordinary cells are 1:S, and index NS is the absorbing crash state; cells[s] gives the zero-based (row, col) of cell s and sidx is the inverse map.

The map geometry (grid, succ, out_s, out_p) is known to the planner, while the traversal costs (terrain) and the contact risk (haz) are what a learner has to discover online. cbar[s, a] is the expected step cost and pcrash[s, a] the contact probability, both used only for exact evaluation.

The exported helpers optimal_value, eval_policy, outcome_rates, causality_margin and reduced_costs accept a NavSSP, exactly as they accept a TabularSSP.

build(; n=20, eps=0.10, c_bump=1.5, c_crash=80.0, c_to=60.0, horizon=150,
      c_min=0.25, p_haz=0.14, cost_noise=0.12, rough=0.0,
      terrain_rng=nothing) -> NavSSP

Construct the warehouse navigation SSP used as the paper's primary benchmark. The defaults are the paper values.

n is the side length of the square grid. The shelf layout is fixed, and it admits a start and a goal only for n >= 12 with n % 4 ∈ (0, 1) — for example 12, 13, 16, 17, 20, 21, 24. Any other size throws an ArgumentError.

rough adds a smoothed random field to the terrain costs. Generating it needs a stream, so passing rough > 0 without a terrain_rng throws an ArgumentError rather than silently producing flat terrain. terrain_rng should be a SplitMix64 so that the generated terrain matches the Python reference implementation bit for bit.

Smallest value decrease along a positive probability transition of pi, and the fraction of states at which every such transition decreases the value. A nonnegative margin means the policy is consistently improving, which is the condition under which one pass label setting is exact.

Expected horizon truncated cost of a stationary policy. The crash state carries the known dead end penalty c_crash and the goal carries zero.

Horizon truncated optimal value and its greedy stationary policy.

Exact success, collision and timeout probabilities from the start state.

Reduced costs w(s,a) = Q(s,a) - V(sigma(s,a)) on the determinized map. Entries with no determinized successor are Inf.

POMDPs.jl maximizes reward, so this returns the negative traversal cost.

Binary heap Dijkstra on the determinized navigation graph.

The search runs backward from the goal, so the label of a state is its cost-to-goal and the parent pointer is the greedy action. Ties are broken by the smaller action index, which makes the returned tree deterministic.

The counter OPS records edge scans. It is the implementation independent measure of planner work reported in the paper. It is a single process-global counter, read through edge_scans() and cleared with reset_ops!(), and the learners account for their own work by differencing it around a call. That makes it correct for the single threaded experiment protocol used here, but it is not thread safe: planning concurrently from several tasks would interleave the increments and mix up the per-learner totals. Deliberately left as is, so that the reported work counts stay comparable with the reference implementation and no synchronisation cost enters the search loop.

Reverse adjacency of the determinized map. The geometry is static, so this is built once and reused by every planning call.

dijkstra_policy(rev, w, goal, avail, ns, na)

Dijkstra derived policy. States with no finite route fall back to the lowest indexed available action so the policy is always well defined.

dijkstra_to_goal(rev, w, goal, ns, na)

Backward Dijkstra from goal under nonnegative weights w[s,a]. Returns the cost-to-goal vector d and the greedy action g[s] that attains it. States with no finite route keep d = Inf and g = 0.

SplitMix64. A small deterministic generator used so that the Julia results reproduce the Python reference implementation exactly. Every random draw in the experiments goes through this type, in a fixed order.

SplitMix64(seed::Integer)

Deterministic SplitMix64 stream, seeded by seed.

It deliberately does not subtype Random.AbstractRNG. Every draw in the experiments goes through rand01, randint, uniform and categorical in a fixed order, and each of those is defined here to match the Python reference implementation bit for bit. Subtyping AbstractRNG would make the generic Base/Random samplers applicable, and those consume a different number of bits per draw, which would silently break that correspondence. Use a MersenneTwister or Xoshiro wherever a standard Julia RNG is wanted.

Index in 1:length(p) sampled by scanning p in order.

Uniform in [0,1) from the top 53 bits.

Uniform integer in 0:n-1.