MIT Reports to the President 1998-99

LABORATORY FOR INFORMATION AND DECISION SYSTEMS

The Laboratory for Information and Decision Systems (LIDS) is an interdepartmental laboratory for research and education in systems, communication, and control. It is staffed by faculty members, research scientists, postdoctoral fellows and graduate students drawn principally from the Department of Electrical Engineering and Computer Science, as well as the Department of Aeronautics and Astronautics, Mechanical Engineering and the Sloan School of Management. Undergraduate students participate in the research program of the Laboratory through the Undergraduate Research Opportunities Program (UROP). Every year several research scientists from various parts of the world visit the Laboratory to participate in its research programs.

The fundamental research goal of the Laboratory is to advance the field of systems, communication, control, and signal processing. In doing this, it explicitly recognizes the interdependence of these fields and the fundamental role that computers and computation play in this research. Specifically, the work conducted at LIDS falls into several areas. Research in the area of communications, networks and systems includes fundamental work on data networks, information theory and communication theory. Systems research includes satellite communications, wireless communication, optical communications and networks. Research in the area of estimation and signal processing includes work on multi-resolution statistical signal processing, robust estimation in the presence of non-normal noise, and the analysis of large scale systems. Research in the area of control ranges from theoretical issues such as robustness, aggregation, and adaptive control, to the construction of a computer-aided design environment for the control of unmanned air vehicles, the use of neural networks for approximating optimal controller designs and system identification and the study of natural neuro-control systems. Research in the area of algorithms includes analytical and computational methods for solving broad classes of optimization problems arising in engineering and operations research, and for applications in communication networks, control theory, power systems, computer-aided manufacturing, as well as such topics as resource allocation and scheduling under uncertainty and neuro-dynamic programming. Research on perceptual systems and machine learning includes the problems of speaker-independent speech recognition, on- and off-line handwritten character recognition.

As an interdepartmental laboratory, LIDS reports to the Dean of the School of Engineering, Thomas L. Magnanti and The Director of the laboratory is Professor Vincent W. S. Chan.

The Center for Intelligent Control Systems, an inter-university, interdisciplinary research center operated by a consortium of Brown University, Harvard University, and MIT, resides administratively within LIDS.

Twenty faculty members, several research staff members, and approximately 80 graduate students are presently associated with the Laboratory and the Center. Currently, the Laboratory and the Center provide some 50 research assistantships to graduate students. Undergraduate students also participate in research and thesis activities. A number of postdoctoral and visiting appointments are made.

Financial support is provided by the Air Force Office of Scientific Research (AFOSR), the Army Research Office (ARO), the DefenseD Advanced Research Projects Agency (DARPA), C.S. Draper Laboratory, Motorola University Partnerships in Research, the National Science Foundation (NSF), the Office of Naval Research (ONR), Siemens AG, Tellabs, Inc., and the University Research Initiative Program (ARO).

The current research activities of the laboratory cover a wide range of theoretical and applied areas in systems, communications, control and signal processing. These areas include the following:

During the last year, Professors Vincent Chan, Bob Gallager, Eytan Modiano and Sunny Siu participated in the initiation of a ‘Next Generation Internet' program funded by DARPA. The focus of the program is to design and prototype the next generation local and metropolitan area access network with orders (up to 4) of magnitude increase in data rate, but at the same time decrease the cost of delivery per bit by approximately the same amount. The network will use multiple wavelengths (colors) to increase capacity and optical devices for routing and switching. One interesting architectural features of the network will be an option for the user of the network to set up direct end-to-end optical flows for future applications with very large transactions (Gigabytes and beyond). The architecture design will culminate in a test network deployed in eastern Massachusetts (LIDS as one of the nodes), with 10 Gbps access rate for users and well over a Tbps capacity. In the future DARPA will connect this test network and others around the country to form SUPERNET as a prototype for the Next Generatin Internet. Because of the interdisciplinary nature of the research, LIDS is able to partner with members of LCS (Dr. David Clark), Lincoln Laboratory, AT&T, Cabletron, JDS Fitel and Nortel.

Professors Vincent Chan, Edward Crawley and John Tsitsiklis and Steven Finn have been working on a new research project on satellite data communications and networking. A DARPA funded Next Generation Internet Program is started with Motorola and Teledesic as research partners.

