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.

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.

We present socially-aware navigation for an intelligent robot wheelchair in an environment with many pedestrians. The robot learns social norms by observing the behaviors of human pedestrians, interpreting detected biases as social norms, and incorporating those norms into its motion planning. We compare our socially-aware motion planner with a baseline motion planner that produces safe, collision-free motion.

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.

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 105times 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.

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.

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.

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.

Pointing is a typical means of directing a human's attention to a specific object or event. Robot pointing behaviours that direct the attention of humans are critical for human-robot interaction, communication and collaboration. In this paper, we describe an experiment undertaken to investigate human comprehension of a humanoid robot's pointing behaviour. We programmed a NAO robot to point to markers on a large screen and asked untrained human subjects to identify the target of the robots pointing gesture. We found that humans are able to identify robot pointing gestures. Human subjects achieved higher levels of comprehension when the robot pointed at objects closer to the gesturing arm and when they stood behind the robot. In addition, we found that subjects performance improved with each assessment task. These new results can be used to guide the design of effective robot pointing behaviours that enable more effective robot to human communication and improve human-robot collaborative performance.

An indoor navigating agent needs to efficiently understand the geometric structure of its local environment in order to act. A common scene understanding approach is to generate a set of hypotheses about the geometric structure of the indoor environment and then test the hypotheses to select the one with the highest rank, from a single image [1, 4, 5, 6] or from a continuous stream of images (e.g. a video) [8, 9]. These methods simply detect features (e.g. lines [1, 4, 6], points [8, 9], and edges [6]) that are easily detectable for evaluating the hypotheses. In fact, some of the most informative features to discriminate the hypotheses may not be extracted if features are detected by fixed thresholds, since the informative regions may not have high image contrasts for features to be detected. This paper demonstrates that by focusing attention on features in the informative regions, we can evaluate the hypotheses more efficiently. The idea of focusing on informative regions of the image space is inspired by the idea of saliency detection [2, 3, 7]. While these works typically define saliency regions based on image and motion properties of the pixels in the images [2, 3] or based on human fixations [7], our informative regions are defined in terms of the agent’s own state of knowledge, the current set of hypotheses about the geometric structure of the indoor environment. Given a set M of hypotheses, we divide the image into regions based on the expected information gain that each feature provides, which we call informativeness (Figure 1). We define the informativeness I(p j,M)∈ [0,1] of point p j, measuring its discriminating power among the set M as,

The use of semantic attributes in computer vision problems has been gaining increased popularity in recent years. Attributes provide an intermediate feature representation in between low-level features and the class categories, and offer several attractive properties, among which are improved learning of novel categories based on few examples, as well as allowing for zero-shot learning. However, the major caveat is that learning semantic attributes is a laborious task, requiring a significant amount of time and human intervention to provide labels. In order to address this issue, we propose a weakly supervised approach to learn mid-level features, where the only supervision is provided by the category classes of the training examples. We develop a novel extension of the restricted Boltzmann machine (RBM) with Beta-Bernoulli process priors. Unlike the standard RBM, our model uses the class labels to promote more efficient sharing of information by different categories. This tends to improve the generalization performance. By using semantic attributes for which annotations are available, we show that we can find correspondences between the mid-level features that we learn and the labeled attributes. Therefore, the mid-level features have distinct semantic characterization which is very similar to that given by the semantic attributes, even though their labeling was not used during the training process. Our experimental results in object recognition tasks show significant performance gains, outperforming methods which rely on manually labeled semantic attributes.

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.

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.

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.

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.

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.

In this paper we explore the idea of using high-level semantic concepts, also called attributes, to represent human actions from videos and argue that attributes enable the construction of more descriptive models for human action recognition. We propose a unified framework wherein manually specified attributes are: i) selected in a discriminative fashion so as to account for intra-class variability; ii) coherently integrated with data-driven attributes to make the attribute set more descriptive. Data-driven attributes are automatically inferred from the training data using an information theoretic approach. Our framework is built upon a latent SVM formulation where latent variables capture the degree of importance of each attribute for each action class. We also demonstrate that our attribute-based action representation can be effectively used to design a recognition procedure for classifying novel action classes for which no training samples are available. We test our approach on several publicly available datasets and obtain promising results that quantitatively demonstrate our theoretical claims.

