MIME-Version: 1.0 Server: CERN/3.0 Date: Tuesday, 07-Jan-97 15:51:07 GMT Content-Type: text/html Content-Length: 35995 Last-Modified: Monday, 18-Nov-96 16:14:57 GMT
The technique exemplified by Q3 is shown to possess properties often used in analyzing both qualitative and quantitative simulators. Qualitative and quantitative inferences are correct. Theoretical convergence to the true solution and stability in the presence of partial model inputs are also shown.
Q3 has been applied to the problem of finding probabilities of qualitative behaviors, an important problem. Partial quantitative characterization of model inputs, in the form of intervals and probability distributions, may be used to bound the probabilities of different behaviors. This is demonstrated for simple models including one in the dependability analysis application domain.
At the control level, a robot finds places or follows travel edges which can be described by qualitatively definable features. The distinctive features allow development of distinctiveness measures. The robot uses these measures to find, with negative feedback control, the distinctive places by hill-climbing search algorithms, and the travel edges by edge-following algorithms. Distinctive places and travel edges are connected to build a topological model. This model is created prior to the construction of a global geometrical map. Cumulative location error is essentially eliminated while traveling among distinctive places and travel edges by alternating between the hill-climbing search control algorithms and the edge-following control algorithms. On top of the topological model, metrical information is accumulated first locally and then globally.
Using a simulation package with a robot instance, NX, we demonstrate the robustness of our method against sensorimotor errors. The control knowledge for distinctive places and travel edges, the topological matching process, and the metrical matching process with local geometry make our approach robust in the face of metrical errors. In addition to robust navigation at the control and topological levels, our framework can incorporate certain metrically-based methods and thus provide the best of both approaches.
This paper presents a design for monitoring and diagnosis of deterministic continuous dynamic systems based on the paradigms of "monitoring as model corroboration" and "diagnosis as model modification" in which a semiquantitative model of aphysical system is simulated in synchrony with incoming sensor readings. When sensor readings disagree with predictions, variant models are created representing different fault hypotheses. These models are then simulated and either corroborated or refuted as new readings arrive. The set of models changes as new hypotheses are generated and as old hypotheses are exonerated. In contrast to methods that base diagnosis on a snapshot of behavior, this simulation-based approach exploits the system's time-varying behavior for diagnostic clues and exploits the predictive power of the model to forewarn of imminent hazards.
The design holds several other advantages over existing methods: 1) semiquantitative models provide greater expressive power for states of incomplete knowledge than differential equations, thus eliminating certain modeling compromises; 2) semiquantitative simulation generates guaranteed bounds on variables, thus providing dynamic alarm thresholds and thus fewer fault detection errors than with fixed-threshold alarms; 3) the guaranteed prediction of all valid behaviors eliminates the "missing prediction bug" in diagnosis; 4) the branching-time descruption of behavior permits recognition of all valid manifestations of a fault (and of interacting faults); 5) hypotheses based on predictive semiquantitative models are more informative because they show the values of unseen variables and can predict future consequences; and 6) fault detection degrades gracefully as multiple faults are diagnosed over time.
A capability for automated modeling and simulation requires
This dissertation describes QPC, an implemented approach to reasoning about physical systems that builds on the expressiveness of Qualitative Process Theory [Forbus, 1984] and the mathematical rigor of the QSIM qualitative simulation algorithm [Kuipers, 1986].
The semantics of QPC's modeling language are grounded in the mathematics of ordinary differential equations and their solutions. This formalization enables the statement and proof of QPC's correctness. If the domain theory is adequate and the initial description of the system is correct, then the actual behavior of the system must be in the set of possible behaviors QPC predicts.
QPC has been successfully applied to problems in Botany and complex examples drawn from Chemical Engineering, as well as numerous smaller problems. Experience has shown that the modeling language is expressive enough to describe complex domains and that the inference mechanism is powerful enough to predict the behavior of substantial systems.
We demonstrate the behavior language, teleology language, acquisition of teleological descriptions, and application of teleological descriptions in explanation, diagnosis, and design reuse via examples in the thermal, hydraulic, electrical, and mechanical domains. We define additional teleological operators that express purposes like prevent, order, synchronize, maintain, and regulate, demonstrating the ability to represent common human-generated descriptions of purpose in TeD. Expressing the purpose of preventing an undesirable behavior is unique to TeD, and is an example of TeD's ability to express purposes regarding missing behaviors and components removed from a design.
The teleology language developed in this work represents a significant advance over previous work by providing a formal language that 1) is independent of any particular domain of mechanisms or behavior language, 2) can be effectively acquired during the design process, and 3) provides an effective means of classifying and indexing teleological descriptions.
Previous work in high-speed navigation falls into two categories. Global optimization approaches assume that an accurate model of environment geometry and robot dynamics are available, and address the problem of efficiently approximating the minimum-time control between a start and goal state. Reactive navigation methods use only immediately sensed environment geometry to avoid obstacles while moving to a specified goal position. The global optimization approach has the theoretical advantage of high performance, but it does not address the significant uncertainty typical of mobile robots. The reactive navigation approach can respond to unanticipated geometry, but its overall performance is limited.
This dissertation describes a method for high-speed map-guided navigation in realistic conditions of uncertainty. A previously-developed method is used to acquire a topologically correct, metrically approximate map of the environment despite positioning errors. Information in the approximate map guides the operation of a novel, high-performance reactive navigator. Performance does not critically depend on the availability of expensive, accurate metrical information. Nonetheless, the map may be elaborated with more detailed information, and, as its level of detail and accuracy is improved, performance smoothly improves.
Programming plans are units of programming knowledge connecting abstract concepts and their implementations. Existing research assumes that plan instances can be recognized to recover the programmer's abstract concepts and intentions, but this approach has not been confirmed empirically.
We present a practical method for bottom-up control concept recognition in large, unstructured imperative programs. Control concepts are abstract notions about interactions between control flow, data flow and computation, such as "do loop", "read process loop", and "bounded linear search". They are recognized by comparing an abstract program representation against a library of standard implementation plans. The program representation is a hierarchical control flow/data flow graph decomposed into a tree of sub-models using propers (single entry/exit control flow sub-graphs). Plans are represented by similar graphs with added qualifications. Recognition is based on simple matching between sub-models and plans. The method was implemented in the UNPROG program understander and tested with Cobol and Lisp source programs.
This method is robust, efficient, and scalable. The program representation can be formed for all language constructs which permit static determination of control and data flow. Comparing sub-models and comparisons increases linearly with program size.
UNPROG has been applied to automatic Cobol restructuring. Knowledge associated with plans and concepts permits more specific and insightful transformation, code generation, and documentation than is possible with syntactic methods. Control understanding can similarly raise the level of other reverse engineering and re-engineering tools for applications like analysis, documentation, and translation.
We also showed how our method and UNPROG can be used for empirical study of programs at the conceptual level. Results can be used to improve recognizer performance, acquire plans, catalog natural plans and concepts, test the hypothesis that programs are planful, and characterize program populations.
The path planning problem has been shown to be PSPACE-complete in terms of the number of degrees of freedom (DOF) of the manipulator. We present a method which overcomes the complexity with a strong heuristic: utilizing redundancy by means of a continuous manipulator model. The continuous model allows us to change the complexity of the problem from a function of both the DOF of the manipulator (believed to be exponential) and the complexity of the environment (polynomial), to a polynomial function of the complexity of the environment only.
The power of the continuous model comes from the ability to decompose the manipulator into segments, with the number, size, and boundaries of the segments, varying smoothly and dynamically. First, we develop motion schemas for the individual segments to achieve a basic set of goals in open and cluttered space. Second, we plan a smooth trajectory through free space for a point robot with a maximum curvature constraint. Third, the path generates a set of position subgoals for the continuous manipulator which are achieved by the basic motion schemas. Fourth, the mapping from the continuous model to an available jointed arm provides the curvature bound and obstacle envelopes required (in step 2) to guarantee a collision-free path.
The validity of the continuous model approach is also supported by an extensive simulation which we performed. While the simulation has been performed in 2-D, we show a natural extension to 3-D for each technique we have implemented for the 2-D simulation.
While model uncertainty cannot be completely eliminated, it is possible to reduce it. Model refinement uses observations of a physical process to rule out portions of the model space that could not have produced the observations. As more experience with the physical process is gained, the imprecision in the model is further reduced.
This dissertation describes three methods for reasoning with imprecise ODE models. SQSim is a simulator that produces a guaranteed bound on the behavior of an imprecise ODE model. By using a multiple-level representation and inference methods that span the qualitative-to-quantitative spectrum, SQSim produces predictions whose uncertainty is consistent with model imprecision. We demonstrate SQSim on a complex, nonlinear chemical process and compare it to other methods for simulating imprecise ODE models.
MSQUID is a function estimator for fitting (and bounding) noisy data that is known to be monotonic. It uses a neural-network inspired model and nonlinear constrained optimization to search a space of monotonic functions. We prove that MSQUID can estimate any monotonic function and show that it produces better estimates than does unconstrained optimization.
SQUID, which uses SQSim and MSQUID as components, is a system identification method that refines an imprecise model using a stream of observations from a physical process. SQUID uses refutation to rule out portions of the model space that are inconsistent with the observations. We show that this approach to refinement is significantly more efficient than parameter estimation for models with functional uncertainty and that it provides greater robustness in the face of uninformative observations.
The SSH approach for robot exploration and mapping was first developed in the context of a simulated robot, NX, and tested in simulated environments with very simple models of sensorimotor error. Physical implementations of aspects of the SSH approach have been built by other researchers but they do not provide adequate demonstration of its strengths or adequate analysis of its conditions of applicability.
The dissertation work extended and improved the SSH mapping theory from its original prototype to a version capable of handling real sensorimotor interaction with a real (office) environment. The underlying goal of this research is to demonstrate how symbolic representations and symbol-based behaviors of an autonomous robot can be grounded in non-symbolic, continuous sensorimotor interaction with a real environment through the SSH approach. The extended theory is implemented on a physical robot to explore a previously unknown environment, and to create an SSH spatial description of the environment. This dissertation describes the improved SSH mapping theory, the details of its implementation on a physical robot, and a demonstration and evaluation of several features of the implemention.
At the lowest level of the hierarchy, the critter analyzes the effects of its actions in order to define control signals, one for each of the robot's degrees of freedom. It uses a generate-and-test approach to define sensory features that capture important aspects of the environment. It uses linear regression to learn action models that characterize context-dependent effects of the control signals on the learned features. It uses these models to define high-level control laws for finding and following paths defined using constraints on the learned features. The critter abstracts these control laws, which interact with the continuous environment, to a finite set of actions that implement discrete state transitions. At this point, the critter has abstracted the robot's world to a finite-state machine and can use existing methods to learn its structure.
We provide the first set of solutions, given only a qualitative description of a spatial scene, for reasoning about dynamic change in both the spatial and non-spatial properties of a physical system. We use diagrams to compactly input the spatial scene for a problem, and text to describe any non-spatial properties. To match diagram and text objects so their descriptions can be integrated, we have developed a method for describing the conceptual class of objects directly in diagrams. Then, diagram and text objects can be matched based on their conceptual class.
The given problem is solved through qualitative simulation, and all spatial reasoning is done with respect to an extrinsic Cartesian coordinate system. We model the relative positions of objects through inequality constraints on the coordinates of the points of interest. Changes due to translational motion are detected by noting changes in the truth values of inequality constraints. We model the orientation of an object through knowledge of its extremal points and its qualitative angle of rotation with respect to each coordinate axis. This model has been used to reason qualitatively about the effects of rotational motion, such as changes in the area projected by one object onto another.
We have implemented our spatial representation as production rules and as model fragments in the QPC qualitative modeling system. The former has been used for solving static-world problems such as understanding descriptions of an urban scene. The latter has been used to reason about situations where changes in spatial properties play a critical role, such as the operation of transformers, oscillators, generators, and motors. To support dynamic spatial reasoning, we have expanded the modeling capabilities of QPC to include methods for modeling piecewise-continuous variables, non-permanent objects, and variables with circular quantity spaces.
This report describes HEATX, a program for model-based diagnosis of non-linear mechanisms with continuous variables. Previous work in model-based diagnosis has avoided arbitrating numeric evidence, often by representing continuous variables as discrete symbols (e.g., high, cold). Such restricted representation have had difficulty in diagnosing mechanisms with feedback or reconvergent fanout. HEATX represents numerical data explicitly in the hypotheses and in the inferencing procedures; it is thereby able to arbitrate evidence numerically.
HEATX uses both nonlinear numerical simulations and approximate linear models to perform diagnosis in the domain of heat-exchanger networks. The response of these networks to changes in their inputs is nonlinear; the networks also have feedback and reconvergent fanout. This dissertation introduces several novel techniques for diagnosing such networks. It interleaves the generation of complete fault hypotheses with several tests on partially formed hypotheses. Two of these tests are the qualitative filter and the clustering filter.
The qualitative filter analyzes the signs of gains between fault and symptom variables. The clustering filter constructs linear approximations to individual components and assembles these into a linear model of the network. It then uses the linear model to assess the consistency of a hypothesis. It does so by determining whether there is a value for the candidate fault variable which is consistent with the quantitative values of the symptom variables; the degree of agreement between the symptoms and best value for the fault variable is used to score the hypothesis. This filter is extended to multi-fault diagnosis, in which values for several fault variable may be estimated and judged simultaneously.