PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2608.17703v1cs.ROcs.AImath.OC

TL;DR

Online stochastic navigation needs low-cost planning despite unknown traversal costs and imperfect actuation, while exact value-iteration planning becomes expensive on large maps. The paper develops DORA, a reduced-cost Dijkstra learner, and finds that it matches optimistic value iteration with substantially less planner work while reducing contacts during learning.

  • Problem

    Exact stochastic shortest-path planning becomes computationally burdensome because value iteration requires sweeps that grow with graph diameter and replanning repeats this cost.

  • Method

    DORA iteratively forms learned reduced-cost weights, calls Dijkstra a fixed number of times per episode, avoids estimating a transition kernel, and supports risk budgets with logarithmic survival weights.

  • Results

    DORA matches optimistic value iteration given the true kernel while performing 10.9 times less planner work and reduces contacts during learning by a factor of seventeen relative to determinize and replan.

  • Takeaways & Limitations

    Shortest-path search can support exact, safe, and computationally efficient online stochastic navigation when reduced costs on the determinized map are nonnegative.

  • Takeaways & Limitations

    DORA requires a calibrated slip probability and map geometry, while its finite-iteration implementation lacks the proved regret guarantee and evaluation is limited to small grid-map benchmarks.

Abstract

from arXiv · show

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.

I. INTRODUCTION … B. Online Learning for Goal Oriented Problems

The paper studies online stochastic shortest-path navigation with unknown traversal costs and imperfect actuation, showing that Dijkstra can be exact under nonnegative reduced costs. It introduces DORA, which uses a fixed number of shortest-path oracle calls without estimating transitions, and positions this approach against existing deterministic and stochastic planning methods.

  • I. INTRODUCTION: Robots must learn traversal costs online while reaching goals cheaply and avoiding contacts with obstacles and people.Floor condition, local clutter, and foot traffic affect route costs and are learned through traversal.
  • I. INTRODUCTION: Value iteration solves stochastic shortest-path problems optimally, but its computation grows with graph diameter and repeated replanning repeats that cost.Value iteration propagates information one step per sweep, whereas Dijkstra propagates across the map in one pass with near-linear edge-time complexity.
  • I. INTRODUCTION: Nonnegative reduced costs are sufficient for Dijkstra to return the exact optimal value function and policy, weakening the usual consistently improving condition.The reduced cost is the stochastic state-action value minus the value of the state the action intended to reach.
  • I. INTRODUCTION: DORA iteratively forms reduced-cost weights from a current goal-cost estimate, calls Dijkstra, and updates the estimate using a small number of damped iterations.The learner uses a fixed number of shortest-path oracle calls per episode and does not estimate a transition model.
  • I. INTRODUCTION: DORA also supports chance constraints by enforcing a risk budget through an additive logarithmic survival weight.The contribution includes a chance-constrained variant for limiting contact risk.
  • A. Shortest Path Search for Robot Navigation: D* Lite, ARA*, and Anytime D* provide deterministic-transition planning with reuse or explicit suboptimality bounds, while LAO* extends planning to stochastic policies.In stochastic settings, the solution is a policy rather than a path.
  • A. Shortest Path Search for Robot Navigation: The paper situates its contribution among exact and approximate stochastic Dijkstra-like methods, including generalized Dijkstra solvers, bounded real-time dynamic programming, and topological value iteration.These approaches extend label-setting or Dijkstra sweeps to stochastic or structured problems.
  • B. Online Learning for Goal Oriented Problems: Prior stochastic shortest-path learning methods use value iteration or occupancy-measure optimization, while combinatorial oracle learners generally assume deterministic edges.The paper places a shortest-path oracle inside a learner for a stochastic shortest-path problem.

C. Determinization and the Price of Structure · D. Safe Navigation under Uncertainty · III. PROBLEM FORMULATION

