
Multiple sensors may transmit similar data
of variable trustworthiness and accuracy; multiple controllers may perform
similar functions and may send packets with commands to the same actuator.
The control functionality will explicitly depend on the trustworthiness
of the data: using timestamped data packets, our research will quantify
the usefulness of each received piece of information.

Traditionally, the problem of allocating communication
channel resources has been treated separately from the problem of optimizing
the performance of linear systems. In this research we explore the notion
of doing both allocation and optimization simultaneously. We consider a
linear system, such as a controller or estimator, in which several signals
are transmitted over communication channels with bit rate limitations.
We focus on finding the allocation of communication resources such as transmission
powers, bandwidths, or timeslot fractions, that yields optimal system
performance.
HYBRID
SYSTEMS
REACHABILITY
TOOL
C. Tomlin, I.
Mitchell, A. Bayen
Designed and implemented a Local Level
Set variant of the Mitchell and Tomlin algorithm for analyzing safety properties
of hybrid systems in prototype C++ code; demonstrated its use in proving
safety of an autoland function in a single aircraft's autopilot, under
mode switching, and in multiple aircraft coordination. Presented this work
to the Boeing OCP group and discussed implementation of this demonstration
in the OCP.
IMPACT: this is the first time such a
computational reachability tool has been designed for hybrid systems with
general nonlinear dynamics.
DRAGONFLY
TESTBED
DEVELOPMENT
C. Tomlin, J.
Evans, G. Inalhan, J.S. Jang, R. Teo

Unique platform for applied advanced control
system research

Distributed cooperative control
multiple agents
peerpeer networking

Autonomous fleet management
client/server architecture
pointmultipoint networking

Sensor integration
GPS/INS blending
redundancy
For more information, check out the DragonFly
UAV Project web page.
ALGORITHMS
FOR COMPUTING LOW RANK
MATRICES
S. Boyd, H. Hindi,
M. Fazel
Several important problems arising in
control system analysis and design, such as reduced order controller synthesis,
involve minimizing the rank of a matrix variable subject to linear matrix
inequality (LMI) constraints. Except in some special cases, solving this
rank minimization problem (globally) is very difficult.
Previously, we had investigated the trace
heuristic for solving matrix rank minimization problems. We provided new
theoretical insights into the technique, extended it to handle problems
with nonsquare matrices and applied it to the problem of minimum order
system realization.
In our most recent research, we have investigated
the logdet heuristic, which can refine solutions obtained by the trace
heuristic. We have extended this technique to handle nonsquare matrices
and demonstrated its effectiveness on further applications, namely loworder
controller design, Hankel matrix rank minimization, as well as problems
from other fields such as statistics, molecular biology and economics.
CONTROL
OVER NETWORKS
S. Boyd, L. Xiao,
M. Johansson, H. Hindi
Traditionally, the problem of allocating
communication channel resources has been treated separately from the problem
of optimizing the performance of linear systems. In this research we explore
the notion of doing both allocation and optimization simultaneously. We
consider a linear system, such as a controller or estimator, in which several
signals are transmitted over communication channels with bit rate limitations.
We focus on finding the allocation of communication resources such as transmission
powers, bandwidths, or timeslot fractions, that yields optimal system
performance.
Assuming conventional uniform quantization
and a standard whitenoise model for quantization errors, we consider two
specific problems. In the first, we assume that the linear system is fixed
and address the problem of allocating communication resources (bandwidth,
power allocation, and bit rates), for various important channel models,
to optimize system performance. We observe that this problem is often convex
and hence readily solved. The second problem we consider is that of jointly
allocating communication resources and designing the linear system in order
to optimize system performance. This problem is in general not convex,
but can be solved heuristically in a way that exploits the special structure
of the communication resource allocation problems. Numerical examples show
that our approach of jointly optimizing both the system and communication
resources can have very significant benefits over the traditional approach.
LOCALIZATION
METHODS
AND APPLICATIONS IN OPTIMIZATION,
ESTIMATION
AND CONTROL
S. Boyd, L. Xiao,
M. Johansson, H. Hindi
In the last meeting, we presented a technique,
MVEbased pruning, which made polyhedral estimation feasible in practice.
The MVEbased pruning was used to overcome the main stumbling block in
polyhedral estimation, which is keeping the size of the polyhedral description
from growing without bound. The technique involved computing the Maximum
Volume Ellipsoid (MVE) contained in the polyhedron, and then ranking all
the faces of the polyhedron with respect to the MVE metric, and pruning
off faces whose MVE ranking was beyond a certain threshold.
In our most recent research, we have shown
how the MVE framework can be easily extended to handle the problem of distributed
active sensing. In this problem, a base station can send information and
receive measurements from a large number of reconfigurable sensors, deployed
in a field. The goal is to estimate the location of a target moving in
the field, by coordinating the sensors in such a way that the sensors can
(a) reconfigure themselves to provide effective measurements; (b) decide
whether their measurement is likely to make a significant improvement to
the current estimate of the target. This is known to be a hard problem,
which is very difficult to solve exactly.
Once again, the MVE approach provided
an effective heuristic for solving this problem. The base station broadcasts
to the sensors the MVE associated with the current best estimate of the
target, and the sensors reconfigure themselves so that their measurements
can make the best possible reduction in the MVE. They decide to actually
make the measurement only if the measurement would substantially reduce
MVE. In this way the sensors coordinate, conserve power and bandwidth,
and avoid detection. This technique was shown to work very well on a number
of examples, and could easily handle scenarios with sensors themselves
moving and multiple targets.
DISCRETE
REACHABILITY
D. Dill, H. Sipma,
M. Colon
For a high dimensional cell network example,
we constructed a discrete model that preserved the relevant properties
of the continuous model and we proved eventual stability for a planar configuration
of an arbitrary number of cells. The ranking function, a discrete analogue
of a Lyapunov function, that witnesses stability provides an upper bound
on the number of times cells may change differentiation before they stabilize.
We are currently investigating how this result can be generalized and how
a ranking function for a discrete model can be related to a Lyapunov function
for the corresponding continuous system.
PROGRESS
IN DISTRIBUTED ASYNCHRONOUS CONTROL

