Supervisory control using variable lookahead policies

Abstract

This paper deals with the efficient on-line calculation of supervisory controls for discrete event systems (DES's) in the framework of limited lookahead control policies (or LLPs) that we introduced in previous papers. In the LLP scheme, the control action after a given trace of events has been executed is calculated on-line on the basis of an N -step ahead projection of the behavior of the DES. To compute these controls, one must calculate after the execution of each event the supremal controllable sublanguage of a finite language with respect to another finite larger language. In our previous work, we showed how the required supremal controllable sublanguage calculation can be performed by using a backward dynamic programming algorithm over the nodes of the tree representation of these two languages. In this paper, we pursue the same approach for the calculation of LLP controls, but instead we adopt a forward calculation procedure over the N -level tree of interest. This forward procedure improves upon previous work by avoiding the explicit consideration of all the nodes of the N -level tree, while still permitting tree-to-tree recursiveness as enabled events are executed by the system. The forward search ends whenever a control decision can be made unambiguously or whenever the boundary of the N -level tree is reached, whichever comes first. This motivates the name “Variable Lookahead Policy” (or VLP) for this implementation of the LLP supervisory control scheme. This paper presents a general VLP algorithm and studies the properties of several special cases of it. The paper also discusses the implementation of the VLP algorithms and presents computational results regarding the application of these algorithms to a “time-varying” DES.