Risk Density RRT$^*$: Planning in the Space of Probability

TL;DR RD-RRT* makes a closed-form approximation of collision probability with uncertain obstacles the cost that RRT* minimizes, rather than path length under a risk constraint. In the default 2D benchmark its paths have a Monte Carlo collision probability near 0.34, versus 0.63-0.65 for length-optimizing and chance-constrained baselines.
What they do
Most planners under uncertainty minimize path length subject to a chance constraint. RD-RRT* instead makes collision probability itself (or risk, probability times severity) the cost that RRT* minimizes, for a robot moving among known static obstacles and obstacles with Gaussian position uncertainty. It builds on the authors’ Risk Density functional, a first-order approximation of a whole path’s collision probability.
How it works
- Risk Density. A line integral of the obstacle position density along the path, times the combined robot-obstacle radius, approximates collision probability. To first order it is the same whether uncertainty is resolved once at the start or as the robot moves.
- Closed-form edge cost. For a straight edge the integral reduces to an error function, so edge costs are cheap and path costs add up along the tree.
- RRT* changes. Steering also caps each edge’s risk (solved with Halley’s method). Variants weight obstacles by severity or add a small path-length term, which keeps the tree exploring where risk is nearly zero and avoids “rewiring catastrophes”.
- Julia implementation, with 2D and 3D edge costs for Gaussian and Cauchy uncertainty.
Results
- Default scenario, 100 runs, each path checked with 10,000 Monte Carlo samples: collision probability near 0.34 versus 0.63-0.65 for length-optimizing RRT, BIT and AIT* and for CC-RRT. Median planning time is 0.113 s versus 0.071 s for RRT and 0.053 s for BIT*.
- Risk Trap scenario: about 7% collision probability (path length 23.7) versus about 15% for CC-RRT* (22.4) and 24% for inflated RRT* (13.2).
- The approximation tracks Monte Carlo probability linearly. In MuJoCo rollouts of a TidyBot mobile base among 15 static and 8 uncertain obstacles the fit is looser but in the same range.
- Planning time grows near-linearly with the number of uncertain obstacles, with 100% success.
Limitations
No asymptotic-optimality guarantee is established for the modified cost, steering and neighbor radius. Uncertainty is not propagated through robot dynamics, the planner only handles Euclidean spaces where task and configuration space coincide, and there are no physical-robot experiments.
Figures



Abstract
Planning under uncertainty is a fundamental problem in robotics. While much of the literature seeks minimum-cost paths subject to probabilistic constraints, this paper instead considers collision probability, or risk classically defined as probability times severity, directly as the planning objective. We propose Risk Density RRT$^*$ (RD-RRT$^*$), an extension of RRT$^*$ for high-level planning in environments with deterministic and uncertain obstacles. RD-RRT$^*$ builds on Risk Density, a functional that evaluates a continuous path as a whole and provides a tractable approximation of its collision probability. The framework also supports severity-weighted risk and a hybrid variant that adds a path-length penalty, balancing risk and geometric efficiency while regularizing exploration in low-density regions. We validate the method across a wide range of scenarios. The results show that RD-RRT$^*$ consistently finds paths with lower estimated collision probability by optimizing a global risk-based objective. We further demonstrate the fidelity of the underlying approximation through Monte Carlo simulations. Finally, we discuss how the topological structure induced by Risk Density may provide a useful representation of the environment and offer insights into risk-aware planning.
Summaries are written automatically from each paper's text. Figures and videos come from the paper and its project page; all credit goes to the authors.
