MIT Reports to the President 1994-95

Laboratory for Information and Decision Systems

The Laboratory for Information and Decision Systems (LIDS) is an interdepartmental research laboratory of the Massachusetts Institute of Technology. Its staff includes faculty members, full-time research scientists, postdoctoral fellows, graduate research assistants, and support personnel. 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, and control. In doing this, it explicitly recognizes the interdependence of these fields and the fundamental role that computers and computation play in this research. The Laboratory is conducting basic theoretical studies in communication and control and is committed to advancing the state of knowledge in technologically important areas.

As an interdepartmental laboratory, LIDS reports to the Acting Dean of the School of Engineering, Professor John B. Vander Sande. The Co-Directors of the laboratory are Robert G. Gallager, Fujitsu Professor of Electrical Engineering, and Sanjoy K. Mitter, Professor of Electrical Engineering.

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.

Fifteen faculty members, several research staff members, and approximately 65 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 National Science Foundation, NASA, the University Research Initiative Program (Army Research Office), Advanced Research Projects Agency (ARPA), Siemens, IBM, C.S. Draper Laboratory, the Office of Naval Research, and the Air Force Office of Scientific Research.


Automatic Target Recognition

Professor Alan Willsky, Dr. Hamid Krim, and Professor Clem Karl from Boston University (an MIT research affiliate) have initiated a significant research effort in automatic target recognition. The increasing demand for resolution in Synthetic Aperture Radar (SAR) requires highly sophisticated new methods at both the theoretical and experimental levels. Analysis and evaluation of some new algorithms using statistical techniques with notions from mathematical analysis have been successfully wed and used to identify/classify features that play a central role in the recognition step.

Wireless Sensors

Professor Trott, together with Professors Sodini, Schlecht, Chandrakasan, and Lee in the Microsystems Technology Laboratory, has begun work on a low-power wireless sensor, a project newly-funded through ARPA. The goal of the communication-related aspect of the project is to characterize the interface between technological and information-theoretic constraints on power consumption. This characterization will help guide the construction of a communication device that operates efficiently over a wide range of powers and bit rates.

Photonic Networks and Data Fusion

Professors Robert Gallager, Sanjoy Mitter, Dimitri Bertsekas, John Tsitsiklis, and Drs. Steve Finn and Hamid Krim have initiated a major project investigating the use of heterogeneous networks, particularly optical networks, in large scale distributed fusion problems. This will provide an important application area for the testbed constructed by the consortium on wide band, all-optical networks. It also presents a challenge to the architectures needed to meet quality of service requirements in large distributed systems operating over internetworks of heterogeneous networks. Finally, it provides a focus for work on routing, congestion control, and image fusion and compression. The work is funded by ARO.

Robust Control in Intelligent Manufacturing of Material

This is a new application area led by Professor Dahleh and his students. By utilizing feedback, a process for developing material such as semi-conductor films can be controlled to meet accurate specifications with only simplified models of the process. This research is being conducted in collaboration with local industry.

Identification and Adaptive Control

Determining the fundamental limitations and capabilities of identification and adaptive control has become an active area of research carried out by Professors Munther Dahleh, John Tsitsiklis, Sanjoy Mitter, and their students. This newly-initiated research program draws upon areas such as information-based complexity theory and computational learning theory, as well as upon the theory of robust control. It aims at developing a deterministic theory for system identification that can directly deal with finite data.

Neural Networks, Dynamic Programming, and Reinforcement Learning

