MIT Reports to the President 1996-97

LABORATORY FOR INFORMATION AND DECISION SYSTEMS

The Laboratory for Information and Decision Systems (LIDS) is an interdepartmental research laboratory of the Massachusetts Institute of Technology. Its staff includes faculty members, full-time research scientists, postdoctoral fellows, graduate research assistants, and support personnel. Undergraduate students participate in the research program of the Laboratory through the Undergraduate Research Opportunities Program (UROP). Every year several research scientists from various parts of the world visit the Laboratory to participate in its research programs.

The fundamental research goal of the Laboratory is to advance the field of systems, communication, control, and signal processing. In doing this, it explicitly recognizes the interdependence of these fields and the fundamental role that computers and computation play in this research. The Laboratory is conducting basic theoretical studies in communication, control, and signal processing, and is committed to advancing the state of knowledge in technologically important areas.

As an interdepartmental laboratory, LIDS reports to the Dean of the School of Engineering, Professor Robert A. Brown. The Co-Directors of the Laboratory are Professors Robert G. Gallager, Sanjoy K. Mitter, and John N. Tsitsiklis (Acting Co-Director).

The Center for Intelligent Control Systems, an interuniversity, interdisciplinary research center operated by a consortium of Brown University, Harvard University, and MIT, resides administratively within LIDS.

Twelve faculty members, several research staff members, and approximately 60 graduate students are presently associated with the Laboratory and the Center. Currently, the Laboratory and the Center provide some 25 research assistantships to graduate students. Undergraduate students also participate in research and thesis activities. A number of postdoctoral and visiting appointments are made.

Financial support is provided by the Air Force Office of Scientific Research (AFOSR), the Army Research Office (ARO), the Advanced Research Projects Agency (ARPA), C.S. Draper Laboratory, Motorola University Partnerships in Research, the National Science Foundation (NSF), the Office of Naval Research (ONR), Siemens AG, Tellabs, Inc., and the University Research Initiative Program (ARO).

NEW RESEARCH INITIATIVES

To complement a recently initiated effort in Automatic Target Recognition useful for synthetic aperture Radar, Prof. Alan Willsky and Dr. Hamid Krim have started a new research initiative in Representation theory for recognition which accounts for physical morphology of target objects. The theoretical effort is paralleled with its direct application on many aspects of their other research. The research effort in this area has continued and significant progress has been made in also applying these results. Professor Willsky, Dr. Krim and their students have indeed had great success in object recognition/identification with Real Radar and Synthetic Aperture Radar data.

Problems of sequential decision making under uncertainty are all-pervasive; for example, they arise in the contexts of communication networks, manufacturing systems, logistics, and in the control of nonlinear dynamical systems. In theory, such problems can be addressed using dynamic programming techniques; in practice, however, only problems with a moderately-sized state space can be handled. This research effort deals with the application of neural networks and other approximation and interpolation methodologies to overcome the curse of dimensionality of real-world stochastic control problems. The objectives driving this research are twofold. First, to develop the theoretical foundations and improve the understanding of such methods, using a combination of tools from approximation theory, dynamic programming, and stochastic algorithms. Second, to use these methods for solving some large-scale problems of practical interest. Application areas being currently investigated include problems in logistics (resource scheduling and assignment), finance (pricing of high-dimensional derivative instruments), and communications (dynamic channel allocation). This work is conducted by Professors Dimitri Bertsekas and John Tsitsiklis and their students and has been summarized in their recent prize-winning book, Neuro-Dynamic Programming.

CURRENT RESEARCH
Communications
A joint project with Microsystems Technology Laboratory (MTL), supported by ARPA, involves constructing a low power wireless sensor that operates efficiently over a wide range of powers and bit rates, from 1 Mb/s for full-motion video to 1 b/s for temperature sensing. One goal of the project is to characterize how constraints on device

technology interact with information theoretic limits to determine the best architecture for low power communication. As an example, for indoor line-of-sight communication, radiated RF power is swamped by

