Recursive computation of limited lookahead supervisory controls for discrete event systems

We continue the study of limited lookahead policies in supervisory control of discrete event systems undertaken in a previous paper. On-line control of discrete event systems using limited lookahead policies requires, after the execution of each event, the calculation of the supremal controllable sublanguage of a given language with respect to another larger language. These two languages are finite and represented by their tree generators, where one tree is a subtree of the other. These trees change dynamically from step to step, where one step is the execution of one event by the system. We show in this paper how to perform this calculation in a recursive manner, in the sense that the calculation for a new pair of trees can make use of the calculation for the preceding pair, thus substantially reducing the amount of computation that has to be done on-line. In order to make such a recursive procedure possible from step to step, we show how the calculation for a single step (i.e., for a given pair of trees) can itself be performed recursively by means of a backward dynamic programming algorithm on the vertices of the larger tree. These two nested recursive procedures are also extended to the limited lookahead version of the supervisory control problem with tolerance.Research supported in part by the National Science Foundation under grants ECS-9057967 and ECS-9008947. The first two authors also acknowledge support from GE and DEC.