Benjamin Kuipers

IROS Conference 2024 Conference Paper

Multi-Fingered End-Effector Grasp Reflex Modeling for One-Shot Tactile Servoing in Tool Manipulation Tasks

• Emily Sheetz
• Misha Savchenko
• Emma Zemler
• Abbas Presswala
• Andrew Crouch
• Shaun Azimi
• Benjamin Kuipers

Autonomous tool manipulation tasks are challenging for robots because they must reason over the tool’s object affordances, how to grasp the tool so it may be used, how the tool will interact with other objects in the environment, and how to perform the complex tool affordances to complete the manipulation task. Focusing on tool grasping presents further challenges, specifically generalization to novel tools and modeling the problem in an explainable way suitable for safety-critical task domains, such as robots operating autonomously to perform repair tasks in NASA lunar habitats. In this work, we focus on grasping tools in an explainable way that can be generalized to novel tools. We present a logistic regression based grasp reflex model, which maps continuous end-effector sensor data to a set of discrete symbolic states. An adjustment policy uses these symbolic states to compute the appropriate gradient to change the end-effector pose and increase the probability of a secure tool grasp. Once the tool grasp is sufficiently secure, the robot proceeds with the rest of the manipulation task. We test our grasp reflex model on 6 novel tools, and find that the model achieves one-shot generalization by successfully using tactile servoing to secure grasps from one example of a secure grasp state. The robot’s ability to learn to grasp tools in an explainable way that achieves one-shot generalization to novel tools demonstrates the power of our grasp reflex model in allowing robots to achieve autonomous tool manipulation tasks.

ICRA Conference 2023 Conference Paper

The Reflectance Field Map: Mapping Glass and Specular Surfaces in Dynamic Environments

• Paul Foster
• Collin Johnson
• Benjamin Kuipers

We present the Reflectance Field Map, a reliable real-time method for detecting shiny surfaces, like glass, metal, and mirrors, with lidar. The Reflectance Field Map combines the theory developed for Light Field Mapping, common in computer graphics, with occupancy grid mapping. Like early methods for sonar-based robot mapping, we show how the addition of angular viewpoint information to a standard 2D grid map enables robust mapping in the presence of specular reflections. However unlike previous approaches, our method works in dynamic environments. Additionally, unlike recent approaches for lidar-based mapping of specular surfaces, our approach is sensor-agnostic and has no reliance on either intensity or multi-return measurements. We demonstrate the ability of the Reflectance Field Map to accurately map a campus environment containing numerous pedestrians and significant plate glass, both straight and curved. The algorithm runs in real-time (75+Hz) on a single core of a standard desktop processor. An open source implementation of the algorithm is available at https://github.com/collinej/reflectance_field_map.

IROS Conference 2018 Conference Paper

Learning to Grasp by Extending the Peri-Personal Space Graph

• Jonathan Juett
• Benjamin Kuipers

We present a robot model of early reach and grasp learning, inspired by infant learning without prior knowledge of the geometry, kinematics, or dynamics of the arm. Human infants at reach onset are capable of using a sequence of jerky submotions to bring the hand to the position of a nearby object. A robotic learning agent can produce qualitatively similar behavior by using a graph representation to encode a set of safe, potentially useful arm states and feasible moves between them. These observations show that the Peri-Personal Space (PPS) Graph model is sufficient for early reaching and suggest that infants may use analogous models during this phase. In this paper, we show that the PPS Graph, with a simulated Palmar reflex (a reflex in infants that closes the fingers when the palm is touched), allows accidental grasps to occur during continued reaching practice. Given these occasional events, the agent can bootstrap to a simple deliberate grasp action. In particular, the agent must learn three new necessary conditions for a grasp: the hand should be open as the grasp begins, the final motion of the hand should be led by the gripper opening so that it reaches the target first, and the wrist must be oriented such that the gripper fingers may close around the target object, often requiring the opening to be perpendicular to the object's major axis. Combined with the existing capability to reach and interact with target objects, knowledge of these conditions allows the agent to learn increasingly reliable purposeful grasps. The first two conditions are addressed in this paper, and allow 45% of grasps to succeed. This work contributes toward the larger goal of foundational robot learning after the model of infant learning, with minimal prior knowledge of its own anatomy or its environment. The ability to grasp will allow the agent to control the motion and position of objects, providing a richer representation for its environment and new experiences to learn from.

