Control of Discrete-Event Systems
by Jan H. van Schuppen
The use of computers for control has recently led to control theory for logical operations in addition to control theory for continuous variable systems. The long term aim of control of discrete-event systems is to develop theory and algorithms for the logic control of engineering systems by computers. The following ERCIM institutes participate in this research topic: CWI, INRIA-IRISA, and SICS.KTH.
Control of engineering systems is implemented by computers nowadays. This then leads to problems of ordering and of sequencing of discrete operations.
This may be seen in contrast with control of dynamic systems in which states take values in continuous spaces and the dynamics are described by differential equations. Examples of engineering systems for which control of discrete-event systems has been used are: communication protocols, feature interaction in telephone networks, failure diagnosis in heating and ventilation systems, and failure diagnosis in telephone switches. Computer science terms used for the topic are embedded systems and embedded software. Control of discrete-event systems is likely to develop in cooperation with computer scientists. The common root of control theory and computer science in automaton theory facilitates communication.
Control theory makes use of models in the form of dynamic systems. For the sequencing of operations such a system is called a discrete-event system which may be an automaton, a Petri net, or a process algebra. The choice of the model class is generally based on a trade-off between the expressiveness of the language of the system and the complexity of control problems of a system in the model class. Automata and Petri nets are most often used because of their ease of use and closeness to engineering models.
The control problem is to synthesize and to design controllers or supervisors such that the closed-loop system consisting of the system and the controller meets the specifications. The problem encompasses verification as studied in computer science. Control objectives are to guarantee safety criteria and to guarantee a minimal behaviour or liveness criteria. There is now a body of results on the existence and the design of controllers for automaton and Petri net based discrete-event systems. Control theory for automaton based discrete-event systems has been mainly developed by W.M. Wonham (University of Toronto) and his Ph.D. students. Control of infinite-string automata has been developed by J.G. Thistle (Ecole Polytechnique de Montréal) under supervision of W.M. Wonham.The research groups of S. Lafortune (University of Michigan, Ann Arbor) and S.I. Marcus (University of Maryland, College Park) have contributed substantially to this theory and to the algorithms. Control of Petri nets has been studied by several researchers including R.K. Boel, A. Giua, and B.H. Krogh. There are several software packages available for the design of controllers.
Control of discrete-event systems for realistic engineering systems must be able to handle control problems for discrete-event systems of large sizes with moderate complexity. Several research directions follow from this aim. First, to develop hierarchical models and control theory for hierarchical systems. Inspiration sources are the publications by D. Harel on statecharts and the hierarchical systems of W.M. Wonham and K.C. Wong. Second, to develop control theory for decentralized or distributed systems. Distributed systems are often used in engineering because of the geographical distribution of engineering systems. Third, to study special classes of discrete-event systems and the relation between discrete-event systems. The main tool in this context is universal algebra, coalgebra, and lattice theory. Computer science concepts like observational equivalence introduced by R. Milner, bisimulation equivalence between discrete-event systems, other semantics, and coalgebra introduced by J.J.M.M. Rutten are useful here. A fourth research direction is a fundamental study of expressiveness of languages of systems and of complexity. This may point the way to the selection of subclasses of systems for which the development of a realistic and substantial control theory is possible.
Please contact:
Jan H. van Schuppen - CWI
Tel. +31 20 592 4085
E-mail: J.H.van.Schuppen@cwi.nl