The field of neural networks has experienced a dramatic growth leading to a broad range of commercial applications in many industries. In most applications, neural networks are employed as a powerful function approximation tool used to solve problems of pattern recognition, nonlinear time series analysis, fault detection, system identification, and process control. In the last few years, a new and exciting application of neural networks has emerged due to a convergence of several ideas from the fields of artificial intelligence, cognitive science, learning theory, and the classical methodology of stochastic dynamic programming. This is the field of "reinforcement learning." It deals with systems that learn how to make good decisions by observing their own behavior and that have built-in mechanisms for improving their actions through a reinforcement mechanism. Reinforcement learning has the potential of addressing problems that were thought to be intractable due to either the "curse of dimensionality" or the "curse of modeling." These problems involve multidimensional complex systems that, although easy to simulate, are difficult to model exactly and to analyze. Thus, there is a broad variety of important problems in many critical areas of national importance such as logistics, manufacturing, communications, and defense that can be addressed in this way. Investigations into the theoretical and practical aspects of this methodology and its applications are conducted by Professors Bertsekas and Tsitisiklis and their students.


Consortium on Wideband All Optical Networks

Researchers from LIDS, RLE, Lincoln Laboratories, and Digital Equipment Corporation have been collaborating for the last several years in developing a universal, wide area, wide band, all optical network. Current funding for the research is provided by ARPA. The goal of the consortium is to pursue research and development on optical technologies, architecture, and application interfaces required for a scalable national or international hierarchical network including local, metropolitan area, and wide area levels. An operational test bed is now in place and a node has been installed at LIDS. The current research in this area is focused on extending the channel speeds of the current wavelength division multiplexing implementation to 10 Gbps., on constructing a soliton based TDM local area network, and on developing the architecture for the wide area level. Professor Gallager, Dr, Steve Finn, and a number of their graduate students are involved in this research.

Multiresolution Statistical Signal Processing

Over the last few years, the multiresolution models on trees that Prof. Willsky and researchers at INRIA (France) have developed have received tremendous international attention from the research community. Prof. Willsky, Dr. Krim, Prof. Karl from BU (also research affiliate at MIT), and their students have successfully applied this framework to dramatically reduce high computational complexity and greatly improve performance in a wide array of problems ranging from remote sensing in oceanography to image segmentation and classification in SAR imaging.

Medical Imaging, Tomography and Inverse Problems

The interest in imaging in general and medical applications in particular has greatly grown over the last few years. Professor Willsky and Professor Karl from Boston University and their students have used to great advantage the inherent multiscale features in images to progressively retrieve significant cues important for enhancement, identification/classification, and ultimately diagnosis. This multiscale framework further provides one with tremendous computational advantages for image reconstruction known for its high computational demand. Their work is referenced in numerous journals and has received international attention for its innovative ideas and provision of a novel, fresh look at a very important problem.

Information Transfer and Retrieval

Research on information transfer and retrieval focuses on making interaction with computer-based information systems easier and more effective for human users. This research is supervised by Mr. Richard S. Marcus. A current project involves the development and testing of an expert computer retrieval assistant that makes searching a quantified science rather than an informal art through proper structuring of, and operations on, verbal descriptions of database objects. These objectives are to be obtained through such semi-automated techniques as : (1) derivation of a conceptual formulation of a user's problem and its translation into an initial search strategy; (2) ranking by estimated relevance of documents retrieved thereby; and (3) analysis of user relevance feedback to estimate number of relevant documents not yet received and reformulation of the search strategy to retrieve those missing nuggets. Experiments with a precursor to the expert system have already demonstrated retrieval effectiveness in terms of relevant documents found,equivalent to that achievable by a human information specialist acting as a search assistant. Partly based on this research, a series of operational and retrieval assistant systems have been developed and a new object-oriented expert system with a graphic user interface is now being tested.

Wireless Communication

Research in the communications area, carried out by Professors Gallager and Trott and their students, has focused on four areas: determining fundamental limits on communication over time-varying channels, coding techniques that approach capacity, the use of multiple antennas to improve communication efficiency, and network issues. Progress has been made in all three areas. For example, it has been demonstrated that complex coding can be combined with suboptimal decoding in such a way as to improve the performance of current voice-band modems by over 1dB with essentially no increase in implementation complexity. As another example, it has been shown that for coherent CDMA systems, the multipath can be measured well enough to employ the multiaccess stripping predicted by information theory. This work is supported by NSF, ARO, and Motorola.