AAMAS Conference 2017 Conference Paper

A Tale of Two Architectures: A Dual-Citizenship Integration of Natural Language and the Cognitive Map

• Tom Williams
• Collin Johnson
• Matthias Scheutz
• Benjamin Kuipers

Vulcan and DIARC are two robot architectures with very different capabilities: Vulcan uses rich spatial representations to facilitate navigation capabilities in real-world, campus-like environments, while DIARC uses high-level cognitive representations to facilitate human-like tasking through natural language. In this work, we show how the integration of Vulcan and DIARC enables not only the capabilities of the two individual architectures, but new synergistic capabilities as well, as each architecture leverages the strengths of the other. This integration presents interesting challenges, as DIARC and Vulcan are implemented in distinct multi-agent system middlewares. Accordingly, a second major contribution of this paper is the Vulcan-ADE Development Environment (VADE): a novel multi-agent system framework comprised of both (1) software agents belonging to a single robot architecture and implemented in a single multi-agent system middleware, and (2) “Dual-Citizen” agents that belong to both robot architectures and that use elements of both multi-agent system middlewares. As one example application, we demonstrate the implementation of the new joint architecture and novel multi-agent system framework on a robotic wheelchair, and show how this integration advances the state-of-the-art for NL-enabled wheelchairs.

ICRA Conference 2017 Conference Paper

Discrete-time dynamic modeling and calibration of differential-drive mobile robots with friction

• Jong Jin Park
• Seungwon Lee
• Benjamin Kuipers

Fast and high-fidelity dynamic model is very useful for planning, control, and estimation. Here, we present a fixed-time-step, discrete-time dynamic model of differential-drive vehicle with friction for reliable velocity prediction, which is fast, stable, and easy to calibrate. Unlike existing methods which are predominantly formulated in the continuous-time domain (very often ignoring dry friction) that require numerical solver for digital implementation, our model is formulated directly in a fixed-time-step discrete-time setting, which greatly simplifies the implementation and minimizes computational cost. We also explicitly take into account friction, using the stable formulation developed by Kikuuwe [1]. Friction model, while non-trivial to implement, is necessary for predicting wheel locks and velocity steady-states which occur in real physical systems. In this paper, we present our dynamic model and evaluate it on a physical platform, a commercially-available electric powered wheelchair. We show that our model, which can run over 10 5 times faster than real-time on a typical laptop, can accurately predict linear and angular velocities without drift. The calibration of our model requires only a time-series of wheel speed measurements (via encoders) and command inputs, making it readily deployable to physical mobile robots.

IROS Conference 2015 Conference Paper

Feedback motion planning via non-holonomic RRT* for mobile robots

• Jong Jin Park
• Benjamin Kuipers

Here we present a non-holonomic distance function for unicycle-type vehicles, and use this distance function to extend the optimal path planner RRT* to handle nonholonomic constraints. The critical feature of our proposed distance function is that it is also a control-Lyapunov function. We show that this allows us to construct feedback policies that stabilizes the system to a target pose, and to generate the optimal path that respects the non-holonomic constraints of the system via the non-holonomic RRT*. The composition of the Lyapunov function that is obtained as a result of this planning process provides stabilizing feedback and the cost-to-go to the final destination in the neighborhood of the planned path, adding much flexibility and robustness to the plan.

IROS Conference 2014 Conference Paper

Handling perceptual clutter for robot vision with partial model-based interpretations

• Grace Tsai
• Benjamin Kuipers

For a robot to act in the world, it needs to build and maintain a simple and concise model of that world, from which it can derive safe opportunities for action and hazards to avoid. Unfortunately, the world itself is infinitely complex, containing aspects (“clutter”) that are not well described, or even well approximated, by the simple model. An adequate explanatory model must therefore explicitly delineate the clutter that it does not attempt to explain. As the robot searches for the best model to explain its observations, it faces a three-way trade-off among the coverage of the model, the degree of accuracy with which the model explains the observations, and the simplicity of the model. We present a likelihood function that addresses this trade-off. We demonstrate and evaluate this likelihood function in the context of a mobile robot doing visual scene understanding. Our experimental results on a corpus of RGB-D videos of cluttered indoor environments demonstrate that this method is capable of creating a simple and concise planar model of the major structures (ground plane and walls) in the environment, while separating out for later analysis segments of clutter represented by 3D point clouds.

