Automatic Construction of Accurate Models of Physical Systems

Project Description

PRET automates the process that control theorists call system identification: deducing the internal dynamics of a black-box system solely from observations of its outputs. PRET builds ordinary differential equation (ODE) models of physical systems, linear or nonlinear; it accomplishes this by wrapping a layer of AI techniques around a core of traditional system identification (SID) methods. This AI layer executes many of the high-level parts of the SID procedure that are normally performed by a human expert: it intelligently assesses the situation at each stage of the process and then reasons from the available information to automatically choose, invoke, and interpret the results of appropriate lower-level techniques. During its parameter estimation phase, for example, PRET uses qualitative reasoning techniques to derive good starting values for a nonlinear least-squares solver call, allowing the latter to avoid local extrema in the regression landscape. Like human experts, PRET uses a heterogeneous collection of reasoning modes during the model-building process, and the intelligent orchestration of these modes is critical to its success. This knowledge representation and reasoning task is performed by a special first-order logic system, which selects and coordinates the appropriate reasoning tactics in order to guide the search quickly and accurately to an ODE model that accounts for the important behavior of the system.

PRET is designed to be an engineer’s tool; because of this, it differs sharply from other AI modeling programs in a variety of important ways. First, it explicitly avoids all attempts to “discover” any physics that falls outside its user’s specifications; rather, it works very hard to find a minimal model - one that matches the observations to within a user-prescribed resolution, and no more. Second, it does not adhere to a single, neat paradigm; rather, it calls upon a wide variety of reasoning techniques, ranging from classic AI ideas like constraint propagation to standard engineering tricks like power series, and it works hard to use the right technique at the right time. This mix of methods is the source of PRET’s ability to solve real-world problems in a variety of engineering domains. Third, PRET works directly with the physical world, using sensors and actuators to interact with its target systems — an input/output modeling approach that is both very powerful and extremely difficult because of the nonlinear control theory that is involved.

In terms of performance, PRET attained the functional level of a smart undergraduate. It solves garden-variety textbook SID problems fairly well, struggles occasionally with the harder ones, and has successfully (with some minor hand-holding concerning the relationships between different coordinate systems) modeled one real-world system: a radio-controlled car destined for use in a soccer-playing robot project. SID is an essential first step in the design of a system like this; without an accurate ODE model of the car’s dynamics, it is impossible to build a controller to direct its behavior according to a plan - and ODEs are not part of a Radio Shack spec sheet. From an engineering standpoint, modeling this device is a nontrivial accomplishment; nonlinear SID is considered to be an open problem. The AI issues in this example were also interesting: PRET not only duplicated the model that the project analyst had derived by hand; interacting with the AI tool also helped the human expert refine his explicit mental model of the system.

People

  • Prof. Liz Bradley, project leader.
  • Matt Easley, who finished his Ph.D. in 2000, developed representation and reasoning facilities for model building and input/output modeling.
  • Apollo Hogan, an undergraduate research assistant, wrote PRET's GUI and helped Reinhard with lots of other bits and pieces.
  • Brian LaMacchia helped write some of PRET's symbolic algebra facilities.
  • Janet Rogers and Abbie O'Gallagher of NIST helped write PRET's nonlinear parameter estimator.
  • Reinhard Stolle, who finished his Ph.D. in 1998, designed and implemented PRET's model tester and its declarative reasoning techniques. He also played a key role in most of the main design decisions on the project as a whole.
  • Tom Wrensch wrote PRET's qualitative simulator.

Papers

For space reasons, sets of closely related papers have been pruned. See my publications page for a complete list, and please contact me for reprints if what you want isn’t here (or won’t download).

Links

  • The qualitative reasoning/qualitative physics home page.

Support

  • This material is based upon work supported by the National Science Foundation under grant numbers MIP-9403223 and National Young Investigator Award CCR-9357740, by the Office of Naval Research under grant number N00014-96-1-0720, and by a Packard Fellowship in Science and Engineering. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of these funding agencies.