Estimating Reachable Sets with Scenario Optimization

Alex Devonport, Murat Arcak
Proceedings of the 2nd Conference on Learning for Dynamics and Control, PMLR 120:75-84, 2020.

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 this Paper

BibTeX
@InProceedings{pmlr-v120-devonport20a, 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}, pages = {75--84}, year = {2020}, editor = {Bayen, Alexandre M. and Jadbabaie, Ali and Pappas, George and Parrilo, Pablo A. and Recht, Benjamin and Tomlin, Claire and Zeilinger, Melanie}, volume = {120}, series = {Proceedings of Machine Learning Research}, month = {10--11 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v120/devonport20a/devonport20a.pdf}, url = {https://proceedings.mlr.press/v120/devonport20a.html}, 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.} }
Endnote
%0 Conference Paper %T Estimating Reachable Sets with Scenario Optimization %A Alex Devonport %A Murat Arcak %B Proceedings of the 2nd Conference on Learning for Dynamics and Control %C Proceedings of Machine Learning Research %D 2020 %E Alexandre M. Bayen %E Ali Jadbabaie %E George Pappas %E Pablo A. Parrilo %E Benjamin Recht %E Claire Tomlin %E Melanie Zeilinger %F pmlr-v120-devonport20a %I PMLR %P 75--84 %U https://proceedings.mlr.press/v120/devonport20a.html %V 120 %X 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.
APA
Devonport, A. & Arcak, M.. (2020). Estimating Reachable Sets with Scenario Optimization. Proceedings of the 2nd Conference on Learning for Dynamics and Control, in Proceedings of Machine Learning Research 120:75-84 Available from https://proceedings.mlr.press/v120/devonport20a.html.

Related Material