Keywords

Introduction

Modern control systems often comprise of multiple decentralized control agents that interact over communication channels (Fig. 1). What characteristic distinguishes a centralized control problem from a decentralized one? One fundamental difference is a “knowledge gradient”: agents in a decentralized team often observe, and hence know, different things. This observation leads to the idea of information patterns (Witsenhausen 1971), a formalization of the notion of “who knows what and when do they know it” (Ho et al. 1978; Mitter and Sahai 1999)

Information Structures, the Witsenhausen Counterexample, and Communicating Using Actions, Fig. 1
figure 98figure 98

The evolution of control systems. Modern “networked control systems” (also called “cyber-physical systems”) are decentralized and networked using communication channels

Full size image

.

The information pattern is said to be classical if all agents in the team receive the same information and have perfect recall (so they do not forget it). What is so special about classical information patterns? For these patterns, the presence of external communication links has no effect on the optimal costs! After all, what could the agents use the communication links for, when there is no knowledge gradient? More interesting, therefore, are the problems for which the information pattern is nonclassical. These problems sit at the intersection of communication and control: communication between agents can help reduce the knowledge differential that exists between them, helping them perform the control task. Intellectually and practically, the concept of nonclassical information patterns motivates a lot of formulations at the control-communication intersection. Many of these formulations – including some discussed in this Encyclopedia (e.g., Data Rate of Nonlinear Control Systems and Feedback Entropy;  Information and Communication Complexity of Networked Control Systems  Quantized Control and Data Rate Constraints;  Networked Control Systems: Architecture and Stability Issues;  and   Networked Control Systems: Estimation and Control Over Lossy Networks) – intellectually ask the question: for a realistic channel that is constrained by noise, bandwidth, and speed, what is the optimal communication and control strategy?

One could ask the question of optimal control strategy even for decentralized control problems where no external channel is available to bridge this knowledge gradient. Why could these problems be of interest? First, these problems are limiting cases of control with communication constraints. Second, and perhaps more importantly, they bring out an interesting possibility that can allow the agents to “communicate,” i.e., exchange information, even when the external channel is absent. It is possible to use control actions to communicate through changing the system state! We now introduce this form of communication using a simple toy example.

Communicating Using Actions: An Example

To gain intuition into when communication using actions could be useful, consider the inverted pendulum example shown in Fig. 2. The goal of the two agents is to bring the pendulum as close to the origin as possible. Both controllers have their strengths and weaknesses. The “weak” controller C w has little energy, but has perfect state observations. On the other hand, the “blurry” controller C b has infinite energy, but noisy observations. They act one after the other, and their goal is to move the pendulum close to the center from any initial state. The information structure of the problem is nonclassical: the C w , but not C b , knows the initial state of the pendulum, and C w does not know the precise (noisy) observation of C b using which C b takes actions.

Information Structures, the Witsenhausen Counterexample, and Communicating Using Actions, Fig. 2
figure 99figure 99

Two controllers, with their respective strengths and weaknesses, attempting to bring an inverted pendulum close to the center. Also shown (using green “+” signs) are possible quantization points chosen by the controllers for a quantization-based control strategy

Full size image

A possible strategy: A little thought reveals an interesting strategy – the weak controller, having perfect observations, can move the state to the closest of some predecided points in space, effectively quantizing the state. If these quantization points are sufficiently far from each other, they can be estimated accurately (through the noise) by the blurry controller, which can then use its energy to push the pendulum all the way to zero. In this way, the weak controller expends little energy, but is able to “communicate” the state through the noise to the blurry controller, by making it take values on a finite set. Once the blurry controller has received the state through the noise, it can use its infinite energy to push the state to zero.

The Witsenhausen Counterexample

The above two-controller inverted-pendulum example is, in fact, motivated by what is now known as “the Witsenhausen counterexample,” formulated by Witsenhausen in 1968 (see Fig. 3). In the counterexample, two controllers (denoted here by C w for “weak” and C b for “blurry”) act one after the other in two time-steps to minimize a quadratic cost function. The system state is denoted by x t , where t is the time index. u w and u b denote the inputs generated by the two controllers. The cost function is \(k^{2}\mathbb{E}\left [u_{w}^{2}\right ] + \mathbb{E}\left [x_{2}^{2}\right ]\) for some constant k. The initial state x0 and the noise z at the input of the blurry controller are assumed to be Gaussian distributed and independent, with variances σ02 and 1 respectively. The problem is a “linear-quadratic-Gaussian” (LQG) problem, i.e., the state evolution is linear, the costs are quadratic, and the primitive random variables are Gaussian.

Information Structures, the Witsenhausen Counterexample, and Communicating Using Actions, Fig. 3
figure 910figure 910

