Dissertation Abstracts

Creating and Utilizing Symbolic Representations of Spatial Knowledge using Mobile Robots

Patrick Beeson. 2008. Creating and Utilizing Hybrid Representations of Spatial Knowledge using Mobile Robots.
Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.


A map is a description of an environment allowing an agent---a human, or in our case a mobile robot---to plan and perform effective actions. From a single location, an agent's sensors can not observe the whole structure of a complex, large environment. For this reason, the agent must build a map from observations gathered over time and space. We distinguish between large-scale space, with spatial structure larger than the agent's sensory horizon, and small-scale space, with structure within the sensory horizon.

We propose a factored approach to mobile robot map-building that handles qualitatively different types of uncertainty by combining the strengths of topological and metrical approaches. Our framework is based on a computational model of the human cognitive map; thus it allows robust navigation and communication within several different spatial ontologies. Our approach factors the mapping problem into natural sub-goals: building a metrical representation for local small-scale spaces; finding a topological map that represents the qualitative structure of large-scale space; and (when necessary) constructing a metrical representation for large-scale space using the skeleton provided by the topological map.

The core contributions of this thesis are a formal description of the Hybrid Spatial Semantic Hierarchy (HSSH), a framework for both small-scale and large-scale representations of space, and an implementation of the HSSH that allows a robot to ground the large-scale concepts of place and path in a metrical model of the local surround. Given metrical models of the robot's local surround, we argue that places at decision points in the world can be grounded by the use of a primitive called a gateway. Gateways separate different regions in space and have a natural description at intersections and in doorways. We provide an algorithmic definition of gateways, a theory of how they contribute to the description of paths and places, and practical uses of gateways in spatial mapping and learning.

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.


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.


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.

The Constructivist Learning Architecture: A Model of Cognitive Development for Robust Autonomous Robots

Harold Henry Chaput. 2004. The Constructivist Learning Architecture: A Model of Cognitive Development for Robust Autonomous Robots.
Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin, August 2004.


Autonomous robots are used more and more in remote and inaccessible places where they cannot be easily repaired if damaged or improperly programmed. A system is needed that allows these robots to repair themselves by recovering gracefully from damage and adapting to unforeseen changes. Newborn infants employ such a system to adapt to a new and dynamic world by building a hierarchical representation of their environment. This model allows them to respond robustly to changes by falling back to an earlier stage of knowledge, rather than failing completely. A computational model that replicates these phenomena in infants would afford a mobile robot the same adaptability and robustness that infants have. This dissertation presents such a model, the Constructivist Learning Architecture (CLA), that builds a hierarchical knowledge base using a set of interconnected self-organizing learning modules. The dissertation then demonstrates that CLA (1) replicates current studies in infant cognitive development, (2) builds sensorimotor schemas for robot control, (3) learns a goal-directed task from delayed rewards, and (4) can fall back and recover gracefully from damage. CLA is a new approach to robot control that allows robots to recover from damage or adapt to unforeseen changes in the environment. CLA is also a new approach to cognitive modeling that can be used to better understand how people learn for their environment in infancy and adulthood.

Solving Complexity and Ambiguity Problems within Qualitative Simulation

Daniel J. Clancy. 1997. Solving Complexity and Ambiguity Problems within Qualitative Simulation.
Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin, December 1997.


Qualitative simulation is used to reason about the behavior of imprecisely defined dynamical systems for tasks such as monitoring, diagnosis, or design. Often, however, simulation of complex dynamical systems results in either an intractable simulation or an ambiguous behavioral description. These results have caused concern regarding the scalability of techniques based upon qualitative simulation to real-world problems. Two different approaches are used to solve these problems: 1) abstraction and problem decomposition techniques are used during simulation to focus on relevant distinctions thus reducing the overall complexity of the simulation; and 2) the expressiveness of the modeling language is extended to allow the modeler to incorporate additional information.

Model decomposition and simulation (DecSIM) uses a component-based simulation algorithm to reason about the complex interactions within a sub-system independent of the interactions between subsystems. Variables within the model are partitioned into closely related components and a separate behavioral description is generated for each component. Links are maintained between related components to ensure that all of the constraints in the model are satisfied. DecSIM results in exponential speed-up for models that lend themselves to decomposition. Furthermore, DecSIM is guaranteed to generate a behavioral description that is equivalent to the description generated by a standard QSIM simulation modulo the temporal ordering of events for variables in separate components.

