Prospects for Intelligent Simulation

MIT Project on Mathematics and Computation
Artificial Intelligence Laboratory
Massachusetts Institute of Technology
N00014-92-J-4097

The objective of this research is to demonstrate breakthrough applications that exploit new computer representations and reasoning mechanisms. These mechanisms enable intelligent systems to autonomously design, monitor, and understand complex physical systems, through appropriate mixtures of numerical computing, symbolic computing, and knowledge-based methods. The techniques of intelligent simulation are broadly applicable, because they are based on the intelligent integration of information from mathematics and physics.

Systems incorporating these mechanisms can automatically prepare computational experiments from high-level domain descriptions. They actively monitor computational and physical experiments. They autonomously explore engineering design spaces and distinguish among theoretical explanations of observed phenomena. They automatically propose models of physical systems and match these against measurements and observations.

Approach

This work is driven by considering particular problems from science and engineering. Scientific theories and engineering designs are tested by computing their consequences and comparing them with the real world. Intelligent simulation research is directed at automating this process.

Intelligent simulators combine numerical, symbolic, and qualitative methods with computational formulations of mathematical and physical phenomena. They automatically prepare and monitor simulations and automatically interpret results. They carefully choose simulations to survey the range of possible models of unknown systems. By matching the observable details of the experimental situation with these consequences, they identify the model that best accounts for the observations.

Our work has already demonstrated applications to the design of high-performance automatic control systems. Other applications areas include dynamically stabilized structures, precision measurement, and intelligent materials.

We plan to create the system-architectural, algorithmic, and technological foundations for exploiting programmable materials. These are materials that incorporate vast numbers of programmable elements that react to each other and to their environment. Such materials can be fabricated economically, provided that the computing elements are amassed in bulk without arranging for precision interconnect and testing. In order to exploit programmable materials we must identify engineering principles for organizing and instructing myriad programmable entities to cooperate to achieve pre-established goals, even though the individual entities are unreliable and interconnected in unknown, irregular, and time-varying ways. We call this effort the study of amorphous computing.

Look here for an extensive bibliography of our publications.


Progress

Look here for latest highlighted accomplishment.