ICML Conference 2014 Conference Paper

Structured Recurrent Temporal Restricted Boltzmann Machines

• Roni Mittelman
• Benjamin Kuipers
• Silvio Savarese
• Honglak Lee

The Recurrent temporal restricted Boltzmann machine (RTRBM) is a probabilistic model for temporal data, that has been shown to effectively capture both short and long-term dependencies in time-series. The topology of the RTRBM graphical model, however, assumes full connectivity between all the pairs of visible and hidden units, therefore ignoring the dependency structure between the different observations. Learning this structure has the potential to not only improve the prediction performance, but it can also reveal important patterns in the data. For example, given an econometric dataset, we could identify interesting dependencies between different market sectors; given a meteorological dataset, we could identify regional weather patterns. In this work we propose a new class of RTRBM, which explicitly uses a dependency graph to model the structure in the problem and to define the energy function. We refer to the new model as the structured RTRBM (SRTRBM). Our technique is related to methods such as graphical lasso, which are used to learn the topology of Gaussian graphical models. We also develop a spike-and-slab version of the RTRBM, and combine it with our method to learn structure in datasets with real valued observations. Our experimental results using synthetic and real datasets, demonstrate that the SRTRBM can improve the prediction performance of the RTRBM, particularly when the number of visible units is large and the size of the training set is small. It also reveals the structure underlying our benchmark datasets.

ICRA Conference 2013 Conference Paper

Autonomous person pacing and following with Model Predictive Equilibrium Point Control

• Jong Jin Park
• Benjamin Kuipers

The ability to follow or move alongside a person is a necessary skill for an autonomous mobile agent that works with human users. To accomplish the task, the robot must be able to track and follow the person it is accompanying while maneuvering through obstacles without collision. Also, the robot must be able to respect user preferences and exhibit behaviors that are intuitive and socially acceptable. That is, the robot is required to make complex decisions on-line, in environments that are almost always dynamic and uncertain in the presence of pedestrians. This paper discusses a versatile motion planning algorithm for person pacing, which refers to the capability to walk next to another person at user-preferred distance and orientation [1]. The algorithm is based on the Model Predictive Equilibrium Point Control (MPEPC) framework [2] which allows a robot to navigate gracefully in dynamic, uncertain, and structured environments. We show that with a simple task description for person pacing, an agent with the MPEPC navigation algorithm can make intelligent decisions on-line, maximizing the expected progress toward achieving the task while minimizing the action cost and the probability of collision. We present navigation examples generated from real data traces, where a wheelchair robot exhibits very reasonable behaviors across a wide range of situations.

ICRA Conference 2013 Conference Paper

VisAGGE: Visible angle grid for glass environments

• Paul Foster
• Zhenghong Sun
• Jong Jin Park
• Benjamin Kuipers

We describe a new algorithm for occupancy grid mapping using LIDAR in the presence of glass and other non-diffuse surfaces. This is a major problem for robot navigation in many indoor environments due to the prevalence of glass paned doors, windows, and even glass walls, as well as mirrors and polished metal surfaces. Current formulations of occupancy grid mapping make the assumption that objects in the environment are detectable from all angles. However, glass and other specular surfaces are invisible to LIDAR at most angles and so become washed out as “noise”. We modify the standard occupancy grid algorithm to allow for mapping objects that are only visible from certain view angles, by tracking the subset of angles from which objects are reliably visible. We show that these angles can be determined reliably with a single pass through the environment, and that the information can be used to map both diffuse and specular surfaces.

IROS Conference 2012 Conference Paper

Dynamic visual understanding of the local environment for an indoor navigating robot

• Grace Tsai
• Benjamin Kuipers

We present a method for an embodied agent with vision sensor to create a concise and useful model of the local indoor environment from its experience of moving within it. Our method generates and evaluates a set of qualitatively distinct hypotheses of the local environment and refines the parameters within each hypothesis quantitatively. Our method is a continual, incremental process that transforms current environmental-structure hypotheses into children hypotheses describing the same environment in more detail. Since our method only relies on simple geometric and probabilistic inferences, our method runs in real-time, and it avoids the need of extensive prior training and the Manhattan-world assumption, which makes it practical and efficient for a navigating robot. Experimental results on a collection of indoor videos suggests that our method is capable of modeling various structures of indoor environments.

