Shannon theory tells us how to communicate explicit sources across explicit channels. However, systems in nature and human society are rife with examples where neither the source nor channel is explicit, and actions, not words, appear to "speak." This phenomena of what we can call implicit communication is little understood in the theory of control, and little explored in theory of communication. Consequently, almost no engineering systems systematically exploit implicit communication. In this dissertation, using toy models, we first argue that dramatic improvements could be possible in control precision and control costs with proper use of actions that communicate.
Theoretically, implicit communication has proven to be a hard nut to crack. From a control stand-point, implicit communication makes problems hard because the same actions that are traditionally used exclusively for control can now communicate as well. From a communications view, there is often another conceptual difficulty: since the source is not specified explicitly, the message can be altered by control actions!
Consequently, even the minimalist toy problem that distills these two difficulties -- the infamous Witsenhausen counterexample -- has remained unsolved for the past four decades. Worse, its discrete counterpart is known to be NP-complete, ruling out the possibility of an algorithmic solution. Since the problem is hard as well as minimalist, it is a bottleneck in understanding implicit communication in particular and decentralized control in general.
The main contribution of this dissertation is two-fold. First, using a sequence of three simplifications of the counterexample, we release this bottleneck by providing the first provably approximately-optimal solutions to the Witsenhausen counterexample. Second, we generalize this sequence of simplifications and propose them as a program for addressing more complicated problems of decentralized control. As an indication of the potential success of this program, we provide approximately-optimal solutions to various problems where implicit communication is possible. Using our refined understanding of implicit communication, we also identify a few practical situations where the phenomena may prove useful.
Actions can speak more clearly than words
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
The Engineering Library
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).