the power cost of computation. This work is being carried out by Professor Mitchell Trott and his students in LIDS together with Professors Sodini, Schlecht, Chandrakasan, Lee and their students in MTL.

Modern advances in computation have greatly relaxed the complexity constraints that apply to error-correction codes designed for voice-band modems, cable modems, and satellite channels. This has fueled the demand for powerful coding techniques and design methodologies which closely approach the information-theoretic upper

bounds on performance. Professors Mitchell Trott, Amos Lapidoth, and Dr. G. David Forney have begun to develop new methods for constructing and evaluating high-performance codes and decoding methods. Research has also begun on the design of universal codes that perform optimally over a broad class of channels. This work is supported by NSF and Motorola.

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

The major objective of this work is to develop the scientific base needed to design data communication networks that are efficient, robust, and architecturally clean. Both wide and local networks, both high speed and low speed networks, and both point-to-point and broadcast channels are of concern. One of the major topics of current interest is how to meet quality of service requirements at the internet layer through the diverse types of services that can be provided by highly heterogeneous underlying networks. The growth of both high speed optical networks and low speed wireless networks is making the problem critical. Another topic is finding the fundamental tradeoffs between fairness (i.e., multiple quality of service guarantees) and efficiency in high latency networks. This work is conducted by Professors Bertsekas, Gallager, Dr. Finn and their students.

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

Control
Determining the fundamental limitations and capabilities of identification and adaptive control has become an active area of research carried out by Professors Munther Dahleh, John Tsitsiklis, Sanjoy Mitter, and their students. This newly-initiated research program draws upon areas such as information-based complexity theory and computational learning theory, as well as upon the theory of robust control. It aims at developing a deterministic theory for system identification that can directly deal with finite data. Applications involving non-stationary time series will be considered (e.g., feature extraction from EEG Data).

Systematic design of multiple-input-multiple-output systems using a unified time-domain and frequency-domain framework to meet accurate performance in the presence of plant and input uncertainty is an extremely active research area in the Laboratory. Various theoretical and applied studies are being carried out by Professors Michael Athans, Munther Dahleh, Alexandre Megretski, Gunter Stein, and their students. Theoretical research deals with issues of robustness, aggregation, and adaptive control. The aim of the research is to derive a computer-aided design environment for design control systems that can address general performance objectives for various classes of uncertainty. Recent application-oriented studies include the control of large space structures, helicopters, submarine control systems, issues of integrated flight control, control of chemical processes and distillation columns, and automotive control systems.

Professors Munther Dahleh and Alexandre Megretski and his students are working on the development of new methods of nonlinear system analysis, and application of these techniques in various control systems, (flight control, firm control, animation control, hybrid systems, etc.). The work involves a broad spectrum of system-theoretic topics including modelling, identification, stability analysis, and optimization. One important objective is to learn how simplifications necessarily made in nonlinear system modelling affect the validity of nonlinear control design.

Hybrid systems are those containing mixtures of logic and continuous dynamics, e.g., digital computers and subsystems modeled as finite automata, coupled with controllers and plants modeled by differential or difference equations. A mathematical model of such systems, based on interacting collections of dynamical systems has been developed. This model is consistent with the theory of optimal control of hybrid systems developed in our laboratory by Professor Sanjoy K. Mitter in collaboration with Professor Michael Branicky, now at Case Western Reserve University, and Professor Vivek Borkar, a visitor from the Indian Institute of Science. Further, since this model builds on the rich theory of dynamical systems, extensions of that theory have been developed. For example, we have extended Lyapunov's stability theory to hybrid systems by developing a theory of multiple Lyapunov functions. Possible applications include programmable logic controllers and power-switching electronics. These analysis tools were also the basis of a collaboration begun with Professor Branicky and Professor Nancy Lynch of MIT's Laboratory for Computer Science on the formal verification of hybrid systems. LIDS' Professor Dahleh and doctoral candidate Jorge Goncalves have also shown interest in this effort. Finally, Professor Branicky was recently a visitor at the Department of Automatic Control, Lund Institute of Technology, Sweden (DAC), where he created some tools for the simulation of hybrid systems. These tools were developed within existing DAC software (Omola/Omsim) and will be ported to LIDS computers for future simulation/experimentation work. Professor Mitter, in collaboration with Professors Borkar and Chandru, has developed a theory of inference involving logic variables by suitably embedding it in Mathematical Programming.

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

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

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

