Mesh-Based Affine Abstraction of Nonlinear Systems with Tighter Bounds
Pages 3056 - 3061
Abstract
In this paper, we consider the problem of piecewise affine abstraction of nonlinear systems, i.e., the over-approximation of its nonlinear dynamics by a pair of piecewise affine functions that “includes” the dynamical characteristics of the original system. As such, guarantees for controllers or estimators based on the affine abstraction also apply to the original nonlinear system. Our approach consists of solving a linear programming (LP) problem that over-approximates the nonlinear function at only the grid points of a mesh with a given resolution and then accounting for the entire domain via an appropriate correction term. To achieve a desired approximation accuracy, we also iteratively subdivide the domain into subregions. Our method applies to nonlinear functions with different degrees of smoothness, including Lipschitz continuous functions, and improves on existing approaches by enabling the use of tighter bounds. Finally, we compare the effectiveness of our approach with existing optimization-based methods in simulation and illustrate its applicability for estimator design.
References
[1]
P. Tabuada, Verification and control of hybrid systems: a symbolic approach. Springer, 2009.
[2]
M. Althoff, O. Stursberg, and M. Buss, “Reachability analysis of nonlinear systems with uncertain parameters using conservative linearization,” in IEEE Conference on Decision and Control, 2008, pp. 4042–4048.
[3]
A. Girard and S. Martin, “Synthesis for constrained nonlinear systems using hybridization and robust controller on symplices,” IEEE Transactions on Automatic Control, vol. 57, no. 4, pp. 1046–6051, 2012.
[4]
V. Alimguzhin, F. Mari, I. Melatti, I. Salvo, and E. Tronci, “Linearizing discrete-time hybrid systems,” IEEE Transactions on Automatic Control, vol. 62, no. 10, pp. 5357–5364, 2017.
[5]
K. Singh, Y. Ding, N. Ozay, and S.Z. Yong, “Input design for nonlinear model discrimination via affine abstraction,” in IFAC Conference on Analysis and Design of Hybrid Systems, 2018, pp. 1–8, accepted.
[6]
E. Asarin, T. Dang, and A. Girard, “Hybridization methods for the analysis of nonlinear systems,” Acta Informatica, vol. 43, no. 7, pp. 451–476, 2007.
[7]
E. Asarin, “Reachability analysis of nonlinear systems using conservative approximatimn,” in Int. Workshop on Hybrid Systems: Computation and Control. Springer, 2003, pp. 20–35.
[8]
S.-I. Azuma, J.-I. Imura, and T. Sugie, “Lebesgue piecewise affine approximation of nonlinear systems,” Nonlinear Analysis: Hybrid Systems, vol. 4, no. 1, pp. 92–102, 2010.
[9]
Z. Han and B.H. Krogh, “Reachability analysis of nonlinear systems using trajectory piecewise linearized models,” in the American Control Conference, 2006, pp. 1505–1510.
[10]
S. Bak, S. Bogomolov, T.A. Henzinger, T.T. Johnson, and P. Pradyot, “Scalable static hybridization methods for analysis of nonlinear systems,” in the 19th International Conference on Hybrid Systems: Computation and Control. Springer, 2016, pp. 155–164.
[11]
N. Ramdani, N. Meslem, and Y. Candau, “A hybrid bounding method for computing an over-approximation for the reachable set of uncertain nonlinear systems,” IEEE Transactions on Automatic Control, vol. 54, no. 10, pp. 2352–52364, 2009.
[12]
M. Stämpfle, “Optimal estimates for the linear interpolation error for simplices,” Journal of Approximation Theory, vol. 103, pp. 78–90, 2000.
[13]
T. Dang, O. Maler, and R. Testylier, “Accurate hybridization of nonlinear systems,” in ACM International Conference on Hybrid Systems: Computation and Control, 2010, pp. 11–20.
[14]
H.W. Kuhn, “Some combinatorial lemmas on topology,” IBM Journal of Research and Development, vol. 4, no. 5, pp. 518–524, 1960.
[15]
R.H. Mladineo, “An algorithm for finding the global maximum of a multimodal, multivariate function,” Mathematical Programming, vol. 34, no. 2, pp. 188–200, 1986.
[16]
L.E. Dubins, “On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents,” American Journal of Mathematics, vol. 79, pp. 497–516, 1957.
Index Terms
- Mesh-Based Affine Abstraction of Nonlinear Systems with Tighter Bounds
Index terms have been assigned to the content through auto-classification.
Recommendations
Abstraction for model checking multi-agent systems
Model checking multi-agent systems (MAS) always suffers from the state explosion problem. In this paper we focus on an abstraction technique which is one of the major methods for overcoming this problem. For a multi-agent system, we present a novel ...
SAT-based Abstraction Refinement for Real-time Systems
In this paper, we present an abstraction refinement approach for model checking safety properties of real-time systems using SAT-solving. We present a faithful embedding of bounded model checking for systems of timed automata into propositional logic ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Dec 2018
6675 pages
Copyright © 2018.
Publisher
IEEE Press
Publication History
Published: 17 December 2018
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Dec 2024