Safety Verification of Uncertain Max-Plus-Linear Systems
Abstract
In this work, we discussed the verification of autonomous uncertain Max-Plus-Linear (uncertain MPL) systems with respect to safety property by using the reachability analysis approach. More precisely, given an uncertain MPL system, a nonempty set of initial conditions, a time horizon and an unsafe set, we want to determine whether the state can reach the unsafe set within the given time horizon. If the unsafe set is reachable, then the system is not safe. Otherwise, the system is safe. Our approach uses the piecewise affine representation of MPL systems to compute the reachable sets exactly.
References
F. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat, Synchronization and linearity: an algebra for discrete event systems. John Wiley & Sons Ltd, 1992.
B. Heidergott, G. J. Olsder, and J. Van der Woude, Max Plus at work: modeling and analysis of synchronized systems: a course on Max-Plus algebra and its applications. Princeton University Press, 2014.
D. Adzkiya, B. De Schutter, and A. Abate, “Finite abstractions of max-plus-linear systems.” IEEE Trans. Automat. Contr., vol. 58, no. 12, pp. 3039–3053, 2013.
D. Adzkiya, B. De Schutter, and A. Abate, “Computational techniques for reachability analysis of max-pluslinear systems,” Automatica, vol. 53, pp. 293–302, 2015.
R. M. F. Candido, L. Hardouin, M. Lhommeau, and R. S. Mendes, “Conditional reachability of uncertain max plus linear systems,” Automatica, vol. 94, pp. 426–435, 2018.
D. Adzkiya, Y. Zhang, and A. Abate, “Verisimpl 2: An open-source software for the verification of max-plus-linear systems,” Discrete Event Dynamic Systems, vol. 26, no. 1, pp. 109–145, 2016.
W. Heemels, B. De Schutter, and A. Bemporad, “Equivalence of hybrid dynamical models,” Automatica, vol. 37, no. 7, pp. 1085–1091, 2001.
