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, a
postdoc, 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).
- General:
- R. Stolle, M. Easley, and E. Bradley, "Reasoning about Models of
Nonlinear Systems," in Logical and Computational Aspects of
Model-Based Reasoning, L. Magnani et al., eds. Kluwer,
2002.
- E. Bradley, M. Easley, and R. Stolle, "Reasoning about nonlinear system
identification," Artificial Intelligence
133:139-188 (2001)
- E. Bradley and R. Stolle, "Automatic Construction of Accurate
Models of Physical Systems," Annals of Mathematics and
Artificial Intelligence, 17:1-28 (1996).
- Knowledge representation and reasoning:
- R. Stolle, A. Hogan, and E. Bradley, "Agenda Control for
Heterogeneous Reasoners," Journal of Logic and Algebraic
Programming 62:41-69 (2005)
- M. Easley and E. Bradley, "Incorporating Engineering Formalisms
into Automated Model Builders," in The Computational Discovery of
Communicable Knowledge, L. Todorovski and S. Dzeroski, eds.
Springer, 2004.
- R. Stolle and E. Bradley, "Communicable Knowledge in Automated
System Identification," in The Computational Discovery of
Communicable Knowledge, L. Todorovski and S. Dzeroski, eds.,
Springer 2004.
- M. Easley and E. Bradley, "Meta-domains for automated system
identification," Smart Engineering System Design (ANNIE)
St. Louis; November 2000. Also available as
Department of Computer Science Technical Report CU-CS-904-00
- M. Easley and E. Bradley, "Generalized physical networks for model
building," Proceedings
International Joint Conference on Artificial Intelligence
(IJCAI), Stockholm, August 1999.
- R. Stolle and E. Bradley, "Multimodal Reasoning for Automatic
Model Construction", Proceedings Fifteenth
National Conference on Artificial Intelligence 1998 (AAAI-98),
Madison, Wisconsin, July 1998.
- R. Stolle and E. Bradley, "Opportunistic modeling,"
Proceedings of the IJCAI (International Joint Conference on
Artificial Intelligence) Workshop on Engineering Problems in
Qualitative Reasoning, Nagoya Japan; August 1997.
- Input/output modeling:
- M. Easley and E. Bradley, "Information Granulation in Automated
Modeling," in W. Pedrycz, editor, Granular Computing: An Emerging
Paradigm, Physica-Verlag, 2001.
- M. Easley and E. Bradley, "Intelligent Sensor Analysis and
Actuator Control," IDA-01 (International Symposium on Intelligent
Data Analysis), Lisbon; September 2001.
- M. Easley and E. Bradley, "Reasoning
about input-output modeling of dynamical systems," International Symposium on
Intelligent Data Analysis (IDA), Amsterdam; August 1999.
- E. Bradley and M. Easley, "Reasoning About Sensor Data for
Automated System Identification," Intelligent Data Analysis: An
International Journal, volume 2, number 2, Elsevier Science
(1998).
- Nonlinear parameter estimation:
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.