Distributed Estimation and Control in Networked Systems
-- Vijay
Gupta, Ph. D.
Dissertation, California Institute of Technology, Defended June 2006.
Abstract: Rapid advances in information processing, communication
and sensing
technologies have enabled more and more devices to be provided with
embedded processors, networking capabilities and sensors. For the field
of estimation and control, it is now possible to consider an
architecture in which many simple components communicate and cooperate
to achieve a joint team goal. This distributed (or networked)
architecture promises much in terms of performance, reliability and
simplicity of design; however, at the same time, it requires extending
the traditional theories of control, communication and computation and,
in fact, looking at a unified picture of the three fields. A systematic
theory of how to design distributed systems is currently lacking.
This dissertation takes the first steps towards understanding the
effects of imperfect information flow in distributed systems from an
estimation and control perspective and coming up with new design
principles to counter these effects. Designing networked systems is
difficult because such systems challenge two basic assumptions of
traditional control theory - presence of a central node with access to
all the information about the system and perfect transmission of
information among components. We formulate and solve many problems that
deal with the removal of one, or both, of these assumptions. The chief
idea explored in this dissertation is the joint design of information
flow and the control law. While traditional control design has
concentrated on calculating the optimal control input by assuming a
particular information flow between the components, our approach seeks
to synthesize the optimal information flow along with the optimal
control law that satisfies the constraints of the information flow. Thus
besides the question of 'What should an agent do?', the questions of
'Whom should an agent talk to?', 'What should an agent communicate?',
'When should an agent communicate?' and so on also have to be answered.
The design of the information flow represents an important degree of
freedom available to the system designer that has hitherto largely been
ignored. As we demonstrate in the dissertation, the joint design of
information flow and the optimal control input satisfying the
constraints of that information flow yields large improvements in
performance over simply trying to fit traditional design theories on
distributed systems.
We begin by formulating a distributed control problem in which many
agents in a formation need to cooperate to minimize a joint cost
function. We provide numerical algorithms to synthesize the optimal
constrained control law that involve solving linear equations only and
hence are free from numerical issues plaguing the other approaches
proposed in the literature. We then provide and analyze a model to
understand the issue of designing the topology according to which the
agents interact. The results are very surprising since there are cases
when allowing communication to happen between two agents may, in fact,
be detrimental to the performance.
We then move on to consider the effects of communication channels on
control performance. To counter such effects, we propose the idea of
encoding information for the purpose of estimation and control prior to
transmission. Although information theoretic techniques are not possible
in our problem, we are able to solve for a recursive yet optimal encoder
/ decoder structure in many cases. This information flow design oriented
approach has unique advantages such as being optimal for any packet drop
pattern, being able to include the effect of known but random delays
easily, letting us escape the limits set by reliability for transmission
of data across a network by using intermediate nodes as 'repeaters'
similar to a digital communication network and so on.
We finally take a look at combining the effects of multiple sources of
information and communication channels on estimation and control. We
look at a distributed estimation problem in which, at every time step,
only a subset out of many sensors can transmit information to the
estimator. This is also a representative resource allocation problem. We
propose the idea of stochastic communication patterns that allows us to
include the effects of communication channels explicitly during system
design. Thus, instead of tree-search based algorithms proposed in the
literature, we provide stochastic scheduling algorithms that can take
into account the random packet drop effect of the channels. We also
consider a distributed control problem with switching topologies and
solve for the optimal controller. The tools that we develop are
applicable to many other scenarios and we demonstrate some of them in
the dissertation.
Along the way, we look at many other related problems in the
dissertation. As an example, we provide initial results about the issue
of robustness of a distributed system design to a malfunctioning agent.
This notion is currently lacking in the control and estimation
community, but has to be a part of any effective theory for designing
networked or distributed systems.
Complete thesis ( 1.73Mb, 266 pages)
A shorter version of the thesis, without some
supplementary material in the appendices ( 1.17Mb, 193 pages)
back