×

Reasoning about nonlinear system identification. (English) Zbl 0984.68158

Summary: System identification is the process of deducing a mathematical model of the internal dynamics of a system from observations of its outputs. The computer program Pret automates this process by building a layer of artificial intelligence techniques around a set of traditional formal engineering methods. Pret takes a generate-and-test approach, using a small, powerful meta-domain theory that tailors the space of candidate models to the problem at hand. It then tests these models against the known behavior of the target system using a large set of more-general mathematical rules. The complex interplay of heterogeneous reasoning modes that is involved in this process is orchestrated by a special first-order logic system that uses static abstraction levels, dynamic declarative meta control, and a simple form of truth maintenance in order to test models quickly and cheaply. Unlike other modeling tools—most of which use libraries to model small, well-posed problems in limited domains and rely on their users to supply detailed descriptions of the target system—Pret works with nonlinear systems in multiple domains and interacts directly with the real world via sensors and actuators. This approach has met with success in a variety of simulated and real applications, ranging from textbook systems to real-world engineering problems.

MSC:

68T50 Natural language processing
68U20 Simulation (MSC2010)

Software:

Maple; UCPOP; Prodigy
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abarbanel, H., Analysis of Observed Chaotic Data (1995), Springer: Springer Berlin · Zbl 0843.93004
[2] Abelson, H., The bifurcation interpreter: A step towards the automatic analysis of dynamical systems, Internat. J. Comput. Math. Appl., 20, 13 (1990)
[3] Addanki, S.; Cremonini, R.; Penberthy, J. S., Graphs of models, Artificial Intelligence, 51, 145-178 (1991)
[4] Amsterdam, J., Automated qualitative modeling of dynamic physical systems, Ph.D. Thesis (1992), MIT: MIT Cambridge, MA
[5] Astrom, K.; Eykhoff, P., System identification—A survey, Automatica, 7, 123-167 (1971) · Zbl 0219.93004
[6] Barrett, A.; Christianson, D.; Friedman, M.; Kwok, C.; Golden, K.; Penberthy, S.; Sun, Y.; Weld, D., UCPOP User’s Manual (version 4.0) (1995), Technical Report 93-09-06d, Department of Computer Science and Engineering, University of Washington: Technical Report 93-09-06d, Department of Computer Science and Engineering, University of Washington Seattle, WA
[7] Beckstein, C.; Stolle, R.; Tobermann, G., Meta-programming for generalized Horn clause logic, (Proc. 5th International Workshop on Metaprogramming, Metareasoning in Logic (META-96), Bonn, Germany (1996)), 27-42
[8] Beckstein, C.; Tobermann, G., Evolutionary logic programming with RISC, (Proc. 4th International Workshop on Logic Programming Environments, Washington, DC (November 1992), Technical Report TR 92-143, Center for Automation and Intelligent Systems Research at Case Western Reserve University: Technical Report TR 92-143, Center for Automation and Intelligent Systems Research at Case Western Reserve University Cleveland, OH), 16-21
[9] Beckstein, C.; Tobermann, G., Algorithmic debugging and hypothetical reasoning, J. Automat. Software Engineering, 4, 151-178 (1997)
[10] Besinger, F.; Cebon, D.; Cole, D., Damper models for heavy vehicle ride dynamics, Vehicle System Dynamics, 24, 35-64 (1997)
[11] Boggs, P.; Byrd, R.; Rogers, J.; Schnabel, R., User’s reference guide for odrpack—Software for weighted orthogonal distance regression (1991), Technical Report 4103, National Institute of Standards and Technology: Technical Report 4103, National Institute of Standards and Technology Gaithersburg, MD, 20899
[12] Boggs, P.; Byrd, R.; Schnabel, R., A stable and efficient algorithm for nonlinear orthogonal distance regression, SIAM J. Sci. Statist. Comput., 8, 6, 1052-1078 (1987) · Zbl 0637.65150
[13] Bradley, E., Autonomous exploration and control of chaotic systems, Cybernetics and Systems, 26, 299-319 (1995)
[14] Bradley, E., Time-series analysis, (Berthold, M.; Hand, D., Intelligent Data Analysis: An Introduction (2000), Springer: Springer Berlin) · Zbl 0443.62070
[15] Bradley, E.; Easley, M., Reasoning about sensor data for automated system identification, Intelligent Data Analysis, 2, 2, 123-138 (1998)
[16] Bradley, E.; O’Gallagher, A.; Rogers, J., Global solutions for nonlinear systems using qualitative reasoning, Ann. Math. Artificial Intelligence, 23, 211-228 (1998) · Zbl 0917.93030
[17] Bradley, E.; Stolle, R., Automatic construction of accurate models of physical systems, Ann. Math. Artificial Intelligence, 17, 1-28 (1996) · Zbl 0891.68018
[18] Branicky, M.; Borkar, V.; Mitter, S., A unified framework for hybrid control, (Proc. 33rd IEEE Conference on Decision & Control, Lake Buena Vista, FL (1994)), 4228-4234
[19] Bredehoeft, J.; Cooper, H.; Papadopulos, I., Inertial and storage effects in well-aquifer systems, Water Resource Research, 2, 4, 697-707 (1966)
[20] Brogan, W., Modern Control Theory (1991), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0747.93001
[21] Capelo, A.; Ironi, L.; Tentoni, S., Automated mathematical modeling from experimental data: An application to material science, IEEE Trans. Systems Man Cybernet., 28, 356-370 (1998)
[22] Carbonell, J.; Blythe, J.; Etzioni, O.; Gil, Y.; Joseph, R.; Kahn, D.; Knoblock, C.; Minton, S.; Pérez, A.; Reilly, S.; Veloso, M.; Wang, X., PRODIGY 4.0: The manual and tutorial (1992), Technical Report CMU-CS-92-150, School of Computer Science, Carnegie Mellon University: Technical Report CMU-CS-92-150, School of Computer Science, Carnegie Mellon University Pittsburgh, PA
[23] Char, B. W.; Geddes, K. O.; Gonnet, G. H.; Leong, B. L.; Monagan, M. B.; Watt, S. M., Maple V Language Reference Manual (1991), Springer: Springer Berlin · Zbl 0758.68038
[24] Cherniack, M.; Zdonik, S., Changing the rules: Transformations for rule-based optimizers, (Proc. ACM SIGMOD International Conference on Management of Data, Seattle, WA (1998))
[25] Chin, D., Water-Resource Engineering (2000), Prentice Hall: Prentice Hall Englewood Cliffs, NJ
[26] Davis, R., Meta-rules: Reasoning about control, Artificial Intelligence, 15, 3, 179-222 (1980)
[27] de Kleer, J., An assumption-based TMS, Artificial Intelligence, 28, 2, 127-162 (1986)
[28] (Kleer, J.de; Williams, B. C., Artificial Intelligence, 51 (1991), Elsevier Science: Elsevier Science Amsterdam), Special Volume on Qualitative Reasoning about Physical Systems II
[29] D’Humieres, D.; Beasley, M.; Huberman, B.; Libchaber, A., Chaotic states and routes to chaos in the forced pendulum, Phys. Rev. A, 26, 3483-3496 (1982)
[30] Džeroski, S.; Todorovski, L., Discovering dynamics: From inductive logic programming to machine discovery, J. Intelligent Inform. Systems, 4, 89-108 (1995)
[31] Easley, M., Automating input-output modeling of dynamic physical systems, Ph.D. Thesis (2000), University of Colorado at Boulder
[32] Easley, M.; Bradley, E., Generalized physical networks for model building, (Proc. IJCAI-99, Stockholm, Sweden (1999)), 1047-1052
[33] Easley, M.; Bradley, E., Reasoning about input-output modeling of dynamical systems, (Proc. 3rd International Symposium on Intelligent Data Analysis (IDA-99), Amsterdam (1999), Springer: Springer Berlin), 343-355
[34] Easley, M.; Bradley, E., Meta-domains for automated system identification, (Dagli, C. H.; Akay, M.; Ersoy, O. K.; Ferná; Smith, A., Proc. Smart Engineering System Design (ANNIE 00) (2000), ASME Press: ASME Press Fairfield, NJ), 165-170
[35] Everett, J.; Forbus, K., Scaling up logic-based truth maintenance systems via fact garbage collection, (Proc. AAAI-96, Portland, OR (1996)), 614-620
[36] Falkenhainer, B.; Forbus, K., Compositional modeling: Finding the right model for the job, Artificial Intelligence, 51, 95-143 (1991)
[37] Faltings, B.; Gelle, E., Local consistency for ternary numeric constraints, (Proc. IJCAI-97, Nagoya, Japan (1997)), 392-397
[38] (Faltings, B.; Struss, P., Recent Advances in Qualitative Physics (1992), MIT Press: MIT Press Cambridge, MA)
[39] Forbus, K., Qualitative process theory, Artificial Intelligence, 24, 85-168 (1984)
[40] Forbus, K., Interpreting observations of physical systems, IEEE Trans. Systems Man Cybernet., 17, 3, 350-359 (1987)
[41] Forbus, K., Qualitative reasoning, (Tucker, A., CRC Computer Science and Engineering Handbook (1997), CRC Press: CRC Press Boca Raton, FL)
[42] Forrester, J., World Dynamics (1971), Wright Allen Press: Wright Allen Press New York
[43] Gabbay, D. M.; Sergot, M. J., Negation as inconsistency I, J. Logic Programming, 3, 1, 1-36 (1986) · Zbl 0606.68086
[44] Gallaire, H.; Lasserre, C., Controlling knowledge deduction in a declarative approach, (Proc. IJCAI-79, Tokyo, Japan (1979)), S.1, S.6
[45] Gallaire, H.; Lasserre, C., Metalevel control for logic programs, (Clark, K. L.; Tärnlund, S. A., Logic Programming (1982), Academic Press: Academic Press London), 173-185
[46] Goldstein, H., Classical Mechanics (1980), Addison Wesley: Addison Wesley Reading, MA · Zbl 0491.70001
[47] Grosof, B., Courteous logic programs: Prioritized conflict handling for rules (1997), Technical Report RC 20836, IBM Research
[48] (Halling, J., Principles of Tribology (1978), MacMillan)
[49] Hannon, B.; Ruth, M., Dynamic Modeling (1995), Springer: Springer New York
[50] Standard Instrument Control Library Reference Manual (1996)
[51] Hill, P.; Lloyd, J., The Gödel Programming Language (1994), MIT Press: MIT Press Cambridge, MA · Zbl 0850.68138
[52] Hogan, A.; Stolle, R.; Bradley, E., Putting declarative meta control to work. Technical Report CU-CS-856-98, University of Colorado at Boulder (1998)
[53] Hong, D.; Velinsky, S.; Feng, X., Verification of a wheeled mobile robot dynamic model and control ramifications, Dynamic Systems, Measurement, and Control, 131, 1, 58-63 (1999)
[54] Horst, R.; Pardalos, P.; Thoai, N., Introduction to Global Optimization. Introduction to Global Optimization, Nonconvex Optimization and its Applications, 3 (1987), Kluwer: Kluwer Dordrecht
[55] Hsu, C., A theory of cell-to-cell mapping dynamical systems, J. Appl. Mech., 47, 931-939 (1980) · Zbl 0452.58019
[56] Hsu, C., Cell-to-Cell Mapping (1987), Springer: Springer New York
[57] Huang, K.-M.; Zytkow, J. M., Discovering empirical equations from robot-collected data, (Ras, Z.; Skowron, A., Foundations of Intelligent Systems. Foundations of Intelligent Systems, Lecture Notes in Computer Science, 1325 (1997), Springer: Springer Berlin), 287-297, Proceedings of ISMIS-97, Charlotte, NC, October 1997
[58] Jaffar, J.; Maher, M., Constraint logic programming: A survey, J. Logic Programming, 20, 503-581 (1994)
[59] Juang, J.-N., Applied System Identification (1994), Prentice Hall: Prentice Hall Englewood Cliffs, NJ
[60] Karnopp, D.; Margolis, D.; Rosenberg, R., System Dynamics: A Unified Approach (1990), Wiley: Wiley New York
[61] Kuipers, B. J., Qualitative simulation, Artificial Intelligence, 29, 3, 289-338 (1986) · Zbl 0624.68098
[62] Kuipers, B. J., Qualitative Reasoning: Modeling and Simulation with Incomplete Knowledge (1992), Addison-Wesley: Addison-Wesley Reading, MA
[63] (Langley, P.; Simon, H. A.; Bradshaw, G. L.; Zytkow, J. M., Scientific Discovery: Computational Explorations of the Creative Process (1987), MIT Press: MIT Press Cambridge, MA)
[64] Langlois, R.; Anderson, R., Preview control algorithms for the active suspension of an off-road vehicle, Vehicle System Dynamics, 24, 65-97 (1997)
[65] LeFèvre, J., Reactive system dynamics: An extension of forrester’s system dynamics using bond graph-like notations, (Bond Graph Modeling and Simulations, ICBGM ’97, Conference Proceedings, Phoenix, AZ (1997)), 149-155
[66] (Ljung, L., System Identification: Theory for the User (1987), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ) · Zbl 0615.93004
[67] Lloyd, J. W., Foundations of Logic Programming (1987), Springer: Springer Berlin · Zbl 0547.68005
[68] McCarty, L., Clausal intuitionistic logic I. Fixed-point semantics, J. Logic Programming, 5, 1-31 (1988) · Zbl 0645.03006
[69] Morrison, F., The Art of Modeling Dynamic Systems (1991), Wiley: Wiley New York
[70] Mosterman, P.; Biswas, G., Formal specifications for hybrid dynamical systems, (Proc. IJCAI-97, Nagoya, Japan (1997)) · Zbl 0948.68210
[71] Mosterman, P. J.; Biswas, G., A formal hybrid modeling scheme for handling discontinuities in physical system models, (Proc. AAAI-96, Portland, OR (1996)), 985-990
[72] Muscettola, N.; Nayak, P.; Pell, B.; Williams, B., Remote agent: To boldly go where no AI system has gone before, Artificial Intelligence, 103, 5-48 (1998) · Zbl 0909.68167
[73] Nayak, P. P., Automated Modeling of Physical Systems. Automated Modeling of Physical Systems, Lecture Notes in Computer Science, 1003 (1995), Springer: Springer Berlin, Revised version of Ph.D. Thesis, Stanford University, 1992 · Zbl 0920.93005
[74] Paynter, H., Analysis and Design of Engineering Systems (1961), MIT Press: MIT Press Cambridge, MA
[75] Rees, J.; Clinger, W., The \(revised^3\) report on the algorithmic language Scheme, ACM SIGPLAN Notices, 21, 37 (1986)
[76] Reid, J., Linear System Fundamentals (1983), McGraw-Hill: McGraw-Hill New York
[77] Robins, V.; Meiss, J.; Bradley, E., Computing connectedness: An exercise in computational topology, Nonlinearity, 11, 913-922 (1998) · Zbl 0957.54010
[78] Robins, V.; Meiss, J.; Bradley, E., Computing connectedness: Disconnectedness and discreteness, Physica D, 139, 276-300 (2000) · Zbl 1098.37546
[79] Sanford, R., Physical Networks (1965), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[80] Sauer, T.; Yorke, J.; Casdagli, M., Embedology, J. Statist. Phys., 65, 579-616 (1991) · Zbl 0943.37506
[81] Sontag, E. D., Mathematical Control Theory (1998), Springer: Springer Berlin · Zbl 0844.93012
[82] Sterling, L.; Shapiro, E., The Art of PROLOG (1986), MIT Press: MIT Press Cambridge, MA · Zbl 0605.68002
[83] Stolle, R., Integrated multimodal reasoning for modeling of physical systems, Ph.D. Thesis (1998), University of Colorado, To appear in Lecture Notes in Computer Science, Springer, Berlin
[84] Stolle, R.; Bradley, E., A customized logic paradigm for reasoning about models, (Iwasaki, Y.; Farquhar, A., Proc. 10th International Workshop on Qualitative Reasoning (QR-96), Stanford Sierra Camp, CA (1996), AAAI Technical Report WS-96-01)
[85] Stolle, R.; Bradley, E., Multimodal reasoning for automatic model construction, (Proc. AAAI-98, Madison, WI (1998)), 181-188
[86] Strogatz, S., Nonlinear Dynamics and Chaos (1994), Addison-Wesley: Addison-Wesley Reading, MA
[87] Sussman, G.; Steele, G., CONSTRAINTS—A language for expressing almost hierarchical descriptions, Artificial Intelligence, 14, 1-39 (1980)
[88] Todorovski, L.; Džeroski, S., Declarative bias in equation discovery, (Proc. 14th International Conference on Machine Learning (ICML-97), San Francisco, CA (1997), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 376-384
[89] Top, J.; Akkermans, H., Computational and physical causality, (Proc. IJACI-91, Sydney, Australia (1991)) · Zbl 0754.68106
[90] Torn, A.; Zilinskas, A., Global Optimization. Global Optimization, Lecture Notes in Computer Science, 350 (1995), Springer: Springer Berlin
[91] Washio, T.; Motoda, H.; Yuji, N., Discovering admissible model equations from observed data based on scale-types and identity constraints, (Proc. IJCAI-99, Stockholm, Sweden (1999)), 772-779
[92] (Weld, D.; de Kleer, J., Readings in Qualitative Reasoning about Physical Systems (1990), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA)
[93] Weld, D. S., Reasoning about model accuracy, Artificial Intelligence, 56, 255-300 (1992) · Zbl 0787.68090
[94] Williams, B. C.; Millar, W., Decompositional, model-based learning and its analogy to diagnosis, (Proc. AAAI-98, Madison, WI (1998))
[95] Yip, K., KAM: A System for Intelligently Guiding Numerical Experimentation by Computer. KAM: A System for Intelligently Guiding Numerical Experimentation by Computer, Artificial Intelligence Series (1991), MIT Press: MIT Press Cambridge, MA
[96] Zhao, F., Computational dynamics: Modeling and visualizing trajectory flows in phase space, Ann. Math. Artificial Intelligence, 8, 285-300 (1993) · Zbl 1047.93500
[97] Zytkow, J. M., Model construction: Elements of a computational mechanism, (Proc. Conference on Creativity, Edinburgh (1999))
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.