Quantitative control of probabilistic discrete event systems: A formal measure-theoretic approach

The theory of Supervisory Control for Discrete Event Systems (DES), originally initiated by Ramadge and Wonham [1], is based on a non-probabilistic language framework. However, any practical model for an actual physical process (which inherently involves modeling errors and noise corrupted observations) by a finite state automaton requires consideration of event occurrence probabilities. Garg, Kumar and others investigated probabilistic language (p-language) models and proposed techniques of supervisor design based on a direct generalization of Wonham's original idea of DES supervision. However, the technique involves complicated methodologies for specification of control objectives and is not amenable to online control reconfigurations. The work reported in this thesis takes an alternate approach. Building on the preliminary concept of measure of regular languages, first reported by Ray and his co-workers, a comprehensive methodology for control of arbitrary finite state probabilistic processes is developed. Several possible generalizations of the language measure is presented which extend the measure to the entire class of regular p-languages thereby removing the previously existing restriction of a non-zero termination probability at each state. The most important among these generalizations is the "renormalized" measure which is used to develop an algorithm for deriving the optimal supervision policy for both terminating and non-terminating p-languages. It is shown that the computed supervisor is optimal in the rigorous mathematical sense of elementwise maximizing the language measure vector for the controlled plant behavior and is efficiently computable. Further, a completely general analysis of event unobservability in DES is presented along with the rigorous derivation of two important decidability results on the State Determinacy problem. It is shown that the optimal control algorithm (referred to above) can be modified to yield an online implementable supervision algorithm that takes into account unobservable event occurrences in the underlying plant and achieves performance which is optimal under this limited information. The theoretical results are verified and validated in simulated examples and in actual implementations on mobile robotic platforms.