SDP Synthesis of Distributionally Robust Backward Reachable Trees for Probabilistic Planning
<|reference_start|>SDP Synthesis of Distributionally Robust Backward Reachable Trees for Probabilistic Planning: 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. The computation of these maximal ambiguity sets and edges is carried out via a convex semidefinite relaxation to a novel nonlinear program. We also formally prove a theorem on maximum coverage for a technique proposed in our prior work.<|reference_end|>
@article{aggarwal2024sdp,
    title={SDP Synthesis of Distributionally Robust Backward Reachable Trees for
  Probabilistic Planning},
    author={Naman Aggarwal and Jonathan P. How},
    journal={arXiv preprint arXiv:2409.09059},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.09059},
    primaryClass={eess.SY cs.RO cs.SY}
}