The paper contrasts determinized replanning’s potentially poor guarantees with approaches that restore structure or enforce risk constraints, then formulates navigation as an online stochastic shortest path problem with unknown costs and imperfect actuation. It evaluates learners by performance and planner work, measured through implementation-independent elementary operations.

  • C. Determinization and the Price of Structure: Determinized replanning can be exponentially worse than optimal, and reduced-model analyses provide little general guarantee on replanner plan quality.This motivates examining when shortest-path structure remains reliable under stochastic transitions.
  • D. Safe Navigation under Uncertainty: Chance-constrained planning tightens deterministic problems, while RAO* searches belief states with admissible utility and execution-risk bounds.FIRM restores graph-search optimal substructure by making edge costs independent in belief space.
  • III. PROBLEM FORMULATION: Navigation is modeled as a stochastic shortest path problem over free-map cells plus an absorbing crash state, with four motion primitives and a goal-reaching objective.Imperfect actuation sends a commanded action to its intended successor with probability 1 − ε and to either lateral cell with probability ε/2.
  • III. PROBLEM FORMULATION: Traversal costs are unknown, observed through noisy samples, and bounded between cmin > 0 and cmax.The true mean cost is denoted by c̄(s, a).
  • III. PROBLEM FORMULATION: The value of a stationary policy is its expected pre-absorption cost, truncated at horizon H with a timeout penalty, and V⋆ denotes the optimal value.The supplied formulation also introduces c̄(s, a) for true mean costs.
  • III. PROBLEM FORMULATION: The map geometry induces a determinized graph whose edges pair states and actions with their intended destination cells.The paper assumes these graph edges can reach the goal from every state and that costs lie in [cmin, cmax] with cmin > 0.
  • III. PROBLEM FORMULATION: Across K episodes, the learner commits to a stationary policy, executes it until absorption or timeout, and updates its estimates.Performance is assessed using regret, success, contact, and timeout rates, together with planner work per episode.
  • III. PROBLEM FORMULATION: Planner work counts edge scans for shortest-path calls and successor evaluations for value-iteration sweeps rather than wall-clock time.This makes comparisons independent of planner implementation.

IV. METHOD · A. The Dijkstra Policy Class · B. Reduced Costs and Exactness

The method defines a finite Dijkstra-induced policy class on a determinized graph and shows that nonnegative reduced costs suffice for Dijkstra to recover an optimal stochastic policy exactly in one call. This condition is weaker than consistent improvement because it constrains only the determinized successor, not every possible slip outcome.

  • A. The Dijkstra Policy Class: Any nonnegative weight vector on the determinized graph induces a policy in the Dijkstra policy class.
  • A. The Dijkstra Policy Class: The class consists of policies π_w defined by shortest-path labels d_w solving the determinized fixed-point equations.
  • A. The Dijkstra Policy Class: Dijkstra computes the labels in O(|E|+|S| log |S|) time, and one backward call defines actions at every state despite slips.The policy can act greedily after displacement without replanning.
  • B. Reduced Costs and Exactness: The reduced cost, rather than the determinized cost used by determinize and replan, is the weight choice shown to be exact.
  • B. Reduced Costs and Exactness: Under Assumption 1, if every reduced cost w⋆(s, a) is nonnegative, then Dijkstra labels equal the optimal value function and π_w⋆ is optimal.Thus, the Dijkstra policy class contains an optimal policy, recovered in one oracle call.
  • B. Reduced Costs and Exactness: At the optimal action, reduced-cost nonnegativity equals causality restricted to the determinized edge and is implied by, but does not imply, consistent improvement.Consistent improvement additionally requires strict value decreases for all positive-probability successors.
  • B. Reduced Costs and Exactness: Slip can immediately violate causality through a lateral outcome while preserving reduced-cost nonnegativity when each determinized step costs at least c_min and progresses toward the goal.

C. The DORA Algorithm

DORA alternates between constructing optimistic, nonnegative edge weights and calling Dijkstra, while updating a damped cost-to-go estimate from observed episodes. With correct estimates and nonnegative reduced costs, its inner loop has the optimal value as a fixed point, and its regret and computation scale favorably.

  • Algorithm procedure: The drift term requires the calibrated actuation scalar ε, known map geometry, and the oracle’s estimated cost to goal.It represents the expected penalty for not landing where the action intended.
  • Algorithm procedure: DORA forms optimistic weights from empirical costs, confidence information, and a current label vector, then calls Dijkstra and applies a damped update with parameter α.The algorithm executes the resulting policy for one episode and updates empirical counts and costs from observed step costs.
  • Guarantees: When ˆc = ¯c, ˆP = P, b ≡0, and w⋆≥0 on E, d = V ⋆ is a fixed point and the returned policy is optimal.Under these conditions, the constructed weights equal w⋆, so Dijkstra returns V ⋆ and the damped update leaves d unchanged.
  • Guarantees: The regret is bounded by ˜O(cmaxτmax√|S||A|K) against the best member of Πσ and, under Proposition 1, against V ⋆.The bound follows from optimistic step costs and confidence radii along the visited trajectory; τmax bounds expected absorption time.
  • Computational cost: I oracle calls and I drift evaluations are required per episode, with I independent of map size because one Dijkstra pass propagates cost information across the graph.The iteration therefore only corrects for local slip, unlike value iteration, whose sweeps grow with graph diameter.