In the past, commercial satellite communication systems have always been used for trunking purposes, whereas military satellite systems have been providing direct individual user access for decades. With the launching of several new satellite communications systems such as the Iridium system by Motorola and the Globalstar system by Loral, the commercial sector has started a major new trend of providing economic and ubiquitous communication services to mobile users and users with small earth terminals. There are several proposed systems that will focus on supporting data communications. Inevitably, in the future, these satellite systems will be interconnected among themselves and with other terrestrially based networks to form a multi-purpose integrated heterogeneous network of global extent. With the goal towards a commercially based network, the integration of disparate communication modalities of satellite systems, fiber and wireless networks presents the usual challenges of internetworking such as the creation of gateway functions, routing and QoS negotiations across different network domains and network management and control. With this space/terrestrial network multiplely connected, new and interesting dimensions open up for the consideration of efficient routing between users and new and more effective congestion control algorithms. The added property of rich path diversity also permits applications with more robust requirements when exploited properly. The proposed research addresses architecture designs for efficient data communications over an interconnected heterogeneous LEOS/terrestrial-wired-wireless network. We have been concentrating on three main themes that we have identified as areas where significant impact to network performance can be made when efficient designs are applied:

• Adaptive power and rate control techniques for the LEOS systems over time-varying satellite channels to achieve greatly improved (an order of magnitude) data throughputs.
• Efficient routing algorithms over a time-varying integrated and heterogeneous global network for maximum resource utilization, especially the space segments
• Efficient congestion control algorithms at the transport and network layers for an integrated satellite/terrestrial network

Professor G. David Forney, Jr. and several students and colleagues have been studying codes defined on graphs and iterative decoding algorithms, such as turbo codes, low-density parity-check codes, and tail-biting codes.

Some of these codes have been shown to be able to approach the Shannon limit remarkably closely, using implementable decoding algorithms. However, understanding of the construction of such codes and of the behavior of these decoding algorithms is still in a fairly primitive state.

In many applications, e.g., mobile wireless communication and military communication in the presence of jamming, the channel characteristic and the nature of the noise are unknown in the design stage of the communication link. For such applications it is imperative to design robust receivers and codes that allow reliable communication over each of a wide family of channels. To this end Professor Amos Lapidoth is studying universal receivers that do not require precise knowledge of the channel law, and yet perform asymptotically as well as the best receivers that could have been designed had the channel been known in advance. Professor Lapidoth is also studying the ultimate bounds on the rates at which reliable communication can be guaranteed over a channel that is only known to belong to some given family of channels.

The major objective of this work is to develop the scientific base needed to design data communication networks that are efficient, robust, and architecturally clean. Both wide-area and local-area networks, both high-speed and low-speed networks, and both point-to-point and broadcast communication channels are of concern. Some specific topics of current interest are power control, the capacity of wireless channels with parallel relays, splitting and successive decoding for wireless networks, routing in wireless networks, quality of service control, diverse traffic mixes, failure recovery, topological design, and the use of pricing as a mechanism for efficient resource allocation. Professors Dimitri P. Bertsekas, Robert G. Gallager, Dr. Steven G. Finn, and their students are conducting this research.

Professor Robert G. Gallager together with several students, have ongoing projects in mobile communication aimed at developing a cohesive theory and set of insights for wireless multiple access. Specific research includes the capacity of fading channels, the transmission of bursty sources over a shared time-varying channel, transmitter power allocation across many cells, and capacity improvements through joint decoding.

The Laboratory for Information and Decision Systems and Tellabs Operations, Inc., a telecommunications equipment manufacturer, are developing a novel approach to collaborative research. In this approach, LIDS and Tellabs integrate industrial research interests within MIT's research and educational environment. The key difference between this new model of collaboration and traditional approaches is the focus on human resources as the primary enabler. Toward this end, LIDS provides Tellabs with access to faculty, students, visitors, facilities, and infrastructure support, while Tellabs dedicates resident corporate research positions to the effort, assuming responsibility both for co-advising students research and for technology transfer as an internal corporate process. LIDS benefits from the persistent presence of industrial researchers, and Tellabs benefits from the leveraging of LIDS's staff. LIDS and Tellabs have been jointly working on this new research model for three years and look forward to its growth and refinement.

