Algorithms for identifying flagged and guarded linear systems
(2024) 27th ACM International Conference on Hybrid Systems: Computation and Control — Location: Hong Kong, China (13.May.2024)
Files
36415133650140.pdf
Open Access - Adobe PDF
- 3.69 MB
Details
- Authors
- Abstract
- We present an approach for identifying two subclasses of piecewise affine (PWA) systems that we call flagged and guarded linear systems. Flagged linear system dynamics are given by a sum of k linear dynamical modes, each activated based on a latent binary variable, called a flag. Additionally, guarded linear systems define each flag as the sign of an affine ``guard'' function. We term the discovery of the latent flag values and the corresponding linear dynamics as the ``flagged regression'' and ``guarded regression'' problems, respectively. We show that the system identification problem is NP-hard even for these models, making the identification problem computationally challenging. For both problems, we provide approximation algorithms that identify a model whose error is within some user-defined constant away from the optimum. The time complexity of these algorithms is linear in the number of data points but exponential in the state-space dimension and the number of flags. The linear complexity in data size allows our approach to potentially scale to large data sets. We evaluate our algorithms on benchmark problems in order to learn models for mechanical systems with contact forces and a nonlinear robotic arm benchmark. Our approach compares favorably against neural network learning and the PARC algorithm for identifying PWA models proposed by Bemporad.
- Affiliations
Citations
Berger, G., Narasimhamurthy, M., & Sankaranarayanan, S. (2024). Algorithms for identifying flagged and guarded linear systems. Published. 27th ACM International Conference on Hybrid Systems: Computation and Control, Hong Kong, China. https://doi.org/10.1145/3641513.3650140