Taming intractable branching in qualitative simulation

Qualitative simulation of behavior from structure is a valuable method for reasoning about partially known physical systems. Unfortunately, in many realistic situations, a qualitative description of structure is consistent with an intractibly large number of behavioral predictions. We present two complementary methods, representing different trade-offs between generality and power, for taming an important case of intractible branching. The first method applies to the most general case of the problem. It changes the level of the behavioral description to aggregate an exponentially exploding tree of behaviors into a few distinct possibilities The second method draws on additional mathematical knowledge, and assumptions about the smoothness of partially known functional relationships, to derive a correspondingly stronger result. Higher-order derivative constraints are automatically derived by manipulating the structural constraint model algebraically, and applied to eliminate impossible branches These methods have been implemented as extensions to QSIM and tested on a substantial number of examples They move us significantly closer to the goal of reasoning qualitatively about complex physical system