In this talk we discuss the problem of constructing decentralized control systems, which is an outstanding problem in control theory. For centralized control systems, there are many effective algorithms for computing controllers, and this is possible for a wide class of systems including deterministic models such as linear dynamical systems and stochastic models such Markov decision processes. For decentralized control the situation is very different. For many problems where the centralized counterpart is simple, such as control to minimize the mean square error, there are no known computationally tractable algorithms for the decentralized case. We present an overview of what is known, along with our recent results, in which we show that for certain restricted classes of problems efficient algorithms for finding optimal controller do exist, and for a more general class of systems one may compute approximately optimal controllers efficiently.
