Friday, November 13, 2009
Location: EBU2, Room 479
Understanding Implicit Communication in Distributed Control
Pulkit Grover, UC Berkeley
In distributed systems, control actions often serve a dual purpose -- minimizing the immediate control cost, and communicating relevant information to help other controllers. Unfortunately, though this “implicit communication” is ubiquitous, it also seems to make such problems hard. General communication problems have been addressed quite successfully using information theory. In this talk we will see how information theory can help improve our understanding of implicit communication, and thereby, of distributed control.
First, we focus on Witsenhausen's counterexample -- a deceptively simple distributed control problem that has remained unsolved for more than 40 years. It has been observed that an implicit channel connects the two controllers in the counterexample. Using information-theoretic techniques, we provide upper and lower bounds to the optimal cost, characterizing the optimal cost of Witsenhausen's counterexample (and its vector extensions) to within a constant factor uniformly over all problem parameters. The information-theoretic technique of dirty-paper coding provides the best upper bounds. Lower bounds are derived using concepts from lossy communication of a source and a large-deviations (or sphere-packing) technique.
Next, we show that the implicit channel based understanding extends to other two-controller problems, providing solutions to within a constant factor for these problems. Information theory thus emerges as an important toolset for obtaining provably good solutions to distributed control problems.
Joint work with Anant Sahai, Se Yong Park.
Pulkit Grover (BS '03, MS '05, IIT Kanpur) is a graduate student at UC Berkeley, where he's a member of the Wireless Foundations center. His research interests include applications of information theory to distributed control and power consumption in circuits, use of technology for development, and economics. Grover is the recipient of the US-Vodafone fellowship at UC Berkeley (2005-07), Microsoft Award for Innovation (CSIDC 2003), and National and State Science talent scholarships (by Govt. of India and Govt. of Rajasthan, respectively).