IROS Conference 2012 Conference Paper

Efficient search for correct and useful topological maps

• Collin Johnson
• Benjamin Kuipers

We present an algorithm for probabilistic topological mapping that heuristically searches a tree of map hypotheses to provide a usable topological map hypothesis online, while still guaranteeing the correct map can always be found. Our algorithm annotates each leaf of the tree with a posterior probability. When a new place is encountered, we expand hypotheses based on their posterior probability, which means only the most probable hypotheses are expanded. By focusing on the most probable hypotheses, we dramatically reduce the number of hypotheses evaluated allowing real-time operation. Additionally, our approach never prunes consistent hypotheses from the tree, which means the correct hypothesis always exists within the tree.

IROS Conference 2012 Conference Paper

Robot navigation with model predictive equilibrium point control

• Jong Jin Park
• Collin Johnson
• Benjamin Kuipers

An autonomous vehicle intended to carry passengers must be able to generate trajectories on-line that are safe, smooth and comfortable. Here, we propose a strategy for robot navigation in a structured, dynamic indoor environment, where the robot reasons about the near future and makes a locally optimal decision at each time step.

ICRA Conference 2011 Conference Paper

A smooth control law for graceful motion of differential wheeled mobile robots in 2D environment

• Jong Jin Park
• Benjamin Kuipers

Although recent progress in 2D mobile robot navigation has been significant, the great majority of existing work focuses only on ensuring that the robot reaches its goal. But to make autonomous navigation truly successful, the “quality” of planned motion is important as well. Here, we develop and analyze a pose-following kinematic control law applicable to unicycle-type robots, such that the robot can generate intuitive, fast, smooth, and comfortable trajectories. The Lyapunov-based feedback control law is derived via singular perturbation. It is made up of three components: (i) egocentric polar coordinates with respect to an observer on the vehicle, (ii) a slow subsystem which describes the position of the vehicle, where the reference heading is obtained via state feedback, and (iii) a fast subsystem which describes the steering of the vehicle, where the vehicle heading is exponentially stabilized to the obtained reference heading. The resulting path is a smooth and intuitive curve, globally converging to an arbitrary target pose without singularities, from any given initial pose. Furthermore, we present a simple path following strategy based on the proposed control law to satisfy arbitrary velocity, acceleration and jerk bounds imposed by the user. Such requirements are important to any autonomous vehicle so as to avoid actuator overload and to make the path physically realizable, and they are critical for applications like autonomous wheelchairs where passengers can be physically fragile.

IJCAI Conference 2009 Conference Paper

• Jonathan Mugan
• Benjamin Kuipers

There has been intense interest in hierarchical reinforcement learning as a way to make Markov decision process planning more tractable, but there has been relatively little work on autonomously learning the hierarchy, especially in continuous domains. In this paper we present a method for learning a hierarchy of actions in a continuous environment. Our approach is to learn a qualitative representation of the continuous environment and then to define actions to reach qualitative states. Our method learns one or more options to perform each action. Each option is learned by first learning a dynamic Bayesian network (DBN). We approach this problem from a developmental robotics perspective. The agent receives no extrinsic reward and has no external direction for what to learn. We evaluate our work using a simulation with realistic physics that consists of a robot playing with blocks at a table.

IROS Conference 2009 Conference Paper

A framework for planning comfortable and customizable motion of an assistive mobile robot

• Shilpa Gulati
• Chetan Jhurani
• Benjamin Kuipers
• Raul G. Longoria

Assistive mobile robots that can navigate autonomously can greatly benefit people with mobility impairments. Since an assistive mobile robot transports a human user from one place to another, its motion should be comfortable for human users. Moreover, it should be possible for users to customize the motion according to their comfort. While there exists a large body of work on motion planning for mobile robots, very little attention has been paid to characterizing comfort and planning comfortable trajectories. In this paper, we first characterize comfortable motion by formulating a measure of discomfort as a weighted sum of the total travel time and time integrals of various kinematic quantities. We then present a method for factoring the weights such that once a user has customized the weights for one task, the same choice of weights leads to similar average value of the discomfort measure in other tasks. We seek trajectories that minimize the discomfort and satisfy boundary conditions on pose, velocity and acceleration. Such a problem can naturally be formulated as a variational optimization problem. Unlike previous work, we present a comprehensive formulation that allows the travel time to be unspecified and includes boundary conditions on position, orientation, velocity and acceleration. This makes the formulation very general as it can be used to compute trajectories for various kinds of tasks, such as starting from rest, coming to rest, moving from one specified velocity to another, arriving at a goal with a specified orientation etc. Finally, we present a fast and robust numerical method for solving the minimization problem.

