Robust-RRT: Probabilistically-Complete Motion Planning for Uncertain Nonlinear Systems

[Paper] [Code]

We present a sampling-based algorithm for computing motion plans that explicitly account for uncertainty: it returns robust motion plans that satisfy system dynamics, respect all constraints, avoid obstacles, and reach the goal for all possible uncertainty realizations belonging to a bounded set. Importantly, we prove the probabilistic completeness of the algorithm: it will eventually find a valid solution if there exists one.

Our method applies to a broad class of complex systems and works with black-box simulators.

It can handle both epistemic (such as uncertain model parameters) and aleatoric (such as external disturbances due to wind) sources of uncertainty.

Standard RRT consists of constructing a tree of states. In this work, we extend this concept by constructing a tree of reachable sets, where each set corresponds to all states that can be reached for all possible uncertain parameters and disturbances). Using a new sampling-based algorithm, these forward reachable sets can be efficiently computed for general classes of systems.

We also verify our method on a jumping robotic system with uncertain guard surfaces.

Bibtex

@inproceedings{WuLewEtAl2022,
	author = {Wu, A. and Lew, T. and Solovey, K. and Schmerling, E. and Pavone, M.},
	booktitle = {International Symposium on Robotics Research},
	title = {Robust-RRT: Probabilistically-Complete Motion Planning for Uncertain Nonlinear Systems},
	year = {2022},
}