Discrete-Event Systems

A discrete-event system (DES) is a dynamic system whose evolution in time is governed by the abrupt occurrence of physical events, at possibly irregular intervals. The study of such systems has become increasingly important in recent times because of the proliferation of "human-made" and computer-controlled systems. Such systems typically have "discrete" quantities that are controlled (e.g., how many parts are in an inventory, how many planes are in a runway, how many telephone calls are active, how many parts are in a buffer.) Many examples of DES's exist, especially where digital computers are involved: communication networks, manufacturing facilities, or the execution of a computer program are typical examples.

The controlling agent for a DES (plant) is a supervisor that observes masked versions of the events that occur in the plant. Each time an event is observed, the supervisor presents the plant with a set of events to be `disabled'. In doing so, the supervisor tries to steer the plant away from `forbidden' states and to prevent the occurrence of undesirable event sequences. A common objective of DES designers is to compute supervisors that ensure that the (controlled) behavior is within a specified `legal' behavior.

Recently, a control theoretic formalism has been devised by Peter J. Ramadge and W. Murray Wonham that facilitated the study of DESs systems. They have modeled such systems as state machines or generators that permit (from an initial state) a set of event sequences (or strings ) to occur. A set of these strings forms a language that contains every possible event sequence that can occur in the DES. When a supervisor disables events in the plant, some events can get disabled and the resulting behavior is another language (i.e., set of event sequences) called the closed-loop language.

To ensure that the controlled behavior of the plant is within a specified `legal' behavior, we specify the legal behavior as a legal language that contains all allowable event sequences. The objective of the supervisor is to ensure (while taking into account the above constraints) that every event sequence possible in the controlled system is in the legal language.

This problem can be approached from either a centralized or decentralized viewpoint. In the centralized case, a single supervisor recieves all event observations and the set of events-to-disable is chosen among all those the supervisor can disable. In the decentralized case, there can be many supervisors, where each supervisor receives its own observations, and each has its own set of events that it can disable. In addition, the legal language can be specified as a global constraint (where the supervisors have the same objectives) or a conjunction of local constraints (where each supervisor satisfies its own objectives but the global system behavior is affected by the actions of others.) The supervisors can be designed centrally (where all supervisors are designed simultaneously and the overall effect of the supervisors acting together is considered) or they can be designed locally (where each acts independently from the others.) There is also the possibility of allowing restricted communication between the supervisors as frequently is the case in manufacturing systems.

The main challenge we face in the field of DES comes from the inherent complexity of Discrete-event systems. Among the topics we have studied are a technique of on-line implementation of supervisors in both the centralized and decentralized architectures. The on-line implementation technique takes the complex calculations of a supervisor and breaks them down into a series of simpler ones. We have studied (on-line) supervisor synthesis techniques that guarantee that the closed-loop behavior is a legal one.

Members working with Discrete-Event Systems

Joe Prosser