IROS Conference 2009 Conference Paper

A stereo vision based mapping algorithm for detecting inclines, drop-offs, and obstacles for safe local navigation

• Aniket Murarka
• Benjamin Kuipers

Mobile robots have to detect and handle a variety of potential hazards to navigate autonomously. We present a real-time stereo vision based mapping algorithm for identifying and modeling various hazards in urban environments - we focus on inclines, drop-offs, and obstacles. In our algorithm, stereo range data is used to construct a 3D model consisting of a point cloud with a 3D grid overlaid on top. A novel plane fitting algorithm is then used to segment the 3D model into distinct potentially traversable ground regions and fit planes to the regions. The planes and segments are analyzed to identify safe and unsafe regions and the information is captured in an annotated 2D grid map called a local safety map. The safety map can be used by wheeled mobile robots for planning safe paths in their local surroundings. We evaluate our algorithm comprehensively by testing it in varied environments and comparing the results to ground truth data.

IROS Conference 2008 Conference Paper

Detecting obstacles and drop-offs using stereo and motion cues for safe local motion

• Aniket Murarka
• Mohan Sridharan
• Benjamin Kuipers

A mobile robot operating in an urban environment has to navigate around obstacles and hazards. Though a significant amount of work has been done on detecting obstacles, not much attention has been given to the detection of drop-offs, e. g. , sidewalk curbs, downward stairs, and other hazards where an error could lead to disastrous consequences. In this paper, we propose algorithms for detecting both obstacles and drop-offs (also called negative obstacles) in an urban setting using stereo vision and motion cues. We propose a global color segmentation stereo method and compare its performance at detecting hazards against prior work using a local correlation stereo method. Furthermore, we introduce a novel drop-off detection scheme based on visual motion cues that adds to the performance of the stereo-vision methods. All algorithms are implemented and evaluated on data obtained by driving a mobile robot in urban environments.

AIIM Journal 2008 Journal Article

Drinking from the firehose of experience

• Benjamin Kuipers

ICRA Conference 2008 Conference Paper

High performance control for graceful motion of an intelligent wheelchair

• Shilpa Gulati
• Benjamin Kuipers

To be acceptable to human drivers, the motion of an intelligent robotic wheelchair must be more than just collision-free: it must be graceful. We define graceful motion as being safe, comfortable, fast and intuitive. In this paper, we quantify these properties of graceful motion, providing formal evaluation criteria. We propose a method for graceful motion and present implementation results for the task of driving through a narrow doorway, evaluated on a simulated model of the wheelchair. We use B-splines to specify an intuitive path to a goal, and then describe path-following control law for a differential- drive wheeled vehicle to follow that path within velocity and acceleration bounds. Existing methods typically respond to tight clearances with very slow motion which is not graceful. Our results show that, starting from a set of representative poses, the wheelchair passes through the door at near maximum speed, staying close to the mid-line of the doorway. The velocity of the wheelchair reflects the curvature of the path rather than the closeness of the door edges, so it can move smoothly, safely, and quickly through the doorway. Thus, this paper makes two contributions - first it introduces the concept of graceful motion and provides quantitative measures for the same, and second, it proposes a method for graceful motion and demonstrates it on a specific task.

ICRA Conference 2008 Conference Paper

Trajectory generation for dynamic bipedal walking through qualitative model based manifold learning

• Subramanian Ramamoorthy
• Benjamin Kuipers

Legged robots represent great promise for transport in unstructured environments. However, it has been difficult to devise motion planning strategies that achieve a combination of energy efficiency, safety and flexibility comparable to legged animals. In this paper, we address this issue by presenting a trajectory generation strategy for dynamic bipedal walking robots using a factored approach to motion planning - combining a low-dimensional plan (based on intermittently actuated passive walking in a compass-gait biped) with a manifold learning algorithm that solves the problem of embedding this plan in the high-dimensional phase space of the robot. This allows us to achieve task level control (over step length) in an energy efficient way - starting with only a coarse qualitative model of the system dynamics and performing a data-driven approximation of the dynamics in order to synthesize families of dynamically realizable trajectories. We demonstrate the utility of this approach with simulation results for a multi-link legged robot.