The Stochastic Systems Group (SSG) is led by Prof. Alan S. Willsky, with the assistance of Research Scientist, Dr. John Fisher. In addition the group includes 10-12 graduate students, several postdoctoral researchers (currently 2), visitors, and participants from other groups within LIDS and from other MIT laboratories and departments. The general focus of research within SSG is on the development of statistically-based algorithms and methodologies for complex problems of information extraction from signals, images, and other sources of data. The work in the group extends from basic mathematical theory to specific areas of application. Current applications include SAR-based automatic target recognition (ATR), biomedical image analysis, oceanographic and hydrological data assimilation, and situation modeling for complex phenomena (such as military situations). Funding for this research comes from a variety of sources, including ONR, AFOSR,, ARO, DARPA, ODDR&E (through AFOSR and ONR), NIH, and NSF.

In addition to directing these research activities, Prof. Willsky is very active in supporting government and, in particular, DoD organizations in assessing and planning technology investments. In particular, he is a member of the Air Force Scientific Advisory Board and also was co-chair of an ONR panel on the role of probability and statistics in command and control.

Each of the following research areas being pursued within SSG involves both theoretical development as well as applied studies to the application areas mentioned previously:

For some time now (and in part sparked by the flurry of activity associated with the wavelet transform) there has been considerable interest in algorithms for processing signals or images at multiple resolutions. SSG has played a leadership role in developing a statistical basis for such multiresolution processing that has had a significant impact as evidenced not only by the applications pursued within the group (in SAR-based ATR, ocenaography and hydrology, and computer vision, for example) but also by the increasing use of our methodology by others in fields ranging from biomedical imaging to chemical engineering to helioseismology.

The key to this research area is the direct statistical modeling of phenomena at multiple resolutions using graphical models known as trees, in which each level on a tree corresponds to a particular resolution. We have developed very efficient algorithms for estimation, data fusion, and other image analysis tasks using these models and have also demonstrated, primarily through example and application, that a wide variety of real phenomena and applications can be captured within this framework. Because of this success, our current and planned efforts involve expanding the domain of applicability of our methodology, both by pursuing additional applications and by developing tools for constructing multiresolution models needed as the basis for applying our results. In particular, we have recently had several important new results that allow us much more easily to construct multiresolution models for complex phenomena, and we are continuing to develop and exploit this model construction theory.

Most recently we have begun investigating how we can exploit our methodology for problems involving much more complex graphical models as arise in military command and control or in problems of monitoring complex systems, a problem of great national concern because of its relevance to making critical national infrastructure secure. In particular our approach to modeling takes a very different perspective from most work on graphical models--in particular, we focus explicitly on developing accurate but approximate models that have structure that leads to very fast optimal algorithms, rather than most work on graphical models that involves trying to find tractable suboptimal solutions to exact graphical models that do not have structure that allows fast optimal inference. Our work in image processing makes clear that our alternative approach can lead to very different and in many cases vastly superior algorithms, and we are now exploring extensions of this approach to graphical models arising in other applications than image processing.

A second and closely related part of SSG research on multidimensional statistical signal processing and estimation focuses on the development of efficient and highly parallelizable algorithms for multidimensional estimation. Essentially all multidimensional estimation problems involve potentially explosive computational demands, caused both by working in multiple spatial dimensions and by the compounding lack of an obvious notion of causality and hence recursion (in contrast to traditional time series analysis). Our work on multiresolution processing can be viewed as one part of our effort to overcome these computational obstacles. In addition, in the past year we have developed several new methods involving the novel blending of statistical estimation with numerical methods for solving partial differential equations. The result is a contribution both to numerical algorithms more generally and also a method for constructing fast estimation algorithms that can be applied to a variety of very challenging large-scale applications.

In the area of space-time processes, a key contribution of our work has been the recognition that the major computational problem in space-time filtering, namely that of calculating error covariance functions for predicted spatial fields and using these co-variances in the incorporation of new measurements, can be viewed as a problem of statistical modeling of random fields. This perspective leads to a new way in which assimilate date for large, dynamic problems such as arise in remote sensing applications. In the past year we have developed two methods that exploit these ideas and are in the process of demonstrating their utility in dynamic oceanographic data assimilation.

