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