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, control, and signal processing.

Highlights

In academic year 2003, LIDS maintained its visibility in teaching and research. Research volume continued to remain strong at $6 million.

The following LIDS personnel received recognition and honors for their work over the past year:

Faculty

Graduate Students

Staff

return to top

About LIDS

LIDS is staffed by faculty, research scientists, postdoctoral fellows, and graduate students drawn principally from the Department of Electrical Engineering and Computer Science, as well as from the Department of Aeronautics and Astronautics, the Department of Mechanical Engineering, and the Sloan School of Management. Every year, many research scientists from various parts of the world visit the laboratory to participate in its research programs.

Twenty faculty, several research staff, and approximately 130 graduate students are presently associated with the laboratory. Undergraduate students also participate in research and thesis activities through the Undergraduate Research Opportunities Program. A number of postdoctoral and visiting appointments are made annually.

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.

return to top

Research Overview

The research goal of the laboratory is to advance the fields of systems, communication, control, and signal processing. In doing this, LIDS explicitly recognizes the interdependence of these fields and the fundamental role that mathematics, computers, and computation play in this research. The work conducted at LIDS falls into the following areas:

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; Hewlett-Packard; Intel; Merrill Lynch; Pierce, Fenner, and Smith, Inc.; the National Aeronautics and Space Administration (NASA); the National Science Foundation (NSF); the National Reconnaissance Office; the Office of Naval Research (ONR); and the Ford Motor Company.

return to top

Research Areas

The current research activities of the laboratory cover a wide range of theoretical and applied areas in systems, communication, control, and signal processing.

Communication

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, and John Tsitsiklis, Doctors John Chapin, Steven G. Finn, Charles Rohr, and Peter Young, and their students are conducting this research.

