Decentralized Control of Discrete-Event Systems With Bounded or Unbounded Delay Communication

Abstract

We introduce problems of decentralized control with delayed communication, where delays are either unbounded or bounded by a given constant k. In the k-bounded-delay model, between the transmission of a message and its reception, the plant can execute at most k events. In the unbounded-delay model, the plant can execute any number of events between transmission and reception. We show that our framework yields an infinite hierarchy of control problems, where the containments are strict, CC is the set of control problems solvable with a single controller (centralized case) and DCC/sub k/ (respectively, DCUC, DC) is the set of problems solvable with two controllers in a k-bounded- delay network (respectively, in an unbounded-delay network, without communication). The hierarchy is a result of the following property: Controllers which "work" in a given network will also work in a less nondeterministic network. This property does not hold when nonblockingness is introduced. Checking the existence of controllers in the unbounded-delay case or in the case without communication are undecidable problems. However, a related decentralized observation problem with bounded-delay communication is decidable.