In this paper, we present a novel approach to recognizing human actions from different views by view knowledge transfer. An action is originally modelled as a bag of visual-words (BoVW), which is sensitive to view changes. We argue that, as opposed to visual words, there exist some higher level features which can be shared across views and enable the connection of action models for different views. To discover these features, we use a bipartite graph to model two view-dependent vocabularies, then apply bipartite graph partitioning to co-cluster two vocabularies into visual-word clusters called bilingual-words (i.e., high-level features), which can bridge the semantic gap across view-dependent vocabularies. Consequently, we can transfer a BoVW action model into a bag-of-bilingual-words (BoBW) model, which is more discriminative in the presence of view changes. We tested our approach on the IXMAS data set and obtained very promising results. Moreover, to further fuse view knowledge from multiple views, we apply a Locally Weighted Ensemble scheme to dynamically weight transferred models based on the local distribution structure around each test example. This process can further improve the average recognition rate by about 7%.

We present a method whereby an embodied agent using visual perception can efficiently create a model of a local indoor environment from its experience of moving within it. Our method uses motion cues to compute likelihoods of indoor structure hypotheses, based on simple, generic geometric knowledge about points, lines, planes, and motion. We present a single-image analysis, not to attempt to identify a single accurate model, but to propose a set of plausible hypotheses about the structure of the environment from an initial frame. We then use data from subsequent frames to update a Bayesian posterior probability distribution over the set of hypotheses. The likelihood function is efficiently computable by comparing the predicted location of point features on the environment model to their actual tracked locations in the image stream. Our method runs in real-time, and it avoids the need of extensive prior training and the Manhattan-world assumption, which makes it more practical and efficient for an intelligent robot to understand its surroundings compared to most previous scene understanding methods. Experimental results on a collection of indoor videos suggest that our method is capable of an unprecedented combination of accuracy and efficiency.

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.

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.

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.

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.

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.

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.

Trading rules are widely used by practitioners as an effective means to mechanize aspects of their reasoning about stock price trends. However, due to the simplicity of these rules, each rule is susceptible to poor behavior in specific types of adverse market conditions. Naive combinations of such rules are not very effective in mitigating the weaknesses of component rules. We demonstrate that sophisticated approaches to combining these trading rules enable us to overcome these problems and gainfully utilize them in autonomous agents. We achieve this combination through the use of genetic algorithms and genetic programs. Further, we show that it is possible to use qualitative characterizations of stochastic dynamics to improve the performance of these agents by delineating safe, or feasible, regions. We present the results of experiments conducted within the Penn-Lehman Automated Trading project. In this way we are able to demonstrate that autonomous agents can achieve consistent profitability in a variety of market conditions, in ways that are human competitive. Categories and Subject Descriptors [Real World Applications]: finance, intelligent agents, automated

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

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

To be autonomous, intelligent robots must learn the foundations of commonsense knowledge from their own sensorimotor experience in the world. We describe four recent research results that contribute to a theory of how a robot learning agent can bootstrap from the ‘blooming buzzing confusion’ of the pixel level to a higher level ontology including distinctive states, places, objects, and actions. This is not a single learning problem, but a lattice of related learning tasks, each providing prerequisites for tasks to come later. Starting with completely uninterpreted sense and motor vectors, as well as an unknown environment, we show how a learning agent can separate the sense vector into modalities, learn the structure of individual modalities, learn natural primitives for the motor system, identify reliable relations between primitive actions and created sensory features, and can define useful control laws for homing and path-following. Building on this framework, we show how an agent can use self-organizing maps to identify useful sensory features in the environment, and can learn effective hill-climbing control laws to define distinctive states in terms of those features, and trajectory-following control laws to move from one distinctive state to another. Moving on to place recognition, we show how an agent can combine unsupervised learning, map-learning, and supervised learning to achieve high-performance recognition of places from rich sensory input. Finally, we take the first steps toward learning an ontology of objects, showing that a bootstrap learning robot can learn to individuate objects through motion, separating them from the static environment and from each other, and can learn properties useful for classification. These are four key steps in a larger research enterprise on the foundations of human and robot commonsense knowledge.

A major challenge in reinforcement learning research is to extend the methods that have worked well on discrete, short-range, low-dimensional problems to continuous, high-diameter, high-dimensional problems, such as robot navigation using high-resolution sensors. Self-organizing distinctive-state abstraction (SODA) is a new, generic method by which a robot in a continuous world can better learn to navigate, by learning a set of high-level features and building temporally extended actions to carry it between distinctive states based on those features. A SODA agent first uses a self-organizing feature map to develop a set of high-level perceptual features while exploring the environment with primitive, local actions. The agent then builds a set of high-level actions composed of generic trajectory-following and hill-climbing control laws that carry it between the states at local maxima of feature activations. In an experiment on a simulated robot navigation task, the SODA agent learns to perform a task requiring 300 small-scale, local actions using as few as nine new, temporally extended actions, significantly improving learning time over navigating with the local actions.

