Approximation Methods in Stochastic Max-Plus Systems

Abstract

Stochastic max-plus systems belong to a special class of discrete-event systems. This class consists of systems with synchronization but no choice and the models of such systems are defined using the operators maximization and addition. Stochastic max-plus systems can be further extended to stochastic switching max-plus systems and stochastic min-max-plus-scaling systems. In the identification and control problem of all these systems, the objective function appearing in the optimization problem can be written as the expected value of the maximum of several affine expressions. The focus of this thesis is on finding an efficient method to compute this expected value since the currently available methods are both too complex and too time-consuming. To address this issue, this thesis proposes an approximation method based on the higher-order moments of a random variable. By considering the relationship between the infinity-norm and the p-norm of vectors, we obtain an upper bound for the expected value of the maximum of several affine expressions. This approximation method can be applied to any distribution that has finite moments and in the case that these moments have a closed form (such as for a uniform distribution, normal distribution, beta distribution, or gamma distribution), the approximation method results in an analytic expression. For all the above-mentioned systems, we have compared the performance of the proposed approximation method with other available methods, such as analytic and numerical integration, and Monte Carlo simulation. In nearly all cases, the computation time of the proposed approximation method is at least two orders of magnitude smaller than that of other methods, while still resulting in a comparable control performance.