Imagistic reasoning

  • Ken Yip's KAM program explores a dynamical system by visually examining the phase-space trajectories that it discovers by its own numerical experiments. In collaboration with the KAM program, a team of ocean engineers determined some of the conditions that lead to wave instabilities in towing tanks, a new result in hydrodynamics. The joint effort accomplished more in seven weeks than had been accomplished in the previous year with conventional tools.

    Automatic control

  • Feng Zhao's MAPS (Modular Analyzer for Phase Spaces) and PSN (Phase Space Navigator) programs are the core of a system that automatically designs high-performance controllers for nonlinear systems by reasoning about phase-space geometry. This system automatically synthesized a high-performance controller for a magnetic levitation system. The new controller can stabilize maglev vehicles with displacements of up to 20 times those allowed in a previous manually-developed controller for the same system.

  • Liz Bradley's Perfect Moment program exploits chaos and instability to automatically synthesize control systems that achieve very fast target acquisition.

  • Mike Eisenberg's Kineticist's Workbench combines numerical simulation and symbolic methods to characterize chemical reaction mechanisms and suggest ways to simplify complex mechanisms.

    Intelligent Structures

  • Andy Berlin demonstrated that intelligent simulation can help in creating dynamically stabilized structures. Such structures will be sensitive and active, incorporating networks of high-performance controllers. Berlin constructed a prototype column that is actively stabilized by piezo-electric actuators. This column supports 5.6 more load than a passive column of the same size could support. He also demonstrated a truss bridge that uses actively stabilized members to support greater loads than would be possible without active control.

  • Natalya Cohen extended Berlin's work on active structures. Centralized controllers assume both the existence of a global model for the system to be controlled and the availability of global state information. These assumptions fail for complex structures with many sensing sites and many interacting controlled members. Cohen investigated the application of decentralized control to these systems. She constructed controllers, conducted qualitative analysis, simulation, and physical experiments on a prototype beam. She showed that even a very simple, unsophisticated decentralized controller is capable of increasing the load-bearing strength of the beam to the levels comparable to those achieved through the use of centralized control.

    Support for high-speed scientific computing

  • Andy Berlin implemented partial evaluation and parallel scheduling techniques that dramatically improve performance for an important class of numerical programs, achieving speedups over conventionally compiled code that range from 7 times faster to 91 times faster.

  • Rajeev Surati built upon Berlin's work to create a user-extensible partial evaluator. The viability of this approach was demonstrated by applying it to the Stormer integrator on a 6-body problem, achieving a factor of 610 speedup over conventional compilation.

  • In cooperation with Hewlett-Packard, we constructed an 8-processor prototype of a Supercomputer Toolkit -- a technology for configuring a variety of multiprocessor computing instruments that achieve supercomputer-performance computation.

  • Panayotis Skordos demonstrated an effective approach to simulating subsonic fluid dynamics on a cluster of non-dedicated workstations. Using this, he implemented the first plausible simulation of the interaction between subsonic hydrodynamic flow and acoustic waves. Skordos' simulation achieve 80% parallel efficiency (speedup/processors) using 20 HP-Apollo workstations. For this work, Skordos won the 1995 Gordon Bell Prize Prize for best price-performance in supercomputing applications.

    Computations of Scientific Importance

  • Gerry Sussman and Jack Wisdom used the the Supercomputer Toolkit and the associated compilation technology to perform a breakthrough computation in solar-system dynamics, integrating the complete Solar System, with General Relativity and Earth-Moon quadrupole correction, for 100 million years. The longest previous such integration was for 3 million years. This was a computation of major scientific significance, because it apparently confirmed that the motion of the Solar System is chaotic. A report on this analysis was published in Science (July 1992), which devoted an editorial to the significance of this achievement.

    Computational Formulations of Scientific Knowledge

  • Gerry Sussman, Jack Wisdom, Hardy Mayer, Chris Hanson, and Hal Abelson have developed the Scheme numerical and symbolic library to the point where it can support a novel approach to variational mechanics. Expressing the methods of variational mechanics in a computer language forces them to be unambiguous and computationally effective. This approach and software are now being used in a graduate subject in physics at MIT, and we are preparing a textbook based on this material.

  • Does knowledge of language consist of symbolic rules? How are the signals of our perception related to the symbols in our minds? How do children learn and use their linguistic knowledge? In an attempt to elucidate these questions Kenneth Yip and Gerald Jay Sussman presented a computational model of the acquisition and use of phonological knowledge. Their model encapsulates phonological information as boolean constraint relations operating on the classical linguistic representations of speech sounds in term of distinctive features. The performance model is described as a hardware mechanism that incrementally enforces the constraints. Phonological behavior arises from the action of this mechanism. Constraints are induced from a corpus of common English nouns and verbs. The induction algorithm compiles the corpus into increasingly sophisticated constraints. The algorithm is incremental, greedy, and fast. It yields one-shot learning from a few examples. Their model has been implemented as a computer program. The program exhibits phonological behavior similar to that of young children. As a bonus the constraints that are acquired can be interpreted as classical linguistic rules.

    Mathematics of Dynamical Systems

  • Thanos Siapas discovered a new invariant that quantifies the dependence of global geometry of dynamical systems on parameter variations. This is one of the first attempts to characterize fine changes in the geometry of phase-space structures, as opposed to coarse changes in their topology. The invariant determines a power law governing the change in basin geometry as parameters very.

  • Thanos Siapas also discovered a deep relationship between phase transitions in physical systems and the behavior of parallel methods in numerical optimization.

    When hunting for a minimum of a function a search algorithm makes a series of local changes, each of which is intended to get closer to the minimum. Of course, the search can get stuck in a bad local minimum. Various strategies, such as simulated annealing, have been employed to prevent this behavior by allowing some updates which actually move away from the minimum. This contrarian tendency is usually characterized by a "temperature" parameter.

    When changes are made in parallel there may be conflicts, so that even if each change is intended to go downhill there may be an increase in the function to be minimized. Thus there is a conflict between the downhill trend and the increases caused by parallelism. Siapas discovered that this conflict behaves in a way analogous to a phase transition in a physical system: as the amount of parallelism increases the performance of the optimization algorithm improves until a critical amount of parallelism is reached, and with more parallelism the performance decreases rapidly to random search. However, Siapas shows that the variation of the performance with the parallelism parameter is quite unlike the variation of the performance with the temperature parameter.

    Siapas reported on numerical experiments establishing this novel phenomenon in both NK landscapes and in the traveling-salesman problem. He also provided a theoretical framework based on finite-size scaling and on mean-field approximations to shed light on his discovery.

  • Elmer Hung discovered two properties of dynamical systems that are helpful in performing parameter estimation in unstable dynamical systems. First, although most observations in a time series provide little information about the parameters, there are portions of the trajectory that are extremely sensitive to parameter variations. Second, although the phenomenon of "shadowing" causes trouble in parameter estimation, there is an asymmetry of shadowing behavior that provides a handle on the parameter values. Using these properties, Hung devised an algorithm that achieves accuracies several orders of magnitude better than the Kalman filter and has good convergence properties for large data sets.

    Computing Languages and Systems

  • Bill Rozas introduced the idea of translucent procedures. These are like ordinary procedures in all ways, except that their opacity is violated in a controlled way to allow structure matching against a representation of the procedure text and environment. Rozas implemented a system based on translucent procedures and used it to demonstrate a novel equation-solving system, a compiler for threaded interpreters, and a method for the automatic construction of scientific subroutines to compute special functions.

  • Jonathan Rees demonstrated how the call-by-value lambda-calculus, with a few simple extensions, can provide the complete basis for an operating-system security kernel. Each agent (user or subsystem) has a separate evaluation environment that holds objects representing privileges granted to that agent. Because environments ultimately determine availability of object references, protection and sharing can be controlled largely by the way in which environments are constructed. To demonstrate the feasibility of this approach with the Rees used Scheme 48 to build a programming environment for mobile robots, and a secure multi-user environment that runs on workstations. Olin Shivers has exploited these same ideas to develop a Scheme-based server for the World-Wide Web.

  • Brian LaMacchia invented the Internet Fish, a novel resource-discovery tool designed to help users extract and refine useful information from the rich ore seams of the Internet. Unlike monolithic indexing schemes, Mr. LaMacchia's fish are sophisticated persistent autonomous information agents that are intended to model the behavior of research librarians. A user may deploy a fish intended to develop information on a particular topic. The fish will initiate research on that topic, continue to discover new sources of information on that topic, and will keep tabs on new developments in that topic. From time to time the user will interact with his fish, as it swims through cyberspace, to find out what it has learned, and to make suggestions for guidance.

    The internet fish is an entirely new kind of "life" on the network. It differs from a search engine or indexing system in that it is personal, persistent, and autonomous. It explores, maintaining internal state, accumulating information, and interacting with the user in extended conversations. It incorporates deep structural knowledge of the organization of the net; it includes explict knowledge of human naming conventions; and it is capable of on-the-fly reconfiguration, modification and expansion. A human user may specify or dynamically change heuristic policies to be used to help determine how interesting a datum is, and the fish may make these changes itself. Because the fish maintains a model and representation of its own structure and behavior, as well as a model of its information environment and its user, a fish can do meta-level reasoning. Thus LaMacchia's internet fish display the signs of a feeble sort of consciousness and a weak symbiotic relationship with the users.

    But LaMacchia did more. He did not just make a fish, he made an Internet Fish Construction Kit. This is enabling technology encapsulating a variety of useful heuristic and technical information into a catalog of mix-and-match components for fish-like systems. This is important because the separation of the fish into almost orthogonal components gives us a crude epistemology of the network. It also allows one to add interfaces to new services easily and immediately incorporate them into a fish.

    Recognition for Research and Education

  • Over the last five years, five of our recent graduates have received National Young Investigator awards, largely based on their work on the development and application of intelligent simulation technology. Jack Wisdom was selected as a MacArthur Fellow, partly on the basis of work done in our group. Gerry Sussman was selected as founding Fellow of the ACM, a Fellow of the American Academy of Arts and Sciences, and was winner of the ACM Karl Karlstrom Outstanding Educator Award in 1991. Hal Abelson was selected as a Fellow of the IEEE, and he is winner of the Abelson is also the winner of the 1995 Taylor L. Booth Education Award given by IEEE Computer Society, cited for his continued contributions to the pedagogy and teaching of introductory computer science.

    Technology Transfer

    We have a played key role in the standardization of Scheme by ANSII and by IEEE (IEEE Std 1178-1990). Scheme is a dialect of Lisp that is well-suited for educational use and for experiments in symbolic computing and parallelism. Our MIT Scheme implementation for Windows and Unix-based systems, which we maintain and distribute over the Internet, includes a high-performance compiler and an integrated text editor. Our research in novel compilation technology, and in mixed numeric/symbolic computation, rests on this substrate.

    We estimate that MIT Scheme is currently used at over 100 sites around the world. It serves as the primary computational vehicle for core computer science courses at many US universities, including MIT, Berkeley, Stanford, Princeton, and Cornell. Many of these courses are based on the textbook Structure and Interpretation of Computer Programs, by Hal Abelson, Gerry Sussman, and Julie Sussman. In 1996, we completed a second edition of this book, which is published by the MIT Press and the McGraw-Hill book company.

    Videotapes based of our lectures, produced by Hewlett Packard Co. have played major roles in industrial training programs at companies including Hewlett Packard, Texas Instruments, Digital Equipment, and Harris Corporation. See http://www.hp.com/wsg/programs/mit.html.

    For information on obtaining Scheme software and documentation, see http://www-swiss.ai.mit.edu/scheme-home.html. We have collaborated with Hewlett Packard Co. on a number of specific projects, including the development of the Supercomputer Toolkit, and our work on intelligent structures is being followed up at Xerox PARC.


    Hal Abelson (hal@mit.edu)
    Gerry Sussman (gjs@martigny.ai.mit.edu)

    Last modified June 29, 1996