What can Coding do for Control?

Professor Babak Hassibi
Professor, California Institute of Technology
Given on: October 25, 2012

Abstract

We all know what coding can do for communication: it essentially allows us to replace a lossy channel with a lossless one (up to a certain rate). This is done using block codes and tolerating arbitrarily long delays at the encoder and decoder. Such delays are often acceptable in communication scenarios. However, they are not in most control systems which must contend with real-time constraints upfront, since controllers must take action using information only currently available. As a result of this, and the fact that in early control systems the plant, observer and controller were often collocated, control theory has by-and-large developed independently of information theory and has had little use for coding. However, there are now ever-increasing applications where the plant, observer and controller are distributed in different locations and exchange information (measurements and control signals) over unreliable channels and networks. In such settings conventional coding-theoretic or control-theoretic approaches do not work: one needs to deal with both the real-time constraints and the underlying unreliability in a simultaneous and systematic way.

We will review the works of Schulman and Sahai, developed over the past two decades, that study such problems and that introduce the notions of “tree codes” and “anytime capacity”, respectively. Tree codes are a new construct in coding theory that allow interactive communication between multiple parties over unreliable links; in particular, they allow real-time control over unreliable channels. While their existence was shown by Schulman in 1994, the field has largely remained dormant because to date there have been no explicit constructions of tree codes and no efficient encoding and decoding schemes. We will show the existence with “high probability” of “linear” tree codes and, for the first time, construct codes with efficient encoding and decoding for the erasure channel. We show the efficacy of the method by stabilizing example unstable plants over erasure channels, and by demonstrating how to implement distributed protocols, such as consensus, over networks with asymmetric erasures.

Finally, we will argue that what coding can do for control is to replace a lossy channel with a lossless one, but with “random delay”. We will also discuss what this means.

Biography

Babak Hassibi is professor and executive officer of electrical engineering at the California Institute of Technology. Previously, he was a member of the technical staff at the Mathematical Sciences Research Center at Bell Laboratories, Murray Hill, NJ, and prior to that he obtained his PhD in electrical engineering from Stanford University. His research interests span different aspects of communications, signal processing and control. Among other awards, he is a recipient of the David and Lucille Packard Foundation Fellowship, and the Presidential Early Career Award for Scientists and Engineers (PECASE).