In the past few years we have increased our efforts in the area of nonlinear/non-Gaussian image analysis, including the explicit estimation/extraction of geometric information such as object boundaries and segmentation. There are three distinct components of this work. The first involves a new method for so-called anisotropic diffusion of images. The idea behind methods of this type is that diffusing an image corresponds to smoothing it, which can reduce noise but also blur edges. This suggests using nonlinear diffusions that diffuse selectively away from areas of high contrast. In our work we have developed what can be viewed as a limiting case of this concept, leading to algorithms that are very efficient to implement and that explicitly segment images. The resulting segmentations are extremely robust to noise and outliers and have a number of attractive statistical properties. We have demonstrated the efficacy of this approach on applications ranging from SAR image segmentation to the extraction of regions of interest in noisy ultrasound images.

A second related area of work involves the development of statistically-based curve evolution algorithms. Such algorithms involve explicitly defining and dynamically evolving curves in ways that lead to accurate and efficient segmentation of images. Methods of this type that had been developed by others had a number of very attractive features, including the fact that they provided seamless ways in which a curve could separate into multiple curves or merge from several disjoint curves to a single curve, allowing automatic and easy segmentation of multiple regions of interest (e.g., multiple blood cells in a microscopic image). However, previously developed methods either were very sensitive to noise or required ad hoc preprocessing to remove noise but that also reduced the resolution of the resulting segmentation. In our work we have developed a first principles statistical approach to curve evolution that deals with noise and variability in a statistically optimal way without sacrificing resolution. The results obtained to date are quite stunning in terms of their accuracy and robustness, and we are pursuing both applications of these methods (at present in biomedical image analysis and military surveillance) and the further development of this methodology.

Finally, we have recently initiated an effort to develop non-Gaussian multiresolution models for images that capture more faithfully the scale-to-scale variability observed in real images. In particular, real images have what are commonly referred to has "heavy-tailed" statistical behavior which is not captured by Gaussian distributions. At this point we have developed a simple non-Gaussian model for dependencies across scale and have shown that this model can capture behavior that is observed in real images. This provides the starting point both for further modeling studies and for new, nonlinear image analysis algorithms that exploit these new models.

Over the past year we have greatly increased our efforts in developing and using methods of non-parametric statistics for a variety of very complex image analysis and fusion problems. In particular, in our work on SAR-based ATR we are building non-parametric probabilistic models that capture statistically significant differences in the scattering response of different types of scatterers and then using these models to exploit these differences for feature extraction, enhancement, and recognition. We are also using non-parametric statistics together with the concept of mutual information to develop new approaches for functional MRI studies in which we wish to correlate particular experimental protocols (e.g., a patient squeezes and then releases a ball) with brain activity so that mapping of brain activity to function can be performed. This work is interesting in that it involves fusing information of very different modalities (force applied to a ball and Magnetic Resonance Imagery), and we are also using similar ideas in order to develop new approaches for fusing imagery and audio inputs.

A unifying framework and the so-called scale space analysis with the wavelet and wavelet-packet-based denoising. The robustness achieved in a newly introduced class of edge enhancement algorithms has been shown theoretically as well as experimentally, and the results are extremely promising.

Professor Alan S. Willsky and his students are engaged in research on the estimation and reconstruction of geometric features in multidimensional data. Interest in this area is motivated by the need to develop radically different methods for problems in which the focus is on geometric rather than pixel-by-pixel features. Major contributions of this work include the development of a methodology for the reconstruction of 3-D objects from their 2-D silhouettes, and the tracking of objects with time-varying shape. This methodology has been tested in practice, resulting in a new approach to temporal imaging of the heart given very low-dose (and thus low SNR) imagery. New approaches have also been developed to the characterization and parameterization of geometrically-described random fields and to the direct extraction of geometric information from tomographic data providing new algorithms in computational geometry that directly accommodate, and hence are robust to, uncertainties and errors in the observed data. These methods are applied to such problems as the estimation and tracking of geophysical and oceanic features from sparse data, the nondestructive evaluation of materials, the detection and quantification of atherosclerotic plaques, and the evaluation of cardiac structure and function. Extension and fusion of these methods with multiresolution approaches promise to allow multiscale descriptions of object geometry.

