(12a) Active Deep Learning for Scalable Approximation of Reachable and Invariant Sets for Mixed-Integer Nonlinear Systems

Set invariance theory is fundamental to the design and control of constrained systems [1]. Since system constraints can be satisfied at all times if and only if the initial state of a system lies inside an invariant set, set invariance is essential for ensuring safe evolution of a dynamical system under some admissible input. Recently, there has been renewed interest in the theory and application of set invariance in the areas of predictive control and learning-based control of uncertain systems to guarantee feasibility and constraint satisfaction and, thus, guarantee safe learning and control (see, e.g., [2,3]).

For linear time-invariant systems subject to linear inequality constraints, methods for constructing invariant sets based on set operations are well-established [4,5]. Algorithms have also been developed for constructing reachable sets and control invariant sets, which are generally harder to compute, for certain classes of nonlinear, such as piecewise affine and hybrid systems (e.g., [6-8]). Nonetheless, construction of these sets for general dynamical systems that exhibit complex forms of nonlinearities and/or a mixture of continuous and discrete behavior, as commonly observed in hybrid and switched systems, remains an open problem. Not only is the construction of robust and/or invariant sets using set-theoretic methods strongly dependent on the structure and accuracy of a system model, the scalability of these methods is also an important limitation since set-based operations can quickly become prohibitively expensive for high-dimensional state and input spaces. These challenges have motivated learning-based methods for data-driven approximation of reachable and invariant sets [9,10]. The fundamental idea in such methods is to generate admissible state and input trajectories (those that satisfy constraints) by solving an underlying optimization problem for a fixed initial state value. These samples can then be used to estimate reachable and/or invariant sets using the state-of-the-art machine learning approaches. A key advantage of learning-based methods for set construction is that they can even be applied when the underlying system dynamics are completely unknown; for example, when only a black-box or high-fidelity system model is available. However, their performance strongly depends on how efficiently one can sample the state space.

In this talk, we will present a sample-efficient, learning-based approach for estimating reachable/invariant sets for general constrained nonlinear systems with mixtures of discrete states, inputs, and/or operating modes. The proposed approach circumvents the need for making any assumptions about the structure or complexity of the system dynamics. It relies on the notion of learning the decision boundary of a feasibility oracle (that can be queried by solving the aforementioned optimization problem) for different initial state values. This allows us to effectively transform the set-based reachability problem into a binary classification problem that can tackled with deep learning methods. The use of deep learning is critical in this application since the reachable/invariant sets in the problems of interest can be arbitrarily complex, i.e., the set boundary can be highly non-convex and/or disjoint. To enhance the sample efficiency of deep learning-based oracle estimation, we present an active learning algorithm, based on information-theoretic criteria, to sequentially enrich training data in an efficient and information-optimal manner. Active learning allows us to drastically mitigate the computational cost of invoking the oracle repeatedly on randomly-selected initial state samples, which can be prohibitive when the feasibility test for control invariance involves solving mixed-integer nonlinear programs. Randomized verification methods [11] are used to provide a probabilistic guarantee on the likelihood that a state within a learned invariant set boundary is truly invariant. We will demonstrate the proposed approach on a benchmark two-tank system that exhibits switching behavior.

References

[1] F. Blanchini and S. Miani, Set-theoretic methods in control. Springer, Switzerland, 2008.

[2] K. P. Wabersich, L. Hewing, A. Carron, and M. N. Zeilinger,“Probabilistic model predictive safety certification for learning-based control,” IEEE Transactions on Automatic Control, vol. 67, no. 1, pp. 176–188, 2021.

[3] A. D. Bonzanini, J. A. Paulson, and A. Mesbah, “Safe learning-based model predictive control under state-and input-dependent uncertainty using scenario trees,” in Proceedings of the 59th IEEE Conference on Decision and Control, Jeju Island, Republic of Korea, 2020, pp. 2448–2454.

[4] F. Blanchini, “Set invariance in control,” Automatica, vol. 35, no. 11, pp. 1747–1767, 1999.

[5] E. C. Kerrigan, “Robust constraint satisfaction: Invariant sets and predictive control,” Ph.D. dissertation, University of Cambridge, 2001.

[6] S. Rakovic, P. Grieder, M. Kvasnica, D. Mayne, and M. Morari, “Computation of invariant sets for piecewise affine discrete time systems subject to bounded disturbances,” in Proceedings of the 43^rd IEEE Conference on Decision and Control, Atlantis, Bahamas, 2004, pp. 1418–1423.

[7] J. M. Bravo, D. Limon, T. Alamo, and E. F. Camacho, “On the computation of invariant sets for constrained nonlinear systems: An interval arithmetic approach,” Automatica, vol. 41, no. 9, pp. 1583–1589, 2005.

[8] W. Esterhuizen, T. Aschenbruck, and S. Streif, “On maximal robust positively invariant sets in constrained nonlinear systems,” Automatica, vol. 119, p. 109044, 2020.

[9] A. Chakrabarty, A. Raghunathan, S. Di Cairano, and C. Danielson, “Data-driven estimation of backward reachable and invariant sets for unmodeled systems via active learning,” in Proceedings of the IEEE Conference on Decision and Control, Miami, 2018, pp. 372–377.

[10] S. Bansal and C. J. Tomlin, “Deepreach: A deep learning approach to high-dimensional reachability,” in Proceedings of the IEEE International Conference on Robotics and Automation, Xi’an, China, 2021, pp. 1817–1824.

[11] R. Tempo, G. Calafiore, and F. Dabbene, Randomized algorithms for analysis and control of uncertain systems: with applications. London, UK: Springer Science & Business Media, 2012.