A common source of irrelevant distinctions within qualitative simulation is intractable branching due to chatter. Chatter occurs when the derivative of a variable is constrained only by continuity within a restricted region of the state space. We present two different abstraction techniques that completely eliminate the problem of chatter by abstracting a chattering region into a single abstract state. Both techniques retain the QSIM soundness guarantee and eliminate all instances of chatter without over-abstracting.

To address the problem of an ambiguous behavioral description, Temporally Constrained QSIM (TeQSIM) integrates temporal logic model checking into the qualitative simulation process allowing the modeler to specify behavioral information via trajectory constraints. Trajectory constraints, specified using an extension of a propositional linear-time temporal logic, can be used to focus the simulation, simulate non-autonomous systems and reason about boundary condition problems.

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.


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.


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 a physical 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 description 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.


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.


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 compute this 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 acquisition 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.


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.


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.


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.

Computational Perceptual Attention

Micheal Hewett. 2001. Computational Perceptual Attention.
Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin, May 2001.


This dissertation describes CPA, a general-purpose mechanism for expressing and implementing attention policies that control the allocation of resources among sensory processing tasks in a robot or other advanced intelligent system. A wide variety of attention policies can be expressed in this mechanism, which also supports soft real-time constraints on perceptual processing.

Intelligent systems can become inundated with data, resulting in perceptual overload and a consequent inability to formulate a timely or appropriate response. Perceptual overload is often modulated by a perceptual attention mechanism that filters and prioritizes incoming data. Most existing attention mechanisms are tailored to the specific task the system is performing. A general-purpose attention mechanism must have a task-independent interface for controlling attention; support a heterogeneous set of sensors; support heterogeneous methods for processing sensor data; and support real-time throughput constraints.

The CPA is a general-purpose attention mechanism that supports multimodal perceptual attention. Using it, an intelligent system can enact and control a variety of attention policies for any type or combination of sensor or sensor data. An intelligent system dynamically creates multiple heterogeneous perception tasks in accord with behavioral goals and installs them in the CPA. The CPA supports two general categories of perception tasks: detectors, which do not retain information between perception cycles; and trackers, which do. Perception tasks are prioritized using an attention policy and are executed using a priority-based scheduler. A wide range of attention policies can be expressed in this mechanism, including policies that dynamically modify perception priorities, policies in which emergency input overrides normal perception processing, and policies that dynamically change the level of resistance to perceptual distractions.

Results show that perception intervals as short as 100 milliseconds can be achieved with a five-sensor robot under a variety of attention policies. Analysis of the system's performance under perceptual load shows that qualitatively different attention policies can be realized in the attention mechanism. We show that intelligent systems can use the CPA to implement the four primary characteristics of human perceptual attention: selective attention, sustained attention, divided attention, and top-down control.

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.


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.


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 implementation.

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.


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.

Following Natural Language Route Instructions

Matt MacMahon. 2007. Following Natural Language Route Instructions.
Doctoral dissertation, Electrical and Computer Engineering Department, The University of Texas at Austin.


Following natural language instructions requires transforming language into situated conditional action; robustly following instructions, despite the director's natural mistakes and omissions, requires the pragmatic combination of language, action, and domain knowledge. This dissertation demonstrates a software agent that parses, models and executes human-written natural language instructions to accomplish complex navigation tasks. We compare the performance against people following the same instructions. By selectively removing various syntactic, semantic, and pragmatic abilities, this work empirically measures how often these abilities are necessary to correctly navigate along extended routes through unknown, large-scale environments to novel destinations.

To study how route instructions are written and followed, this work presents a new corpus of 1520 free-form instructions from 30 directors for 252 routes in three virtual environments. 101 other people followed these instructions and rated them for quality, successfully reaching and identifying the destination on only approximately two-thirds of the trials. Our software agent, MARCO, followed the same instructions in the same environments with a success rate approaching human levels. Overall, instructions subjectively rated 4 or better of 6 comprise just over half of the corpus; MARCO performs at 88% of human performance on these instructions. MARCO's performance was a strong predictor of human performance and ratings of individual instructions. Ablation experiments demonstrate that implicit actions are crucial for following verbal instructions using an approach integrating language, knowledge and action. Other experiments measure the performance impact of linguistic, execution, and spatial abilities in successfully following natural language route instructions.

