Benjamin J. Kuipers

AIJ Journal 1997 Journal Article

Map learning with uninterpreted sensors and effectors

• David Pierce
• Benjamin J. Kuipers

This paper presents a set of methods by which a learning agent 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 motor control signals on sensory features. At the lowest level of the hierarchy, the learning agent analyzes the effects of its motor control signals in order to define a new set of 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 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 agent 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 agent has abstracted the robot's continuous world to a finite-state world and can use existing methods to learn its structure. The learning agent's methods are evaluated on several simulated robots with different sensorimotor systems and environments.

AIJ Journal 1997 Journal Article

Proving properties of continuous systems: qualitative simulation and temporal logic

• Benjamin Shults
• Benjamin J. Kuipers

We demonstrate an automated method for proving temporal logic statements about solutions to ordinary differential equations (ODEs), even in the face of an incomplete specification of the ODE. The method combines an implemented, on-the-fly, model checking algorithm for statements in the temporal logic CTL∗ with the output of the qualitative simulation algorithm QSIM. Based on the QSIM Guaranteed Coverage Theorem, we prove that for certain CTL∗ statements, Φ, if Φ is true for the temporal structure produced by QSIM, then a corresponding temporal statement, Φ, holds for the solution of any ODE consistent with the qualitative differential equation (QDE) that QSIM used to generate the temporal structure.

AIJ Journal 1997 Journal Article

Qualitative and quantitative simulation: bridging the gap

• Daniel Berleant
• Benjamin J. Kuipers

Shortcomings of qualitative simulation and of quantitative simulation motivate combining them to do simulations exhibiting strengths of both. The resulting class of techniques is called semiquantitative simulation. One approach to semi-quantitative simulation is to use numeric intervals to represent incomplete quantitative information. In this research we demonstrate semi-quantitative simulation using intervals in an implemented semi-quantitative simulator called Q3. Q3 progressively refines a qualitative simulation, providing increasingly specific quantitative predictions which can converge to a numerical simulation in the limit while retaining important correctness guarantees from qualitative and interval simulation techniques. Q3's simulations are based on a technique we call step size refinement. While a pure qualitative simulation has a very coarse step size, representing the state of a system trajectory at relatively few qualitatively distinct states, Q3 interpolates newly explicit states between distinct qualitative states, thereby representing more states which instantiate new constraints, leading to improved quantitative inferences. Q3's techniques have been used for prediction, measurement interpretation, diagnosis, and even analysis of the probabilities of qualitative behaviors. Because Q3 shares important expressive and inferential properties of both qualitative and quantitative simulation, Q3 helps to bridge the gap between qualitative and quantitative simulation.

AIJ Journal 1993 Journal Article

Qualitative simulation: then and now

• Benjamin J. Kuipers

AIJ Journal 1993 Journal Article

Reasoning with qualitative models

• Benjamin J. Kuipers

AIJ Journal 1991 Journal Article

Higher-order derivative constraints in qualitative simulation

• Benjamin J. Kuipers
• Charles Chiu
• David T.Dalle Molle
• D.R. Throop

Qualitative simulation is a useful method for predicting the possible qualitatively distinct behaviors of an incompletely known mechanism described by a system of qualitative differential equations (QDEs). Under some circumstances, sparse information about the derivatives of variables can lead to intractable branching (or “chatter”) representing uninteresting or even spurious distinctions among qualitative behaviors. The problem of chatter stands in the way of real applications such as qualitative simulation of models in the design or diagnosis of engineered systems. One solution to this problem is to exploit information about higher-order derivatives of the variables. We demonstrate automatic methods for identification of chattering variables, algebraic derivation of expressions for second-order derivatives, and evaluation and application of the sign of second- and third-order derivatives of variables, resulting in tractable simulation of important qualitative models. Caution is required, however, when deriving higher-order derivative (HOD) expressions from models including incompletely known monotonic function (M +) constraints, whose derivatives beyond the sign of the slope are completely unspecified. We discuss the strengths and weaknesses of several methods for evaluating HOD expressions in this situation. We also discuss a second approach to intractable branching, in which we change the level of description to collapse an infinite set of distinct behaviors into a few by ignoring certain distinctions. These two approaches represent a tradeoff between generality and power. Each application of these methods can take a position on this tradeoff depending on its own critical needs.

AAAI Conference 1988 Conference Paper

A Robust, Qualitative Method for Robot Spatial Learning

• Benjamin J. Kuipers