System identification takes a space of possible models and a stream of observational data of a physical system, and attempts to identify the element of the model space that best describes the observed system. In traditional approaches, the model space is specified by a parameterized differential equation, and identification selects numerical parameter values so that simulation of the model best matches the observations. We present SQUID, a method for system identification in which the space of potential models is defined by a semi-quantitative differential equation (SQDE): qualitative and monotonic function constraints as well as numerical intervals and functional envelopes bound the set of possible models. The simulator SQSIM predicts semi-quantitative behavior descriptions from the SQDE. Identification takes place by describing the observation stream in similar semi-quantitative terms and intersecting the two descriptions to derive narrower bounds on the model space. Refinement is done by refuting impossible or implausible subsets of the model space. SQUID therefore has strengths, particularly robustness and expressive power for incomplete knowledge, that complement the properties of traditional system identification methods. We also present detailed examples, evaluation, and analysis of SQUID.
This article describes a method for representing and simulating Ordinary Differential Equation (ODE) systems which are imprecise -- that is, where the ODE model contains both parametric and functional uncertainty. Such models, while useful in engineering contexts, are not used in practice because they require either special structures which limit the describable uncertainty or produce predictions which are extremely weak. This article describes SQsim (for SemiQuantitative SIMulator), a system which provides a general language for representing and reasoning about many common types of engineering uncertainty. By defining the model both qualitatively and quantitatively and by using a simulation method that combines inferences across the qualitative-to-quantitative spectrum, SQsim produces predictions that maintain a precision consistent with the model imprecision.
Shortcomings of qualitative simulation and of quantitative simulation motivate combining them to do simulations exhibiting the strengths of both. The resulting class of techniques is called semi-quantitative simulation. One approach to semi-quantitative simulation is to use numerical intervals to represent incomplete quantitative information. In this research we demonstrate semi-quantitative simulation using intervals in an implemented semi-quantitative simulator called Q3. Q3 progressively refines a qualitative simulation, providing increasingly specific quantitative predictions which can converge to a numerical simulation in the limit while retaining important correctness guarantees from qualitative and interval simulation techniques.
Q3's simulations are based on a technique we call step-size refinement. While a pure qualitative simulation has a very coarse step size, representing the state of a system trajectory at relatively few qualitatively distinct states, Q3 interpolates newly explicit states between distinct qualitative states, thereby representing more states which instantiate new constraints, leading to improved quantitative inferences.
Q3's techniques have been used for prediction, measurement interpretation, diagnosis, and even analysis of the probabilities of qualitative behaviors. Because Q3 shares important expressive and inferential properties of both qualitative and quantitative simulation, Q3 helps to bridge the gap between qualitative and quantitative simulation.
Traditionally, qualitative simulation uses a global, state--based representation to describe the behavior of the modeled system. For larger, more complex systems this representation proves extremely inefficient since it provides a complete temporal ordering of all potential distinctions leading to a large, complex behavioral description that obscures relevant distinctions, or even fails to terminate. The model decomposition and simulation algorithm (DecSIM) uses a divide and conquer approach to qualitative simulation. Variables within the system are partitioned into components. Each component is viewed as a separate system and is simulated using a state--based representation limited to the variables within the component. Interactions between components are reasoned about separately. DecSIM provides a promising paradigm for qualitative simulation whose complexity is driven by the complexity of the problem specification rather than the inference mechanism used.
One of the major factors hindering the use of qualitative simulation techniques to reason about the behavior of complex dynamical systems is intractable branching due to a phenomenon called chatter. This paper presents two general abstraction techniques that solve the problem of chatter. Eliminating the problem of chatter significantly extends the range of models that can be tractably simulated using qualitative simulation. Chatter occurs when a variable's direction of change is constrained only by continuity within a region of the state space. This results in intractable, potentially infinite branching within the behavioral description due to irrelevant distinctions in the direction of change. While a number of techniques have been proposed to eliminate chatter, none of them provide a general solution that can eliminate all instances of chatter. {\em Chatter box abstraction} and {\em dynamic chatter abstraction} provide two such solutions to this problem. Both solutions eliminate chatter by abstracting the chattering region of the state space into a single qualitative state with an abstract direction of change. The algorithms differ in the manner in which they identify the chattering region of the state space.
One of the major factors hindering the use of qualitative simulation techniques to reason about the behavior of complex dynamical systems is intractable branching due to a phenomenon called chatter. This paper presents a general abstraction technique that provides a scalable solution to this problem. This technique is used to simulate models that previously could not be simulated to completion. Eliminating the problem of chatter significantly extends the range of models that can be tractably simulated using qualitative simulation. Chatter occurs when a variable's direction of change is constrained only by continuity within a region of the state space. This results in intractable, potentially infinite branching within the behavioral description due to irrelevant distinctions in the direction of change. While a number of techniques have been proposed to eliminate chatter, chatter box abstraction [Clancy and Kuipers, 1993] is the only one that provides a general solution that can eliminate all instances of chatter. Chatter box abstraction, however, explores the potentially chattering region of the state space via a restricted simulation that is exponential in the number of chattering variables. Dynamic chatter abstraction uses a similar abstraction technique; however, the potentially chattering region of the state space is explored via a dynamic analysis of the model and the current qualitative state using knowledge of the inference capability of the simulation algorithm. Thus, a scalable solution is provided that abstracts chattering regions of the state space into a single state within the behavioral description. The algorithm is described along with an empirical evaluation demonstrating that dynamic chatter abstraction eliminates all instances of chatter without over-abstracting. This evaluation also shows that the algorithm is significantly more efficient than chatter box abstraction and thus supports the simulation of more complex models.
One of the factors hindering the wide--spread application of qualitative simulation techniques is the difficulty encountered when developing a qualitative model. Analyzing the resulting behavioral description and revising the model in response to this analysis requires a significant amount of expertise and is often left up to the modeler. As a result, developing a qualitative model is difficult for users who are not familiar with the field. Furthermore, this process is often not addressed within the literature making it difficult for such a user to obtain the necessary expertise except through trial and error. This paper addresses the process of model revision and presents a set of tools and methods to assist in the performance of this task. It also demonstrates how qualitative simulation can be used to obtain a more detailed understanding of the dynamical properties of the modeled system. The tools presented help the modeler extract information from a complex behavioral description by providing alternative views of the description, allowing the modeler to perform a focused search of the potential state space and providing explanation facilities for the branches occuring within the description. These tools and the methods are discussed with respect to the development of a semi--quantitative model of a controller for a tank.