Perceptual Systems and Machine Learning
Problems of speech recognition (speaker-independent), handwritten character recognition (on and off-line), and robust vision system design have turned out to be much more difficult than originally thought, owing to the richness and variability of the data and the resulting complexity of the problem of representation. Professor Sanjoy K. Mitter and his team have recently worked on two different approaches to compute useful representations. The top-down approach, inspired by the work of Grenander, is based on deformable templates and has been applied to character recognition. The bottom-up or compositional approach emphasizes computational efficiency and has been applied to edge detection. Shared by both approaches is the idea that uncertainties and ambiguities must be represented properly and resolved in the right context. This leads naturally to multi-layered representations where the lower levels contain local and data-driven information and the higher levels contain more global and goal-oriented information. Current research efforts attempt to exploit the synergies of the bottom-up and top-down approaches by using feedback mechanisms. Research has shifted toward this compositional, hierarchical approach for recognition of objects in cluttered scenes.

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

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

Musical and Image Variation via Nonlinear Dynamics and Chaos
In prior work (Dabby, Chaos, AIP 1996), a chaos-based technique was designed for generating musical variations of an original work. The variations can be close to the original, mutate almost beyond recognition, as well as achieve degrees of variability in between these two extremes. A virtually infinite set of variations is possible. The goal is to make music that changes from one hearing to the next -- not in random ways -- but rather by musical choice of the composer. Accordingly, the musical score becomes dynamic, not fixed. The technique employs two chaotic trajectories, each corresponding to a different set of initial conditions for the Lorenz system. These trajectories map the pitch sequence of a musical score into a variation based on the pitch events of the original piece. The mapping tempers the sensitive dependence of chaotic trajectories to initial conditions via two mechanisms -- linking and tracking -- to help the variations maintain a tie with the original. At present, the chaotic mapping has been extended to generate rhythmic, as well as pitch, variations. The chaotic mapping can also be used to infuse a given work with the attributes of another, e.g., Bach can metamorphose into Gershwin. The design reflects dynamic system concepts, especially those found in nonlinear and chaotic dynamics, coupled with the rich tradition of Western music theory. That the technique produces variations capable of being analyzed and used for musical means -- despite the highly context-dependent nature of music -- suggests the chaotic mapping might be applicable to other context-dependent sequences of symbols, e.g., symbol sequences from scanned art work. Algorithmic development for extension of the chaotic mapping to image and other applications is underway. Research conducted by Diana Dabby, PhD EECS, MIT, and Visiting Assistant Professor of Music at Middlebury College.

Center for Intelligent Control Systems
The Center for Intelligent Control Systems (CICS) combines distinguished faculty from MIT, Harvard University, and Brown University in interdisciplinary research on the foundations of intelligent machines and intelligent control systems. Established in October 1986, CICS is headed by Professor Sanjoy Mitter, Director; Professor Roger Brockett, Harvard University, Associate Director; and Professor Donald McClure, Brown University, Associate Director. The research activities of the Center are loosely grouped in five areas: Signal Processing, Image Analysis, and Vision; Automatic Control; Mathematical Foundations of Machine Intelligence; Distributed Information and Control Systems; and Algorithms and Architectures. A number of outstanding graduate students are appointed Graduate Fellows. The Center also hosts several senior visitors for varying lengths of time each year.

