# Robust Shortest Path Planning and Semicontractive Dynamic Programming

arXiv: https://arxiv.org/abs/1608.01670 · HTML: https://mlsanity.com/paper/1608.01670/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Aug 2016.

## Built on by (most cited first, 1 of 1)

- [Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guarantees](https://mlsanity.com/paper/2608.17703/) (2026)

## Abstract (arXiv)

In this paper we consider shortest path problems in a directed graph where the transitions between nodes are subject to uncertainty. We use a minimax formulation, where the objective is to guarantee that a special destination state is reached with a minimum cost path under the worst possible instance of the uncertainty. Problems of this type arise, among others, in planning and pursuit-evasion contexts, and in model predictive control. Our analysis makes use of the recently developed theory of abstract semicontractive dynamic programming models. We investigate questions of existence and uniqueness of solution of the optimality equation, existence of optimal paths, and the validity of various algorithms patterned after the classical methods of value and policy iteration, as well as a Dijkstra-like algorithm for problems with nonnegative arc lengths.