VARIABLE LOOKAHEAD SUPERVISORY CONTROL WITH STATE INFORMATION

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