D. Chance-Constrained Navigation

DORA-S incorporates a contact-probability budget by adding a logarithmic survival penalty to oracle weights, causing shortest paths to trade distance against survival. A projected dual-ascent update adjusts the penalty without extra planning, meeting the constraint in time average rather than at every iterate.

  • Chance-Constrained Navigation: DORA-S enforces the safety requirement ρ(π) ≤ ∆ by augmenting each oracle weight with λ(−log(1 − p̂(s, a))).Here, p̂(s, a) is the empirical contact probability.
  • Chance-Constrained Navigation: The logarithmic survival term makes route cost equal to a distance–survival tradeoff, since it measures the negative log probability of traversing the route without contact.The same transformation also underlies counterexample generation in probabilistic verification.
  • Chance-Constrained Navigation: Projected dual ascent updates λ using the realized contact indicator from the executed episode, requiring no extra planning sweep.This update is applied after each episode.
  • Chance-Constrained Navigation: Because constrained Markov decision processes may require mixtures of deterministic policies, DORA-S satisfies the contact constraint in the time-averaged sense rather than at every iterate.The passage identifies this as a consequence of the structure of optimal constrained policies.

V. EXPERIMENTS … C. Losslessness of Dijkstra-class Algorithms

Experiments evaluate DORA and related planners on warehouse navigation and stochastic shortest-path instances, showing competitive regret, reduced planner work, improved safety, and exactness under the reduced-cost condition. The results also show that reduced-cost weighting remains optimal where classical causality largely fails.

  • A. Setup: The warehouse benchmark has 266 states, shelf blocks, cross aisles, and a picking zone that can be crossed or bypassed through perimeter aisles.Traversal costs combine shelf proximity with a smoothed random field, while contact in the picking zone ends the episode.
  • A. Setup: DORA uses three oracle iterations and reduced-cost correction, while comparisons include uncorrected determinize-and-replan, certainty-equivalent Dijkstra, ε-greedy exploration, and optimistic value iteration.OVI-U estimates the transition kernel, whereas OVI-K uses the true kernel.
  • B. Online Navigation: 203 regret matches OVI-K while using 10.9 times less planner work; DORA also improves over OVI-U by factors of 9.4 in regret and 13.0 in work.The main comparison covers K = 800 episodes.
  • B. Online Navigation: 12.7 expected contacts matches the true-dynamics agent, while uncorrected planners accumulate more than 218 contacts during training.The reduced-cost correction accounts for slips into the picking zone, which cause contact.
  • B. Online Navigation: As the map grows from 266 to 1202 states, the OVI-K-to-DORA planner-work ratio rises from 13.7 to 21.1.DORA makes a fixed number of oracle calls, while value iteration requires sweeps that grow with map diameter.
  • C. Losslessness of Dijkstra-class Algorithms: At slip probability 0.45, classical causality holds at only 47.3 percent of states, whereas the reduced-cost condition holds for 92.8 percent of state-action pairs.The reduced-cost condition holds everywhere up to slip 0.30.
  • C. Losslessness of Dijkstra-class Algorithms: The reduced-cost Dijkstra-class member is exactly optimal at every tested slip level, while expected-one-step-cost weighting loses up to 7.1 percent and has a ninetieth-percentile loss of 14.5 percent.The expected-one-step-cost member corresponds to determinize and replan.
  • C. Losslessness of Dijkstra-class Algorithms: The a posteriori residual bound exceeds the optimal value for slip above 0.15, contrasting a vacuous worst-case bound with an exact policy.Figure 3 reports the DORA fixed point within 0.011 percent of the optimum.