Control of Hybrid Systems

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 Dr. Michael Branicky and Professor Vivek Borkar, a visitor from the Indian Institute of Science. Numerical methods for the dynamic programming inequalities arising out of the optimality conditions for these systems has also been developed.

Perceptual Systems and Machine Learning

Problems of speech recognition (speaker-independent), handwritten character recognition (on and off-line), and robust vision system design have turned out to be much more difficult than originally thought, owing to the richness and variability of the data and the resulting complexity of the problem of representation. Moreover, the precise characterization of similarity between objects poses major challenges. Professor Sanjoy K. Mitter and his students have recently proposed a new paradigm for pattern recognition, where primary emphasis has been placed on representation. These ideas are being tested in the domains of speech recognition, character recognition, and image analysis. Inspired by the work of Grenander, this new approach emphasizes multiscale representation, deformation of templates, and the role of missing data. In the case of character recognition, the problem is cast in an information theory framework, where special emphasis is placed on channel-modelling and joint source-channel decoding. A much more difficult situation arises in a noisy environment. In a general sense, recognition is viewed as representation at a suitably abstract level, bypassing such issues as feature extraction and segmentation.

Data Communication Networks

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 and local networks, both high speed and low speed networks, and both point-to-point and broadcast channels are of concern. One of the major topics of current interest is how to meet quality of service requirements at the internet layer through the diverse types of services that can be provided by highly heterogeneous underlying networks. The growth of both high speed optical networks and low speed wireless networks is making the problem critical. Another topic is finding the fundamental tradeoffs between fairness (i.e., multiple quality of service guarantees) and efficiency in high latency networks.

Three-Dimensional Structure Determination

Problems of three-dimensional chemical structure determination provide several test-bed problems for three-dimensional random-field estimation which are simultaneously of great intrinsic importance. Solution of these problems is crucial to an understanding of natural biological molecules and for engineering of novel newly modified molecules - catalysts for industrial processes, drugs, and so forth. Furthermore, this is currently a field of intense interest in chemistry and biology with many eager collaborators within MIT. Finally, the understanding developed by studying these three-dimensional problems will transfer to other three-dimensional problems such as signal processing for sequence of images and atmospheric/oceanographic/seismic sensing with detailed, and therefore three-dimensional, models. To address these problems, a research program involving Professors Mitter and Willsky is ongoing.

Estimation, Statistical Signal Processing, and Inverse Problems

A variety of stochastic estimation, analysis, and signal processing problems are being studied by Professors Sanjoy Mitter, Alan Willsky, William Karl and their students. Theoretical studies are conducted in the areas of estimation algorithms for spatially distributed random processes, nonlinear filtering, relationships among filtering problems in scattering theory, and the analysis of large-scale systems subject to a variety of very rare events. Complementing this theoretical research are more applied projects, including the design of algorithms for detecting and compensating for sensor or actuator failure, and the development of model-based signal processing

algorithms. The specific signal processing problems include the detection and identification of objects observed in synthetic aperture radar and laser radar imaging systems, the processing and assimilation of extremely large oceanographic data sets, the analysis and inversion of spatially-distributed geophysical data, the fusion multimodal data sets, image processing and understanding, and computational vision.

Multivariable Robust and Adaptive Control

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 a re being carried out by Professor Michael Athans, Professor Munther Dahleh, Professor Sanjoy Mitter, Professor Gunther Stein, 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 design control systems that can address general performance objectives for various classes of uncertainty. 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, and automative control systems.

Deterministic and Stochastic Nonlinear Dynamical Systems

The theory of nonlinear systems, both deterministic and stochastic, has developed rapidly over the last ten years. There is increasing interest in deterministic nonlinear control and various problems of adaptive control which lead to problems of nonlinear control. In the context of stochastic dynamical systems, problems of the qualitative behavior of such systems under different time-scales are of great interest. Recent work on nonlinear filtering has shown a relationship to infinite-dimensional, bilinear systems, and there is increasing interest in the understanding of qualitative behavior of nonlinear filters for large and small time intervals. Finally, research is under way on the subject of control of discrete-event systems. Various investigations in this area are being conducted by Professors Athans, Mitter, Tsitsiklis, Verghese, Willsky, and their students.