Professor Jeffrey H. Shapiro stepped down from his position as Associate Head of the Department of Electrical Engineering and Computer Science (EECS) on January 16, 1999, and joined the Laboratory for Information and Decision Systems (LIDS). The work of Professor Shapiro and his students has two principal foci: quantum optics and radar-based automatic target recognition (ATR). The quantum optics research is done in collaboration with Dr. Ngai C. Wong, and resides within the Research Laboratory of Electronics, of which Prof. Shapiro is also a member. Professor Shapiro's radar research is part of several joint programs, involving other MIT faculty (Profs. Mitter and Willsky) as well as staff from MIT Lincoln Laboratory (Dr. Thomas Green). This portion of Prof. Shapiro's research has moved to LIDS from its prior home in RLE. The following paragraphs give a brief overview of recent accomplishments in Prof. Shapiro's ATR research.

Professor Shapiro and his students have been working to develop a statistically optimum approach for doing model-based object recognition using low-resolution, noise-degraded laser radar range images. The object recognition system consists of preprocessing, segmentation, feature extraction and alignment/scoring steps. Encouraging preliminary performance results have been obtained from our object recognition system using laser radar data from the MIT Lincoln Laboratory Infrared Airborne Radar (IRAR) data release, together with 3-D CAD models which account for the possible military targets that may have been present on the site imaged by the laser radar.

Professor Shapiro and his students have also been working on a physics-based approach to target detection and recognition using synthetic aperture radars (SARs). Theoretical models for stripmap-mode and spotlight-mode polarimetric radar returns for targets and clutter using physical optics theory have been established. Using these models adaptive-resolution processors and performance analysis has been completed for the detection of single-component and multi-component targets in a SAR image.

Professor Alexandre Megretski and his students are working on the development of new methods of nonlinear system analysis, and application of these techniques in various control systems, (flight control, firm control, animation control, hybrid systems, etc.). The work involves a broad spectrum of system-theoretic topics including modelling, identification, stability analysis, and optimization. One important objective is to learn how simplifications necessarily made in nonlinear system modelling affect the validity of nonlinear control design.

Professor Dahleh and Massaquoi are interested in two problems. The first is the development of a hierarchical model of the cerebellum that is anatomically justified that can explain two-dimensional arm motions. The second problem is deriving a multi-scale, multi-resolution model that explains EEG data, with specific interests in Anesthesia. These projects are in collaboration with various laboratories/departments at MIT as well as the Massachusetts General Hospital.

This project focuses on analytical and computational methods for solving broad classes of optimization problems arising in engineering and operations research, as well as for applications in communication networks, control theory, power systems, computer-aided manufacturing, and other areas. Currently, in addition to traditional subjects in nonlinear and dynamic programming, there is an emphasis on the solution of large-scale problems involving network flows, as well as in the application of decomposition methods. Professors Dimitri P. Bertsekas and John N. Tsitsiklis and their students perform this work.

Problems of sequential decision making under uncertainty are all pervasive; for example, they arise in the contexts of communication networks, manufacturing systems, logistics, and in the control of nonlinear dynamical systems. In theory, such problems can be addressed using dynamic programming techniques; in practice, however, only problems with a moderately-sized state space can be handled. This research effort deals with the application of neural networks and other approximation and interpolation methodologies to overcome the curse of dimensionality of real-world stochastic control problems. The objectives driving this research are twofold. First, to develop the theoretical foundations and improve the understanding of such methods, using a combination of tools from approximation theory, dynamic programming, and stochastic algorithms. Second, to use these methods for solving some large-scale problems of practical interest. Application areas being currently investigated include problems in logistics (resource scheduling and assignment), finance (pricing of high-dimensional derivative instruments, dynamic portfolio management in the presence of risk constraints), and communications (dynamic channel allocation). Professors Dimitri P. Bertsekas and John N. Tsitsiklis and their students perform this work.

Sanjoy Mitter, Stefano Casadei and their collaborators have been working on various aspects of Perception and Recognition. Perception and recognition consist in recovering useful information about the environment from sensed data and prior knowledge about the real world and the sensors. Artificial systems designed to carry out this task are yet much inferior to biological systems, largely due to the size and intricacy of the knowledge required to carry out reliable inference in unrestricted and uncertain domains. For instance, in visual perception, several factors contribute to render the problem difficult: clutter, occlusion, and variability of the objects in the scene. The basic engineering principle of decomposing a complex task into simpler and independent tasks is difficult to apply to perception and recognition due to the extremely complicated and yet unknown pattern of interdependency among the many "acts of perception" involved. For instance the recognition of an occluded chair in a cluttered office environment is highly dependent on the interpretation of its subparts, the other objects near to it and the overall scene of which it is part.

