Optimal Nonblocking Directed Control of Discrete Event Systems

For the control of discrete-event systems, we introduced the notion of directed control in (J. Huang et al., 2005), where a directed controller, simply referred as director, is one that selects at most one controllable event to be enabled at any instant. In (J. Huang et al., 2006), we developed a framework for the computation of optimal directors and a polynomial synthesis algorithm for acyclic plants. In this paper, we present a novel synthesis approach that works for general plants, i.e., plants with or without cycles, thus providing a complete solution to the optimal directed control problem introduced in (J. Huang et al., 2006). Moreover, we show that the complexity of the new approach remains polynomial in the size of plant. (Note that an exhaustive search has an exponential complexity.)