On the synthesis of optimal schedulers in discrete event control problems with multiple goals

This paper deals with a new type of optimal control for discrete event systems that extends the theory of Sengupta and Lafortune (1998). Our aim is to make a system optimally evolve through a set of multiple goals, one by one, with no order necessarily prespecified. Our method is divided into two steps. We first use the earlier results to synthesize individual optimal controllers for each goal. We then develop the solution of another optimal control problem, namely, how to adapt, if necessary, and schedule all of the controllers built in the first step in order to visit all of the goals with least total cost. We solve this problem by defining the notion of a scheduler and then by mapping the problem of finding an optimal scheduler to an instance of the traveling salesman problem.