Optimal supervisory control of discrete event systems for cyclic tasks

In this paper, we investigate the problem of optimal supervisory control for cyclic tasks in the context of discrete-event systems (DES). We consider the completion of each single task as the visit of a marked state, and overall control objective is to complete tasks cyclically in the sense that marked states are visited infinitely often. Following the standard optimal supervisory control framework, two types of costs, disable cost and occurrence cost, are considered. However, instead of considering the standard accumulated total cost or the average cost per event, we consider the measure for the control performance using the average cost per task. We show that such an optimality measure is more suitable for tasks that need to be completed cyclically. Our goal is to design a live and non-blocking supervisor such that the average cost per task in the worst-case is minimized. To solve the problem, we propose a game-theoretical approach by converting the optimal control problem as a two-player graph game. Structural properties of the converted game are discussed. In particular, we show that this game can be solved by a set of mean payoff decision problems, for which effective algorithms exist. Our problem can be considered as a special instance of the general ratio-game in the literature. However, by exploring new structural property for this problem, we achieve superior computational efficiency when compared to the conventional solution designed for more general problem formulations. Illustrative examples are provided to demonstrate the proposed algorithm.