Thesis Summary

I received my Ph.D. in Computer Sciences under the supervision of Prof. Benjamin Kuipers from the University of Texas at Austin in May 1993. My dissertation is titled Automated Reasoning about Physical Systems in the Presence of Incomplete Knowledge.

My dissertation research developed QPC (the qualitative physics compiler), an approach to and tools for automated reasoning about the behavior of physical systems in the presence of incomplete knowledge. This includes incomplete knowledge about parameter values, coefficients, and functional forms, as well as the entities that exist in the world, the relations among them, and the physical phenomena that affect them.

This is an important problem both because predicting the behavior of physical systems is essential for engineering tasks such as design, monitoring, control, or diagnosis, and also because our knowledge of such systems is always incomplete and imprecise. Other approaches to automatic model construction and simulation either require complete precise information about both the system and its initial conditions, or are unable to take advantage of initial conditions and are consequently unable to model large classes of complex systems.

An essential characteristic of QPC is the separation of the model building task, which builds a model to describe the system, and a simulation task, which uses the model to generate a description of the possible behaviors of the system. This decomposition substantially eases formal analysis and provides a practical implementation architecture.

Modeling knowledge is captured in a general purpose domain theory that describes related phenomena and systems. A domain theory consists of a set of quantified definitions, called model fragments, each of which describes some aspect of the domain, such as processes (liquid flows), devices (pumps), and objects (containers). A domain theory can be used to describe a wide range of physical systems under varying conditions. Each definition applies whenever there exists a set of participants for whom the stated conditions are satisfied. A specific system or situation being modeled is called a scenario. A model consists of fragments that logically follow from the domain theory and the scenario definition. A model is incomplete if there are model fragment instances that cannot be proven active or inactive. An incomplete model is refined into complete ones by making assumptions about the preconditions of model fragments. Each complete model is mapped into an initial value problem suitable for solution by the QSIM qualitative simulation engine. In case predicted behavior extends across the boundary of a single model's applicability, a new model of the resulting situation is constructed.

I show that the QPC algorithms will construct all complete models of a physical system. Given a sound simulation engine, such as QSIM, I show that every possible behavior of the physical system will be covered by the behaviors predicted by QPC.

Experience has shown that the QPC modeling language is expressive and the algorithms are powerful enough to provide useful behavioral predictions for a wide variety of systems. Researchers at several institutions have already used QPC to build domain models and predict behavior in numerous scenarios. At the University of Pennsylvania, Catino and Prof. Ungar have constructed a substantial chemical engineering domain theory; Catino has constructed models of a nitric acid processing plant with several hundred variables and over a hundred model fragments. At the University of Texas, Rickel has solved over a dozen problems of more moderate size in the domain of plant physiology, and Rajogapolan has constructed models for geometric and spatial reasoning. At the University of Udine, Italy, Prof. Brajnik has constructed models of lakes, damns, and turbines in the domain of water supply control.