Robot Developmental Learning of an Object Ontology Grounded in Sensorimotor Experience

Joseph Modayil. 2007. Robot Developmental Learning of an Object Ontology Grounded in Sensorimotor Experience.
Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.


How can a robot learn to conceptualize its environment in terms of objects and actions, starting from its intrinsic "pixel-level" sensorimotor interface? Several domains in artificial intelligence (including language, planning, and logic) rely on the existence of a symbolic representation that provides objects, relations, and actions. With real robots it is difficult to ground these high-level symbolic representations, because hand-written object models and control routines are often brittle and fail to account for the complexities of the real world. In contrast, developmental psychologists describe how an infant's naive understanding of objects transforms with experience into an adult's more sophisticated understanding. Can a robot's understanding of objects develop similarly?

This thesis describes a learning process that leads to a simple and useful theory of objects, their properties, and the actions that apply to them. The robot's initial "pixel-level" experience consists of a range-sensor image stream and a background model of its immediate surroundings. The background model is an occupancy grid that explains away most of the range-sensor data using a static world assumption. To this developing robot, an "object" is a theoretical construct abduced to explain a subset of the robot's sensorimotor experience that is not explained by the background model.

This approach leads to the Object Perception and Action Learner (OPAL). OPAL starts with a simple theory of objects that is used to bootstrap more sophisticated capabilities. In the initial theory, the sensor returns explained by an object have spatial and temporal proximity. This allows the robot to individuate, track, describe, and classify objects (such as a chair or wastebasket) in a simple scene without complex prior knowledge. The initial theory is used to learn a more sophisticated theory. First, the robot uses the perceptual representations described above to create structurally consistent object models that support object localization and recognition. Second, the robot learns actions that support planning to achieve object-based goals.

The combined system extends the robot's representational capabilities to include objects and both constant and time-varying properties of objects. The robot can use constant properties such as shape to recognize objects it has previously observed. It can also use time-varying properties such as location or orientation to track objects that move. These properties can be used to represent the learned preconditions and postconditions of actions. Thus, the robot can make and execute plans to achieve object-based goals, using the pre- and post-conditions to infer the ordering constraints among actions in the plan.

The learning process and the learned representations were evaluated with metrics that support verification by both the robot and the experimenter. The robot learned object shape models that are structurally consistent to within the robot's sensor precision. The learned shape models also support accurate object classification with externally provided labels. The robot achieved goals specified in terms of object properties by planning with the learned actions, solving tasks such as facing an object, approaching an object, and moving an object to a target location. The robot completed these tasks both reliably and accurately.

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.


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.

Reinforcement Learning in High-Diameter, Continuous Environments

Jefferson Provost. 2007. Reinforcement Learning in High-Diameter, Continuous Environments.
Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.


Many important real-world robotic tasks have high diameter, that is, their solution requires a large number of primitive actions by the robot. For example, they may require navigating to distant locations using primitive motor control commands. In addition, modern robots are endowed with rich, high-dimensional sensory systems, providing measurements of a continuous environment. Reinforcement learning (RL) has shown promise as a method for automatic learning of robot behavior, but current methods work best on low-diameter, low-dimensional tasks. Because of this problem, the success of RL on real-world tasks still depends on human analysis of the robot, environment, and task to provide a useful set of perceptual features and an appropriate decomposition of the task into subtasks.

This thesis presents Self-Organizing Distinctive-state Abstraction (SODA) as a solution to this problem. Using SODA a robot with little prior knowledge of its sensorimotor system, environment, and task can automatically reduce the effective diameter of its tasks. First it uses a self-organizing feature map to learn higher level perceptual features while exploring using primitive, local actions. Then, using the learned features as input, it learns a set of high-level actions that carry the robot between perceptually distinctive states in the environment.

