Compositional Modeling for Spatial Problems

Solving a problem about a complex physical system generally involves the creation and execution of a model needed to reason about the problem. Effective problem solving about a physical system requires the use of an adequate model, the creation of which in turn depends on the types of knowledge available for the physical system and their representation. Such a model is normally created by the person studying the system, but a hand-crafted model is often error-prone. Modifying a hand-crafted model to solve a similar problem about other physical systems is also difficult, and may take more time than building a new model for the systems. My research has two main goals: (1) automating the construction and execution of models of physical systems for spatial problems, where objects are related to each other either geometrically or topologically to satisfy a set of constraints on the physical systems; and (2) making the modeling process general so that common domain theories can be shared and reused instead of being duplicated. This dissertation focuses on two subclasses of spatial problems - problems about the physical phenomena of motion of mechanical systems and RNA secondary structure (folding). I have made important progress in automating the model-building and simulation process for the physical phenomena by developing new methods which use knowledge from physics laws, biological principles, and other sources. The methods have a common characteristic framework at a high level which analyzes a problem, searches for model fragments relevant to the problem, constructs a model with them, and applies the model to solve the problem. The model fragments for the model of motion represent knowledge in a purely declarative, algorithm independent form; most knowledge is just the same fundamental equations that appear in any standard text on the subject. The model fragments for the model of folding are structural elements. The methods have been implemented in working programs and tested in the domains of mechanical devices, sailboats, and RNA molecules. Experimental results show that the methods are capable of automatically generating correct behavioral or structural models of several different types of physical systems which involve motion or folding.Technical report DCS-TR-30