Estimating Reachable Sets with Scenario Optimization
Abstract
Many practical systems are not amenable to the reachability methods that give guarantees of correctness, since they have dynamics that are strongly nonlinear, uncertain, and possibly unknown. While reachable sets for these kinds of systems can still be estimated in a data-driven way, data-driven methods typically do not guarantee the validity of their results. However, certain data-driven approaches may be given a probabilistic guarantee of correctness, by reframing the problem as a chance-constrained optimization problem that is solved with scenario optimization. We apply this approach to the problem of approximating a reachable set by a norm ball from data. The method requires only O(n^2) sample trajectories and the solution of a convex problem. A variant of the method restricted to axis-aligned norm balls requires only O(n) samples.
Cite
Text
Devonport and Arcak. "Estimating Reachable Sets with Scenario Optimization." Proceedings of the 2nd Conference on Learning for Dynamics and Control, 2020.Markdown
[Devonport and Arcak. "Estimating Reachable Sets with Scenario Optimization." Proceedings of the 2nd Conference on Learning for Dynamics and Control, 2020.](https://mlanthology.org/l4dc/2020/devonport2020l4dc-estimating/)BibTeX
@inproceedings{devonport2020l4dc-estimating,
title = {{Estimating Reachable Sets with Scenario Optimization}},
author = {Devonport, Alex and Arcak, Murat},
booktitle = {Proceedings of the 2nd Conference on Learning for Dynamics and Control},
year = {2020},
pages = {75-84},
volume = {120},
url = {https://mlanthology.org/l4dc/2020/devonport2020l4dc-estimating/}
}