Optical Networks

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 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.

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 (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. This work opens up an important area for future research on network restoration, so that various restoration functions are done at the appropriate layer in a compatible manner.

A new program sponsored by DARPA on all-optical, local, and metro area networks with ultra-high reliability and performance 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.

Professor Medard, in collaboration with her students, 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. Other MIT researchers on this URI project are Professors George Verghese and Bernard Lesieutre.

Professor Medard and her students are also working on reliability of access networks. She is the MIT member of a recent NSF Information Technology Research (ITR) project with the University of Illinois in the area of robust optical local and metropolitan area networks. This project, conducted in collaboration with Professor Chan, considers the use of coarse unit of measure (UOM) and limited signal-to-noise ratios (SNRs) in architecting robust networks.

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.

Satellite Communications and Networking

The overall goal of this research addresses architecture designs for efficient data communications over low-Earth orbiting satellites (LEOs) 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; and efficient congestion-control algorithms at the transport and network layers for an integrated satellite/terrestrial network. Professors Chan, Modiano, and Tsitsiklis, Doctors Finn and Rohr, and their students are conducting this research.

This year, Professor Modiano and his students developed a power allocation scheme for a satellite data relay to a ground sink problem with multiple downlink beams that maximizes the satellite's data throughput. Professor Modiano's group also developed energy-efficient transmission scheduling schemes that take into account channel conditions in deciding when to transmit data. These schemes can be used to significantly reduce the amount of energy needed for data transmission.

During the past year, Professor Chan and his students have researched the power and beam allocation method based on traffic demands and channel conditions over satellite downlinks. The study indicates that the use of a parallel multibeam scheme with optimized power allocation provides a substantial power gain and fairness advantage amongst different demands.

On congestion control for hybrid networks, Professor Modiano and his students have explored the interaction between protocols at different layers. They developed models for analyzing the interaction between TCP and lower-layer protocols. In particular, they developed a model for the interaction between TCP and the Aloha multiple-access protocol and showed that channel "collisions" due to the Aloha protocol result in TCP window closures that significantly degrade end-to-end network performance. In order to alleviate the problem, they are exploring alternative access schemes that result in much-improved end-to-end throughput.

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. 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

In the last six months, Professor Modiano and his students initiated a study on the preferred constellation topology of the space backbone. Based on providing coverage for spaceborne users alone, the minimum number of satellites in the backbone constellation can be as small as 12 for low-Earth orbiting satellites (LEOs), 6 for medium-Earth orbiting satellites (MEOs) and the usual 3 for geostationary-Earth orbiting satellites (GEOs).

The team also completed a ministudy to reach a baseline understanding of current traditional space-qualified processors and commercial processors. Subsequently, Professor Modiano's group has begun to analyze the architecture of a networked processing system in space and the associated problem of task scheduling.

Multiple-Access Wireless Channels

Professor Medard is working in the area of capacity and stability of coded packetized multiple-access channels with students at MIT and with Professor Sean Meyn of the University of Illinois at Urbana-Champaign and Professor Andrea Goldsmith of Stanford University. This research establishes the capacity of such channels and examines trade-offs between energy and delay. It 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 an emulator using an IS-95 code division multiple-access standard. This emulator provides a practical implementation of theoretical coded multiple-access results. Along with Professor Medard, Professors Chan, Gallager, Modiano, and Moe Win, Doctors Chapin, Finn, Rohrs, and 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, she has investigated the effect of unequal channel knowledge at the sender and receiver. In particular, the team has 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 Goldsmith of Stanford University, Professor Medard has investigated the capacity of time-varying channels with sender- and receiver-side information—in particular, channels with perfect-side information but significant inter-symbol interference for which no capacity formulas existed. In collaboration with Dr. Ibrahim Abou-Faycal of MIT and Professor Madhow of University of California at Santa Barbara, 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.

Professors Medard and Zheng, with their students, have established a new, practical way of transmission over ultrawideband channels. Their work has discovered a significant family of signals that can achieve capacity under infinite bandwidth limits, whereas only a single such scheme was heretofore known. This work establishes for the first time a relation between infinite bandwidth capacity-achieving schemes and practical schemes for finite bandwidth and limited peak energy.

Professor Medard, Dr. Abou-Faycal, and their students have established new results relating bandwidth and error probability for ultrawideband fading channels. Their results show that error probability decreases very slowly with bandwidth and therefore, unlike nonfading channels, infinite-bandwidth performance cannot be achieved in the finite bandwidth regime. These results in effect achieve a strong coding theorem, which relates capacity, energy, bandwidth, and delay fundamentally with error probability.

Professor Win and his graduate students are working on the application of mathematical and statistical theories to communication, detection, and estimation problems with application to measurement and modeling of time-varying channels, design and analysis of multiple antenna systems, ultrawide bandwidth (UWB) communications systems, optical communications systems, and space communications systems. Their accomplishments include: receiver design, analysis and simulations for UWB communications; reduced-complexity Rake receivers; inverse symbol error probability for diversity reception; and efficient evaluation of error rate for hybrid diversity systems.

Wireless Ad Hoc Networks

Professor Modiano continues to work with Draper Laboratory on management and control of mobile ad hoc networks. Such networks are of critical importance for future combat systems, sensor networks, and autonomous systems involving mobile ground and air vehicles. These systems heavily depend on cooperative control between mobile vehicles and consequently on the availability of a communication capability between the vehicles. In a dynamic, mobile environment, one cannot assume that such communication capabilities are always present. In this effort, Professor Modiano and his students are developing architectures and protocols for providing reliable communication in this environment.

In addition, Professors Modiano, Eric Feron, and Nancy Lynch, along with Dr. Jinane Abounadi, are collaborating on a multidisciplinary university research initiative with Stanford University and the University of Illinois on Cooperative Networked Control of Dynamical Peer-to-Peer Vehicle Systems. A major focus of the project is the interplay between communication and control in an environment of networked vehicles.

Coding and Statistical Physics

Professor David 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 Sanjoy 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.

Sensor Web, Interference, 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 recently given a talk entitled, "Information Theoretic View of Maximum Likelihood Decoding and Nonlinear Estimation of Diffusion Processes." In the recently completed thesis of Maurice Chu, a unified view of distributed estimation with application to the Sensor Web has been presented. In the soon-to-be-completed thesis of Louay Bazzi, various aspects of coding and complexity have been investigated. Finally, Professor Mitter, with Dr. Reuben Rabi, is developing a theory of interconnections that has applications in distributed control, coding, and inference on graphs.

Codes on Graphs and Iterative Decoding

Professor Forney continued his research on codes on graphs and iterative decoding algorithms. He gave several plenary talks and published a review article in this area. He also wrote several new research papers. In joint work with A. Barg and A. Montanari, Professor Forney redeveloped Gallager's error exponent bounds for discrete memoryless channels from the point of view of large-deviation theory and showed that random codes typically have poorer minimum distance than random linear codes.

Network Codes

Professor Medard, in collaboration with her students and 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. This is the first research to establish theoretical bounds for the network management needs of networks in order to be able to recover from failures.

Professor Medard, in collaboration with her students and with Professor David Karger of the Laboratory for Computer Science, Professor Koetter, Professors Michelle Effros and Babak Hassibi of Caltech, and Dr. Abounadi of MIT, is working on using linear network codes as a unified framework for source, channel, and network coding.

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.

Collaboration with Draper Laboratory

LIDS and Draper Laboratory are developing a novel approach to collaborative research. In this approach, the two 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 Draper Laboratory with access to faculty, students, visitors, facilities, and infrastructure support, while Draper Laboratory mirrors the research at LIDS in its own programs, assuming responsibility both for coadvising 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' staff.

Systems, Detection, Estimation, and Optimization

Stochastic Systems Group

The Stochastic Systems Group (SSG) is led by Professor Alan S. Willsky, with the assistance of Dr. Mujdat Cetin and Dr. John Fisher of the AI Laboratory. In addition, the group includes 10 to 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 and analysis 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 biomedical image analysis, oceanographic and hydrological data assimilation, and fusion of multisource (e.g., acoustic and video) information both in centralized processors and in power-limited distributed sensor networks. Funding for this research comes from a variety of sources, including ONR, AFOSR, ARO, Office of the Director, Research & Engineering (through AFOSR, ARO, and ONR), the National Institutes of Health, 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 has just completed a four-year tour as a member of the Air Force Scientific Advisory Board but continues to support that organization informally. Each of the following research areas being pursued within SSG involves both theoretical development and applied studies involving the application areas mentioned previously.

Multiresolution Statistical Signal/Image Processing and Graphical Models

For a number of years, SSG research in multiresolution statistical and image processing has received considerable international attention and has found application in an extremely wide range of disciplines. The disciplines extend well beyond those in which the group has been and continues to be involved (i.e., large-scale geophysical data assimilation, computer vision, and distributed sensor networks) to fields such as chemical engineering and biomedical imaging. Because of the wide use of and interest in these methods, Professor Willsky was invited to prepare a tutorial/survey paper on this field, which appeared in the Proceedings of the IEEE. This area remains one of the most vigorous components of SSG research activities, with significant expansions of the scope of inquiry.

The key to SSG's previous (and some of its current) research in this area is the direct statistical modeling of phenomena at multiple resolutions. For example, the group's multiresolution methods are a key component of the 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, major new thrusts involve the investigation of how SSG can exploit its methodology for problems involving much more complex graphical models, such as those that arise in military command and control, or in problems of monitoring complex systems—problems of great national concern because of the need to make critical national infrastructure secure. For a more detailed discussion of SSG's work, see our web site.

Nonlinear and Geometric Image Analysis

During the past year, SSG has continued its efforts in the area of nonlinear/non-Gaussian image analysis. These include the explicit estimation/extraction of geometric information, such as object boundaries and segmentation. The group's work continues to focus on the development of statistically based curve evolution algorithms.

The group's work aims at developing first-principles statistical approaches to curve evolution that deal with noise and variability in a statistically optimal way. A paper based on the recent work of one recent SSG graduate, Dr. Andy Tsai, received the best paper award at a major international meeting. Another major interdisciplinary effort involves problems of dynamically estimating and tracking curves, with applications including both 4-D medical imaging of the heart and the tracking of major fronts in meteorology and oceanography (e.g., the Gulf Stream).

A third component of SSG's research program involves the development of statistically based algorithms for the fusion of information from multiple sensors in the presence of substantial uncertainties—for example, in the nature of the signals being sensed (such as 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.

The group's work has found application in medical image analysis, in particular in functional magnetic resonance imaging and in a variety of multisensor fusion applications. These include fusion of audio and video sensors (e.g., for the localization of acoustic sources in video scenes) and fusion of multiple acoustic sensors for the detection and localization of multiple sources in complex and highly uncertain environments that defeat standard coherent processing methods. SSG has demonstrated that information-theoretic methods can provide robust solutions to such problems without the need for any training (i.e., fusion is performed "on-the-fly" as data are collected).

Neurobiological Modeling

Professors Munther Dahleh and Steve Massaquoi are interested in three 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 multiscale, multiresolution 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 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 and in motor programming.

Algorithms

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.

Neurodynamic Programming

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 in real-world stochastic control problems. 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 minimax/saddle point theory using a handful of unifying principles that can be easily visualized and readily understood. Numerous research results on these topics are published in the new graduate-level textbook Convex Analysis and Optimization, by Dimitri Bertsekas, with Angelia Nedic and Asuman Ozdaglar (Athena Scientific, April 2003).

Network Optimization

Multicommodity network flow problems involve several types of supply/demand (or "commodities"), which simultaneously use the network and are coupled through either link capacities or through the cost function. This research considers linear/integer multicommodity flow problems for some special types of graphs, such as rings, that frequently arise in practical applications, such as data communication networks. Professors Bertsekas and Ozdaglar and their students show that these problems can be polynomially solved without loss of optimality by relaxing the integer constraints and rounding the solutions.

Game Theory and Equilibrium Problems

Problems that involve multiple-person decision making arise in a wide variety of areas, including communication networks, economics, and electric power systems. Game theory provides the mathematical framework to analyze the conflict and cooperation between rational decision makers. An important research question in this theory is to show the existence of an equilibrium for different models. Professor Ozdaglar performs this research.

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 lead times. Student Alp Muharremoglu's work in this area has been cited for excellence.

Perceptual Systems

Professor Sanjoy Mitter and his collaborators, Professor Stefano Soatto of UCLA and Dr. Horst Haussecker of Intel, 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.

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. Please refer to our web site for details.

Language Modeling and Word Meaning

During academic year 2003, Professor Robert Berwick and his research group made the following advances in the computational modeling of language learning, word meaning, language change, and language parsing: a new method for learning word meanings from just one or two examples, as children do; new results on language evolution, as modeled with dynamical systems; a probabilistic parser for minimalist grammars that can be trained to improve by parsing example sentences; and a textbook (in progress) on natural language processing with associated software, based on the course taught here at MIT and to be distributed via OpenCourseWare.

Biological Modeling

Professor Berwick and his students have modeled the apoptosis (programmed cell death) biological pathways using Stochastic Petri Nets (SPNs) as a way to examine the evolutionary origins and system development of this important biological system. They expect SPNs to provide a general framework to model biochemical pathways, leading to insights that may prove valuable for new experiments or interventions.

Automotive Safety

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 onboard a single vehicle or in a networked fashion.

Control

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 Dahleh, Eric Feron (chair of the IEEE Technical Committee on Robust Control), Steve Massaquoi, Alexandre Megretski, and their students.

Professors Feron and 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.

Evolutionary Control

Another new thrust regards the general question of how control systems might evolve over time to manage complex control problems. Professors Mitter, Dahleh, Massaquoi, and 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. This research is carried out by Professor Dahleh and his 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 Professor Dahleh and his 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.

Computational Complexity

Problems in systems and control theory are of varying degrees of difficulty, ranging from polynomial-time solvable to undecidable. Professor John Tsitsiklis and coworkers have been using tools from theoretical computer science (the 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 Communication Constraints

Professor Mitter and colleagues Professor Nicola Elia of Iowa State University, Professor Sekhar Tatikonda of Yale University, 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.

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 Laboratory, Barron Associates, and the Air Force Research Laboratory.

With sponsorship from Draper Laboratory, Professor John Deyst and his 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 together 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.

Identification and Learning of Complex Systems

Professor Dahleh has led a research effort in developing a theoretical framework for learning and identification of complex systems. To accurately define such a problem, one needs to make assumptions about the generation of data; choose a model class from which a model will be selected; and choose a metric that captures the distance between the model and the actual system. One can also choose multiple model classes and derive a metric to evaluate which model class to choose.

Professor Dahleh and his students have developed a new theoretical framework in which undermodeling is explicit in the problem formulation. Equivalently, the process that generates the data is not a member of the model classes considered. This work began in Dr. Saligrama Venkatesh's thesis several years ago. Recently, Dr. Soosan Beheshti developed a new measure of model quality evaluation, Model Description Complexity (MDC), that is computed from finite data.

Identification of Jump Parameter Systems

Many systems are best modeled as jump-systems—systems that switch between relatively simple systems. Switching is controlled by a Markovian system. A hurdle in identifying such systems is the estimation of the sequence of switching from the continuous observations at the output. Professor Dahleh and his students have developed a new framework for analyzing such systems based on Shannon's channel coding theorem and distortion theory. This work is the topic of the PhD thesis of Nuno Martins.

Control, Communication, Computation

Communication channels impose constraints on feedback systems that limit the achievable closed-loop stability and performance. Control theory has focused on characterizing the fundamental limitations and capabilities of closed-loop systems in the presence of both plant and input uncertainty. Communication constraints introduce a new class of uncertainty (e.g., quantization, average bit rate, or capacity) that existing theory deals with only indirectly. Professor Nicola Elia visited LIDS for a semester to help in this area. Professor Dahleh and his students, in collaboration with Professor Elia, have derived new results for computing stability limitations of feedback systems in the presence of various channels, using both deterministic and probabilistic models.

Analysis and Synthesis of Hybrid Systems

Many applications involve the interaction of both discrete (logic) and continuous systems. A feedback system with bit constraints is an example of such interaction. The motion planning problems of UAVs is another example. Professor Dahleh and Professor Megretski are leading an effort to derive a formal theory for modeling, analysis, and synthesis of pure discrete systems. This work is the first step toward the derivation of a complete formal theory for hybrid systems.

return to top

Events and Visitors

LIDS Colloquium and Seminar

Speakers in the LIDS Colloquium and Seminar series included Nicola Elia, Iowa State University; Feng Zhao, PARC; Paul Tseng, University of Washington; Alek Kavcic, Harvard University; Manindra Agarwa, ITT Kanpur; John Proakis, Northeastern University; Yuval Peres, University of California–Berkeley; Michelle Effros, Caltech; Nigel Boston, University of Wisconsin; Sekhar Tatikonda, Yale University; Shie Mannor, Technion University; Geir Dullerud, University of Illinois; Don Towsley, University of Massachusetts; Bernd Sturnfels, University of California atBerkeley; Robert Gray, Stanford University; Eric Jacobsen, Intel; Andrea Goldsmith, Stanford University; Iraj Saniee, Lucent Technologies; Tamer Basar, University of Illinois; Peter Shor, AT&T Research; David Mumford, Brown University; Radia Perlman, Sun Microsystems; Kevin Wise, Boeing; Ken Loparo, Case Western University; Prakash Narayan, University of Maryland; Shlomo Shamai, Technion University; and Ramir Zamir, Tel Aviv University.

Visiting Scholars

Visiting scholars at LIDS this year included Dr. Rod Alferness, research affiliate, Lucent Technologies; Dr. Richard A. Barry, research affiliate, Sycamore Networks; Aya Bedar, visiting student, University of Beruit, Lebanon; Dr. C. Boussios, research affiliate, Open Ratings, Inc., Greece; Dr. Stefano Casadei, research affiliate, Enuvis, Inc., Italy; Professor Vijay Chandru, research affiliate, Indian Institute of Science; Dr. John Chapin, visiting scientist, Vanu Inc.; Andrea Conti, visitor; Professor Diane Dabby, research affiliate, Franklin W. Olin College of Engineering; Professor Raffaello D'Andrea, visiting professor, Cornell University; Professor Michelle Effros, visiting professor, Caltech; Professor Nicola Elia, research affiliate, Iowa State University; Dr. Peter Falb, research affiliate, Brown University; Mr. Sleiman Itani, visiting student, University of Beruit, Lebanon; Dr. Alan Kirby, research affiliate, Okena, Inc.; Dr. Philip Lin, research affiliate, Tellabs Inc.; Dr. Richard Marcus, research affiliate, LIDS; Dr. Debasis Mitra, research affiliate, Bell Labs/Lucent; Dr. James Mills, research affiliate, Tellabs Inc.; Randolph L. Moses, visiting scientist, Ohio State University; Professor Nigel Newton, visiting scholar, University of Essex, England; Reza Olfati-Saber, visiting scientist, Caltech; Professor Yannis Paschalidis, visiting scholar, Boston University; Dr. Charles Rockland, visiting scholar, RIKEN Brain Science Institute, Japan; Dr. Adel A. M. Saleh, research affiliate, Kirana Networks, Inc.; Dr. Iraj Sanlee, research affiliate, Lucent Technologies; Professor Jeff Shamma, visiting scientist, University of California–Los Angeles; Dr. Eric A. Swanson, research affiliate, Sycamore Networks; Dr. Jorge Tierno, visiting scientist, Honeywell Laboratories; Dr. Masahito Tomazawa, visiting scientist, Nippon Telegraph & Telephone, Japan; Dr. Eugene Wong, visitor, Versata; and Dr. Lee Yang, visiting scientist, Draper Laboratory.

Vincent W. S. Chan
Director
Joan and Irwin M. Jacobs Professor of Electrical Engineering and Aeronautics and Astronautics

More information about the Laboratory for Information and Decision Systems can be found on the web at http://lids.mit.edu/.

 

return to top
Table of Contents