Optimal Supervisory Control of Discrete Event Dynamical Systems

The notion of optimal supervisory control of discrete event dynamical systems (DEDSs) is formalized in the framework of Ramadge and Wonham. A DEDS is modeled as a state machine and is controlled by disabling some of its transitions. Two types of cost functions are defined: a cost of control function corresponding to disabling transitions in the state machine, and a penalty of control function corresponding to reaching some undesired states or not reaching some desired states in the controlled system. The control objective is to design an optimal control mechanism, if it exists, so that the net cost is minimized. Since a DEDS is represented as a state machine—a directed graph—network flow techniques are naturally applied for designing optimal supervisors. It is also shown that our techniques can be used to solve supervisory control problems under complete as well as partial observation. In particular, for the first time, techniques for computing the supremal controllable and normal sublanguage and the infimal controllable and normal/observable superlanguage without having to perform alternate computations of controllable and normal/observable languages are obtained.