SDP Synthesis of Distributionally Robust Backward Reachable Trees for Probabilistic Planning

• 成果类型: Article
• 署名作者: Aggarwal, Naman; How, Jonathan P.
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2025.3578298
• 发表日期: 2025
• 关键词: uncertainty; optimization

摘要

In this article, we present Maximal Ellipsoid Backward Reachable Trees MAXELLIPSOID BRT, which is a multiquery 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 multiquery 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 backward 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 on probabilistic planning (Aggarwal et al., 2024).