The Witsenhausen counterexample is a deceptively simple two-time-step two-controller decentralized control problem. The weak and the blurry controllers, C w and C b act in a sequential manner

Full size image

Why is the problem called a “counterexample”? The traditional “certainty-equivalence” principle (Bertsekas 1995) shows that for all centralized LQG problems, linear control laws are optimal. Witsenhausen (1968) provided a nonlinear strategy for the Witsenhausen problem which outperforms all linear strategies. Thus, the counterexample showed that the certainty-equivalence doctrine does not extend to decentralized control.

What is this strategy of Witsenhausen that outperforms all linear strategies? It is, in fact, a quantization-based strategy, as suggested in our inverted-pendulum story above. Further, it was shown by Mitter and Sahai (1999) that multipoint quantization strategies can outperform linear strategies by an arbitrarily large factor! This observation, combined with the simplicity of the counterexample, makes the problem very important in decentralized control. This simple two-time-step two-controller LQG problem needs to be understood to have any hope of understanding larger and more complex problems.

While the optimal costs for the problem are still unknown (even though it is known that an optimal strategy exists (Witsenhausen 1968; Wu and Verdú 2011)), there exists a wealth of understanding of the counterexample that has helped address more complicated problems. A body of work, starting with that of Baglietto et al. (1997), numerically obtained solutions that could be close to optimal (although there is no mathematical proof thereof). All these solutions have a consistent form (illustrated in Fig. 4), with slight improvements in the optimal cost. Because the discrete version of the problem, appropriately relaxed, is known to be NP-complete (Papadimitriou and Tsitsiklis 1986), this approach cannot be used to understand the entire parameter space and hence has focused on one point: \(k^{2} = 0.5,\sigma _{0}^{2} = 5\). Nevertheless, the approach has proven to be insightful: a recent information-theoretic body of work shows that the strategies of Fig. 4 can be thought of as information-theoretic strategies of “dirty-paper coding” Costa (1983) that is related to the idea of embedding information in the state. The question here is: how do we embed the information about the state in the state itself ?

Information Structures, the Witsenhausen Counterexample, and Communicating Using Actions, Fig. 4
figure 911figure 911

The optimization solution of Baglietto et al. (1997) for k2 = 0. 5, σ02 = 5. The information-theoretic strategy of “dirty-paper coding” Costa (1983) also yields the same curve (Grover and Sahai 2010)

Full size image

An information-theoretic view of the counterexample: This information-theoretic approach that culminated in Grover et al. (2013) also obtained the first approximately optimal solutions to the Witsenhausen counterexample as well as its vector extensions. The result is established by analyzing information flows in the counterexample that work toward minimizing the knowledge gradient, effectively an information pattern in which C w can predict the observation of C b more precisely. The analysis provides an information-theoretic lower bound on cost that holds irrespective of what strategy is used. For the original problem, this characterizes the optimal costs (with associated strategies) within a factor of 8 for all problem parameters (i.e., k and σ02). For any finite-length extension, uniform finite-ratio approximations also exist (Grover et al. 2013). The asymptotically infinite-length extension has been solved exactly (Choudhuri and Mitra 2012).

The problem has also driven delineation of decentralized LQG control problems with optimal linear solutions and those with nonlinear optimal solutions. This led to the development and understanding of many variations of the counterexample (Bansal and Başar 1987; Başar 2008; Ho et al. 1978; Rotkowitz 2006) and understanding that can extend to larger decentralized control problems. More recent work shows that the promise of the Witsenhausen counterexample was not a misplaced one: the information-theoretic approach that provides approximately optimal solutions to the counterexample (Grover et al. 2013) yields solutions to other more complex (e.g., multi-controller, more time-steps) problems as well (Grover 2010; Park and Sahai 2012).

Summary and Future Directions

Even simple problems with nonclassical information structures can be hard to solve using classical techniques, as is demonstrated by the Witsenhausen counterexample. However, nonclassical information pattern for some simple problems – starting with the counterexample – has recently been explored via an information-theoretic lens, yielding the first optimal or approximately optimal solutions to these problems. This approach is promising for larger decentralized control problems as well. It is now important to explore what is the simplest decentralized control problem that cannot be solved (exactly or approximately) using ideas developed for the counterexample. In this manner, the Witsenhausen counterexample can provide a platform to unify the more modern (i.e., external-channel centric approaches, see  Quantized Control and Data Rate Constraints;  Data Rate of Nonlinear Control Systems and Feedback Entropy;  Networked Control Systems: Architecture and Stability Issues;  Networked Control Systems: Estimation and Control Over Lossy Networks;  Information and Communication Complexity of Networked Control Systems; in the encyclopedia) with the more classical decentralized LQG problems, leading to enriching and useful formulations.

Cross-References