Probabilistic Supervisory Control of Probabilistic Discrete Event Systems

Abstract

This thesis considers probabilistic supervisory control of probabilistic discrete event systems (PDES). PDES are modeled as generators of probabilistic languages. The probabilistic supervisors employed are a generalization of the deterministic ones previously employed in the literature. At any state, the supervisor enables/disables events with certain probabilities. The probabilistic supervisory control problem (PSCP) that has previously been considered in the literature is revisited: find, if possible, a supervisor under whose control the behavior of a plant is identical to a given probabilistic specification. The existing results are unified, complemented with a solution of a special case and the computational analysis of synthesis problem and the solution. The central place in the thesis is given to the solution of the optimal probabilistic supervisory control problem (OPSCP) in the framework: if the conditions for the existence of probabilistic supervisor for PSCP problem are not satisfied, find a probabilistic supervisor such that the achievable behaviour is as close as possible to the desired behaviour. The proximity is measured using the concept of pseudometric on states of generators. The distance between two systems is defined as the distance in the pseudometric between the initial states of the corresponding generators. The pseudometric is adopted from the research in formal methods community and is defined as the greatest fixed point of a monotone function. Starting from this definition, we suggest two algorithms for finding the distances in the pseudometric. Further, we give a logical characterization of the same pseudometric such that the distance between two systems is measured by a formula that distinguishes between the systems the most. A trace characterization of the pseudometric is then derived from the logical characterization by which the pseudometric measures the difference of (appropriately discounted) probabilities of traces and sets of traces generated by systems, as well as some more complicated properties of traces. Then, the solution to the optimal probabilistic supervisory control problem is presented. Further, the solution of the problem of approximation of a given probabilistic generator with another generator of a prespecified structure is suggested such that the new model is as close as possible to the original one in the pseudometric (probabilistic model fitting). The significance of the approximation is then discussed. While other applications are briefly discussed, a special attention is given to the use of ideas of probabilistic model fitting in the solution of a modified optimal probabilistic supervisory control problem.