What are the components, which are involved in perception and recognition? What architecture should these components to be organized into? How does one minimize the interdependence of these components? How should uncertainty be represented? How does one acquire and represent the knowledge about the real-world and the sensors? Several projects are being undertaken to find answers to these questions.

• Work in character recognition initiated several years ago is currently being extended to handwriting recognition and signature verification.
• A hierarchical approach to contour estimation is being developed by adding more general models of object contours to the hierarchy. The current edge model being worked on includes illusory contours and curve singularities (corners and junctions) but is limited to convex closed contours.
• Non conventional probabilistic approaches, such as De Finetti's theory of probability, are being explored to represent uncertainty without resorting to the introduction of artificial priors. In this context, the relationship between set-based models of uncertainty and the probabilistic approach are being studied.
• A new computational theory for the recognition of occluded deformable templates in a cluttered scene has led to efficient algorithms with guaranteed performance in terms of localization errors and time complexity. Currently, this approach has been applied to features consisting of points in the plane and to affine deformations. Future work will seek to generalize these assumptions.
• Early recognition of moving ground targets from an approaching platform is an important task for the military. To enhance the performance of existing systems, it is necessary to combine information from multiple frames, which contain the target at different resolutions. This project is still at an early stage and initial efforts have focused on the incorporation of continuity and smoothness constraints of the relative motion of the target with respect to the camera by means of a geodesic approach.

The systematic design of multiple-input, multiple-output systems, using a unified time-domain and frequency-domain framework to meet accurate performance in the presence of plant and input uncertainty is an extremely active research area in the Laboratory. Various theoretical and applied studies are being carried out by Professors, Munther A. Dahleh, Gunter Stein, Steve Massaquoi and their students. Theoretical research deals with issues of robustness, aggregation, and adaptive control. The aim of the research is to derive a computer-aided design environment for the design of control systems which can address general performance objectives for various classes of uncertainty. Furthermore, new results on the robustness of nonlinear feedback systems, using feedback linearization, have been obtained for unstructured uncertainty model errors. Recent application-oriented studies include the control of large space structures, helicopters, submarine control systems, issues of integrated flight

control, control of chemical processes and distillation columns, automotive control systems, and the modeling and analysis of biological control systems.

In related research, the quick maturation of robustness concepts when applied to linear systems has led Professor Eric Feron to redirect his efforts in this area towards other classes of systems. In particular, Professor Feron is now interested in systematic analysis and design methods for the robust nonlinear control of systems subject to "hard" non-linearities such as actuators with position and rate saturations, as well as other nonlinear systems. The main tools for robust stability and performance analysis are Lyapunov's stability theory as well as the theory of approximation of difficult, non-convex problems via positive semidefinite programming. The current applications of this research include Unmanned Aerial Vehicle (UAV) control as well as vehicle anticollision problems arising in Air Traffic Control.

Feedback controllers for nonlinear systems are often driven by potential (Lyapunov) functions, whereby the controller at each step steers the system in a direction of decrease of the potential function. The optimal cost-to-go function that results from dynamic programming formulations of control problems is a suitable such Lyapunov function, except that it may be difficult to compute. This research investigates whether recent approximate dynamic programming methods, that rely extensively on simulation and neural network training, can lead to a viable methodology for designing Lyapunov functions and controllers for nonlinear feedback systems. This research is carried out by Professors Munther A. Dahleh and John N. Tsitsiklis, and their students.

Determining the fundamental limitations and capabilities of identification and adaptive control is an active area of research, carried out by Professors Munther A. Dahleh, John N. Tsitsiklis, and their students. This research program draws upon areas such as information-based complexity theory and computational learning theory, as well as upon the theory of robust control. One aim of this research is to develop a theory that combines both system identification and robust control within the same framework, in which a controller that meets given performance specifications can be designed based on finite noisy data. Issues studied include the representation of uncertainty in both noise and model, design of experiments, sample and computational complexity, as well as implementation of optimal algorithms.

Problems in systems and control theory are of varying degrees of difficulty, ranging from polynomial-time solvable to undecidable. Prof. Tsitsiklis and coworkers have been using tools from theoretical computer science (theory of computation) to characterize the intrinsic difficulty of problems in stochastic optimal control, and various stability problems for hybrid systems, saturated linear systems, and linear time-varying systems.

