Backward reachability of autonomous max-plus-linear systems

Dieky Adzkiya; Bart De Schutter; Alessandro Abate

Backward reachability of autonomous max-plus-linear systems

Dieky Adzkiya, Bart De Schutter, Alessandro Abate

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

This work discusses the backward reachability of autonomous Max-Plus-Linear (MPL) systems, a class of continuous-space discrete-event models that are relevant for applications dealing with synchronization and scheduling. Given an MPL system and a continuous set of final states, we characterize and compute its "backward reach tube" and "backward reach sets," namely the set of states that can reach the final set within a given event interval or at a fixed event step, respectively. We show that, in both cases, the computation can be done exactly via manipulations of difference-bound matrices. Furthermore, we illustrate the application of the backward reachability computations over safety and transient analysis of MPL systems.

Original language	English
Title of host publication	12th IFAC/IEEE Workshop on Discrete Event Systems, WODES 2104
Editors	Jean-Jacques Lesage, Jean-Marc Faure, José E. Ribeiro Cury, Bengt Lennartson
Publisher	Univelt Inc.
Pages	117-122
Number of pages	6
ISBN (Print)	9783902823618
Publication status	Published - 2014
Externally published	Yes
Event	12th IFAC/IEEE Workshop on Discrete Event Systems, WODES 2104 - Cachan, France Duration: 14 May 2014 → 16 May 2014

Publication series

Name	Advances in the Astronautical Sciences
Volume	12
ISSN (Print)	0065-3438

Conference

Conference	12th IFAC/IEEE Workshop on Discrete Event Systems, WODES 2104
Country/Territory	France
City	Cachan
Period	14/05/14 → 16/05/14

Keywords

Backward reach tube
Backward reachability analysis
Difference-bound matrices
Max-plus-linear systems
Piecewise affine systems
Safety and transient analysis

Cite this

@inproceedings{b5913542a98f4ad8a50685f547998ce2,

title = "Backward reachability of autonomous max-plus-linear systems",

abstract = "This work discusses the backward reachability of autonomous Max-Plus-Linear (MPL) systems, a class of continuous-space discrete-event models that are relevant for applications dealing with synchronization and scheduling. Given an MPL system and a continuous set of final states, we characterize and compute its {"}backward reach tube{"} and {"}backward reach sets,{"} namely the set of states that can reach the final set within a given event interval or at a fixed event step, respectively. We show that, in both cases, the computation can be done exactly via manipulations of difference-bound matrices. Furthermore, we illustrate the application of the backward reachability computations over safety and transient analysis of MPL systems.",

keywords = "Backward reach tube, Backward reachability analysis, Difference-bound matrices, Max-plus-linear systems, Piecewise affine systems, Safety and transient analysis",

author = "Dieky Adzkiya and {De Schutter}, Bart and Alessandro Abate",

note = "Publisher Copyright: Copyright {\textcopyright} 2014 IFAC.; 12th IFAC/IEEE Workshop on Discrete Event Systems, WODES 2104 ; Conference date: 14-05-2014 Through 16-05-2014",

year = "2014",

language = "English",

isbn = "9783902823618",

series = "Advances in the Astronautical Sciences",

publisher = "Univelt Inc.",

pages = "117--122",

editor = "Jean-Jacques Lesage and Jean-Marc Faure and {Ribeiro Cury}, {Jos{\'e} E.} and Bengt Lennartson",

booktitle = "12th IFAC/IEEE Workshop on Discrete Event Systems, WODES 2104",

address = "United States",

}

Adzkiya, D, De Schutter, B & Abate, A 2014, Backward reachability of autonomous max-plus-linear systems. in J-J Lesage, J-M Faure, JE Ribeiro Cury & B Lennartson (eds), 12th IFAC/IEEE Workshop on Discrete Event Systems, WODES 2104. Advances in the Astronautical Sciences, vol. 12, Univelt Inc., pp. 117-122, 12th IFAC/IEEE Workshop on Discrete Event Systems, WODES 2104, Cachan, France, 14/05/14.

Backward reachability of autonomous max-plus-linear systems. / Adzkiya, Dieky; De Schutter, Bart; Abate, Alessandro.
12th IFAC/IEEE Workshop on Discrete Event Systems, WODES 2104. ed. / Jean-Jacques Lesage; Jean-Marc Faure; José E. Ribeiro Cury; Bengt Lennartson. Univelt Inc., 2014. p. 117-122 (Advances in the Astronautical Sciences; Vol. 12).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Backward reachability of autonomous max-plus-linear systems

AU - Adzkiya, Dieky

AU - De Schutter, Bart

AU - Abate, Alessandro

PY - 2014

Y1 - 2014

N2 - This work discusses the backward reachability of autonomous Max-Plus-Linear (MPL) systems, a class of continuous-space discrete-event models that are relevant for applications dealing with synchronization and scheduling. Given an MPL system and a continuous set of final states, we characterize and compute its "backward reach tube" and "backward reach sets," namely the set of states that can reach the final set within a given event interval or at a fixed event step, respectively. We show that, in both cases, the computation can be done exactly via manipulations of difference-bound matrices. Furthermore, we illustrate the application of the backward reachability computations over safety and transient analysis of MPL systems.

AB - This work discusses the backward reachability of autonomous Max-Plus-Linear (MPL) systems, a class of continuous-space discrete-event models that are relevant for applications dealing with synchronization and scheduling. Given an MPL system and a continuous set of final states, we characterize and compute its "backward reach tube" and "backward reach sets," namely the set of states that can reach the final set within a given event interval or at a fixed event step, respectively. We show that, in both cases, the computation can be done exactly via manipulations of difference-bound matrices. Furthermore, we illustrate the application of the backward reachability computations over safety and transient analysis of MPL systems.

KW - Backward reach tube

KW - Backward reachability analysis

KW - Difference-bound matrices

KW - Max-plus-linear systems

KW - Piecewise affine systems

KW - Safety and transient analysis

UR - http://www.scopus.com/inward/record.url?scp=84951835647&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84951835647

SN - 9783902823618

T3 - Advances in the Astronautical Sciences

SP - 117

EP - 122

BT - 12th IFAC/IEEE Workshop on Discrete Event Systems, WODES 2104

A2 - Lesage, Jean-Jacques

A2 - Faure, Jean-Marc

A2 - Ribeiro Cury, José E.

A2 - Lennartson, Bengt

PB - Univelt Inc.

T2 - 12th IFAC/IEEE Workshop on Discrete Event Systems, WODES 2104

Y2 - 14 May 2014 through 16 May 2014

ER -

Backward reachability of autonomous max-plus-linear systems

Abstract

Publication series

Conference

Keywords

Other files and links

Fingerprint

Cite this