Decentralized control: when actions speak

How can we facilitate coordination among agents in a decentralized control system? Existing decentralized systems in nature (e.g. bacteria), society (e.g. dancing), and economics (e.g. market signaling) are rife with examples where participating agents communicate in order to coordinate. However, the notion of communication in these examples is somewhat subtle. Unlike in traditional information-theoretic problems, there is no explicit channel, or even an explicit message here, and control actions are used to talk! In 1967, Witsenhausen formulated a decentralized control problem — called Witsenhausen's counterexample — that distilled aspects of this "implicit" form of communication. Despite its minimalist nature, the Witsenhausen counterexample remains unsolved with more than forty years of research effort. In order to obtain intuition into the counterexample, I will first provide a semi-deterministic abstraction of the problem, which I will use to suggest good strategies. I will then provide an information-theoretic lower bound on the minimum achievable cost which is used to show that these "good" strategies attain within a factor of 5 uniformly over all problem parameters for an asymptotically infinite-length version of the problem. By pulling the results back to finite lengths using a large-deviation based "sphere-packing" analysis, I will then characterize the optimal costs for the (scalar) Witsenhausen counterexample to within a factor of 8 for all problem parameters. These are the first provably-approximately-optimal solutions for the long-standing problem. How is this theory useful? The difficulty of Witsenhausen's counterexample had forced the problem formulations in many cases to disallow implicit communication by imposing artificial restrictions. For instance, many formulations restrict attention to an "observer-controller' framework where one controller cannot act, and one cannot observe the state directly. Using our understanding of the Witsenhausen counterexample, we will see that we can start obtaining solutions to more realistic (and more satisfying) problems where all the controllers can observe the state and act on the system.

Pulkit Grover (BS ’03, MS ’05, IIT Kanpur; Ph.D. UC Berkeley 2010) is a postdoc at the Wireless Foundations, Department of Electrical Engineering and Computer Sciences, UC Berkeley. His research interests are in information theory, decentralized control and low-power circuits. He is particularly interested in developing a theory of information for decentralized control, and developing theoretical foundations for understanding system-level power consumption in wireless communications. Dr. Grover is the recipient of the best student paper award at the IEEE Conference in Decision and Control (CDC) 2010.