LIMITED LOOKAHEAD POLICIES IN SUPERVISORY CONTROL OF DISCRETE EVENT SYSTEMS

The conventional supervisor synthesis methods for a discrete event system require i) a finite automaton model of the process under control, and ii) a finite automaton model of the legal behavior. When the discrete event system is very complex and has a large number of states, or when it is time varying, it may be difficult if not impossible to build these automata. We propose and study a supervisory control scheme which is based on ''limited lookahead control policies.'' 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 (represented as an N-level tree). This procedure then repeats after the execution of the next event. Different ''attitudes'' can be adopted in the calculation of a control action for the given N-level tree in order to resolve uncertainties about the process behavior beyond N steps. We propose and study two such attitudes, termed conservative and optimistic. We present several results about this new supervisory control scheme, including results pertaining to the following issues: i) monotonicity and convergence properties of the optimistic and conservative N-step policies in terms of N, and comparison of these policies with the optimal off-line solution; ii) closed-form expression for the language generated by the N-step conservative policy for prefix-closed legal languages; iii) lower bounds for N that guarantee that the on-line scheme performs as well as an off-line scheme with complete information.