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 many research scientists from various parts of the world visit the laboratory to participate in its research programs.
The 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 architecting and analysis of large-scale systems such as sensor networks. 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 issues on 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. The center resides administratively within LIDS.
Twenty faculty members, several research staff and graduate students are presently associated with the Laboratory. LIDS currently has approximately 100 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 Cambridge University-MIT Alliance, the Defense Advanced Research Projects Agency (DARPA), Draper Laboratory, HP, Intel, Lockheed Sanders, Lucent-Bell-Labs, Merrill Lynch, Pierce, Fenner, and Smith, Inc., Motorola University Partnerships in Research, the Multiple University Research Initiative Program (MURI), the National Aeronautics and Space Administration (NASA), the National Science Foundation (NSF), the National Reconnaissance Office (NRO), the Office of Naval Research (ONR), Siemens AG, Tellabs, Inc., and the Walsin-Lihwa Corporation.
The current research activities of the laboratory cover a wide range of theoretical and applied areas in systems, communications, control and signal processing.
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. Wide-area and local-area networks, high-speed and low-speed networks, and 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, media access control protocols, routing in wireless and satellite 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, Vincent Chan, Robert G. Gallager, Muriel Medard, Eytan Modiano, Vahid Tarokh, John Tsitsiklis, Drs. John Chapin, Steven G. Finn, Charles Rohr, Milica Stojanovic, Peter Young, and their students are conducting this research.
During the last year, Professors Vincent Chan, Robert Gallager, Eytan Modiano participated in 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 feature 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 was successfully completed and a test network is deployed in eastern Massachusetts, with 10 Gbps access rate for users and well over a Tbps capacity. We have also connected this test network and others around the country to form SUPERNET a prototype for the Next Generation Internet. Because of the interdisciplinary nature of the research, LIDS is able to partner with members of Laboratory for Computer Science (Dr. David Clark), Lincoln Laboratory, AT&T, Cabletron, JDS Fitel, and Nortel.
Professor Eytan Modiano continues to work on an NSF grant to study mechanisms for providing optical bypass in the Next Generation Internet (NGI). The goal of the research is to use Wavelength Division Multiplexing (WDM) technology together with novel algorithms to reduce the size, cost and complexity of electronic switches and routers in the network leading to a dramatic increase in the traffic capacity that can be supported by the NGI. A new DARPA Grant on future optical network architectures has also been initiated this year. New collaborations with Lucent Bell Labs have also taken place.
Professor Muriel Medard is working on issues of reliability and robustness of backbone and access networks. Her first project is in the area of probabilistic analysis of optical network robustness as part of an AFOSR University Research Initiative (URI) with Stanford, University of Illinois, and Caltech. The work in this area considers robustness and security of all large network systems such as backbone communication networks and power grids. Other MIT researchers on this URI project are Professors George Verghese and Bernard Lesieutre.
Professor Medard is also working on reliability of access networks. She is the MIT member of a recent NSF Information Technology Research (ITR) with the University of Illinois in the area of robust optical local and metropolitan area networks. In particular, this project considers the use of course unit of measure (UOM) and limited signal-to-noise ratios (SNRs) in architecting robust networks.
Satellite Communications and Networking
The overall goals and objectives of this research addresses architecture designs for efficient data communications over low earth orbiting satellites (LEOS) (and other more generalized satellite systems) and especially when they are interconnected with terrestrial fiber and wireless systems to form a heterogeneous global Internet. There are three main components to this research:
- 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; and
- Efficient congestion control algorithms at the transport and network layers for an integrated satellite/terrestrial network.
During the past year, research on the techniques for adaptive power and modulation control continued. We have been able to provide exact solutions for system performance gains, as a function of the speeds of the dynamics of rain events. The results look very promising for some simple form of power and rate control. To quantify the potential performance gains of optimum spot beam scheduling for bursty data users, we are assessing the fundamental capacity limit of a multiple spot beam antenna system against proposed and currently operational satellite systems. We found the performance of the current system designs very far away from their maximum potential and thus are suffering from extreme inefficiencies in the utilization of precious satellite resources. We have also began to look at optimum scheduling algorithms for multiple beam systems, coupled with efficient power management of space-borne multiple beam transmitters and receivers.
Initial work on routing congestion control over heterogeneous satellite and fiber networks has also begun. We feel this is a very rich area yet to be fully explored. Significant performance gains with the right algorithms are likely. Professors Vincent W. S. Chan, Eytan Modiano, John Tsitsiklis, Drs. Milica Stojanovic, Steve Finn, and Charles Rohr and their students are conducting this research.
Space Relay Networks
In the last six months we initiated a study on the preferred constellation topology of the space backbone. Based on coverage of space-borne users alone, the minimum number of satellites in the backbone constellation can be as small as 12 for LEO's, six for medium-earth orbiting satellites (MEO's) and the usual three for geostationary earth orbiting satellites (GEO's).
The fact that the crosslinks are reconfigurable via pointing and establishing new links between satellites allows a new paradigm in the architecture of the physical network topology. We believe reconfiguration of connection topologies permits much more efficient use of crosslink assets, especially in cases with a few data sinks, and thus may lead to significant cost savings for the complete system.
We also did a mini-study to reach a baseline understanding of current traditional space-qualified processors and commercial processors. It confirms the common believe that rad-hard processors are at least one order of magnitude slower or approximately 7-10 years behind commercial processors. This suggests our view of replenishable-networked space-borne processors may lead to significant improvement of computation power in space. We have begun to look at the architecture of a networked processing system in space and the associated problem of task scheduling.
We continue to look at efficient message routing in space and confirmed that with optimum algorithms, significant performance advantage can be realized over conventional static routing approaches. Moreover, for the case of a large number of bursty lower rate users, such as unattended sensors, trying to gain access to the relay backbone, we have created a new multiple access technique that will greatly improve the efficiency of resource (e.g., communication channels) utilization of the satellites.
Finally, we believe there will be the need to send critical and time-sensitive messages to users in the field and to data processing and storage centers with a high degree of delivery guarantees. Part of the transport can touch commercial and defense networks that are not robust to natural breakage or attacks. Thus, we have proposed a technique to send critical messages over unreliable networks via spatial diversity coding.
Professor Muriel Medard is working in the area of capacity and stability of coded packetized multiple-access channels with students at MIT and with Professor Steven Meyer of the University of Illinois Urbana Champaign and Professor Andrea Goldsmith of Stanford. In particular, this research establishes the capacity of such channels and examines trade-offs between energy and delay. This research allows the un-coordinated access in satellite networks of multiple users without requiring total performance in the event of a packet collision. She is also developing with students an emulator; using code-division multiple-access (CDMA) standards of a practical implementation of such coded multiple-access channels.
Professors Vincent W. S. Chan, Robert Gallager, Eytan Modiano, Muriel Medard, Drs. John Chapin, Steve Finn, Charles Rohrs and Peter Young, and their students are conducting this research.
Communication Under Channel Uncertainty
Professor Medard has been investigating several issues in the area of wireless communications over uncertain channels. In collaboration with Professor R. Srikant at the University of Illinois Urbana-Champaign, she has investigated the effect of unequal channel knowledge at the sender and receiver. In particular, they have developed bounds to assess the effectiveness of applying techniques designed for certain idealized channel models to more channels with more detailed models. In collaboration with Professor Andrea J. Goldsmith of Stanford, she has investigated the capacity of time-varying channel with sender and receiver side information, in particular for channels with perfect side information but significant inter-symbol interference, for which no capacity formulas existed. In collaboration with Dr. Ibraham Abou-Faycal of Vanu Inc. and Professor Madhow of UCSB, she is working on the use of an adaptive modulator without feedback in which the sender adapts to the quality of the receiving channel measurement as well as the channel strength. This technique increases capacity by up to 30 percent without expressly supplemented energy and without requiring real time computation.
Codes On Graphs and Iterative Decoding
Sae-Young Chung completed his work under Professor G. David Forney, Jr. on graphs and iterative decoding algorithms. In joint work with Richardson and Urbanke, he devised optimization algorithms that were able to produce codes that could approach the Shannon limit within 0.0045 dB, with implementable decoding algorithms
Professor Forney was an editor of the February 2001 special issue of the Institute of Electrical and Electronics Engineers (IEEE) Transactions on Information Theory on Codes on Graphs and Iterative Decoding. He also co-organized a Workshop on Capacity-Approaching Codes, Inference on Graphs, and Statistical Physics and the International Centre for Theoretical Physics in Trieste, Italy in May 2001. His current research interests include making connections between codes on graphs and their iterative decoding algorithms and methods of statistical physics.
Professor Muriel Medard in collaboration with Professor Rolf Koetter of the University of Illinois Urbana Champaign is working on an algebraic description of codes on graphs for data transmission over networks. All routing over a network can be described as a code over that network. Moreover, network capacity in error-free networking can be significantly enhanced through the use of codes over these networks. The research by Professors Koetter and Medard has developed a powerful new construct which when extended not only provides all the results previously obtained by graph theoretic methods, but also gives necessary and sufficient conditions for any set of connections to be feasible over a graph where we code. This research is also being extended to robustness when link nodes are permanently removed to the fundamental requirements of a network managed to recover from non-intermittent failures.
Quantum Information Theory
Yonina Eldar (Digital Signal Processing [DSP] Group), working with Professor Forney, has shown the "square-root" measurement of quantum detection theory is actually a "least-squares" measurement, from which many of its properties follow. She has also shown that there is an intimate correspondence between such measurements and the "tight frames" of wavelet and signal representation theory, which allow various quantum mechanical results to be transported to frame theory. Recent results relate to geometrically uniform measurements and frames.
Professor Vahid Tarokh together with several students, have ongoing projects in various fields including mobile communications, switching, data networks, data security, applications of information theory to vary-large-scale integration (VSLI), and free space optical communications. Specific research includes: design of multiple antenna communications systems, peak to average power reduction in wireless optical frequency division multiplexing (OFDM), capacity achieving codes for wireless communications, distributed source coding, tracking fluid policies for crossbar switches, scheduling algorithms for input queued switches, coding for reduction of energy consumption and timing in buses, space-time coding for free space optical communications, hyper-elliptic curves cryptography, and measurement of multi-input multi-output (MIMO) wireless channels in collaboration with Lincoln Laboratories.
Collaboration With Tellabs and Draper Laboratory
The Laboratory for Information and Decision Systems and Tellabs Operations, Inc., a telecommunications equipment manufacturer, and Draper Laboratory are developing a novel approach to collaborative research. In this approach, LIDS, Tellabs and Draper Laboratories 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 and Draper Lab 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 student 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.
Stochastic Systems Group
The Stochastic Systems Group (SSG) is led by Professor Alan S. Willsky, with the assistance of Research Scientist, Dr. John Fisher and Postdoctoral Researcher Dr. Mujdat Cetin. In addition the group includes 10-12 graduate students, 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 automatic target recognition (ATR), biomedical image analysis, oceanographic and hydrological data assimilation, and fusion of multi-source (e.g., acoustic and video) information. Funding for this research comes from a variety of sources, including ONR, AFOSR, ARO, Office of the Director, Defense Research and Engineering (ODDR&E) (through AFOSR, ARO, and ONR), National Institutes of Health (NIH), and NSF.
In addition to directing these research activities, Professor Willsky is very active in supporting government and, in particular, Department of Defense organizations in assessing and planning technology investments. He is a member of the Air Force Scientific Advisory Board. 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.
Multi-Resolution Statistical Signal Processing
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 synthetic aperture radar based [SAR-based] ATR, oceanography 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.
The key to this research area is the direct statistical modeling of phenomena at multiple resolutions using graphical models on trees and other graphs, 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.
Most recently we have increased our investigation on 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-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 sub optimal solutions to exact graphical models that do not have structure that allows fast optimal inference. In the past year we have had several results in this area that represent significant advances in the state of the art in inference for graphical models and in the distributed fusion of information from large collections of irregularly spaced and heterogeneous sensors. Our multiresolution methods are also a key component of a recently awarded $4.4M, five-year NSF-ITR program on large-scale data assimilation for geophysical processes which involves collaboration with MIT researchers in Civil and Environmental Engineering, Earth, Atmospheric, and Planetary Sciences, and Electrical Engineering and Computer Science. In addition, Professor Willsky has been invited to write a tutorial/survey paper on multiresolution statistical signal and image processing for the Proceedings of the IEEE.
Nonlinear and Geometric Image Analysis
During this past year we have continued 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. Our work continues to focus on 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. Our work is aims at developing first principles statistical approaches to curve evolution that deals with noise and variability in a statistically optimal way without sacrificing resolution. During this past year we have added to our suite of algorithms by developing curve evolution methods simultaneous image deblurring and segmentation as well as for the incorporation of prior statistical descriptions of the shapes of regions of interest in a way that is compatible with the curve evolution framework. This latter effort is part of our collaboration with clinicians and researchers at Brigham and Woman's Hospital toward the development of image guided therapy procedures for prostate cancer. In addition, we envision extending these efforts to examine problems of dynamically evolving curves and boundaries as part of the NSF-ITR effort mentioned previously, with the specific aim of developing radically new forms of data assimilation and prediction algorithms for geometric features such as fronts in meteorology and oceanography.
Machine Learning and Optimization Methods for Multisensor Fusion
The third component of our research program involves the development of statistically-based algorithms for the fusion of information from multiple sensors in the presence of substantial uncertainties-e.g., in the nature of the signals being sensed (e.g., acoustic signatures of unknown character), in the number of sources generating those signals, in the locations and calibration of the sensors themselves, and in the relationships among the signals being sensed by sensors of very different modalities. Our work to date has focused on the fusion of audio and video sensors, and the fusion of multiple acoustic sensors for the detection and localization of multiple sources, projects being carried out jointly with researchers in MIT's Artificial Intelligence Laboratory. Our work has already led to two invited journal papers, which are currently in progress.
Information-theoretic Methods in Image Analysis and Fusion
During this past year we have continued to increase 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 have built 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 have also used non-parametric statistics together with the concept of mutual information to develop new approaches for functional Magnetic Resonance Imagery (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). We have also used similar tools for the fusion of video and acoustic data and, in particular, for the localization of the sources of sound (e.g., human voices) in the video field of view.
Atmospheric Optical Communications
Professor Shapiro, in collaboration with Professor Chan and Dr. Wong (of the Research Laboratory of Electronics [RLE]) has been working on approaches to mitigate the effects of atmospheric turbulence on laser communications. A theoretical study of the use of space-time coding has shown that the same orthogonal-design approach that has been developed for conventional wireless communications also optimizes the pairwise probability of error for atmospheric optical communications using coherent detection. Work is presently underway to assess the capacity of direct-detection atmospheric optical communications. In conjunction with the theoretical studies, a laboratory test bed is being assembled as a prelude to performing diversity transmission experiments over outdoor paths.
Professors Munther A. Dahleh and Steve Massaquoi are interested in two problems. The first is the development of a hierarchical model of the interaction between the cerebrum and 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 electroencephalography (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 (MGH) and the Brockton V.A. Medical Center.
Substantial progress was made in the area of developing reduced-order models for the cerebellum and its interactions with the cerebrum and spinal cord. Progress has been made in utilizing these models for interpreting speed and directional information present in actual cerebellar data. This data was collected by collaborator, Dr. Timothy Ebner, from University of Minnesota.
In a parallel effort concerning modeling EEG data, Professors Dahleh and Massaquoi have developed a basic circuit that constitutes the building block of the brain. The circuit describes local and global interconnections between the different layers, and has been successful in simulating several important states of the brain. This development is quite unique and they suspect several interesting fundamental models to emerge. The work is done in collaboration with Professor Dahleh's student, Fadi Karame, Professor Steve Massaquoi, and Dr. Emery Brown (MGH). The objective of this research is to utilize such a model to classify different sleep stages while applying Anesthesia.
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), supply chain management, and communications (dynamic channel allocation). Professors Dimitri P. Bertsekas and John N. Tsitsiklis and their students perform this work.
Professor Sanjoy Mitter, Dr. 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 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 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.
During the year 2000-2001, Professor Berwick organized a new research group of professors, graduate students, and undergraduates, to probe the computational properties of Chomsky's "minimalist framework" for language. He developed a novel, stochastic-based model for learning via parameter setting, which has been applied to both speech (learning stress patterns) and syntax learning. Along with his research group, he developed the first computer implementation of Professor Ken Hale and Jay Keyser's model of the lexicon (dictionary), and has shown how to account for 75 percent of the different word order variations in language via this means. Research papers on these topics were presented at the major conferences in Artificial Intelligence and computational linguistics, leading the publication by Kluwer Academic of a book on these topics due out in November, edited by Professor Berwick.
In addition, Professor Berwick submitted a patent on a novel algorithm to assemble genes from on-line databases of gene sequence fragments, without resorting to biological methods.
Electric Power Systems
Dr Marija Ilic, together with her graduate students, post doctoral associates and international visitors, continues to work on new concepts for planning and operating electric power systems under restructuring. As it is well known from the recent California energy crisis, competitive electric power industry is not evolving as hoped. Prices are high and changeable, supply is sometimes inadequate and there are no true incentives in place for most effective technology penetration. The research group led by Dr. Ilic has performed a series of studies that should help these issues. The entire January-March 2001 MIT E-Lab Newsletter covers the contributions of her group in this area, and the relevance for the industry. More information about this research can be found online at http://web.mit.edu/energylab/www/e-lab/jan-mar01/jan-mar01.html.
It is becoming increasingly clear that the hardest questions as the power industry transforms itself concern complex system interactions, in which technical, economic and regulatory signals interact under various uncertainties and at non-uniform rates. At present, this group is concentrating its efforts on engineering design of energy markets, which recognizes these complex interactions.
More generally, graduate level courses offered by Dr. Ilic as well as the overall research direction, recognize the need for modeling, analysis and design which begin to relate engineering processes to the economic and regulatory processes. As an example, Dr Ilic just co-authored a book with her former doctoral student Dr Petter Skantze, entitled A Fundamental Approach to Valuation, Hedging and Speculation in Competitive Electricity Market. The book is published by Kluwer Academic Publishers, to appear in August 2001. The authors reevaluate a number of key premises underlying modern finance theory, including the arbitrage pricing theory in markets for near non-storable commodities, such as electricity.
Multivariable And Robust Control
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.
New areas of application of robust control theory are now emerging at LIDS, including the real-time, agile guidance of single and multiple Unmanned Aerial Vehicles (UAV) as well as vehicle anticollision problems arising in Air Traffic Control. Some of these concepts are implemented and tested on small helicopter systems. Professors Eric Feron and Steve Massaquoi are beginning a collaboration regarding the brain's internal representation of external world dynamics.
Feedback Control Using Approximate Dynamic Programming
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.
Identification And Adaptive Control
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. Professor 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.
Control In Presence Of Communications Constraints
Professor Sanjoy Mitter in collaboration with Professor Vivek Borkar (Tata Institute of Fundamental Research, India), Dr. 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. The recent completed theses of Drs. Anant Sahai and Sekhar Tatikonda demonstrate significant progress in this important subject.
Interference on Graphs, Coding and Statistical Mechanics
Recent research on turbo coding, decoding of low-density parity check codes and statistical mechanisms of disordered systems has shown that there are deep connections between those subjects. Professor Sanjoy Mitter in collaboration with Dr. Nigel Newton has been conducting research on various aspects of these problems.
Unmanned Air Vehicles
Professors Dahleh and Feron with their students, in collaboration with Draper Laboratories have been working on developing control architectures for unmanned vehicles. They have derived an architecture for the autonomous controller that enables the vehicle to perform agile maneuvers. The basis for this architecture is the derivation of a "Robust Hybrid Automaton". This automaton describes a rich set of controlled trajectories that can be attained by the vehicle as well as the control necessary to transition between these trajectories. The robustness analysis of this dynamical description gives rise to a new and exciting class of robustness analysis problems that has not been looked at in the literature. They have developed a complete simulation/animation environment and their software (based on the above architecture) is now completely integrated on board Draper's small vehicle project (expected to fly sometime next year). They are also building a small helicopter. A recent development in this problem is deriving efficient algorithms for performing real-time motion planning (contrasted from path planning where the vehicle dynamics are not taken into account) in a cluttered environment. These algorithms are based on randomization techniques performed on the manifold on which the dynamics evolve. Student, Emilio Frazzoli presented these results at the control and decision conference in December 2000, and the response was extremely positive. This research entails the development of a hierarchical control system that replaces the human pilot in order to perform agile maneuvers.
Professor John Deyst, with sponsorship from the Draper Laboratory, LIDS researchers and students are developing new guidance and control methods for operation of intelligent unmanned air vehicles (UAVs). This work addresses the coordinated action of groups of UAVs that operate cooperatively to accomplish complex tasks. Such coordinated action is required to accomplish tasks that are impossible, or would take excessively long periods of time, for a single vehicle to complete. Significant issues being addressed are the safe and effective flight of UAVs near each other, including rendezvous and docking of one vehicle with another. This capability is of particular significance for resupply of one vehicle by another, so as to allow sustained operation near some desired location, which might be some distance from a user. Coordinated flight is also essential for integrating various kinds of information sensed by many vehicles simultaneously. The operational needs of this class of systems pose particularly stringent requirements on various aspects of vehicle guidance and control.
Speakers in the LIDS Colloquium and Seminar Series included: Dr. Thomas Kailath, Stanford University; Dr. Robert Kosut, Vice President, Systems and Control Division, SC Solutions; Dr. David Tse, University of California at Berkeley; Dr. Vijay Balasubramanian, University of Pensylvania; Dr. Michel Geomans, MIT; Dr. Muriel Medard, MIT; Dr. Chuanyi Ji, Rensselaer Polytechnic Institute; Dr. Aleksandar Kavcic, Harvard University; Dr. Thomas Marzetta, Bell Laboratories, Lucent Technologies; Dr. Mustafa Khammash, Iowa State University; Dr. Stephan ten Brink, Bell Laboratories, Lucent Technologies; Dr. Lotfi Zadeh, UC Berkeley; Dr. Daniel Liberzon, University of Illinois at Urbana-Champaign; Dr. Seth Lloyd, MIT; Dr. Andrea Goldsmith, Stanford University; Dr. Nancy Lynch, MIT; Dr. Adam Arkin, E.O. Lawrence Berkeley National Laboratory, UC Berkeley; Dr. Francesco Bullo, University of Illinois at Urbana-Champaign; Dr. James C. Anderson, Lincoln Laboratory, MIT; Dr. Mor Harchol-Balter, Carnegie Mellon.
Visitors to the Laboratory for Information and Decision Systems included: Dr. Nigel Newton, Essex University, Colchester, England; Professor Vevek Borkar, Tata Institute of Technology, India; Professor Manolis Christodoulou, Technical University of Crete, Greece; Professor V. J. Chandra, University of Pennsylvania; Professor Chuanyi Ji, Rensselaer Polytechnic Institute, Troy, NY; Dr. Ulf Jonsson, Royal Institute of Technology, Stockholm, Sweden; Dr. Franchesco Morandin, Scuola Normale Superiore, Italy; and Dr. George Moustakides, University of Patros, Greece.
Professor Dimitri Bertsekas received the 2001 American Automatic Control Council (AACC) John R. Ragazzini Education Award and the 2000 Greek National Award for Operations Research. He was also elected to the United States National Academy of Engineering.
Professor Berwick was awarded a Fellowship as a Visiting Professor to the Princeton Institute for Advanced Studies.
Professor David Forney was inducted into the Mass Telecom Hall of Fame.
Professor Sanjoy Mitter was the recipient of the IEEE Control Systems Award, Plenary speaker at the Conference on Optimal Control and Partial Differential Equations, and Visiting Professor at the Institute for Information Theory and Digital Communications, ETH, Zurich.
Vahid Tarokh was awarded the Alan T. Waterman Prize from the National Science Foundation.
More information about the Laboratory for Information and Decision Systems can be found online at http://justice.mit.edu/.