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, the Department of Mechanical Engineering, and the Sloan School of Management. Undergraduate students participate in the research program of the laboratory through the Undergraduate Research Opportunities Program. 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 fields of systems, communication, control and signal processing. In doing this, it explicitly recognizes the interdependence of these fields and the fundamental role that mathematics, computers, and computation play in this research. Specifically, the work conducted at LIDS falls into these areas:
- Communications, networks and systems: Includes fundamental work on data networks, information theory and communication theory. Systems research includes satellite communication, wireless communication, optical communication and networks.
- 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.
- 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.
- Algorithms: Includes analytical and computational methods for solving broad classes of optimization problems arising in engineering and operations research. These methods are used for applications in communication networks, control theory, power systems, computer-aided manufacturing and neuro-dynamic programming, as well as resource allocation and scheduling under uncertainty.
- Research on perceptual systems and machine learning: Includes the problems of speaker-independent speech recognition and on- and off-line handwritten character recognition.
As an interdepartmental laboratory, LIDS reports to the dean of the School of Engineering, Thomas L. Magnanti. The director of the laboratory is Professor Vincent W. S. Chan.
Twenty faculty members, several research staff and approximately 100 graduate students are presently associated with the laboratory. Undergraduate students also participate in research and thesis activities. A number of postdoctoral and visiting appointments are made annually.
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; Lucent Bell Laboratories; Merrill Lynch; Pierce, Fenner, and Smith, Inc.; 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); Tellabs, Inc.; the Ford Motor Company; 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 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 and John Tsitsiklis, doctors Jinane Abounadi, John Chapin, Steven G. Finn, Alan Kirby, Charles Rohr, Milica Stojanovic and Peter Young, and their students are conducting this research.
Professors Chan, Gallager, and Modiano continue to work on the 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 (MAN) with an increase in data rate of up to four orders of magnitude, but at the same time to 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. New results on the use of mesh topology for MANs indicate that the cost structure of MANs is heavily dependent on the optical cross-connect technology at the switching nodes. Efficient topologies that nearly achieve fundamental bounds on performance are found, and these architectures are very different from previously used and accepted architectures. 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 a 10 Gbps access rate for users and well over a Tbps capacity. Direct user-to-user optical flow switching was demonstrated from Boston to Washington, DC. This new communication service type had been the focus of a number of press releases and interviews by the IEEE, Optical Society of America, and trade magazines. We have also connected this test network to 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 the Laboratory for Computer Science (Dr. David Clark), Lincoln Laboratory, AT&T, Cabletron, JDS Fitel, and Nortel.
Professor 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 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. New collaborations with Lucent Bell Labs have also taken place.
Professor 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, 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 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 and limited signal-to-noise ratios in architecting robust networks.
A new program sponsored by DARPA on ultra-high-reliability and performance, all-optical, local and metro area networks has been initiated by professors Chan and Modiano. The objective of this research is to use optical network technology to build a highly reliable network that services high-end applications such as aircraft control and coherent collaborative sensing. It is the expectation of the sponsor that MIT will provide architecture lead and guidance for industry contractors.
Free-Space Optical Communications
Under DARPA sponsorship, professors Chan and Shapiro and Dr. Franco Wong have undertaken an ambitious new development of high-rate and high-performance free-space optical communication systems and networks. This research, a joint venture between LIDS and the Research Laboratory of Electronics, explores diversity transmitter and receiver techniques to mitigate power fading due to atmospheric turbulence. In recent theoretical work, tight bounds on the channel capacity of shot-noise limited, multiple-input, multiple-output, direct-detection communications have been derived. Error probabilities for direct-detection diversity receivers that use optical pre-amplifiers have been obtained. In addition, this research group is optimizing higher-layer network protocols to adapt to the channel conditions to yield higher-network throughputs and faster response time. Substantial gains (>10dB) have been indicated via analysis. An experimental demonstration of such designs is underway in an open-air range between buildings at MIT.
Satellite Communications and Networking
The overall goal of this research addresses architecture designs for efficient data communications over low-earth orbiting satellites and other more generalized satellite systems, 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 satellite communication systems over time-varying satellite channels to achieve greatly improved (an order of magnitude or more) data throughputs
- Efficient routing algorithms over a time-varying integrated and heterogeneous global network for maximum resource utilization, especially the space segments
- Efficient congestion control algorithms at the transport and network layers for an integrated satellite/terrestrial network
Professors Chan, Modiano, and Tsitsiklis, doctors Stojanovic, Finn, and Rohr, and their students are conducting this research.
During the past year, the researchers in this group have provided a power control policy that is optimized according to an outage probability requirement. They have also developed a modulation selection rule designed to satisfy an outage probability requirement for a given bit error rate. They have addressed the issue of multi-beam power allocation based on traffic demands over satellite downlinks with several types of antenna schemes. Their analysis shows that the use of the parallel multi-beam scheme with optimized power splits can achieve a substantial power gain and reasonable proportional fairness. On energy-efficient routing for satellite networks, the group has studied the problem of finding an optimal policy that maximizes expected reward by deciding how much of the demand to service at a given time. This problem is modeled using a dynamic programming formulation that, results show, could produce a significantly higher expected revenue than a simple greedy algorithm.
On congestion control for hybrid networks, the group explores the interaction between the protocols at different layers. They have developed models that could be used to analyze the performance of the Transport Layer Protocol (TCP) in the presence of a lower-layer ARQ protocol and have designed an intelligent lower-layer ARQ scheme that will substantially improve the TCP's overall throughput. They have examined the optimal spare capacity replacement problem based on mesh-torus topology and have derived algorithms for routing and failure recovery that meet the lower bound on capacity requirements.
In the study on satellite system design, and specifically on capacity dimensioning and routing for hybrid satellite and terrestrial networks, the group has formulated satellite-link dimensioning and routing as a two-stage stochastic programming problem and has solved for the optimal link capacity. This will minimize the sum of satellite network investment cost for different link-cost to user-entry-rejection-cost ratios.
In addition, Professor Modiano has initiated a research program with NASA exploring interactions in space networks between protocols at different layers of the protocol stack. A particular focus of this project will be an examination of the overall network architecture across multiple layers of the network hierarchy, seeking opportunities for cross-layer optimization. Such an approach is of particular importance for NASA's space Internet because of its heterogeneous nature. It is a goal of this project to obtain an understanding of the interactions between network layers so that overall, end-to-end performance can be significantly improved.
Space Relay Networks
Professors Chan, Gallager, Modiano, and Medard, Doctors Chapin, Finn, Rohrs, and Young, and their students continue the study on the preferred constellation topology of the space backbone. Based on the analysis of cost vs. complexity of each constellation for the LEO, MEO, and GEO configurations, these researchers showed that a GEO backbone consisting of three satellites has cost-versus-complexity characteristics superior to other constellations and should be the choice for a space-borne data backbone network.
The group has begun to look at the architecture of a networked processing system in space and the associated problem of task scheduling. They decouple the processing units from the traditionally designed mission satellites, which allows processing resources to be shared across network users. This architectural concept alleviates the need for high data-rate downlinks and thus is much more cost-effective than a traditionally designed system. One aspect of using commercially available processors with minimal radiation shielding is the need to frequently replenish the processing resources approximately every one to two years. These frequent upgrades to the system ensure that the latest processor technology and software are used in space, thereby solving the present-day problem of performance-challenged, 10- to 20-year-old, space-qualified processors currently used in space.
The researchers have also continued the study of optimum scheduling algorithms for multiple-beam systems, coupled with efficient power management of space-borne, multiple-beam transmitters and receivers. In particular, they have addressed the tradeoff between serving a transmission request versus saving scarce energy for the sake of future and potentially more valuable requests. They have extended this methodology to other wireless communication settings besides satellite networks.
Finally, this research group believes there will be a 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, the group has proposed a technique to send critical messages over unreliable networks via spatial diversity coding.
Professor 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 at Urbana-Champaign and Professor Andrea Goldsmith of Stanford University. In particular, this research establishes the capacity of such channels and examines trade-offs between energy and delay. This research allows the uncoordinated access in satellite networks of multiple users without requiring total performance in the event of a packet collision. Professor Medard is also developing with students a system emulator using code-division multiple-access standards as a practical implementation of such coded, multiple-access channels.
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 at Urbana-Champaign, she has investigated the effect of unequal channel knowledge at the sender and receiver. In particular, the researchers have developed performance bounds to assess the effectiveness of applying techniques designed for certain idealized channel models to other channels with more detailed models. In collaboration with Professor Goldsmith of Stanford, Professor Medard has investigated the capacity of time-varying channels 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 Professor Madhow of the University of California, Santa Barbara and Dr. Ibrahim Abou-Faycal, 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 additional energy and without requiring real-time computation.
Codes on Graphs and Iterative Decoding
Professor G. David Forney, Jr., continues his research into codes on graphs and iterative decoding algorithms. He is preparing a paper on constraint complexity, which in some respects is more basic than state complexity, the focus of most prior literature.
Coding and Statistical Physics
Professor Forney continued to investigate connections between coding and statistical physics in collaboration with A. Barg (Lucent Bell Laboratories), M. Chiang (Stanford University), A. Montanari (of Paris, visiting professor Mitter at MIT) and J. Yedidia (Mitsubishi Research Labs, Cambridge). A paper with Barg on minimum distances and error exponents of codes for the binary symmetric channel using a large-deviation-theoretic approach has been accepted for the IEEE Transactions on Information Theory. With Montanari, this approach has been extended to general discrete memoryless channels.
Research on turbo coding, decoding of low-density parity check codes, and statistical mechanics of disordered systems has shown that there are deep connections between those subjects. Professor Mitter, in collaboration with Dr. Nigel Newton, has been conducting research on various aspects of these problems.
Professor Medard, in collaboration with Professor Ralf Koetter of the University of Illinois at 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 and to the fundamental requirements of a network whose management system can recover from non-intermittent failures.
Quantum Information Theory
Yonina Eldar (Digital Signal Processing Group), working with Professor Forney, has shown that 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 allows various quantum mechanical results to be transported to frame theory. Recent results relate to geometrically uniform measurements and frames.
Professor Tarokh, together with several students, has ongoing projects in various fields, including mobile communications, switching, data networks, data security, applications of information theory to very-large-scale integration, 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; 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 wireless channels in collaboration with Lincoln Laboratories; and measurement of an ultra-wide-band (UWB) channel in collaboration with AT&T Labs. The models Professor Tarokh developed from UWB measurements are now being adapted by FCC 15.3 as standard models for future system development and comparison of UWB systems.
Collaboration with Tellabs and Draper Laboratory
The Laboratory for Information and Decision Systems; 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 Lab 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 our partners benefit from the leveraging of LIDS's staff.
Stochastic Systems Group
The Stochastic Systems Group (SSG) is led by Professor Alan S. Willsky and currently includes one research scientist, Dr. John Fisher (joint appointment with the AI Lab), one postdoctoral researcher, Dr. Mujdat Cetin, one administrative assistant, Taylore Kelly, nine graduate students and one UROP student. The web site for this group at http://ssg.mit.edu/ describes its activities, mission, current and recent research projects, and theses and publications.
Professor Willsky has been invited to write a tutorial/survey paper for the Proceedings of the IEEE on the extensive research in multiresolution statistical modeling and processing, in which his group has had a leading role. He has continued as an active participant on the US Air Force scientific advisory board and has also taken on a role as an advisor to the National Reconnaissance Office.
Professor Willsky has been involved in three large programs: He was the MIT principal investigator of a large and recently completed MURI program (involving seven universities) on automatic target recognition. This program has been cited twice by the Air Force for excellence. He has taken over the role as principal investigator of the SensorWeb MURI program on data fusion of large arrays of microsensors, a program involving researchers at LIDS, the Artificial Intelligence Laboratory, Princeton University, and the University of Illinois. He is one of the principal investigators of a large NSF-ITR award on innovative methods for large-scale geophysical data assimilation. This is an interdisciplinary program involving faculty from LIDS, the Research Laboratory of Electronics, Earth and Planetary Sciences, and Civil and Environmental Engineering.
The SSG has been actively involved in numerous collaborations extending beyond the boundaries of LIDS. It has had substantial interactions with the AI Lab, including the computer vision and machine learning groups (professors Grimson, Freeman, and Jaakkola) and the AI Smart Room (Professor Darrell). It has growing interactions with LCS in computer graphics (Professor McMillan) and graph theory (Professor Karger). The group has had (and through the NSF-ITR program mentioned above will continue to have) substantial collaborations in data assimilation with faculty in Civil and Environmental Engineering (McLaughlin and Entekhabi) and Earth, Atmospheric and Planetary Sciences (EAPS) (Wunsch, Rizzoli, Emanuel, Hanson). It recently initiated explorations, together with Professor Michael Perrott of Microsystems Technology Laboratories, on use of its image magnification algorithms for magnification of computer-generated art.
The group also has a continuing collaboration with researchers at Brigham and Women's Hospital in the area of medical image analysis, particularly in the area of advanced algorithms for prostate image segmentation.
The research in the SSG currently focuses on three areas.
The group's research in multiresolution algorithms has resulted in powerful algorithms that are finding significant and growing use in a wide variety of disciplines, ranging from geophysical data assimilation to computer vision and image processing. In the past few years, the focus of this work has expanded to a broader class of so-called graphical models. The researchers have developed some powerful new algorithms that will have impact not only on fields mentioned previously but also in the very active fields of machine learning and coding theory. One recent graduate, Dr. Martin Wainwright, has been cited for his work in this area.
Work on robust curve evolution methods is central to the SSG's collaboration with Brigham and Women's Hospital and also to its work on computer art magnification. Recent graduate Dr. Andy Tsai has been recognized for his research in this area. In addition, through the recent NSF-ITR award, the group is exploring significant extensions of its methods to deal with space-time tracking of large coherent structures (e.g., weather fronts) in geophysical data. This work is carried out in collaboration with researchers in EAPS.
The SSG is also actively involved in machine learning and robust statistical methods for the fusion of heterogeneous sensors. This work, which includes work on the SensorWeb program and also the collaboration with the AI Smart Room project, involves developing robust and efficient algorithms for fusing data from distributed ad hoc sensor arrays in the presence of unknown or uncertain relationships among the sensors (e.g., in fusing video and audio, or in fusing audio sensors in complex reverberant environments or in the presence of uncertainties in the locations of the sensors).
Professors Munther 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 and that can explain multivariable dynamic stabilization and control. The second problem is deriving a multi-scale, multi-resolution model that explains electroencephalography (EEG) data, with specific interests in motor control, anesthesia and evaluation of cortical function and dysfunction. These projects are in collaboration with various laboratories/departments at MIT as well as the Massachusetts General Hospital (MGH). The third is the development of a circuit model of basal ganglia that describes the basal ganglia's function in both low-level control of movement speed as well as in motor programming.
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. According to collaborator Dr. Timothy Ebner of the University of Minnesota, a cerebrocerebellar control model now appears to explain observed input-output behavior as well as approximate many neural signals observed in vivo.
In a parallel effort concerning modeling EEG data, Professors Dahleh and Massaquoi have developed a basic circuit that constitutes a fundamental cerebral function module. 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 the professors expect several interesting fundamental models to emerge. The work is done in collaboration with Professor Dahleh's student, Fadi Karame and Dr. Emery Brown (MGH). The objective of this research is to utilize such a model to classify different sleep stages while applying anesthesia, detect structural and functional aberrations in the cerebrum, and ultimately gain insight into the mechanisms of cognition.
Progress has also been made in developing a unified model of basal ganglia function that interprets the structure as implementing a logical operator that enables programmed control of behavior ranging from cruising movements to cooperative interaction with the environment.
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 on the application of decomposition methods. Professors Dimitri Bertsekas and John 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 and 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; and second, to use these methods for solving some large-scale problems of practical interest. Application areas currently being 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 Bertsekas and Tsitsiklis and their students perform this work.
Fundamental Issues in Optimization
This research focuses on fundamental analytical and computational issues in (deterministic) optimization that are connected through the themes of convexity, Lagrange multipliers, and duality. The aim is to develop the core analytical issues of continuous optimization, duality, and saddle point theory using a handful of unifying principles that can be easily visualized and readily understood. As part of this effort, a new approach to Lagrange multiplier theory is being explored, based on a set of enhanced Fritz-John conditions and the notion of constraint pseudonormality. Professor Bertsekas and his students perform this work.
Supply Chain Management
Professor Tsitsiklis and his students have considered uncapacitated serial inventory systems ("supply chains") with Markov-modulated demand and Markov-modulated, stochastic, but non-overtaking leadtimes. We developed a novel approach, based on a decomposition into a collection of single-item, single-customer problems that are essentially decoupled. We have shown that this technique results in a very simple derivation of existing results (optimality of state-dependent echelon basestock policies), new and efficient computational algorithms, and several new results. We expect this general approach to lead to efficient exact or approximate solutions to various other related problems, thus advancing the state of the art. Student Alp Muharremoglu's work in this area has been cited for excellence.
Professor Sanjoy Mitter and his collaborators have been working on various aspects of perception and recognition. Perception and recognition involve 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 patterns of interdependency among the many "acts of perception" involved. For example, the recognition of an occluded chair in a cluttered office environment is highly dependent on the interpretation of its subparts, the other objects near it and the overall scene of which it is part. What are the components involved in perception and recognition? Into what architecture should these components be organized? 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.
An approach to recognition involving both top-down and bottom-up processing of images is being developed in the doctoral thesis of Maurice Chu.
A hierarchical approach to contour estimation has been developed by adding more general models of object contours to the hierarchy. The current edge model in development includes illusory contours and curve singularities (corners and junctions) but is limited to convex closed contours.
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.
Control in Presence of Communications Constraints
Professor Mitter, in collaboration with Professor Vivek Borkar (Tata Institute of Fundamental Research, India) and several graduate students, has 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 recently completed theses of doctors Anant Sahai and Sekhar Tatikonda demonstrate significant progress in this important subject.
Professor Robert C. Berwick and his students have implemented several novel models for learning based on theoretically minimal amounts of information. Children can learn the meaning of a novel word with as little as one example—often called "one-shot learning" or "fast-mapping." Professor Berwick's group has implemented this in a Bayesian framework, integrating both syntactic evidence (what other words appear in the sentence) and scene evidence (how the learner perceives or conceives the world) to acquire word-concept mappings. These models demonstrate that given a hypothesis space of possible word meanings and likelihood models of how syntactic and scene evidence differentially support hypotheses in this space, standard Bayesian analyses predict a posterior probability distribution over possible concepts.
In contrast to constraint-satisfaction-based models (which do not rule out overly general word meanings), connectionist models (which require hundreds of "epochs" and cannot model one-shot learning), or models which use only one type of evidence (typically just syntactic frames), this Bayesian approach explicitly factors prior knowledge, integrates disparate evidence, handles noise, and models a key competence of human language learners: generalization from one example.
These results were reported in the major conferences of the computational linguistics and cognitive science community during the past year.
To test the adequacy of their model, the group is developing a TheoryNet architecture that demonstrates how large numbers of English verbs may map onto particular combinations of causal schemas and that shows how each of the assigned schemas predict the range of syntactic frames in which these verbs may appear. When implemented later this year, this will be able to replace the WordNet system that is now the most widely used computational dictionary on the web. Professor Berwick and his students are currently testing this model with experimental subjects as well—both adults and children. If correct, such a model would afford tremendous improvement over brute-force "statistical" methods currently used.
Electric Power Systems and Critical Network Infrastructures
Dr. Marija Ilic, together with her graduate students, postdoctoral 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, the 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 of that work to the industry. More information about this research can be found on the web 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. Recognizing these complex interactions, the group is at present concentrating its efforts on engineering design of energy markets.
More generally, graduate level courses offered by Dr. Ilic, as well as the overall research direction, recognize the need for modeling, analysis and design that begin to relate engineering processes to economic and regulatory processes. For example, Dr. Ilic just co-authored a book with her former doctoral student Dr. Petter Skantze entitled Valuation, Hedging and Speculation in Competitive Electricity Markets: A Fundamental Approach. The book was published by Kluwer Academic Publishers 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.
Most recently, Dr. Ilic has participated in several workshops concerning security of the national infrastructures, including the electric power grid. She is beginning to develop a control engineering approach to modeling and decision-making to manage the electric power grid securely. In preparation for this major undertaking, she taught a spring 2002 course on large-scale dynamic systems, with an emphasis on identifying theoretical challenges when applying the existing knowledge to modeling and control of complex network infrastructures.
In 2002, LIDS became involved with developing safety-enhancement mechanisms for the automotive industry, under Ford sponsorship. Under the Ford-MIT alliance, Professor Eric Feron has assumed the responsibility of developing and managing the safety research program of the alliance, along with investigators in the AI Lab, the Center for Transportation and Logistics, the Department of Aeronautics and Astronautics, and LIDS. His research group focuses on the development of collision alerting systems for operation on-board a single vehicle or in a networked fashion.
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 LIDS. Various theoretical and applied studies are being carried out by professors Munther A. Dahleh, Eric Feron (chair of the IEEE Technical Committee on Robust Control), Steve Massaquoi, Alexandre Megretski 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 and 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 applications for robust and programmed (finite state-based) control theory are now emerging at LIDS, including the real-time, agile guidance of single and multiple unmanned aerial vehicles, as well as vehicle anti-collision 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 involved in a collaboration regarding the internal mechanisms that underlie the brain's ability to acquire programs that manage external dynamics and communication.
Another new thrust regards the general question of how control systems might evolve over time to manage complex control problems. Professors Sanjoy Mitter, Munther Dahleh, Steve Massaquoi and Robert Berwick and postdoctoral associates Reuben Rabi and Fadi Nabib Karameh conduct this work. The hope is to understand principles common to self-optimizing control systems across multiple scales of time and space. Biology is used as the guiding example, with analysis of systems ranging from molecular biological control of metabolism to organ system interaction to ecological regulation.
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 Dahleh and John 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 Dahleh and 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, and 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, as well as various stability problems for hybrid systems, saturated linear systems and linear time-varying systems.
Control in Presence of Communications Constraints
Professor Mitter, in collaboration with Professor Vivek Borkar (Tata Institute of Fundamental Research, India), Dr. Nicola Elia and several graduate students, has 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 doctors Anant Sahai and Sekhar Tatikonda demonstrate significant progress in this important subject.
Unmanned Air Vehicles
Professors Dahleh and Feron and their students 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.
The researchers have developed a complete simulation/animation environment, and their software (based on the above architecture) is now in use at Draper Laboratories, Barron Associates, Inc. and the Air Force research laboratory. 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. This research entails the development of a hierarchical control system that replaces the human pilot in order to perform agile maneuvers.
In late 2001, a miniature helicopter that the researchers built performed the first-known autonomous aileron roll by a helicopter. The achievement has been covered by the media worldwide, including the Associated Press, abcnews.com, Engineering Times, PM-Redakteur and Sciences et Avenir. Professor Feron and his students have received honors for their work in this area.
With sponsorship from the Draper Laboratory, Professor John Deyst and his students are developing new guidance and control methods for the 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 that 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.
Several LIDS personnel received recognition and honors for their work over the past year.
Professor Robert Gallager won the 2002 Eduard Rhein Foundation's basic research award, Europe's biggest such award.
Professor Muriel Medard was awarded the 2002 Leon K. Kirchmayer prize paper award for her paper titled "The Effect Upon Channel Capacity in Wireless Communications of Perfect and Imperfect Knowledge of the Channel." The award is presented by the IEEE Board of Directors for the most outstanding paper by an author(s) under 30.
A paper by Professor Eric Feron and his students titled "Design and Applications of an Avionics System for a Miniature Acrobatic Helicopter" won the best paper award at the October 2001 Digital Avionics Systems conference.
Professor Sanjoy Mitter was the plenary lecturer at "Control with Limited Information," European Control conference, Porto, Portugal, September 2001. He was the invited lecturer at "Autonomy and Adaptiveness: A Perspective on Neural Organization," IBM Technological Summit on Autonomic Computing, May 2002.
Professor Vahid Tarokh was recognized by Technology Review Magazine as one of the top 100 inventors of the year. He also delivered the Cullimore distinguished lecture series and ETRI distinguished lecture series in 2001.
Professor Vincent Chan was made a fellow of Optical Society of America award in the spring. He was the William Mong distinguished lecturer at the University of Hong Kong during IAP and the distinguished lecturer at the Chinese University of Hong Kong in April. He was also the keynote speaker at the Symposium on Photonics, Networking and Computing in Durham, NC, in March. His brain child, GeoLITE—an optical space communication system—went through successful space demonstration last year and received the David Packard excellence award.
Peter Marbach, LIDS graduate and assistant professor of computer science at the University of Toronto, won the best paper award at the IEEE Infocom 2002 for his paper "Priority Service and Max-Min Fairness." Professor Medard received honorable mention at the same conference for her paper "Beyond Routing: An Algebraic Approach to Network Coding," co-authored with Ralf Koetter.
Student Alp Muharremoglu won first place at the George Nicholson student paper competition (awarded by the Institute for Operations Research and the Management Sciences for the best paper in that field written by a student).
LIDS graduate and Bell Laboratories/Lucent Technologies researcher I. Emre Telatar won the prize paper award of the Information Theory Society at the 2002 IEEE international symposium on information theory for his paper titled "Capacity of Multi-antenna Gaussian Channels."
Dr. Andy Tsai, a member of the Stochastic Systems Group, received the best student paper award at the 2001 Conference on Vision and Pattern Recognition (CVPR 2001).
David Tse, LIDS graduate and associate professor of electrical engineering and computer science at the University of California-Berkeley, won the 2001 IEEE Communications and Information Theory Societies' joint paper award for "Linear Multiuser Receivers: Effective Interference, Effective Bandwidth and User Capacity," co-authored with S. Hanly.
Dr. Martin Wainwright, a member of the Stochastic Systems Group, received honorable mention in the best student paper competition at NIPS (Neural Information Processing Systems) 2001.
LIDS Colloquium and Seminar
Speakers in the LIDS colloquium and seminar series included Dr. Michael Mitzenmacher, Harvard University; Dr. P.R. Kumar, University of Illinois; Professor Anthony Yezzi, Georgia Tech; Dr. Sumeet Sandhu, Stanford University; Professor Sergio, Princeton University; Professor Daniel A. Spielman, MIT; Dr. Daniel Chasman, Variagenics, Cambridge, Massachusetts; Professor Sean Meyan, University of Illinois at Urbana-Champaign; Dr. Ray Leopole, vice president and chief technology officer, Global Telecommunications Solutions Sector, Motorola, Inc.; Dr. Gerhard Kramer, Bell Laboratories, Lucent Technologies; Dr. Marija Ilic, MIT; Dr. Ruediger L. Urbanke, Swiss Federal Institute of Technology, Lausanne; Professor Amos Lapidoth, Swiss Federal Institute of Technology, Zurich; Professor Steven S. Lumetta, University of Illinois at Urbana-Champaign; Professor Rahul Sarpeshkar, MIT; Professor Stanley Osher, UCLA; Professor Rajeev Alur, University of Pennsylvania; Professor H. Vincent Poor, Princeton University; Professor Claire Tomlin, Stanford University; Professor Pierre Moulin, University of Illinois at Urbana-Champaign; Dr. Dennis Goeckel, University of Massachusetts; Dr. Abbas El Gamal, Stanford University; Professor Dimitri Bertsekas, MIT; Professor Abhijit Banerjee, MIT; Professor Alexandra Duel-Hallen, North Carolina State University; and Dr. Steven E. Brenner, University of California at Berkeley.
Visitors to the Laboratory for Information and Decision Systems included Rami Abdallah, RSI, Argentina; Professor Vincent Blondell, Universite de Liege, Liege, Belgium; Professor Vijay Chandru, Tata Institute, Bangalore, India; Mattia Fedrigo, Scuola Normale Superiore, Pisa, Italy; Claudio Ferrero, RSI, Argentina; Professor Ulf Jonsson, Royal Institute of Technology, Stockholm, Sweden; Professor Ralf Koetter, University of Illinois, Urbana, Illinois; Professor Mario Milanese, Politecnico di Torino, Torino, Italy; Dr. Andrea Montanari, Ecole Normale Superieure, Paris, France; Dr. Nigel Newton, University of Essex, Colchester, UK; Linus Nilsson, Lund Technical University, Sweden; Professor Anders Rantzer, Lund Institute, Sweden; Per Rehnquist, KTH, Stockholm, Sweden; and Professor Nicholas Sourlas, Ecole Normale Superieure, Paris, France.
More information about the Laboratory for Information and Decision Systems can be found on the web at http://lids.mit.edu/.