Learn-To-Propagate: Distributionally Robust Motion Planning for Nonlinear Uncertain Systems
Organizations: Delft University of Technology Delft, Netherlands · ETH Zurich Zurich, Switzerland · Virginia Tech Virginia, USA · UCLouvain Louvain-la-Neuve, Belgium ·
Abstract
Motion planning for stochastic systems aims to find a sequence of control inputs that drives a system to a goal set while avoiding unsafe states with high probability. Existing approaches, however, are either restricted to linear dynamics with perfect knowledge of the underlying distributions or lack formal correctness guarantees. To address these limitations, we propose Learn-To-Propagate Distributionally-Robust Forest (L2P-DR-Forest), a distributionally-robust sampling-based planning algorithm for nonlinear stochastic systems with unknown initial state and process noise distributions. Our approach leverages recent advances in optimal transport to learn ambiguity sets that contain the true system distributions with high confidence. We develop an efficient method for propagating these sets through the system dynamics and for verifying their safety. We then integrate these techniques into a novel sampling-based planning algorithm to grow a forest of search trees in the system's state space while accounting for and mitigating the growth of ambiguity-sets radii. We prove that the algorithm is correct, i.e., every returned plan satisfies the specifications with the prescribed confidence, and, under some feasibility and distributional assumptions, is probabilistically complete. Evaluations on several robotic benchmarks demonstrate that our algorithm significantly outperforms existing methods while providing formal guarantees with high confidence.
Figures & tables
| Switched System | AV Maze | Unicycle Maze | Tractor Trailer | Double Integrator | ||
| Dimension | 2D | 3D | 3D | 4D | 6D | |
| L2P-DR-Forest (20 trials) | Max. number of it. per stage | |||||
| Max. number of stages | ||||||
| Succ. rate (%) | ||||||
| Total planning time ( ) | ||||||
| MILP time ( ) |
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
| Switched System | AV Maze | Unicycle Maze | Tractor Trailer | Double Integrator | |
|---|---|---|---|---|---|
| Pre-training samples | |||||
| Training samples | |||||
| Steering candidates | |||||
| Informed search iterations | |||||
| Unsafe-box inflation |
Motion Planning
Motion planning finds safe, feasible paths and trajectories for robots and vehicles amid geometric, dynamic, and task constraints.
See all 440 papers