FILESMALL Research Project

Stochastic Filtering of Max-Plus Linear Systems

Group : Dynamic Systems and Optimization

Labelling: EMC2

Duration: 40 months (09/01/2019 - 12/31/2022)

Funding: RFI Atlanstic 2020

Staff involved from LARIS: Mehdi Lhommeau, Laurent Hardouin, Guilherme Espindola Winck (PhD student)

Project partners: Rafael Santos Mendes (DCA/FEEC, Campinas University)

Abstract and objectives

The theory of discrete event dynamic systems has been developed in recent years from the study of production systems, transport networks, computer systems, etc. It is concerned with performance evaluation problems (calculation of production rates, throughput), verification and control synthesis issues (need to satisfy certain logical constraints, such as non-blocking or mutual exclusion, following a set path, etc.), as well as optimisation problems (e.g. optimal number of processors or machines to perform a given task): optimal number of processors or machines to perform a given task).

The common point of the studied systems is the presence of synchronisation, saturation or competition phenomena linked to the occurrence of events (arrival of a client, interruption of a task...) which seem to prohibit the use of tools familiar to the automatician (differential equations, recurrent equations...).

For several years, the DSO group of LARIS has been interested in the study of these systems in the theoretical framework of max-plus algebra [1]. Many fundamental problems have been studied, such as the control problem with reference model [3], robust controller synthesis [4], disturbance rejection [5] .... 

More recently, we have been interested in the problem of filtering max-plus linear systems. The objective is to be able to estimate the state of the system given a sequence of observations. This is a major issue; indeed, in many applications, the state of the system cannot be completely known, because some state variables are not accessible to measurement or are only partially accessible, and unavoidable measurement errors, or measurement noise, or uncertainty about the system, intervene. 

The theory of estimation shows that all the information for estimating the state of the system is contained in the a posteriori probability density of this state. To meet this objective, in preliminary work we proposed a stochastic filtering method for max-plus linear systems subject to bounded perturbations [2]. These first works on stochastic filtering allowed us to identify the main obstacles to be overcome in order to provide a satisfactory framework for the filtering of max-plus linear systems. 

The objective of this project is to reinterpret the filtering problem for max-plus linear systems. 

To achieve our goal, we propose to follow the following steps over the 3 years of the thesis:

• reinterpret the filtering and estimation problem in order to propose a complete theoretical framework for filtering max-plus systems. In particular, we wish to obtain numerically constructive methods;
• to define criteria correlated to the estimation error that are as relevant as possible with respect to the theoretical framework that will have been defined;
  to develop optimisation algorithms for the various proposed criteria;
• to study the calculation of the mathematical expectation of matrices composed of max-plus non-bounded random variables.

Bibliography

[1] F. Baccelli, G. Cohen, G. J. Olsder, and J. P. Quadrat, “Synchronization and Linearity. An Algebra for Discrete Event Systems”. New York: John Wiley & Sons, 1992.

[2] R. Santos-Mendes, L. Hardouin and M. Lhommeau, "Stochastic Filtering of Max-plus Linear Systems with Bounded Disturbances", IEEE Transactions on Automatic Control, Volume 64(9), 2019

[3] B. Cottenceau, L. Hardouin, J.-L. Boimond, and J.-L. Ferrier, “Synthesis of Greatest Linear Feedback for TEG in Dioid”, IEEE Trans. On Automatic Control, vol. 44(6), pp. 1258–1262, 1999.

[4] M. Lhommeau, L. Hardouin, B. Cottenceau, and L. Jaulin, “Interval analysis and dioid: application to robust controller design for timed event graphs”, Automatica, vol. 40, no. 11, pp. 1923–1930, 2004.

[5] Y. Shang, L. Hardouin, M. Lhommeau, and C. A. Maia, “An integrated control strategy to solve the disturbance decoupling problem for max-plus linear systems with applications to a high throughput screening system”, Automatica , vol. 63, pp. 338–348, 2016.