Reference
D. Adzkiya, B. De Schutter, and A. Abate, "Computational techniques for
reachability analysis of max-plus-linear systems,"
Automatica, vol. 53, pp. 293-302, Mar. 2015.
Abstract
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.
Publisher page
Downloads
BibTeX
@article{AdzDeS:14-007,
author = {Adzkiya, Dieky and De Schutter, Bart and Abate, Alessandro},
title = {Computational Techniques for Reachability Analysis of
Max-Plus-Linear Systems},
journal = {Automatica},
volume = {53},
pages = {293--302},
month = mar,
year = {2015}
}