ICRA Conference 2006 Conference Paper

Adapting Proposal Distributions for Accurate, Efficient Mobile Robot Localization

• Patrick Beeson
• Aniket Murarka
• Benjamin Kuipers

When performing probabilistic localization using a particle filter, a robot must have a good proposal distribution in which to distribute its particles. Once weighted by their normalized likelihood scores, these particles estimate a posterior distribution over the possible poses of the robot. This paper 1) introduces a new action model (the system of equations used to determine the proposal distribution at each time step) that can run on any differential drive robot, even from log file data, 2) investigates the results of different algorithms that modify the proposal distribution at each time step in order to obtain more accurate localization, 3) investigates the results of incrementally adapting the action model parameters based on recent localization results in order to obtain proposal distributions that better approximate the true posteriors. The results show that by adapting the action model over time and, when necessary, modifying the resulting proposal distributions at each time step, localization improves-the maximum likelihood score increases and, when possible, the percentage of wasted particles decreases

ICRA Conference 2006 Conference Paper

Autonomous Shape Model Learning for Object Localization and Recognition

• Joseph Modayil
• Benjamin Kuipers

Mobile robots do not adequately represent the objects in their environment; this weakness hinders a robot's ability to utilize past experience. In this paper, we describe a simple and novel approach to create object shape models from range sensors. We propose an algorithm that defines angular constraints between multiple sensor scans of an object. These constraints are used to align the scans, creating a maximally coherent object shape model. We demonstrate the utility of this shape model, consisting of scans and poses, for both object recognition and localization. The results are accurate to within sensor precision

AAAI Conference 2005 Conference Paper

Consciousness: Drinking from the Firehose of Experience

• Benjamin Kuipers

The problem of consciousness has captured the imagination of philosophers, neuroscientists, and the general public, but has received little attention within AI. However, concepts from robotics and computer vision hold great promise to account for the major aspects of the phenomenon of consciousness, including philosophically problematical aspects such as the vividness of qualia, the first-person character of conscious experience, and the property of intentionality. This paper presents and evaluates such an account against eleven features of consciousness "that any philosophical-scientific theory should hope to explain", according to the philosopher and prominent AI critic John Searle.

ICRA Conference 2005 Conference Paper

Towards Autonomous Topological Place Detection Using the Extended Voronoi Graph

• Patrick Beeson
• Nicholas K. Jong
• Benjamin Kuipers

Autonomous place detection has long been a major hurdle to topological map-building techniques. Theoretical work on topological mapping has assumed that places can be reliably detected by a robot, resulting in deterministic actions. Whether or not deterministic place detection is always achievable is controversial; however, even topological mapping algorithms that assume non-determinism benefit from highly reliable place detection. Unfortunately, topological map-building implementations often have hand-coded place detection algorithms that are brittle and domain dependent. This paper presents an algorithm for reliable autonomous place detection that is sensor and domain independent. A preliminary implementation of this algorithm for an indoor robot has demonstrated reliable place detection in real-world environments, with no a priori environmental knowledge. The implementation uses a local, scrolling 2D occupancy grid and a real-time calculated Voronoi graph to find the skeleton of the free space in the local surround. In order to utilize the place detection algorithm in non-corridor environments, we also introduce the extended Voronoi graph (EVG), which seamlessly transitions from a skeleton of a midline in corridors to a skeleton that follows walls in rooms larger than the local scrolling map.

IROS Conference 2004 Conference Paper

Bootstrap learning for object discovery

• Joseph Modayil
• Benjamin Kuipers

We show how a robot can autonomously learn an ontology of objects to explain aspects of its sensor input from an unknown dynamic world. Unsupervised learning about objects is an important conceptual step in developmental learning, whereby the agent clusters observations across space and time to construct stable perceptual representations of objects. Our proposed unsupervised learning method uses the properties of allocentric occupancy grids to classify individual sensor readings as static or dynamic. Dynamic readings are clustered and the clusters are tracked over time to identify objects, separating them both from the background of the environment and from the noise of unexplainable sensor readings. Once trackable clusters of sensor readings (i. e. , objects) have been identified, we build shape models where they are stable and consistent properties of these objects. However, the representation can tolerate, represent, and track amorphous objects as well as those that have well-defined shape. In the end, the learned ontology makes it possible for the robot to describe a cluttered dynamic world with symbolic object descriptions along with a static environment model, both models grounded in sensory experience, and learned without external supervision.

