VARIABLE LOOKAHEAD SUPERVISORY CONTROL WITH STATE INFORMATION

In cases where the discrete-event system model has an infinite or larg e state space, or when it is not completely specified a priori, applyi ng the traditional off-line methods for computing the control policy m ay be impractical, if not infeasible. We adopt the on-line limited loo kahead approach introduced in [2]. Under this approach, the next contr ol action is determined based on an N-step ahead projection of the sys tem behavior and on one of two attitudes-conservative or optimistic. W e extend this approach to incorporate knowledge of the system state in the computation. This has the potential of improving the efficiency o f the computation as well as the quality of the control policy. There are five specific contributions presented in this paper: 1) a new algo rithm for the on-line computation of supervisory controls with worst c ase complexity that is quadratic in the number of ''expanded' states, 2) an algorithmic proof of the correctness of this algorithm that avoi ds using fixed point methods and offers new insight into the structure of the supremal controllable sublanguage, 3) an off-line version base d on a forward search technique that has the same worst case complexit y as existing off-line algorithms but is potentially more efficient, 4 ) a formal proof of the fact that when the languages of interest are l ivelock free the computations are performed in linear complexity, and 5) new bounds on the depth of the lookahead window that guarantee opti mality.