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 Dissertation Abstracts

Dissertation Abstracts



The Use of Partial Quantitative Information with Qualitative Reasoning

Daniel Berleant. 1991. The Use of Partial Quantitative Information with Qualitative Reasoning Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.

Abstract

There is a need for combining qualitative and quantitative simulations, to do simulation tasks that would be difficult using either alone. This task is made more difficult by the fact that available quantitative information may be incomplete, bounding values with intervals or describing them with probability distribution functions. This research demonstrates the combination of qualitative and quantitative simulation in an implemented system, Q3. Q3 utilizes partial or complete quantitative information, to gradually refine a qualitative simulation into a simulation that has properties and advantages of both qualitative simulations and quantitative ones.

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.


Spatial Learning Mobile Robots with a Spatial Semantic Hierarchical Model

Yung-Tai Byun. 1990. Spatial Learning Mobile Robots with a Spatial Semantic Hierarchical Model Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.

Abstract

The goal of this dissertation is to develop a spatial exploration and map-learning strategy for a mobile robot to use in unknown, large-scale environments. Traditional approaches aim at building purely metrically accurate maps. Because of sensorimotor errors, it is hard to construct accurately such maps. However, in spite of sensory and computation limitation, humans explore environments, build cognitive maps from exploration, and successfully path-plan, navigate, and place-find. Based on the study of human cognitive maps, we develop a spatial semantic hierarchical model to replace the global absolute coordinate frame used in traditional approaches. The semantic hierarchical model consists of three levels: control level, topological level, and geometrical level. The topological level provides the basic structure of the hierarchy.

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.


Access-Limited Logic -- A Language for Knowledge Representation

James Crawford. 1990. Access-Limited Logic -- A Language for Knowledge Representation Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.

Abstract

Access-Limited Logic (ALL) is a language for knowledge representation which formalizes the access limitations inherent in a network structured knowledge-base. Where a deductive method such as resolution would retrieve all assertions that satisfy a given pattern, an access-limited logic retrieves all assertions reachable by following an available access path. The time complexity of inference is thus a polynomial function of the size of the accessible portion of the knowledge-base, rather than the size of the entire knowledge-base. Access-Limited Logic, though incomplete, still has a well defined semantics and a weakened form of completeness, Socratic Completeness, which guarantees that for any query which is a logical consequence of the knowledge-base, there exists a series of queries after which the original query will succeed. We have implemented ALL in Lisp and it has been used to build several non-trivial systems, including versions of Qualitative Process Theory and Pearl's probability networks. ALL is a step toward providing the properties - clean semantics, efficient inference, expressive power - which will be necessary to build large, effective knowledge bases.


Monitoring and Diagnosis of Continuous Dynamic Systems Using Semiquantitative Simulation

Daniel Louis Dvorak. 1992. Monitoring and Diagnosis of Continuous Dynamic Systems Using Semiquantitative Simulation Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.

Abstract

Operative diagnosis or diagnosis of a physical system in operation, is essential for systems that cannot be stopped every time an anomaly is detected, such as in the process industries, space missions, and medicine. Compared to maintenance diagnosis where the system is offline and arbitrary points can be probed, operative diagnosis is limited mainly to sensor readings, and diagnosis begins while the effects of a fault are still propagating. Symptoms change as the system's dynamic behavior unfolds.

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.


Automated Modeling of Physical Systems in the Presence of Incomplete Knowledge

Adam Farquhar. 1993. Automated Modeling of Physical Systems in the Presence of Incomplete Knowledge Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.

Abstract

This dissertation presents an approach to automated reasoning about physical systems in the presence of {\em incomplete knowledge} which supports formal analysis, proof of guarantees, has been fully implemented, and applied to substantial domain modeling problems. Predicting and reasoning about the behavior of physical systems is a difficult and important task that is essential to everyday commonsense reasoning and to complex engineering tasks such as design, monitoring, control, or diagnosis.

A capability for automated modeling and simulation requires

In order to clarify the structure of the knowledge required for reasoning about the behavior of physical systems, we distinguish between the model building task which builds a model to describe the system, and the simulation task which uses the model to generate a description of the possible behaviors of the system.

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.


A Theory of Teleology

David Wayne Franke. 1993. A Theory of Teleology Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.

Abstract

A representation language for teleological descriptions, or descriptions of purpose, is defined. The teleological language, TeD, expresses the descriptions of purpose in terms of design modifications that guarantee the satisfaction of design specifications. These specifications express potential behaviors the designed artifact should or should not exhibit. We define an abstraction relation on behavior and implement model checking and classification algorithms that computethis abstraction relation. The model checking algorithm determines whether or not a behavior satisfies a specification. The classification algorithm provides effective indexing of behaviors and teleological descriptions. We implement an acquistion technique for teleological descriptions and demonstrate how teleological descriptions can subsequently be used in diagnosis, explanation, case-based reasoning, design by analogy, and design reuse.

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.


High-Speed Navigation with Approximate Maps

Richard Allan Froom. 1995. High-Speed Navigation with Approximate Maps. Ph.D. Dissertation, The University of Texas at Austin.

Abstract

A global map of a mobile robot's environment is essential for high-performance navigation in large-scale space. When portions of the environment are not visible, a map is needed for route planning and enables high performance by allowing the robot to anticipate regions that are occluded or beyond sensor range. Yet, autonomously acquired global map information is inevitably uncertain due to the low positioning accuracy of mobile robots and the possibility of changes to the environment.

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.


