On Solvability of a Decentralized Supervisory Control Problem With Communication

We study a decentralized control problem of discrete event systems with communication. We first give a general automata-theoretic formalism that enables us to handle various types of communication, including delay. The decentralized control problem is shown to be undecidable under this formalism. Next we propose a semi-decision procedure for computing finite-state controllers to achieve a given specification in the sense of bisimilarity between the controlled system and a given specification. Using this procedure, we prove decidability of the problem for two special cases, one is the case in which the communication behavior is given as k -bounded-delay communication, and the other is the case in which any cycle in the state transition diagram of the system contains an event observable by all controllers. We also show a method for optimizing controllers based on a graph problem.