Speakers in the Colloquium and Seminar Series included: Prof. Sanjoy K. Mitter of LIDS, Prof. Roger W. Brockett of Harvard University, Prof. Jayant Shah of Northeastern University, Prof. John Baras of the University of Maryland at College Park, Prof. Sanjeev R. Kulkarni of Princeton University, Prof. Dan Spielman of MIT, Dr. Mats Viberg of Chalmers University of Technology, Sweden, Prof. Bixio Rimoldi of Washington University, St. Louis, Prof. Bernard C. Levy of the University of California, Davis, Prof. Andrea Goldsmith of the California Institute of Technology, Prof. Jeff Shamma of the University of Texas at Austin, Dr. Robert Calderbank of AT&T, Prof. Pravin Varaiya of the University of California, Berkeley, Prof. K.J. Astrom of the Lund Institute of Technology, Sweden, Prof. Ken Zeger of the University of California, San Diego, Prof. Drew Fudenberg of Harvard University, Prof. Sergio Verdu of Princeton University, Prof. Amos Lapidoth of LIDS, Dr. Aaron D. Wyner of Lucent Technologies, Dr. Alberto Malinverno of Schlumberger Doll Research, Prof. Mriganka Sur of MIT, Dr. William F. Powers of Ford Motor Company, Prof. Prakash Narayan of the University of Maryland at College Park, Dr. Vincent Chan, MIT Lincoln Lab, Prof. Alexandre Megretski of LIDS, Prof. Petar Kokotovic of the University of California, Santa Barbara, Prof. Christos Papadimitriou of the University of California at Berkeley, and Prof. Vadim Utkin of Ohio State University.

VISITORS TO THE LABORATORY

Visitors to the Laboratory for Information and Decision Systems included: Professor Karl Aström of the Lund Institute of Technology, Sweden; Dr. Vivek Borkar , Professor of Electrical Engineering, Indian Institute of Science; Professor Vijay Chandru of Purdue University, Indiana; Professor Meir Feder, Tel Aviv University, Israel; Dr. James Mills, Tellabs Operations, Indiana; Professor James Modestino, RPI, New York; Professor Bixio Rimoldi, Washington University, St. Louis, Missouri; Dr. Charles Rohrs, Tellabs, Indiana; and Professor Allen Tannenbaum, Electrical Engineering, University of Minnesota.

HIGHLIGHTS

Professors Dimitri Bertsekas and John Tsitsiklis together won the 1997 INFORMS Computer Science Technical Section Prize for their book, Neuro - Dynamic Programming, Athena Scientific, 1996.

Dr. G. David Forney, Jr. became a member of the EECS faculty and was named Bernard M. Gordon Adjunct Professor on July 1, 1996. He was awarded the Christopher Columbus International Communication Award in October 1996 in Genoa, Italy, and the Marconi International Fellowship in January 1997 in New Delhi, India.

Professor Robert G. Gallager delivered the following Keynote talks:

Dr. Hamid Krim delivered the invited talks, "Two Decades of Array Signal Processing: The Parametric Approach," and "Nonlinear Multiscale Signal Analysis" at the International Meeting of Signals and Systems, Monterey, CA.

Professor Sanjoy K. Mitter delivered an invited lecture entitled, "The Embedding of Logic in Mathematical Programming" (joint work with V. Borkar and V. Chandru) at the Hybrid Systems IV Conference, Ithaca, New York, October 12-14, 1996. He will give the Plenary Lecture at the Fifth IEEE Mediterranean Conference on Control and Systems, Paphos, Cyprus, July 21-23, 1997.

Professor Alan Willsky will give the keynote address at the Wavelets and Applications Conference during the SPIE Symposium, July-August 1997, in San Diego.

Dr. Diana Dabby is an Invited Speaker for the Fourth Experimental Chaos Conference sponsored by the ONR (August 1997). She was one of six selected nationwide for the Tufts University Multicultural Teaching Fellows Program, where she taught Nonlinear Dynamics and Chaos in the EECS Department. She won a national search conducted by Middlebury College and will teach the Advanced Composition courses in the Music Department next year with a focus on musical variation.

More information about this Laboratory can be found on the World Wide Web at the following URL: http://donald-duck.mit.edu/lids/

Robert G. Gallager, Sanjoy K. Mitter

MIT Reports to the President 1996-97