Study Group (with
Mikael Johansson)
Aim

To build up a common
background in asynchronous and distributed control

To see what has been
done, what part of the theory applies to our problem, and what needs to
be done
Form

Lectures and guided
readings

Seven meetings, FebruaryApril
2000

Additional invited lectures

Course Outline

Introduction: successful
examples

Asynchronous/Distributed
Computations: models of asynchronicity, convergence results for distributed
iterations, example  power control in mobile phones

Distributed Control
of Largescale Systems: interaction measures and weak interconnections,
stability of interconnected systems, time scales and hierarchies

Optimal Distributed
Control: Witsenhausen's counter example and signaling, team decision theory,
information structures and information value, information structure in
IHVS

Models of Communication:
communication protocols, dynamic models for communication, random latency,
packet drops, periodic schedules

Control of Systems with
Time Delays: jumplinear systems, stochastic stability and optimal control,
the Smith predictor, control of network traffic

Limited Communication
Control: coding for control, quantization, minimizing network traffic,
optimal schedules for shared access

Theoretic algorithms for finding the safe
regions of a hybrid system's state space and for synthesizing the least
restrictive safe control law for that system are detailed in "A Game Theoretic
Approach to Controller Design for Hybrid Systems" (Claire Tomlin, John
Lygeros, and Shankar Sastry, Proc. IEEE, July 2000).

Our current focus is on designing practical
implementations of these algorithms. Among the objectives:

Computing numerically stable solutions to
the HamiltonJacobiBellman partial differential equations describing the
reachable regions of the continuous state space of nonlinear hybrid systems.

Mitigating the exponential growth in storage
and operations required to solve the HJB equations in higher dimensions
(Bellman's "curse of dimensionality").

Determining automatically safe and unsafe
switching rules (for moving between discrete states in the hybrid system)
based on continuous reachability results.