Languages, blocking properties and algorithms in supervisory control of discrete event systems.

Abstract

This thesis addresses three important aspects in the supervisory control of discrete event systems: the study of blocking, the characterization of some important languages, and the representation of relational algebraic algorithms. Blocking occurs in the supervisory control of discrete event systems when the controlled system can generate admissible traces of events that cannot be extended to any member of the set of desired marked (e.g., complete) traces. It is often the case that due to the presence of uncontrollable events, blocking is unavoidable or nonblocking solutions do not yield good performance. We study the issue of blocking in the context of a general "supervisory control problem with blocking" (SCPB). The admissible solutions of this problem are characterized and their properties analyzed. We then consider strategies to improve the performance of a given blocking supervisor. Performance is characterized in terms of two sets termed satisficing measure and blocking measure. We present techniques for improving each of these two conflicting measures. We also present techniques to improve both measures successively in order to optimize a given supervisor. The issue of blocking is of course intimately connected with the concept of controllable languages which is of central importance in supervisory control. Two important controllable languages, namely, the infimal closed controllable superlanguage of a given language and the supremal closed nonconflicting controllable sublanguage of a given language are studied in detail. Their properties are analyzed, their computational algorithms discussed and their application in supervisory control with blocking addressed. We also present a relational algebraic approach for the representation of algorithms that arise in the modular composition and control of discrete event systems modeled by finite-state machines. We show that the relational algebra from relational database theory can be employed to formally, uniformly, and concisely describe these algorithms. Relational algebraic expressions are derived for several algorithms on finite-state machines that arise in the study of discrete event systems. The computer implementation of these algebraic expressions is also discussed.