Experiments in two robot navigation environments demonstrate that SODA learns useful features and high-level actions, that using these new actions dramatically speeds up learning for high-diameter navigation tasks, and that the method scales to large (building-sized) robot environments. These experiments demonstrate SODAs effectiveness as a generic learning agent for mobile robot navigation, pointing the way toward developmental robots that learn to understand themselves and their environments through experience in the world, reducing the need for human engineering for each new robotic application.

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.


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.

Task Encoding, Motion Planning and Intelligent Control with Qualitative Models

Subramanian Ramamoorthy. 2007. Task Encoding, Motion Planning and Intelligent Control with Qualitative Models.
Doctoral dissertation, Electrical and Computer Engineering Department, The University of Texas at Austin.


This dissertation addresses the problem of trajectory generation for dynamical robots operating in unstructured environments in the absence of detailed models of the dynamics of the environment or of the robot itself. We factor this problem into the subproblem of task variation, and the subproblem of imprecision in models of dynamics.

The problem of task variation is handled by defining task level control strategies in terms of qualitative models that support structurally stable phase space trajectories. Such models define low-dimensional spaces within which it is possible to select trajectories that constitute plans for achieving a desired goal.

The second problem, that of model imprecision, arises when embedding the resulting trajectories in the phase space of the more complex higher-dimensional system that actually performs the task of interest. Trajectories in the high-dimensional phase space that are compatible with the low-dimensional plan are restricted to lie on a manifold. In the absence of analytical models of the high-dimensional dynamics, this manifold may be approximated using observed data generated by a randomized exploration of the state space. Approximations driven by such an imperfect set of observations can lead to spurious trajectories, but this problem is solved by regularizing the approximation using the low-dimensional model.

This methodology is developed through a sequence of design problems. First, basic notions regarding control with qualitative models are clarified through the design of a global controller for the inverted pendulum and cart-pole systems. This is followed by the more challenging problem of dynamic bipedal walking on irregular terrain, which is the primary motivating problem for this dissertation. Our solution to the dynamic walking problem advances the state of the art by simultaneously achieving several important properties. Our algorithm generates trajectories to walk on irregular terrain, with only a qualitative model of the dynamics of the robot, and with energy usage comparable with actuated walkers utilizing passive dynamic principles.

Although the definition of tasks in terms of structurally stable orbits and manifolds is very natural when talking about physical systems, this representation yields benefits in more artificial domains as well. This is demonstrated through the example of spatiotemporal control of polygonal shapes, such as in a robot collective.

A Logical Account of Causal and Topological Maps

Emilio Remolina. 2001. A Logical Account of Causal and Topological Maps.
Doctoral dissertation, Department of Computer Sciences, The University of Texas at Austin.


The Spatial Semantic Hierarchy (SSH) is a set of distinct representations for large scale space, each with its own ontology and each abstracted from the levels below it. At the control level, the agent and its environment are modeled as continuous dynamical systems whose equilibrium points are abstracted to a discrete set of distinctive states. The control laws whose execution defines trajectories linking these states are abstracted to actions, giving a discrete causal graph representation for the state space. The causal graph of states and actions is in turn abstracted to a topological network of places and paths (i.e. the topological map). Local metrical models of places and paths can be built within the framework of the control, causal and topological levels while avoiding problems of global consistency.

Most of the SSH's ideas have been traditionally described in procedural terms inspired by implementations of the SSH. This description has various problems when used to implement physical agents. First, some assumptions are not explicitly stated or are difficult to meet by current sensory technology (e.g. sensory information is not rich enough to distinguish one place from another). Second, some important SSH concepts (i.e. paths) are not properly defined or understood. Third, sometimes it is not clear what the representation states and consequently it is hard to apply it to new domains.

In this dissertation we propose a formal semantics for the SSH causal, topological and local metrical theories. Based on this semantics, we extend the SSH in the following important ways: i) we include distinctive states as objects of the theory and handle perceptual aliasing, ii) we define the models associated with the SSH causal and topological levels, iii) we extend the SSH topological theory to handle convergent and self intersecting paths as well as hierarchical maps , iv) we show how to combine causal, topological and noisy local metrical information, v) based on the previous enhancements, we define an algorithm to keep track of different topological maps consistent with the agent's experiences. This algorithm supports different exploration strategies and facilitates map disambiguation when the case arises.

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.


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.

[QR home]