Automatic Control Understanding for Natural Programs

John Hartman. 1991. Automatic Control Understanding for Natural Programs Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.

Abstract

Program understanding involves recognizing abstract concepts like "read-process loop" in existing programs. Programmers spend much of their time understanding programs, so studying and automating the process has many benefits.

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.


Geometrical Motion Planning for Highly Redundant Manipulators Using a Continuous Model

Akira Hayashi. 1991. Geometrical Motion Planning for Highly Redundant Manipulators Using a Continuous Model Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.

Abstract

There is a need for highly redundant manipulators to work in complex, cluttered environments. Our goal is to plan paths for such manipulators efficiently.

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.


Refining Imprecise Models and Their Behaviors

Herbert Kay. 1996. Refining Imprecise Models and Their Behaviors. Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin, December 1996.

Abstract

This dissertation describes methods for simulating and refining imprecisely-defined Ordinary Differential Equation (ODE) systems. When constructing a model of a physical process, a modeler must cope with uncertainty due to incomplete knowledge of the process. For tasks such as design and diagnosis, the effects of this uncertainty must be considered. However, predicting the behavior of an imprecisely-defined model is not easy since the model covers a space of many precise instances, each of which behaves differently.

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.


Spatial Semantic Hierarchy for a Physical Mobile Robot

Wan Yik Lee. 1996. Spatial Semantic Hierarchy for a Physical Mobile Robot. Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin, December 1996.

Abstract

This dissertation describes research to extend and improve the Spatial Semantic Hierarchy (SSH) approach to robot exploration and mapping, and to demonstrate and evaluate its effectiveness in controlling physical mobile robots.

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.


A Qualitative Simulation Based Method To Construct Phase Portraits

Wood Wai Lee. 1993. A Qualitative Simulation Based Method To Construct Phase Portraits Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.

Abstract

We have designed a qualitative simulation based method to construct phase portraits for a significant class of systems of two first order autonomous differential equations. It is intended as a step toward automated understanding of continuous physical systems. Differential equation models are powerful tools for reasoning about physical systems, but they typically require precise information about systems. Recently developed methods for qualitative simulation make it possible to predict all possible behaviors consistent with a state of incomplete, qualitative knowledge of the world, expressed as a qualitative differential equation (QDE). However, qualitative simulation can fail due to intractable branching, and spurious predictions. The field of nonlinear dynamics has introduced the phase portrait representation as a powerful tool for the global analysis of nonlinear differential equations. A state of the system is represented by a point in phase space; its behavior over time is represented by a trajectory. When the phase portrait is two-dimensional, the solutions to a differential equation can be characterized by the system's fixed points, bundles of adjacent trajectories (called flows), and certain bounding trajectories. Numeric methods for constructing phase portraits require numerically specific information about the system. We demonstrate a method and an implemented program, QPORTRAIT, that constructs two-dimensional phase portraits from QDE's. Starting with the total envisionment (a finite transition-graph representation of the possible behaviors of a system), QPORTRAIT progressively identifies, classifies, and combines features of the phase portrait, abstracting away uninteresting distinctions, and filtering out inconsistent combinations of features. Because each step in the analysis is validity-preserving, the prediction is guaranteed to cover all real phase portraits consistent with QDE. In its current form QPORTRAIT phase applies to a restricted but nontrivial set of QDE models. It requires that all fixed-points be non degenerate, and be at landmark values for the phase variables. QPORTRAIT has produced tractable results when applied to qualitative generalizations of several well-known nonlinear systems. Guaranteed coverage of the behavior of a qualitatively described set of QDE's complements the precision of numeric methods based approaches.


Map Learning with Uninterpreted Sensors and Effectors

David M. Pierce. 1995. Map Learning with Uninterpreted Sensors and Effectors. Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.

Abstract

This dissertation presents a set of methods by which a learning agent, called a ``critter,'' can learn a sequence of increasingly abstract and powerful interfaces to control a robot whose sensorimotor apparatus and environment are initially unknown. The result of the learning is a rich, hierarchical model of the robot's world (its sensorimotor apparatus and environment). The learning methods rely on generic properties of the robot's world such as almost-everywhere smooth effects of actions on sensory features.

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.


Qualitative Reasoning about Dynamic Change in the Spatial Properties of a Physical System

Raman Rajagopalan. 1995. Qualitative reasoning about dynamic change in the spatial properties of a physical system. Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.

Abstract

Spatial reasoning is an essential part of human interaction with the physical world. Of the many models that have been developed to support automated spatial reasoning, most rely on numerical descriptions of a spatial scene. This dissertation addresses problems where only qualitative descriptions of a spatial scene are available, such as natural language understanding, qualitative design, and physics problem-solving.

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.


Model-Based Diagnosis of Complex, Continuous Mechanisms

David Rutherford Throop. 1991. Model-Based Diagnosis of Complex, Continuous Mechanisms Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.

Abstract

In diagnosis, when a hypothesis proposes a variable's value, several different lines of evidence may be considered; the different evidence must be arbitrated. The result of this arbitration consists of a single best estimate of the variable value and of a measure of that estimate's plausibility. The plausibility measure reflects the degree of agreement among the lines of evidence.

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.