Comprehending Complex Behavior Graphs through Abstraction

Contents

Qualitative simulation is often a useful tool for studying the behavior of physical systems and has promise for providing automatic explanations of their behavior. However, in some cases it can overwhelm with detail. Behavior graphs with hundreds or thousands of states may obscure the basic patterns of behavior that a qualitative model was intended to explore. This paper describes an approach to comprehending complex behavior graphs by abstracting the behavior graph according to user-specified criteria that are simple and natural to provide. We present properties that an abstraction should meet to be faithful to the original behavior graph, prove necessary and sufficient operational conditions for an abstraction method to maintain these properties, and present a simple algorithm that incorporates these conditions and works for any behavior graph. We demonstrate on several externally-provided problems that our method can greatly simplify complex behavior graphs in number of states and behaviors while remaining faithful to the original behavior graph. It enables simple graphical output that can reveal underlying patterns of behavior that have not been apparent with previous methods, and shows promise for expanding the utility of qualitative reasoning for generating explanations.