Stochastic Analysis of Qualitative Dynamics

Abstract

We extend qualitative reasoning with estimations of the relative likelihoods of the possible qualitative behaviors. We estimate the likelihoods by viewing the dynamics of a system as a Markov chain over its transition graph. This corresponds to adding probabilities to each of the transitions. The transition probabilities follow directly from theoretical considerations in simple cases. In the remaining cases, one must derive them empirically from numeric simulations, experiments, or subjective estimates. Once the transition probabilities have been estimated, the standard theory of Markov chains provides extensive information about asymptotic behavior, including a partition into persistent and transient states, the probabilities for ending up in each state, and settling times. Even rough estimates of transition probabilities provide useful qualitative information about ultimate behaviors, as the analysis of many of these quantities is insensitive to perturbations in the probabilities. The algorithms are straightforward and require time cubic in the number of qualitative states. The analysis also goes through for symbolic probability estimates, although at the price of exponential-time worst-case performance. 1