ICRA Conference 2004 Conference Paper

Local Metrical and Global Topological Maps in the Hybrid Spatial Semantic Hierarchy

• Benjamin Kuipers
• Joseph Modayil
• Patrick Beeson
• Matt MacMahon
• Francesco Savelli

Topological and metrical methods for representing spatial knowledge have complementary strengths. We present a hybrid extension to the spatial semantic hierarchy that combines their strengths and avoids their weaknesses. Metrical SLAM methods are used to build local maps of small-scale space within the sensory horizon of the agent, while topological methods are used to represent the structure of large-scale space. We describe how a local perceptual map is analyzed to identify a local topology description and is abstracted to a topological place. The map building method creates a set of topological map hypotheses that are consistent with travel experience. The set of maps is guaranteed under reasonable assumptions to include the correct map. We demonstrate the method on a real environment with multiple nested large-scale loops.

IROS Conference 2004 Conference Paper

Loop-closing and planarity in topological map-building

• Francesco Savelli
• Benjamin Kuipers

Loop-closing has long been recognized as a critical issue when building maps of large-scale environments from local observations. Topological mapping methods abstract the problem of determining the topological structure of the environment (i. e. , how loops are closed) from the problem of determining the metrical layout of places in the map and dealing with noisy sensors. A recently developed incremental topological mapping algorithm [E. Remolina et al. (2004), B. Kuipers et al. (2004)] generates all possible topological maps consistent with the experienced sequence of actions and observations and the topological axioms. These are then ordered by a preference criterion such as minimality or probability, to determine the single best map for continued planning and exploration. This paper presents the planarity constraint and analyzes its impact on the search-tree of all topological maps consistent with (non-metrical) exploration experience. Experimental studies demonstrate excellent results even in artificial environments where loop-closing is particularly difficult due to large amounts of perceptual aliasing and structural symmetry.

AIJ Journal 2004 Journal Article

Towards a general theory of topological maps

• Emilio Remolina
• Benjamin Kuipers

IROS Conference 2004 Conference Paper

Using the topological skeleton for scalable global metrical map-building

• Joseph Modayil
• Patrick Beeson
• Benjamin Kuipers

Most simultaneous localization and mapping (SLAM) approaches focus on purely metrical approaches to map-building. We present a method for computing the global metrical map that builds on the structure provided by a topological map. This allows us to factor the uncertainty in the map into local metrical uncertainty (which is handled well by existing SLAM methods), global topological uncertainty (which is handled well by recently developed topological map-learning methods), and global metrical uncertainty (which can be handled effectively once the other types of uncertainty are factored out). We believe that this method for building the global metrical map is scalable to very large environments.

AIJ Journal 2000 Journal Article

Semi-quantitative system identification

• Herbert Kay
• Bernhard Rinner
• Benjamin Kuipers

AIJ Journal 2000 Journal Article

The Spatial Semantic Hierarchy

• Benjamin Kuipers

IJCAI Conference 1999 Conference Paper

Monitoring Piecewise Continuous Behaviors by Refining Semi-Quantitative Trackers

• Bernhard Rinner
• Benjamin Kuipers

We present a model-based monitoring method for dynamic systems that exhibit both discrete and continuous behaviors. MIMIC [Dvorak and Kuipers, 1991] uses qualitative and semiquantitative models to monitor dynamic systems even with incomplete knowledge. Recent advances have improved the quality of semi-quantitative behavior predictions, used observations to refine static envelopes around monotonic functions, and provided a semiquantitative system identification method. Using these, we reformulate and extend MIMIC to handle discontinuous changes between models. Each hypothesis being monitored is embodied as a tracker, which uses the observation stream to refine its behavioral predictions, its underlying model, and the time uncertainty of any discontinuous transitions. keywords: model-based monitoring; model refinement, hybrid systems

IROS Conference 1992 Conference Paper

A Continuous Approach To Robot Motion Planning With Many Degrees Of Freedom

