Optimal directed control of discrete event systems with linear temporal logic constraints
Ami Sakakibara, Sasinee Pruekprasert, Toshimitsu Ushio · 2015
We consider a quantitative discrete event system modeled by a weighted automaton, where a weight assigned to each transition represents a cost by the occurrence of the transition. An optimal directed controller selects at most one controllable event at each state to optimize director's cost of the controlled discrete event system. On the other hand, linear temporal logic is often used to specify the qualitatively desired behavior of a discrete event system. In this paper, we formulate a novel optimal directed control problem where the selection of the controllable event at each state is determined so as to maximize the worst-case value of the mean payoffs of controlled behaviors subject to a given linear temporal logic control specification. We propose a design method using a two-player game automaton whose players are the director and the product automaton. The former aims to maximize the worst-case value of the generated behaviors while the latter wants to minimize it. Under this situation, we use the concept of a best response and provide an algorithm to compute an optimal director. Then, we apply the proposed algorithm to a control problem of an AGV.