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 Dean of the School of Engineering, Professor Robert A. Brown. The Co-Directors of the laboratory are Professors Robert G. Gallager, Sanjoy K. Mitter, and John N. Tsitsiklis (Acting Co-Director).
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.
To complement a recently initiated effort in Automatic Target Recognition useful for synthetic aperture Radar and such, Prof. Willsky and Dr. Krim have started a new research initiative in Representation theory for recognition which accounts for physical morphology of target objects. The theoretical effort is paralleled with its direct application on many aspects of their other research.
A joint project with Microsystems Technology Laboratory (MTL), supported by ARPA, involves constructing a low power wireless sensor that operates efficiently over a wide range of powers and bit rates, from 1 Mb/s for full-motion video to 1 b/s for temperature sensing. One goal of the project is to characterize how constraints on device technology interact with information theoretic limits to determine the best architecture for low power communication. As an example, for indoor line-of-sight communication, radiated RF power is swamped by the power cost of computation. This work is being carried out by Professor Trott and his students in LIDS together with Professors Sodini, Schlecht, Chandrakasan, Lee and their students in MTL.
Modern advances in computation have greatly relaxed the complexity constraints that apply to error-correction codes designed for voice-band modems, cable modems, and satellite channels. This has fueled the demand for powerful coding techniques and design methodologies which closely approach the information-theoretic upper bounds on performance. Professors Trott and Lapidoth, together with Dr. G. David Forney, Jr. of Motorola, have begun to develop new methods for constructing and evaluating high-performance codes and decoding methods. Research has also begun on the design universal codes that perform optimally over a broad class of channels. This work is supported by NSF and Motorola.
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.
Hybrid systems are those containing mixtures of logic and continuous dynamics, e.g., digital computers and subsystems modeled as finite automata, coupled with controllers and plants modeled by differential or difference equations. A mathematical model of such systems, based on interacting collections of dynamical systems has been developed. This model is consistent with the theory of optimal control of hybrid systems developed in our lab by Professor Sanjoy K. Mitter in collaboration with Dr. Michael Branicky and Professor Vivek Borkar, a visitor from the Indian Institute of Science. Further, since this model builds on the rich theory of dynamical systems, extensions of that theory have been developed. For example, we have extended Lyapunov's stability theory to hybrid systems by developing a theory of multiple Lyapunov functions. Possible applications include programmable logic controllers and power-switching electronics. These analysis tools were also the basis of a collaboration begun with Dr. Branicky and Professor Nancy Lynch of MIT's Laboratory for Computer Science on the formal verification of hybrid systems. LIDS' Professor Dahleh and doctoral candidate Jorge Goncalves have also shown interest in this effort. Finally, Dr. Branicky was recently a visitor at the Department of Automatic Control, Lund Institute of Technology, Sweden (DAC), where he created some tools for the simulation of hybrid systems. These tools were developed within existing DAC software (Omola/Omsim) and will be ported to LIDS computers for future simulation/experimentation work.
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. Professor Sanjoy K. Mitter and his team have recently worked on two different approaches to compute useful representations. The top-down approach, inspired by the work of Grenander, is based on deformable templates and has been applied to character recognition. The bottom-up or compositional approach emphasizes computational efficiency and has been applied to edge detection. Shared by both approaches is the idea that uncertainties and ambiguities must be represented properly and resolved in the right context. This leads naturally to multi-layered representations where the lower levels contain local and data-driven information and the higher levels contain more global and goal-oriented information. Current research efforts attempt to exploit the synergies of the bottom-up and top-down approaches by using feedback mechanisms.
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.
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.
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. This work is conducted by Professors Bertsekas, Gallager, Dr. Finn and their students.
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. Applications involving non-stationary time series will be considered (e.g., feature extraction from EEG Data).
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.
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 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, classification in SAR imaging.
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 Professor Michael Athans, Professor Munther Dahleh, Professor Sanjoy Mitter, Professor Gunter 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 automotive control systems.
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 Tsitsiklis and their students.
This research aims at developing systematic, computable methods for designing nonlinear controllers for classes of nonlinear systems that are provably stabilizing in the presence of uncertainty. Part of the research focuses on characterizing classes of nonlinear systems that, on one hand, cover a wide range of applications and on the other hand, are amenable to computations. This research is carried out by Profs Munther Dahleh, Mike Athans, Gunter Stein and Sanjoy Mitter.
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.
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 Prof. Kolodziejski from EECS and local industry.
The interest in imaging in general and medical applications in particular has greatly grown over the last few years. Prof. Willsky, Dr. Krim 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 gotten international attention, for its innovative ideas and provision of a novel fresh look at what is considered a very important problem.
Research in the communications area, carried out by Professors Gallager, Lapidoth, and Trott and their students, has focused on four areas: determining fundamental limits on communication over time-varying channels, the use of multiple antennas to improve communication efficiency, joint source and channel coding, and network issues. Progress has been made in all four areas. For example, in audio and video broadcast applications, it has been shown that an integrated data compression and channel coding scheme can outperform any system employing separate compression and coding. As another example, it has been demonstrated that spreading in frequency, using uniform energy allocation over all degrees of freedom, is only beneficial up to a certain limit. This work is supported by the NSF and the ARO.
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.
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: Dr. Jorma Rissanen of the IBM Research Division, Prof. Vwani Roychowdhury of Purdue University , Prof. Allen Tannenbaum of the University of Minnesota, Prof. Karl J. Aström of Lund Institute, Prof. Jean-Jacques Slotine of MIT, Dr. Alan Weiss of Bell Labs, Prof. Roger Brockett of Harvard University, Mr. John T. Preston of MIT, Prof. Frank Kelly of the University of Cambridge, UK, Dr. Irwin Mark Jacobs of Qualcomm, Prof. Jaime Peraire of MIT, Prof. Steven Shreve of Carnegie Mellon University, and Dr. Paul Warbos of the NSF.
Visitors to the Laboratory for Information and Decision Systems included: Professor Karl Aström of the Lund Institute of Technology, Sweden; Dr. Vivek Borkar , Professor of Electrical Engineering, Indian Institute of Science; Professor Meir Feder, Tel Aviv University, Israel; Dr. James Mills, Tellabs Operations, Indiana; Professor James Modestino, RPI, New York; Dr. Charles Rohrs, Tellabs, Indiana; and Professor Allen Tannenbaum, Electrical Engineering, University of Minnesota.
Professor Michael Athans received an honorary doctorate from the National Technical University of Athens, Greece on July 1, 1996, "for outstanding contributions to teaching and research in the field of control theory and systems engineering." He was also elected to the Board of Governors of the IEEE Control Systems Society for the three-year period 1997-2000.
Alexander Megretski has been appointed to the LIDS faculty.
Professor Sanjoy Mitter presented an invited talk on Problems and Issues in Image Processing at the International Congress on Industrial and Applied Mathematics in Hamburg, Germany, July, 1995. He also presented a plenary lecture, "The Role of Hidden Markov Models and Nonlinear Filtering in Signal Analysis" at the August, 1995 Conference on Signal Processing and Communication at the Indian Institute of Science, Bangalore, India.
Robert G. Gallager
Sanjoy K. Mitter
MIT Reports to the President 1995-96