Matrix spans in max-plus algebra and a graph-theoretic approach to switching max-plus linear systems
V.P. Kalamboukis (TU Delft - Mechanical Engineering)
Ton van den Boom – Mentor (TU Delft - Team Ton van den Boom)
JW van der Woude – Graduation committee member (TU Delft - Mathematical Physics)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The relation between graph theory and max-plus algebra has been well studied since the inception of max-plus algebra. It has been shown that any square matrix over the maxplus semiring can be represented as a weighted directed graph. Furthermore, properties of these matrices, such as irreducibility and its (unique) eigenvalue, can be determined by its graph-theoretical interpretation. However, this graph-theoretical interpretation has not yet been extended to SMPL systems.
Switching max-plus-linear (SMPL) systems are an extension of max-plus-linear systems (MPL) for modelling discrete-event systems. While for MPL systems the system is described by one max-plus-linear state equation and one max-plus-linear output equation, for SMPL systems the system is described by more than one mode of operation, each consisting of its own unique max-plus-linear state equation and max-plus-linear output equation. The different modes allow for more efficient modelling of changes to the structure of the system. The switching between the different modes of operation can be deterministic, stochastic or a combination of the two.
Due to the fact that max-plus algebra is an idempotent algebra and there is no opposite operation to max-plus addition, vectors spaces in max-plus algebra cannot be defined in the same way as for conventional algebra. As a result, determining the span of matrices has to be performed in a different way than for matrices in conventional algebra as matrix ranks are also defined in a different way. Determining the span of matrices in both max-plus algebra and conventional algebra is important as it allows for the calculation of the set of states that can be accessed (reached) by MPL systems and LTI systems respectively.
The purpose of this thesis is three-fold: firstly, a method is developed for accurately determining the span of max-plus matrices, secondly, this method is applied to MPL systems with the purpose of determining the set of accessible states for autonomous and non-autonomous MPL systems and establishing the necessary conditions for structural controllability by making use of its graphical representation and thirdly, to model SMPL systems and also establish properties such as structural controllability by means of a graph-theoretic framework.