• Akira Hayashi
• Benjamin Kuipers

IJCAI Conference 1989 Conference Paper

Model-Based Monitoring of Dynamic Systems

• Daniel Dvorak
• Benjamin Kuipers

AAAI Conference 1988 Conference Paper

Using Incomplete Quantitative Knowledge in Qualitative Reasoning

• Benjamin Kuipers

Incomplete knowledge of the structure of mechanisms is an important fact of life in reasoning, commonsense or expert, about the physical world. Qualitative simulation captures an important kind of incomplete, ordinal, knowledge, and predicts the set of qualitatively possible behaviors of a mechanism, given a qualitative description of its structure and initial state. However, one frequently has qzlaniitative knowledge as well as qualitative, though seldom enough to specify a numerical simulation. We present a method for incrementally exploiting incomplete quantitative knowledge, by using it to refine the predictions of a qualitative reasoner. Incomplete quantitative descriptions (currently ranges within which unknown values are assumed to lie) are asserted about some landmark values in the quantity spaces of qualitative parameters. Unknown monotonic function constraints may be bounded by numerically computable envelope functions. Implications are derived by local propagation across the constraints in the model. When this refinement process produces a contradiction, a qualitatively plausible behavior is shown to conflict with the quantitative knowledge. When all predicted behaviors of a given model are contradicted, the model is refuted. If a behavior is not refuted, propagation of quantitative information results in a mixed quantitative/qualitative description of behavior that can be compared with other surviving predictions for differential diagnosis.

AAAI Conference 1987 Conference Paper

Abstraction by Time-Scale in Qualitative Simulation

• Benjamin Kuipers

Qualitative simulation faces an intrinsic problem of scale: the number of limit hypotheses grows exponentially with the number of parameters approaching limits. We present a method called Time-Scale Abstraction for structuring a complex system as a hierarchy of smaller, interacting equilibrium mechanisms. Within this hierarchy, a given mechanism views a slower one as being constant, and a faster one as being instantaneous. A perturbation to a fast mechanism may be seen by a slower mechanism as a displacement of a monotonic function constraint. We demonstrate the time-scale abstraction hierarchy using the interaction between the water and sodium balance mechanisms in medical physiology, an example drawn from a larger, fully implemented, program. Where the structure of a large system permits decomposition by time-scale, this abstraction method permits qualitative simulation of otherwise intractibly complex systems.

IJCAI Conference 1987 Conference Paper

Taming Intractible Branching in Qualitative Simulation

• Benjamin Kuipers
• Charles Chiu

AIJ Journal 1986 Journal Article

Qualitative simulation

• Benjamin Kuipers

IJCAI Conference 1985 Conference Paper

The Limits of Qualitative Simulation

• Benjamin Kuipers

AIJ Journal 1984 Journal Article

Commonsense reasoning about causality: Deriving behavior from structure

• Benjamin Kuipers

IJCAI Conference 1983 Conference Paper

How to Discover a Knowledge Representation for Causal Reasoning by Studying an Expert Physician

• Benjamin Kuipers
• Jerome P. Kassirer

AAAI Conference 1983 Conference Paper

Modeling Human Knowledge of Routes: Partial Knowledge and Individual Variation

• Benjamin Kuipers

Commonsense knowledge of large-scale space (the cognitive map) includes several different types of knowledge: of sensorimotor, topological, and metrical spatial relationships. Sensorimotor knowledge is defined as that knowledge which is necessary to reconstruct a route from memory after travel along that route in a large-scale environment. A representation for route knowledge is proposed with sufficiently robust performance properties to be useful as commonsense knowledge. Its states of partial knowledge are shown to correspond to those observed in humans. We also define and explore the space of all possible variants of this representation, to derive empirical predictions about the nature of individual variation.

AAAI Conference 1982 Conference Paper

Getting the Envisionment Right

• Benjamin Kuipers

The central component of commonsense reasoning about causality is the envisionment: a description of the behavior of a physical system that is derived from its structural description by qualitative simulation. Two problems with creating the envisionment are the qualitative representation of quantity and the detection of previously-unsuspected points of qualitative change. The representation presented here has the expressive power of differential equations, and the qualitative envisionment strategy needed for commonsense knowledge. A detailed example shows how it is able to detect a previously unsuspected point at which the system is in stable equilibrium.