The mathematical and computational engine which we are developing is that of hierarchical, hybrid control systems: discrete state models are used at the highest level to model the large mode spaces in the system, and the lowest level incorporates distributed sensing and control, asynchronous receipt and processing of information, and multiple objective functions.

We are focusing the first and major part of our research in developing a computationally efficient hybrid system interface between the discrete-state system abstraction and the continuous-state subsystems, which will be built using level set techniques (Tomlin), and approximation techniques based on semidefinite progra mming (Boyd) and state reduction techniques (Dill, Sipma).

We are developing a run-time environment to support and validate this interface, which we have designed using the real-time operating system, QNX. The run-time environment is used to control the Stanford DragonFly UAV Project. This application utilizes our generic client/server architecture backbone. Our client/server architecture provides "publish and subscribe" methodology by utilizing QNX specific message passing and network transparent operations.

Our second research thrust focuses on asynchronous control theory. This research direction has two directions:

• 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 time-stamped 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 time-slot 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
peer-peer networking
• Autonomous fleet management
client/server architecture
point-multipoint 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 log-det 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 low-order 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 time-slot fractions, that yields optimal system performance.
Assuming conventional uniform quantization and a standard white-noise 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, MVE-based pruning, which made polyhedral estimation feasible in practice. The MVE-based 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, February-April 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 Large-scale 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: jump-linear 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
 

ANALYSIS AND SYNTHESIS OF SAFE CONTROLLERS FOR HYBRID SYSTEMS

• 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 Hamilton-Jacobi-Bellman 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.