SDP Synthesis of Distributionally Robust Backward Reachable Trees for Probabilistic Planning

Abstract--The paper presents Maximal Ellipsoid Backward Reachable Trees MAXELLIPSOID BRT, which is a multi-query algorithm for planning of dynamic systems under stochastic motion uncertainty and constraints on the control input. In contrast to existing probabilistic planning methods that grow a roadmap of distributions, our proposed method introduces a framework to construct a roadmap of ambiguity sets of distributions such that each edge in our proposed roadmap provides a feasible control sequence for a family of distributions at once leading to efficient multi-query planning. Specifically, we construct a backward reachable tree of maximal size ambiguity sets and the corresponding distributionally robust edge controllers. Experiments show that the computation of these sets of distributions, in a backwards fashion from the goal, leads to efficient planning at a fraction of the size of the roadmap required for state-of-the-art methods. This is typically done via the offline construction of a roadmap of feasible trajectories in the state space, such that In this paper, we are concerned with multi-query planning in real-time, for a pair of initial and goal configurations of the for systems with stochastic dynamics via roadmap based system, planning proceeds by connecting the initial and goal methods under constraints on the control input.