# STEP: Stochastic Traversability Evaluation and Planning for Risk-Aware Off-road Navigation

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 46 references that are in the map.
- First posted on arXiv 4 Mar 2021.

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

- [Distributional Reinforcement Learning with Quantile Regression](https://mlsanity.com/paper/1710.10044/) (2017)
- [Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach](https://mlsanity.com/paper/1506.02188/) (2015)
- [OSQP: An Operator Splitting Solver for Quadratic Programs](https://mlsanity.com/paper/1711.08013/) (2017)
- [How Should a Robot Assess Risk? Towards an Axiomatic Theory of Risk in Robotics](https://mlsanity.com/paper/1710.11040/) (2017)
- [Autonomous Spot: Long-Range Autonomous Exploration of Extreme Environments with Legged Locomotion](https://mlsanity.com/paper/2010.09259/) (2020)
- [LAMP: Large-Scale Autonomous Mapping and Positioning for Exploration of Perceptually-Degraded Subterranean Environments](https://mlsanity.com/paper/2003.01744/) (2020)
- [LOCUS: A Multi-Sensor Lidar-Centric Solution for High-Precision Odometry and 3D Mapping in Real-Time](https://mlsanity.com/paper/2012.14447/) (2020)
- [Constrained Risk-Averse Markov Decision Processes](https://mlsanity.com/paper/2012.02423/) (2020)
- [Deep Learning Tubes for Tube MPC](https://mlsanity.com/paper/2002.01587/) (2020)
- [PLGRIM: Hierarchical Value Learning for Large-scale Exploration in Unknown Environments](https://mlsanity.com/paper/2102.05633/) (2021)
- [Risk-Averse Planning Under Uncertainty](https://mlsanity.com/paper/1909.12499/) (2019)
- [Confidence-rich grid mapping](https://mlsanity.com/paper/2006.15754/) (2020)
- [Risk-Sensitive Motion Planning using Entropic Value-at-Risk](https://mlsanity.com/paper/2011.11211/) (2020)
- [A Framework for Time-Consistent, Risk-Sensitive Model Predictive Control: Theory and Algorithms](https://mlsanity.com/paper/1703.01029/) (2017)
- [Fast Approximate Clearance Evaluation for Rovers with Articulated Suspension Systems](https://mlsanity.com/paper/1808.00031/) (2018)
- [Path Planning and Navigation Inside Off-World Lava Tubes and Caves](https://mlsanity.com/paper/1803.02818/) (2018)
- [Autonomous Off-road Navigation over Extreme Terrains with Perceptually-challenging Conditions](https://mlsanity.com/paper/2101.11110/) (2021)

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

- [Fast Traversability Estimation for Wild Visual Navigation](https://mlsanity.com/paper/2305.08510/) (2023)
- [NeBula: Quest for Robotic Autonomy in Challenging Environments; TEAM CoSTAR at the DARPA Subterranean Challenge](https://mlsanity.com/paper/2103.11470/) (2021)
- [RoadRunner -- Learning Traversability Estimation for Autonomous Off-road Driving](https://mlsanity.com/paper/2402.19341/) (2024)
- [Self-Supervised Traversability Prediction by Learning to Reconstruct Safe Terrain](https://mlsanity.com/paper/2208.01329/) (2022)
- [ScaTE: A Scalable Framework for Self-Supervised Traversability Estimation in Unstructured Environments](https://mlsanity.com/paper/2209.06522/) (2022)
- [EVORA: Deep Evidential Traversability Learning for Risk-Aware Off-Road Autonomy](https://mlsanity.com/paper/2311.06234/) (2023)
- [Risk-Aware Off-Road Navigation via a Learned Speed Distribution Map](https://mlsanity.com/paper/2203.13429/) (2022)
- [Wild Visual Navigation: Fast Traversability Learning via Pre-Trained Models and Online Self-Supervision](https://mlsanity.com/paper/2404.07110/) (2024)
- [Learning Risk-Aware Costmaps via Inverse Reinforcement Learning for Off-Road Navigation](https://mlsanity.com/paper/2302.00134/) (2023)
- [Learning Risk-aware Costmaps for Traversability in Challenging Environments](https://mlsanity.com/paper/2107.11722/) (2021)
- [Sim-to-Real via Sim-to-Seg: End-to-end Off-road Autonomous Driving Without Real Data](https://mlsanity.com/paper/2210.14721/) (2022)
- [Risk-Averse Stochastic Shortest Path Planning](https://mlsanity.com/paper/2103.14727/) (2021)
- [PIETRA: Physics-Informed Evidential Learning for Traversing Out-of-Distribution Terrain](https://mlsanity.com/paper/2409.03005/) (2024)
- [UAVs Beneath the Surface: Cooperative Autonomy for Subterranean Search and Rescue in DARPA SubT](https://mlsanity.com/paper/2206.08185/) (2022)
- [PhysGS: Bayesian-Inferred Gaussian Splatting for Physical Property Estimation](https://mlsanity.com/paper/2511.18570/) (2025)
- [LoGoPlanner: Localization Grounded Navigation Policy with Metric-aware Visual Geometry](https://mlsanity.com/paper/2512.19629/) (2025)
- [Learning Semantics-Aware Locomotion Skills from Human Demonstration](https://mlsanity.com/paper/2206.13631/) (2022)
- [Watch Your STEPP: Semantic Traversability Estimation using Pose Projected Features](https://mlsanity.com/paper/2501.17594/) (2025)
- [ZeST: A VLM-based Zero-Shot Traversability Navigation for Unknown Environments](https://mlsanity.com/paper/2508.19131/) (2025)
- [WildOS: Open-Vocabulary Object Search in the Wild](https://mlsanity.com/paper/2602.19308/) (2026)
- [Risk-Averse Decision Making Under Uncertainty](https://mlsanity.com/paper/2109.04082/) (2021)
- [Uncertainty-aware Semantic Mapping in Off-road Environments with Dempster-Shafer Theory of Evidence](https://mlsanity.com/paper/2405.06265/) (2024)
- [Fast nonlinear risk assessment for autonomous vehicles using learned conditional probabilistic models of agent futures](https://mlsanity.com/paper/2109.09975/) (2021)
- [Steering Generative Robot Policies with Lexicographic Preferences](https://mlsanity.com/paper/2609.15014/) (2026)
- [Learning Smooth State-Dependent Traversability from Dense Point Clouds](https://mlsanity.com/paper/2506.04362/) (2025)
- [ProTerrain: Probabilistic Physics-Informed Rough Terrain World Modeling](https://mlsanity.com/paper/2510.19364/) (2025)
- [CoCoNav: Conformal Control for Safe Robot Navigation in Crowds](https://mlsanity.com/paper/2608.07751/) (2026)

## Abstract (arXiv)

Although ground robotic autonomy has gained widespread usage in structured and controlled environments, autonomy in unknown and off-road terrain remains a difficult problem. Extreme, off-road, and unstructured environments such as undeveloped wilderness, caves, and rubble pose unique and challenging problems for autonomous navigation. To tackle these problems we propose an approach for assessing traversability and planning a safe, feasible, and fast trajectory in real-time. Our approach, which we name STEP (Stochastic Traversability Evaluation and Planning), relies on: 1) rapid uncertainty-aware mapping and traversability evaluation, 2) tail risk assessment using the Conditional Value-at-Risk (CVaR), and 3) efficient risk and constraint-aware kinodynamic motion planning using sequential quadratic programming-based (SQP) model predictive control (MPC). We analyze our method in simulation and validate its efficacy on wheeled and legged robotic platforms exploring extreme terrains including an abandoned subway and an underground lava tube.