# Robust Stochastic Shortest-Path Planning via Risk-Sensitive Incremental Sampling

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 27 references that are in the map.
- First posted on arXiv 16 Aug 2024.

## Builds on (most cited first, 9 of 9)

- [Information Theoretic Model Predictive Control: Theory and Applications to Autonomous Driving](https://mlsanity.com/paper/1707.02342/) (2017)
- [Shortest Paths in Graphs of Convex Sets](https://mlsanity.com/paper/2101.11565/) (2021)
- [Risk-Sensitive Reinforcement Learning with Exponential Criteria](https://mlsanity.com/paper/2212.09010/) (2022)
- [RAP: Risk-Aware Prediction for Robust Planning](https://mlsanity.com/paper/2210.01368/) (2022)
- [On the Dual Representation of Coherent Risk Measures](https://mlsanity.com/paper/1502.06155/) (2015)
- [Risk-Averse Stochastic Shortest Path Planning](https://mlsanity.com/paper/2103.14727/) (2021)
- [Distributionally robust risk map for learning-based motion planning and control: A semidefinite programming approach](https://mlsanity.com/paper/2105.00657/) (2021)
- [Path Integral Methods with Stochastic Control Barrier Functions](https://mlsanity.com/paper/2206.11985/) (2022)
- [On the multi-stage shortest path problem under distributional uncertainty](https://mlsanity.com/paper/2205.09200/) (2022)

## Abstract (arXiv)

With the pervasiveness of Stochastic Shortest-Path (SSP) problems in high-risk industries, such as last-mile autonomous delivery and supply chain management, robust planning algorithms are crucial for ensuring successful task completion while mitigating hazardous outcomes. Mainstream chance-constrained incremental sampling techniques for solving SSP problems tend to be overly conservative and typically do not consider the likelihood of undesirable tail events. We propose an alternative risk-aware approach inspired by the asymptotically-optimal Rapidly-Exploring Random Trees (RRT*) planning algorithm, which selects nodes along path segments with minimal Conditional Value-at-Risk (CVaR). Our motivation rests on the step-wise coherence of the CVaR risk measure and the optimal substructure of the SSP problem. Thus, optimizing with respect to the CVaR at each sampling iteration necessarily leads to an optimal path in the limit of the sample size. We validate our approach via numerical path planning experiments in a two-dimensional grid world with obstacles and stochastic path-segment lengths. Our simulation results show that incorporating risk into the tree growth process yields paths with lengths that are significantly less sensitive to variations in the noise parameter, or equivalently, paths that are more robust to environmental uncertainty. Algorithmic analyses reveal similar query time and memory space complexity to the baseline RRT* procedure, with only a marginal increase in processing time. This increase is offset by significantly lower noise sensitivity and reduced planner failure rates.