TY - JOUR
T1 - Computational techniques for reachability analysis of Max-Plus-Linear systems
AU - Adzkiya, Dieky
AU - De Schutter, Bart
AU - Abate, Alessandro
N1 - Publisher Copyright:
© 2015 Elsevier Ltd. All rights reserved.
PY - 2015/3/1
Y1 - 2015/3/1
N2 - This work discusses a computational approach to reachability analysis of Max-Plus-Linear (MPL) systems, a class of discrete-event systems widely used in synchronization and scheduling applications. Given a set of initial states, we characterize and compute its "reach tube," namely the collection of set of reachable states (regarded step-wise as "reach sets"). By an alternative characterization of the MPL dynamics, we show that the exact computation of the reach sets can be performed quickly and compactly by manipulations of difference-bound matrices, and further derive worst-case bounds on the complexity of these operations. The approach is also extended to backward reachability analysis. The concepts and results are elucidated by a running example, and we further illustrate the performance of the approach by a numerical benchmark: the technique comfortably handles twenty-dimensional MPL systems (i.e. with twenty continuous state variables), and as such it outperforms the state-of-the-art alternative approaches in the literature.
AB - This work discusses a computational approach to reachability analysis of Max-Plus-Linear (MPL) systems, a class of discrete-event systems widely used in synchronization and scheduling applications. Given a set of initial states, we characterize and compute its "reach tube," namely the collection of set of reachable states (regarded step-wise as "reach sets"). By an alternative characterization of the MPL dynamics, we show that the exact computation of the reach sets can be performed quickly and compactly by manipulations of difference-bound matrices, and further derive worst-case bounds on the complexity of these operations. The approach is also extended to backward reachability analysis. The concepts and results are elucidated by a running example, and we further illustrate the performance of the approach by a numerical benchmark: the technique comfortably handles twenty-dimensional MPL systems (i.e. with twenty continuous state variables), and as such it outperforms the state-of-the-art alternative approaches in the literature.
KW - Difference-bound matrices
KW - Forward and backward reachability analysis
KW - Max-Plus-Linear systems
KW - Piecewise affine systems
KW - Reach tube and reach set
UR - http://www.scopus.com/inward/record.url?scp=84924183017&partnerID=8YFLogxK
U2 - 10.1016/j.automatica.2015.01.002
DO - 10.1016/j.automatica.2015.01.002
M3 - Article
AN - SCOPUS:84924183017
SN - 0005-1098
VL - 53
SP - 293
EP - 302
JO - Automatica
JF - Automatica
ER -