D. Chance Constrained Navigation · E. Benchmark Problems Across Navigation Tasks

DORA-S tracks stringent contact-probability budgets by increasing routing cost, while dual ascent mixes routes across episodes when deterministic policies cannot attain intermediate risks. Across three benchmark domains, DORA preserves exactness and achieves competitive regret with substantially less planner work than OVI-K.

  • D. Chance Constrained Navigation: DORA-S sweeps the contact-probability budget from 0.30 to 0.02 using a risk weight and dual update, compared with the best stationary policy on the true model.The experiment sets picking-zone contact probability to 0.16 and bisects a true-model Lagrange multiplier for reference.
  • D. Chance Constrained Navigation: 0.268 at budget 0.30 falls to 0.011 at budget 0.02, versus 0.307 unconstrained, while safety cost rises from 22.41 to 33.99.The added cost reflects routing around rather than through the picking zone.
  • D. Chance Constrained Navigation: Dual ascent mixes two routes across episodes, producing intermediate average contact rates when no deterministic route lies near the target risk.This mixture structure characterizes optimal policies of constrained Markov decision processes.
  • E. Benchmark Problems Across Navigation Tasks: The benchmark suite converts SimpleGridWorld, GeoSteeringMDP, and a drone-surveillance problem from JuliaPOMDP into stochastic shortest path form.SimpleGridWorld is a 10 × 10 slipped grid with one goal and two absorbing hazard cells.
  • E. Benchmark Problems Across Navigation Tasks: Causality ranges from 3.1 percent of states in the grid world to 94.1 percent in the drone problem, while reduced costs are nonnegative on at least 90 percent of state-action pairs.The reduced-cost class is exactly optimal in the grid world and geosteering problem.
  • E. Benchmark Problems Across Navigation Tasks: DORA matches OVI-K regret within one standard deviation on the grid and drone tasks and beats it in geosteering, while using 5.3, 19.3 and 4.5 times less planner work.The comparison runs K = 400 episodes over five seeds per domain with β = 0.05.

VI. DISCUSSION … VII. CONCLUSION

The discussion argues that nonnegative reduced cost, rather than causality, characterizes when Dijkstra’s policy class can represent an optimum, enabling predictable, safety-oriented online planning. The conclusion reiterates this condition, introduces DORA, and reports its validity and exactness on a warehouse benchmark.

  • A. Role of the Reduced Cost Views: Reduced-cost nonnegativity is weaker than causality because it requires value decrease only along the determinized edge after charging other-outcome drift to that edge.The paper argues that causality is the wrong condition for assessing whether Dijkstra’s derived policy class is expressive enough.
  • A. Role of the Reduced Cost Views: Determinize and replan can work well because its policy class may contain the optimum, while its lack of weighting leaves it without a useful guarantee.This interpretation addresses the gap between the method’s empirical success and its worst-case analysis.
  • B. Compute and Deployment: DORA makes a fixed number of oracle calls per episode independent of map size, enabling predictable planning time in real-time control loops.It uses the same shortest-path routine as existing navigation stacks and can be integrated by changing edge weights rather than replacing the planning layer.
  • C. Safety by Construction: The determinized graph has no edge into the crash state, so the oracle cannot plan a collision and risk enters only through edge weights.This construction provides a safety barrier at the planner-search level.
  • C. Safety by Construction: Constraining the planner’s search space is more robust than relying on value iteration to learn that failure is expensive.Value iteration previously sought the absorbing failure state because an unvisited action appeared cheap; the study removed this pathology with a known dead end penalty.
  • D. Limitations: DORA requires the actuation model’s scalar slip probability and map geometry, and the study omits an extension that estimates slip probability online.The scalar slip probability is less information than a transition kernel but remains a required calibrated input.
  • VII. CONCLUSION: Shortest path search contains an optimal policy whenever reduced cost on the determinized map is nonnegative, a condition much weaker than the causality condition used previously.The conclusion identifies this as the paper’s central result and basis for revisiting Dijkstra’s algorithm for SSP navigation.
  • VII. CONCLUSION: 0.30 slip probability is the warehouse benchmark threshold up to which the reduced-cost condition holds for every state-action pair, while the reduced-cost policy is exactly optimal at every tested slip level.The conclusion reports both the condition’s benchmark range and the observed exact optimality of the corresponding policy class.

