July 6, 2017

Study of the problem of reachability analysis of max-plus linear systems using the polyhedral approach

Guilherme Espindola Winck, Mehdi Lhommeau, Laurent Hardouin

Abstract: The reachability analysis problem of Max-Plus linear (MPL) systems has been properly solved using many different approaches. In this work, the approach chosen is polyhedral and is shown that is usable as data structure in order to solve the forward reachability analysis problem of timed automata described by MPL equations. Drawing inspiration from the extensive work that has been done on DBM, as well as previous work on Tropical polyhedra in other areas, we develop the algorithms needed to perform the tracking of the discussed systems. The concepts and results are elucidated by examples that have been solved using a step-by-step handmade solver, and we further illustrate the performance and the limitations of this approach by a step-by-step numerical solver of small systems (2 -dimensional) with a drawing tool (axis x and y) developed in Python, a high-level programming language.

Keywords: Discrete Event Dynamic Systems, Timed Automata, Timed Event Graphs, Tropical Algebra, Max-Plus Linear Systems, Tropical polyhedra, Reachability Analysis

Dissertation: Read more Oral defense presentation (in French)

Tools (.RAR): Code source ( Python )

Ongoing publications: Paper