Theory and Algorithms for Optimization

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 communications networks, control theory, power systems, computer-aided manufacturing, and other areas. Currently, in addition to traditional subjects in nonlinear and dynamic programming, there is emphasis on solution of large scale problems involving network flows as well as in the application of decomposition methods. The thrust is two-fold: first, to find ways to handle the typically huge number of constraints; second, to explore the use of distributed and parallel processing to reduce the computation time needed to solve a problem and to economize on information transfer from remote collection points to a computation center. This gives rise to fundamental issues involving the synchronization of computation and communication that are as yet only partially resolved. Professors Bertsekas and Tsitsiklis and their students perform this work.

System Reliability and Risk Management

Research on risk assessment and management is carried out in many MIT departments and laboratories. At LIDS there is interest in describing the reliability of complex systems in terms of what is known about the reliability of their components. Professor Alvin Drake has supervised research on the development of models and algorithms for studying the manner in which uncertainties about component reliabilities are reflected in uncertainty about systems reliability. The primary area of application has been to low probability, high consequence risks in nuclear reactor safety. Professor Drake is also concerned with probability assessment, particularly the quantification of expert judgment. A current project is detailed probabilistic analysis of the sequence of tests used to screen donated blood for the presence of AIDS-associated antibodies.

Center for Intelligent Control 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 Colloquium and Seminar Series included: Professor Venkat Anantharam, University oif California/Berkeley; Professor Hanfu Chen, Chinese Academy of Sciences; John Doyle, California Institute of Technology; Frederic C. Gey, Data Archivist and Assistant Director of University of California Data Archives, Berkeley; Professor Alexandre Megretski, Iowa State University; Professor R. Narasimha, Jawaharal Nehru Center for Advanced Scientific Research; Dr. Bernard Picinbono, Ecole Superiure d'Electricite; Professor Peter Ramadge, Princeton University; Dr. Alex Sherstinsky; Dr. Jaroslaw Sobieski, NASA Langley; and Dr. Richard S. Sutton of GTE, Inc.


Visitors to the Laboratory for Information and Decision Systems included: Dr. Vivek Borkar , Professor of Electrical Engineering, Indian Institute of Science; Professor Peter Ramadge, Princeton University; Professor N. Viswanadham, Professor of Computer Science, Department of Computer Science, Bangalore, India; Dr. Charles Rohrs of Tellabs.


Professor Amos Lapidoth has been appointed to the LIDS faculty.

Professor Mitchell Trott received an NSF Young Investigator Award from 1994-1999

Dr. Hamid Krim will serve as member of the technical committee of the IEEE International Symposium on Time-Frequency and Time-Scale Analysis to be held in Paris, France.

Professor Sanjoy K. Mitter gave a plenary address at the Indian Science Congress held in Calcutta, India in January 1995. He also gave a plenary lecture at the International Conference on Information Science and Control held at the Chinese University of Hong Kong in June 1995.

Professor Michael Athans received the Richard E. Bellman Award for his contributions in the field of Control.

Professor Gallager gave a plenary address at the Third ORSA Telecommunications Conference in Boca Raton, Florida in March 1995, and a plenary address at the 1995 IEEE Information Theory Workshop on information theory, multiaccess, and queueing in April 1995.

Gunter Stein was elected a Member of the National Academy of Engineering.

Diana Dabby was named recipient of an award for Best Poster Presentation at the International SIAM Conference on Application of Dynamical Systems. Her work was entitled "Musical Variations from a Chaotic Mapping." She was also asked by Encyclopedia Brittannica to contribute an article based on musical variations for the Yearbook of Science and the Future.

MIT Reports to the President 1994-95