APPENDIX A FORMAL STATEMENTS AND PROOFS

The appendix formalizes the exactness of Dijkstra under nonnegative reduced costs and introduces strict determinized progress as the additional condition supporting the proofs. It shows this condition is weaker than consistent improvement and establishes achievability of the optimal stochastic value along the optimal determinized path.

  • Assumptions: Assumption 2 requires the optimal value to strictly decrease along the determinized successor of the optimal action.This is the additional condition used beyond the main-text hypotheses.
  • Assumptions: Strict determinized progress is weaker than consistent improvement because it constrains only the determinized edge, not every stochastic outcome.It can fail only through an exact tie and holds with positive margin on every experimental instance.
  • Achievability: Under Assumption 2, following the optimal policy through the determinized graph reaches the goal without revisiting states, and its total weight equals V ⋆(s).Strict value decrease and finiteness force termination at the goal; the weight telescopes exactly to the optimal value.
  • Dijkstra exactness: When w⋆≥0 on E, Dijkstra computes Dw⋆=V ⋆, and the greedy shortest-path-tree policy is optimal.The result follows from the path lower bound and achievability lemmas.
  • Reduced-cost characterization: Consistent improvement implies nonnegative reduced cost on the optimal determinized edge, but lateral slips can violate consistent improvement while leaving that reduced cost unchanged.The appendix identifies this lateral-slip case as typical rather than exceptional and proceeds to prove Proposition 3 by substituting d = V ⋆ into (7).

A. Regret of the Idealized Variant

The idealized variant runs its inner iteration to a fixed point, executes an optimal policy of an optimistic model with the true kernel, and admits a high-probability regret guarantee under stated assumptions. The implemented algorithm differs through finite damped iterations and potentially active clipping, with formal closure left to future work.

  • Idealized variant: The idealized variant runs the inner iteration to its fixed point each episode, making the executed policy optimal for an optimistic model with the true kernel.The model uses step costs c_k(s, a) = max(c_min, ˆc_k(s, a) − b_k(s, a)), and episodes run to absorption.
  • Regret guarantee: Under Assumptions 1 to 3, Proposition 4 provides a regret guarantee with probability at least 1 −δ.The assumptions include bounded mean-zero cost noise, exactness conditions for every optimistic model, and proper executed policies with expected absorption time at most τ_max.
  • Implementation gap: The implemented algorithm uses I damped iterations instead of convergence and may activate clipping when optimistic reduced costs are negative.Section V reports that I = 3 damped iterations track idealized behavior, while formally closing the gap is left to future work.

APPENDIX B EXPERIMENTAL PARAMETERS

Appendix B points to Tables III and IV for the complete parameterization of all four experiments. It specifies the geosteering map generator settings and shared learner parameters.

  • Parameter overview: Tables III and IV list every parameter for the four experiments, while Sections III–V describe the warehouse model and learners and Section V-E describes benchmark conversions.This appendix consolidates experiment settings and directs readers to the paper sections covering model, learner, and benchmark details.
  • Geosteering and learner settings: The geosteering map uses the original package’s default generator with base amplitude 3.0, base frequency 1.0, amplitude variation 0.5, frequency variation 0.05, phase 0.3, vertical shift 7.0, and target thickness 5.0.All learners use radius scale β = 0.05 and confidence parameter δ = 0.1.

APPENDIX C POLICY ROLLOUTS

Figures 6–9 compare final DORA and OVI-K rollouts across four domains. The policies follow nearly identical routes, despite DORA using fixed shortest-path calls and OVI-K using value iteration with the true kernel.

  • Policy rollouts: In every domain, final DORA and OVI-K policies follow nearly the same route.DORA computes its policy with a fixed number of shortest path calls per episode, whereas OVI-K runs value iteration with the true kernel.
  • Warehouse: In the warehouse, both policies route above the picking zone, which is optimal at the penalized dead end.
  • Geosteering: In geosteering, both follow the sinusoidal target zone and absorb the same drift events.
  • Drone surveillance: In drone surveillance, both policies curve around the region occupied by the ground agent.
Loading 2608.17703v1…