Stavros Tripakis
Decentralized Control of Discrete Event Systems with Bounded or Unbounded Delay Communication (2004)
Decentralized Control of Discrete Event Systems with Bounded or Unbounded Delay Communication (2004)
TR-2004-26.pdf
Keywords: Control, Communication, Synthesis, Finite Automata, Decidability
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, CC = DCC_0 < DCC_1 < ... < DCUC < DC, where the containments < are strict, CC is the set of control problems solvable with a single controller (centralized case) and DCC_k (resp. DCUC, DC) is the set of problems solvable with two controllers in a k-bounded-delay network (resp. 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 non-deterministic network. This property does not hold when non-blockingness 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.