This paper considers a general learning problem akin to the field of learning automata (LA) in which the learning mechanism attempts to learn from a stochastic teacher or a stochastic compulsive liar. More specifically, unlike the traditional LA model in which LA attempts to learn the optimal action offered by the Environment (also here called the "Oracle"), this paper considers the problem of the learning mechanism (robot, an LA, or in general, an algorithm) attempting to learn a "parameter" within a closed interval. The problem is modeled as follows: The learning mechanism is trying to locate an unknown point on a real interval by interacting with a stochastic Environment through a series of informed guesses. For each guess, the Environment essentially informs the mechanism, possibly erroneously (i.e., with probability p), which way it should move to reach the unknown point. When the probability of a correct response is p > 0.5, the Environment is said to be informative, and thus the case of learning from a stochastic teacher. When this probability p < 0.5, the Environment is deemed deceptive, and is called a stochastic compulsive liar. This paper describes a novel learning strategy by which the unknown parameter can be learned in both environments. These results are the first reported results, which are applicable to the latter scenario. The most significant contribution of this paper is that the proposed scheme is shown to operate equally well, even when the learning mechanism is unaware of whether the Environment ("Oracle") is informative or deceptive. The learning strategy proposed herein, called CPL-AdS, partitions the search interval into d subintervals, evaluates the location of the unknown point with respect to these subintervals using fast-converging E-optimal LRI LA, and prunes the search space in each iteration by eliminating at least one partition. The CPL-AdS algorithm is shown to provably converge to the unknown point with an arbitrary degree of accuracy with probability as close to unity as desired. Comprehensive experimental results confirm the fast and accurate convergence of the search for a wide range of values for the Environment's feedback accuracy parameter p, and thus has numerous potential applications.

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.

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.

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.

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.

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.

Exploration and navigation of an environment by a robot usually involves the steps of mapping, localization and path planning. Here we look at the problem of navigation in an environment about which the robot has some a priori information available, namely in the form of an architectural CAD drawing. The CAD drawing is utilized to obtain: (i) a topological map of the environment which is used for large scale path planning between regions in the environment and (ii) a skeleton of each region in the environment for path planning within regions. We then propose that a hierarchy of representations consisting of the topological map, skeleton and a reactive hazard-avoidance control system can be used effectively for navigation and exploration by a robot.

There is a need for highly redundant manipulators to work in complex, cluttered environments. We explore kinematics and path planning for highly redundant manipulators by means of a continuous manipulator model, which captures the macroscopic shape of highly redundant manipulators. A path for the continuous manipulator model can be found by finding a smooth path for its end-effector under a maximum curvature/torsion constraint. Free space decomposition into primary convex regions is suited to finding such smooth paths. On top of the free space representation, we have developed an algorithm to find a continuous curvature path in 2-D with a maximum curvature constraint. We report on an experiment conducted to measure the efficiency of the algorithm. The 2-D path planning algorithm could be used for path planning in 3-D space by restricting the manipulator movement. Alternatively, 3-D free space can be decomposed into primary convex regions. The path planning problem has been shown to be...

Qualitative modeling and simulation make it feasible to predict the possible behavior of a mechanism consistent with an incomplete state of knowledge. Though qualitative simulation predicts all possible types of behavior of a system, it can also produce spurious behavior, i.e., behavior that corresponds to no solution of any ordinary differential equation consistent with the qualitative model. A method for reasoning about energy that eliminates an important source of spurious behavior is presented. This method is applied to a nonlinear proportional-integral controller, and it is shown that qualitative simulation captures the main qualitative properties of such a system, such as stability and zero-offset control. It is believed that this is a significant step toward the application of qualitative simulation to model-based monitoring, diagnosis, and design of realistic mechanisms.>

To give a causal explanation of an event is to show how that event could be deduced from a set of universal laws and a set of initial conditions. How can this philosophical definition be related to the diagnostic causal explanations of a practicing expert? An expert physician gives a causal explanation of a disease state by referring to knowledge of the structure of the physiological mechanisms involved (the laws) and to the environment that the mechanism is exposed to (the initial state). The expert's knowledge, however, is qualitative and is thus able to express incomplete knowledge about the exact structure of the mechanism or the precise state of the patient. A qualitative representation for the structure of a mechanism, as well as the QSIM algorithm for deriving qualitative behavioral predictions from that structure and an initial state, are described. Looking in detail at the mechanism whereby the kidney maintains the body's water balance, qualitative predictions are demonstrated of 1) the response of the normal mechanism to a change in its environment, 2) the response of the diseased mechanism to the normal environment, and 3) the response of the diseased mechanism to therapy. To extend these methods to more complex problems, methods are required to abstract a complex mechanism into a hierarchy of simpler models. An abstraction relation based on relative time scales is presented which allows one equilibrium process in a complex system to view faster processes as instantaneous and slower processes as constant.