Control of discrete event systems using limited lookahead policies.
Sheng‐Luen Chung · Deep Blue (University of Michigan) · 1992
This thesis proposes a new supervisory control scheme for discrete event systems, termed Supervisory Control using Limited Lookahead Policies (LLP), which is capable of addressing some of the most complicated working conditions in supervisory control: the system to be controlled is time-varying, the construction of an automaton recognizer for the legal constraint is difficult, and the state space is too large for conventional approaches. Instead of attempting to calculate off-line the complete control policy for the entire set of possible behaviors of the process, we consider an on-line scheme where after the occurrence of an event, the next control action is determined on the basis of an N-step ahead projection of the behavior of the process; uncertainty beyond this lookahead window is resolved by either a conservative or an optimistic attitude. This procedure then repeats after the execution of the next event. We address two fundamental issues concerning this control scheme: the resultant system behavior and the associated on-line calculations. In characterizing the system behavior, we present a precise formulation of the LLP operational mechanism and, in addition, results pertaining to: monotonicity and convergence properties of the optimistic and conservative N-step policies in terms of N, and comparison of the on-line system behavior with the optimal off-line solution, including lower bounds for N that guarantee that these two are equal. To facilitate the on-line control calculations, we reformulate the problem of finding the supremal controllable sublanguage in the context of LLP as a finite horizon optimal control problem, which helps to reveal the generic two-nested recursive structure inherent in general LLP control schemes: step-to-step and level-to-level recursiveness. Subsequently, we are able to recognize and accordingly to take advantage of (i) the structural similarity between successive windows, and (ii) the fact that not all traces in the window contribute to the control actions, in order to substantially reduce the required on-line calculations. To demonstrate its feasibility in solving general on-line supervisory control problems, the LLP scheme is applied to a complicated time-varying system that would be considered computationally intractable by conventional approaches.