Decentralized Control of Discrete Event Systems with Bounded or Unbounded Delay Communication

We introduce problems of decentralized control with communication, where we explicitly model communication delays. We distinguish two communication models, where delays are, respectively, 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, CC = DCC0 ⊃ DCC1 ⊃ DCC2 ⊃ · · · ⊃ DCUC ⊃ DC, where CC is the set of control problems solvable with a single controller (centralized case), DCCk is the set of problems solvable with two controllers in a k-bounded-delay network, DCUC is the set of problems solvable with two controllers in an unboundeddelay network, and DC is the set of problems solvable with two controllers without communication. The above containments are strict. We prove undecidability of checking the existence of controllers in the unbounded-delay case, or in the case without any communication. Finally, we prove that a decentralized observation problem with bounded-delay communication is decidable