Sanjoy Mitter in collaboration with Vivek Borkar (Tata Inst. of Fundamental Research, India), Nicola Elia and several graduate students have been working on fundamental issues of control in the presence of communication constraints. The goal of this research is to understand the interaction between information and control in the presence of uncertainty. Development of Real-time Information Theory forms an essential part of this research topic.

Professors Dahleh and Feron with their students have been working on developing control architectures for unmanned vehicles. This research entails the development of a hierarchical control system that replaces the human pilot in order perform agile maneuvers. The group is also involved in building and demonstrating these concepts on a small helicopter.

Hybrid systems are compositions of continuous systems (described by ordinary differential equations) and discrete systems that are event-driven. A theory of optimal control of such systems, based on the theory of impulse control and piecewise-deterministic processes, has been developed by Professor Sanjoy K. Mitter in collaboration with Professor Michael Branicky, currently at Case Western Reserve University, Professor Vivek Borkar, visiting from the Indian Institute of Science, and Dr. Nicola Elia, a post-doctoral scientist. Numerical methods for the dynamic programming inequalities arising out of the optimality conditions for these systems have also been developed. Incorporation of the model in the simulation package OMULA/OMSIM has been undertaken in joint work with Prof. Astrom and his group at Lund, Sweden. Professor Mitter has been working with Professors Borkar and Chandru of the Indian Institute of Science, Bangalore on solving questions and problems in logic using mathematical programming. It is planned to unify this work with the previously mentioned work on Hybrid Systems.

The Center for Intelligent Control Systems (CICS) combines distinguished faculty from MIT, Harvard University, and Brown University in interdisciplinary research on the foundations of intelligent machines and intelligent control systems. Established in October 1986, CICS is headed by Professor Sanjoy Mitter, Director; Professor Roger Brockett, Harvard University, Associate Director; and Professor Donald McClure, Brown University, Associate Director. The research activities of the Center are loosely grouped in five areas: Signal Processing, Image Analysis, and Vision; Automatic Control; Mathematical Foundations of Machine Intelligence; Distributed Information and Control Systems; and Algorithms and Architectures. A number of outstanding graduate students are appointed Graduate Fellows. The Center also hosts several senior visitors for varying lengths of time each year.

Speakers in the LIDS Colloquium and Seminar Series included: Dr. Jan Willems, University of Groningen, Dr. Arthur Berger, Lucent Technologies, Dr. Sergei Treil, Michigan State University, Dr. Alberto Isidori, Washington University in St. Louis, Dr. Silvio Micali, MIT LCS, Dr. Michael Tanner, Univesity of California-Santa Cruz, Dr. Toby Berger, Cornell, Dr. Dan Spielman, MIT Math Dept., Dr. Munther Dahleh, MIT LIDS, Dr. Eric Feron, MIT Aero-Astro/ LIDS, Dr. Hari Balakrishnan, MIT LCS, Dr. Ruediger Urbanke and Dr. Tom Richardson, Lucent Technologies, Dr. Victor Solo, Macquarie University, Sydney Australia & NMR Center, MGH, Harvard University, Dr. Madhu Sudan, MIT LCS, Dr. John Doyle, Caltech, Dr. Tammer Basar, University of Illinois, Dr. Andrew Viterbi, QualComm, Inc. , Dr. Joe Traub, Columbia, and Dr. P.S. Krishnaprasad, University of Maryland.

Visitors to the Laboratory for Information and Decision Systems included: Dr. Arthur Berger, Lucent Technologies, Dr, Ernst Dickmanns, Universitat Der Bundeswehr, Munchen, Germany, Dr. Michael Tanner, University of California- Santa Cruz, and Dr. Sergei Treil, Michigan State University.

At the EECS Department's Annual Spring Party, Department Head John Guttag announced Prof. Shapiro's Appointment as Julius A. Stratton Professor of Electrical Engineering, effective 1 July 1999 Professor Vincent W. S. Chan was appointment Joan and Irwin M. Jacobs Professor of Electrical Engineering and Computer Science and Aeronautics and Astronautics.

Robert G. Gallager was awarded the 1999 Harvey Prize Award from the American Friends of the Technion.

Professor Sanjoy K. Mitter received the IEEE Control Systems Award.

Professor John Tsitsiklis was elected Fellow of the IEEE.

Professor Eric Feron was awarded an ONR Young Investigator Award in 1999.

Vincent Chan

MIT Reports to the President 1998-99