Max-plus-algebraic hybrid automata

Abstract

Man-made systems, such as manufacturing and transportation networks, and their interactions with the environment are driven by human-designed operational rules. These rules are most often based on the asynchronous occurrence of discrete events over time, such as the arrival and departure of trains at a station. The modelling, analysis, and control of the system evolution over discrete events result in the discrete-event systems framework. Here, the dynamics are derived from two layers of behaviours: the logical ordering of event occurrences on the one hand, and the timing of events on the other. Automata are untimed finite-state sequential processing machines typically used to study the logical behaviour of the discrete-event system. Here, a state transition diagram encodes the allowed sequences of events, such as the order of successive trains departing a station, resulting in a variable (possibly non-deterministic) schedule of operation. Max-plus algebra, with maximisation and addition as its basic operations, (and associated algebraic structures) conveniently handle the timing aspects of discrete-event systems when the schedule of operation of different tasks, such as the order of trains, is made deterministic.

In this PhD thesis, we develop tools for system-theoretical analysis of discrete-event systems when purely (max-plus) algebraic models, derived from timing constraints among events, are enriched with automata-theoretic conflict resolution schemes to treat variable schedules. We follow the hybrid dynamical systems approach that offers a powerful description of the interplay between the logical and timing aspects of discrete-event systems. On the one hand, the resulting hybrid automata allow a continuous-variable dynamic representation of discrete-event systems analogously to time-driven systems. On the other hand, the framework is convenient when timing constraints are of explicit concern in system dynamics and performance specifications. We address issues related to the stability, reachability, and solvability of discrete-event systems in this PhD thesis.

Firstly, we focus on formalising the discrete-event modelling framework as a novel max- plus-algebraic hybrid automaton analogously to the hybrid automaton framework in conventional algebra. There are mainly two phenomena of concern: synchronisation and choice of event occurrences. We illustrate how the proposed framework offers explicit flexibility in modelling the interplay of synchronisation and choice phenomena among event occurrences. We show that the proposed framework unifies and extends the existing max-plus-algebraic models of discrete-event systems with the variable ordering of events. We derive equivalence relations between the proposed framework and other automata-theoretic models with timing features such as weighted automata.

Stability analysis plays an important role in the operation and control of dynamical systems. There has been considerable research on generalising the notions of stability from linear time-invariant systems to hybrid systems in conventional algebra. The research for the counterpart in max-plus-algebraic systems is still limited. This motivates us to study the stability of discrete-event systems in the second part of the thesis. We present a novel stability analysis framework under the broad setting of max-plus-algebraic hybrid automata. We achieve this by reformulating various notions of stability of discrete-event systems phrased in the classical Lyapunov sense. We then integrate tools from max-plus algebra and Lyapunov theory to demonstrate the decision-making capabilities of the proposed approach.

In the last part of the PhD thesis, we focus on the parametric modelling of constrained discrete-event systems. This allows capturing variations in the timing and ordering of event occurrences within the framework of max-plus-algebraic hybrid automata analogously to the conventional time-driven linear parameter-varying systems. The analysis of the effect of parameter variations on the existence of admissible trajectories is of paramount importance in model-based decision-making for discrete-event systems. Therefore, we focus on validating the coherence of the obtained model in presence of nonlinear implicitness in the system dynamics. In our analysis, we borrow tools from max-plus algebra, monotone functions theory, graph theory, and computational geometry. Finally, we study the application of the proposed approach to an urban railway system.