Offroad mobile robot perception systems must be able to learn robust terrain classification models. Models built from computer vision often fail in their ability to generalize to new environments where appearance characteristics change. Sound and vibration signals from robot-terrain interaction can be used to classify the terrain from characteristics that vary less between environments. Previous work using sound and vibration for terrain classification has only classified ground terrain types. We extend here to building a 7-class multiclass classifier that can classify both ground and above-ground terrain types in challenging outdoor off-road settings, thereby increasing the semantic richness of the terrain classification. Our contributions include: 1) We instrument a robotic vehicle with a variety of sound and vibration sensors mounted at different vehicle locations and directions, as well as color cameras. 2) We collect interactive and visual field data from many outdoor off-road sites with different environments. 3) We build multiclass classifiers for different combinations of sound and vibration signals, and we autonomously learn the optimal signal combination. We compare this against a single microphone from our previous work [1]. 4) We benchmark both of these results against a state-of-the art vision system. All of these multiclass classifiers are tested at different locations from where they are trained. By using one microphone instead of the vision system, we increase balanced accuracy from 70% to 82%. By using the optimal sound and vibration combination, we increase balanced accuracy from 82% to 87%. All four of these contributions are field robotics in nature: we build a sensor system and then we use that system to collect new field data that allows for a comparative evaluation of different modules of the system. Such datasets do not exist that include these varying sensors on varying field terrain. We are also contributing to machine learning research by a) showing how the acoustic classification from our previous work can be extended to new sensors, and then b) implementing an additional learning process for choosing the optimal combination.

We present a fully autonomous robotic system for grasping objects in dense clutter. The objects are unknown and have arbitrary shapes. Therefore, we cannot rely on prior models. Instead, the robot learns online, from scratch, to manipulate the objects by trial and error. Grasping objects in clutter is significantly harder than grasping isolated objects, because the robot needs to push and move objects around in order to create sufficient space for the fingers. These pre-grasping actions do not have an immediate utility, and may result in unnecessary delays. The utility of a pre-grasping action can be measured only by looking at the complete chain of consecutive actions and effects. This is a sequential decision-making problem that can be cast in the reinforcement learning framework. We solve this problem by learning the stochastic transitions between the observed states, using nonparametric density estimation. The learned transition function is used only for re-calculating the values of the executed actions in the observed states, with different policies. Values of new state-actions are obtained by regressing the values of the executed actions. The state of the system at a given time is a depth (3D) image of the scene. We use spectral clustering for detecting the different objects in the image. The performance of our system is assessed on a robot with real-world objects.

Robots are increasingly becoming key players in human-robot teams. To become effective teammates, robots must possess profound understanding of an environment, be able to reason about the desired commands and goals within a specific context, and be able to communicate with human teammates in a clear and natural way. To address these challenges, we have developed an intelligence architecture that combines cognitive components to carry out high-level cognitive tasks, semantic perception to label regions in the world, and a natural language component to reason about the command and its relationship to the objects in the world. This paper describes recent developments using this architecture on a fielded mobile robot platform operating in unknown urban environments. We report a summary of extensive outdoor experiments; the results suggest that a multidisciplinary approach to robotics has the potential to create competent human-robot teams.

We propose a language-driven navigation approach for commanding mobile robots in outdoor environments. We consider unknown environments that contain previously unseen objects. The proposed approach aims at making interactions in human-robot teams natural. Robots receive from human teammates commands in natural language, such as “Navigate around the building to the car left of the fire hydrant and near the tree”. A robot needs first to classify its surrounding objects into categories, using images obtained from its sensors. The result of this classification is a map of the environment, where each object is given a list of semantic labels, such as “tree” and “car”, with varying degrees of confidence. Then, the robot needs to ground the nouns in the command. Grounding, the main focus of this paper, is mapping each noun in the command into a physical object in the environment. We use a probabilistic model for interpreting the spatial relations, such as “left of” and “near”. The model is learned from examples provided by humans. For each noun in the command, a distribution on the objects in the environment is computed by combining spatial constraints with a prior given as the semantic classifier's confidence values. The robot needs also to ground the navigation mode specified in the command, such as “navigate quickly” and “navigate covertly”, as a cost map. The cost map is also learned from examples, using Inverse Optimal Control (IOC). The cost map and the grounded goal are used to generate a path for the robot. This approach is evaluated on a robot in a real-world environment. Our experiments clearly show that the proposed approach is efficient for commanding outdoor robots.

Natural language offers an intuitive and flexible means for humans to communicate with the robots that we will increasingly work alongside in our homes and workplaces. Recent advancements have given rise to robots that are able to interpret natural language manipulation and navigation commands, but these methods require a prior map of the robot's environment. In this paper, we propose a novel learning framework that enables robots to successfully follow natural language route directions without any previous knowledge of the environment. The algorithm utilizes spatial and semantic information that the human conveys through the command to learn a distribution over the metric and semantic properties of spatially extended environments. Our method uses this distribution in place of the latent world model and interprets the natural language instruction as a distribution over the intended behavior. A novel belief space planner reasons directly over the map and behavior distributions to solve for a policy using imitation learning. We evaluate our framework on a voice-commandable wheelchair. The results demonstrate that by learning and performing inference over a latent environment model, the algorithm is able to successfully follow natural language route directions within novel, extended environments.

High-mobility walking robots offer unique capabilities in complex off-road environments where wheeled vehicles are not able to travel. However, these environments can also pose significant autonomous navigation challenges. Key steps in planning a safe path for the robot autonomously include estimating the height of the support ground surface - which is often occluded by vegetation - and classifying the terrain and obstacles above the ground surface. This paper describes the development and experimental evaluation of a terrain classification and ground surface height estimation system to support autonomous navigation for a high-mobility walking robot. We provide experimental evaluation on an extensive, manually-labeled dataset collected from geographically diverse sites over a 28-month period.

Robot perception is generally viewed as the interpretation of data from various types of sensors such as cameras. In this paper, we study indirect perception where a robot can perceive new information by making inferences from non-visual observations of human teammates. As a proof-of-concept study, we specifically focus on a door detection problem in a stealth mission setting where a team operation must not be exposed to the visibility of the team's opponents. We use a special type of the Noisy-OR model known as BN2O model of Bayesian inference network to represent the inter-visibility and to infer the locations of the doors, i.e., potential locations of the opponents. Experimental results on both synthetic data and real person tracking data achieve an F-measure of over .9 on average, suggesting further investigation on the use of non-visual perception in human-robot team operations.

A key challenge of developing robots that work closely with people is creating a user interface that allows a user to communicate complex instructions to a robot quickly and easily. We consider a walking logistics support robot, which is designed to carry heavy loads to locations that are too difficult to reach with a wheeled or tracked vehicle. In this application the robot is carrying equipment and supplies for a group of pedestrians, and the primary task for the user interface is to keep the robot traveling with the overall group in the right formation. This paper presents a marker tracking system that uses near infrared cameras, retro-reflective markers, and LIDAR to allow a particular user to designate himself as the robot's leader, and guide the robot along a desired path. We provide an extensive quantitative evaluation to show that the proposed system is able to detect and track a leader through unconstrained and cluttered off-road environments under a wide variety of illumination and motion conditions.

Manipulating natural objects of irregular shapes, such as rocks, is an essential capability of robots operating in outdoor environments. Physics-based simulators are commonly used to plan stable grasps for man-made objects. However, planning is an expensive process that is based on simulating hand and object trajectories in different configurations, and evaluating the outcome of each trajectory. This problem is particularly concerning when the objects are irregular or cluttered, because the space of feasible grasps is significantly smaller, and more configurations need to be evaluated before finding a good one. In this paper, we first present a learning technique for fast detection of an initial set of potentially stable grasps in a cluttered scene. The best detected grasps are further optimized by fine-tuning the configuration of the hand in simulation. To reduce the computational burden of this last operation, we model the outcomes of the grasps as a Gaussian Process, and use an entropy-search method in order to focus the optimization on regions where the best grasp is most likely to be. This approach is tested on the task of clearing piles of real, unknown, rock debris with an autonomous robot. Empirical results show a clear advantage of the proposed approach when the time window for decision is short.

The use of spoken instructions in human-robot teams holds the promise of enabling untrained users to effectively control complex robotic systems in a natural and intuitive way. Providing robots with the capability to understand natural language directions would enable effortless coordination in human robot teams that operate in non-specialized unknown environments. However, natural language direction following through unknown environments requires understanding the meaning of language, using a partial semantic world model to generate actions in the world, and reasoning about the environment and landmarks that have not yet been detected. We address the problem of robots following natural language directions through complex unknown environments. By exploiting the structure of spatial language, we can frame direction following as a problem of sequential decision making under uncertainty. We learn a policy which predicts a sequence of actions that follow the directions by exploring the environment and discovering landmarks, backtracking when necessary, and explicitly declaring when it has reached the destination. We use imitation learning to train the policy, using demonstrations of people following directions. By training explicitly in unknown environments, we can generalize to situations that have not been encountered previously.

We address the problem of clearing a pile of unknown objects using an autonomous interactive perception approach. Our robot hypothesizes the boundaries of objects in a pile of unknown objects (object segmentation) and verifies its hypotheses (object detection) using deliberate interactions. To guarantee the safety of the robot and the environment, we use compliant motion primitives for poking and grasping. Every verified segmentation hypothesis can be used to parameterize a compliant controller for manipulation or grasping. The robot alternates between poking actions to verify its segmentation and grasping actions to remove objects from the pile. We demonstrate our method with a robotic manipulator. We evaluate our approach with real-world experiments of clearing cluttered scenes composed of unknown objects.

We present an interactive perceptual skill for segmenting, tracking, and modeling the kinematic structure of 3D articulated objects. This skill is a prerequisite for general manipulation in unstructured environments. Robot-environment interactions are used to move an unknown object, creating a perceptual signal that reveals the kinematic properties of the object. The resulting perceptual information can then inform and facilitate further manipulation. The algorithm is computationally efficient, handles partial occlusions, and depends on little object motion; it only requires sufficient texture for visual feature tracking. We conducted experiments with everyday objects on a robotic manipulation platform equipped with an RGB-D sensor. The results demonstrate the robustness of the proposed method to lighting conditions, object appearance, size, structure, and configuration.

Generating future states of the world is an essential component of high-level cognitive tasks such as planning. We explore the notion that such future-state generation is more widespread and forms an integral part of cognition. We call these generated states expectations, and propose that cognitive systems constantly generate expectations, match them to observed behavior and react when a difference exists between the two. We describe an ACT-R model that performs expectation-driven cognition on two tasks – pedestrian tracking and behavior classification. The model generates expectations of pedestrian movements to track them. The model also uses differences in expectations to identify distinctive features that differentiate these tracks. During learning, the model learns the association between these features and the various behaviors. During testing, it classifies pedestrian tracks by recalling the behavior associated with the features of each track. We tested the model on both single and multiple behavior datasets and compared the results against a k-NN classifier. The k-NN classifier outperformed the model in correct classifications, but the model had fewer incorrect classifications in the multiple behavior case, and both systems had about equal incorrect classifications in the single behavior case.

In this paper, we present an approach to bounded optimal planning and flexible execution for a robot team performing a set of spatially distributed tasks related by temporal ordering constraints such as precedence or synchronization. Furthermore, the manner in which the temporal constraints are satisfied impacts the overall utility of the team, due to the existence of both routing and delay costs. We present a bounded optimal offline planner for task allocation and scheduling in the presence of such cross-schedule dependencies, and a flexible, distributed online plan execution strategy. The integrated system performs task allocation and scheduling, executes the plans smoothly in the face of real-world variations in operation speed and task execution time, and ensures graceful degradation in the event of task failure. We demonstrate the capabilities of our approach on a team of three pioneer robots operating in an indoor environment. Experimental results demonstrate that the approach is effective for constrained planning and execution in the face of real-world variations.

Robots that operate in complex physical environments can improve the accuracy of their perception systems by fusing data from complementary sensing modalities. Furthermore, robots capable of motion can physically interact with these environments, and then leverage the sensory information they receive from these interactions. This paper explores the use of sound data as a new type of sensing modality to classify vehicle-terrain interactions from mobile robots operating outdoors, which can complement more typical non-contact sensors that are used for terrain classification. Acoustic data from microphones was recorded on a mobile robot interacting with different types of terrains and objects in outdoor environments. This data was then labeled and used offline to train a supervised multiclass classifier that can distinguish between these interactions based on acoustic data alone. To the best of the author's knowledge, this is the first time that acoustics has been used to classify a variety of interactions that a vehicle can have with its environment, so part of our contribution is to survey acoustic techniques from other domains and explore their efficacy for this application. The feature extraction methods we implement are derived from this survey, which then serve as inputs to our classifier. The multiclass classifier is then built from Support Vector Machines (SVMs). The results presented show an average of 92% accuracy across all classes, which suggest strong potential for acoustics to enhance perception systems on mobile robots.

Building robust and reliable autonomous navigation systems that generalize across environments and operating scenarios remains a core challenge in robotics. Machine learning has proven a significant aid in this task; in recent years learning from demonstration has become especially popular, leading to improved systems while requiring less expert tuning and interaction. However, these approaches still place a burden on the expert, specifically to choose the best demonstrations to provide. This work proposes two approaches for active learning from demonstration, in which the learning system requests specific demonstrations from the expert. The approaches identify examples for which expert demonstration is predicted to provide useful information on concepts which are either novel or uncertain to the current system. Experimental results demonstrate both improved generalization performance and reduced expert interaction when using these approaches.

This paper addresses the problem of planning a policy in large environments where the actions of a robot affect the distribution of uncertainty in the environment. We focus on the problem of robot navigation through interactive crowds and present an anytime receding horizon technique that uses AO* together with small look-up table solutions. We demonstrate the feasibility of this technique in simulations with thousands of uncertain dynamic obstacles.We also investigate the importance of modeling uncertainty and interaction in this problem. We identify situations in which a naïve approach works well and characterize conditions under which our approach is needed.

The high cost of damaging an expensive robot or injuring people or equipment in its environment make even rare failures unacceptable in many mobile robot applications. Often the objects that pose the highest risk for a mobile robot are those that were not present throughout previous successful traversals of an environment. Change detection, a closely related problem to novelty detection, is therefore of high importance to many mobile robotic applications that require a robot to operate repeatedly in the same environment. We present a novel algorithm for performing online change detection based on a previously developed robust online novelty detection system that uses a learned lower-dimensional representation of the feature space to perform measures of similarity. We then further improve this change detection system by incorporating online scene segmentation to better utilize contextual information in the environment. We validate these approaches through extensive experiments onboard a large outdoor mobile robot. Our results show that our approaches are robust to noisy sensor data and moderate registration errors and maintain their performance across diverse natural environments and conditions.

Tasks such as street mapping and security surveillance seek a route that traverses a given space to perform a function. These task functions may involve mapping the space for accurate modeling, sensing the space for unusual activity, or searching the space for an object. In many cases, the use of multiple robots can greatly improve the performance of these tasks. We assume a prior map is available, but it may be inaccurate due to factors such as occlusion, age, dynamic objects, and resolution limitations. In this work, we address the NP-hard problem of environmental coverage with incomplete prior map information using k robots. To utilize related algorithms in graph theory, we represent the environment as a graph and model the coverage problem as a k-Rural Postman Problem. Using this representation, we present a graph coverage approach for plan generation that can handle graph changes online. Our approach proposes two improvements to an existing heuristic algorithm for the coverage problem. Our improvements seek to equalize the length of the k paths by minimizing the length of the maximum tour. We evaluate our approach on a set of comparison tests in simulation.

GPS has become the de facto standard for obtaining a global position estimate during outdoor autonomous navigation. However, GPS can become degraded due to occlusion or interference, to the detriment of autonomous performance. In addition, GPS positions must be aligned with prior data, a tedious and continual process. This work presents a solution to these two problems based on learning generic observation models in the presence of GPS to use in its absence. The models are non-parametric and compared to traditional approaches require few assumptions about either the prior data available or a robot's onboard sensors. Along with allowing for localization to prior data under GPS-denied conditions, this learning approach can be coupled with an EM procedure to automatically register GPS and prior data positions. Experimental results are presented based on data from more than 15 km of autonomous navigation through challenging outdoor terrain.

Tasks such as street mapping and security surveillance seek a route that traverses a given space to perform a function. These task functions may involve mapping the space for accurate modeling, sensing the space for unusual activity, or searching the space for an object. In many cases, the use of multiple robots can greatly improve the performance of these tasks. We assume a prior map is available, but it may be inaccurate due to factors such as occlusion, age, dynamic objects, and resolution limitations. In this work, we address the NP-hard problem of environmental coverage with incomplete prior map information using multiple robots. To utilize related algorithms in graph theory, we represent the environment as a graph and model the coverage problem as a k-Rural Postman Problem where k represents the number of robots. Using this representation, the problem can be solved using a branch-and-bound approach to find an optimal route, and a route division heuristic to separate the route into k pieces. Since the branch-and-bound technique is exponential time, we present an approach to decompose the search problem into subtasks that are distributed among the robots. Using ideas from market-based approaches, we allow the robots to auction particular sections of the problem space to other robots as a way to more evenly divide the work and focus the search. Finally, we evaluate these methods on test graphs in simulation.

Novelty detection is often treated as a one-class classification problem: how to segment a data set of examples from everything else that would be considered novel or abnormal. Almost all existing novelty detection techniques, however, suffer from diminished performance when the number of less relevant, redundant or noisy features increases, as often the case with high-dimensional feature spaces. Many of these algorithms are also not suited for online use, a trait that is highly desirable for many robotic applications. We present a novelty detection algorithm that is able to address this sensitivity to high feature dimensionality by utilizing prior class information within the training set. Additionally, our anytime algorithm is well suited for online use when a constantly adjusting environmental model is beneficial. We apply this algorithm to online detection of novel perception system input on an outdoor mobile robot and argue such abilities could be key in increasing the real-world applications and impact of mobile robotics1.

At the heart of multi-robot task allocation lies the ability to compare multiple options in order to select the best. In some domains this utility evaluation is not straightforward, for example due to complex and unmodeled underlying dynamics or an adversary in the environment. Explicitly modeling these extrinsic influences well enough so that they can be accounted for in utility computation (and thus task allocation) may be intractable, but a human expert may be able to quickly gain some intuition about the form of the desired solution. We propose to harness the expert's intuition by applying imitation learning to the multi-robot task allocation domain. Using a market-based method, we steer the allocation process by biasing prices in the market according to a policy which we learn using a set of demonstrated allocations (the expert's solutions to a number of domain instances). We present results in two distinct domains: a disaster response scenario where a team of agents must put out fires that are spreading between buildings, and an adversarial game in which teams must make complex strategic decisions to score more points than their opponents.

We combine a visual odometry system with an aided inertial navigation filter to produce a precise and robust navigation system that does not rely on external infrastructure. Incremental structure from motion with sparse bundle adjustment using a stereo camera provides real-time highly accurate pose estimates of the sensor which are combined with six degree-of-freedom inertial measurements in an Extended Kalman Filter. The filter is structured to neatly handle the incremental and local nature of the visual odometry measurements and to handle uncertainties in the system in a principled manner. We present accurate results from data acquired in rural and urban scenes on a tractor and a passenger car travelling distances of several kilometers.

This paper presents two new approaches that enable the use of linear landmarks for planning paths with uncertainty in position in outdoor environments. The first approach uses a combination of forward simulation and entropy to reduce the dimensionality of the search space, while still preserving most of the information required to propagate a full covariance matrix. The second approach adds incremental binning to improve the quality of the solution while still keeping the dimensionality of the search space relatively low. These approaches provide a better compromise of speed and quality of the solution than most existing approaches, and are able to successfully utilize linear landmarks in large outdoor environments.

This paper presents two new approaches to planning with uncertainty in position that achieve better performance than existing techniques and that are able to incorporate changes in the environment in near real-time. Both approaches reuse previous searches and replan when changes in the environment are detected. The first approach, called replanning with prior map updates, assumes that changes in the prior map originate from the same source as the original prior map. Therefore, the updates are registered with the existing map, but not with the position of the robot. The resulting path after applying the updates is the same as if the updates had been present in the original prior map. The second approach, called replanning with sensor updates, assumes that changes in the prior map originate from on-board sensors. Therefore, the updates are registered with the robot, but not with the existing map. The resulting path after applying the updates is not the same path that would be found if the updates had taken place in the original prior map. Replanning with prior map updates achieves a speed-up to one order of magnitude with respect to forward planning from scratch, while replanning with sensor updates achieves a speedup of almost two orders of magnitude.

In the path clearance problem the robot needs to reach its goal as quickly as possible without being detected by enemies. The robot does not know the precise locations of enemies, but has a list of their possible locations. These locations can be sensed, and the robot can go through them if no enemy is present or has to take a detour otherwise. We have previously developed an approach to the path clearance problem when the robot itself had to sense possible enemy locations. In this paper we investigate the problem of path clearance when the robot can use multiple scout robots to sense the possible enemy locations. This becomes a high-dimensional planning under uncertainty problem. We propose an efficient and scalable approach to it. While the approach requires centralized planning, it can scale to very large environments and to a large number of scouts and allows the scouts to be heterogenous. The experimental results show the benefits of using our approach when multiple scout robots are available.

Many planning approaches adhere to the two-tiered architecture consisting of a long-range, low fidelity global planner and a short-range high fidelity local planner. While this architecture works well in general, it fails in highly constrained environments where the available paths are limited. These situations amplify mismatches between the global and local plans due to the smaller set of feasible actions. We present an approach that dynamically blends local plans online to match the field of global paths. Our blended local planner generates paths from control commands to ensure the safety of the robot as well as achieve the goal. Blending also results in more complete plans than an equivalent unblended planner when navigating cluttered environments. These properties enable the blended local planner to utilize a smaller control set while achieving more efficient planning time. We demonstrate the advantages of blending in simulation using a kinematic car model navigating through maps containing tunnels, cul-de-sacs, and random obstacles.

We present a sampling-based path planning and replanning algorithm that produces anytime solutions. Our algorithm tunes the quality of its result based on available search time by generating a series of solutions, each guaranteed to be better than the previous ones by a user-defined improvement bound. When updated information regarding the underlying search space is received, the algorithm efficiently repairs its previous solution. The result is an approach that provides low-cost solutions to high-dimensional search problems involving partially-known or dynamic environments. We discuss theoretical properties of the algorithm, provide experimental results on a simulated multirobot planning scenario, and present an implementation on a team of outdoor mobile robots

We present a novel approach to mobile robot navigation that enables navigation in outdoor environments without GPS. The approach uses a path planner that calculates optimal paths while considering uncertainty in position and that uses landmarks to localize the vehicle as part of the planning process. The landmarks are simple, possibly aliased, features that have been previously identified in a high-resolution map. These landmarks are combined with an estimate of the position of the vehicle to create unique and robust features. This approach reduces or eliminates the need for GPS and enables the use of prior maps with imperfect map registration.

In this paper, we present the generalized version of the Hoplites coordination framework designed to efficiently solve complex, tightly-coupled multirobot planning problems. Our extensions greatly increase the flexibility with which teammates can both plan and coordinate with each other; consequently, we can apply Hoplites to a wider range of domains and plan coordination between robots more efficiently. We apply our framework to the constrained exploration domain and compare Hoplites in simulation to competing distributed and centralized approaches. Our results demonstrate that Hoplites significantly outperforms both approaches in terms of the quality of solutions produced while remaining computationally competitive with much simpler approaches. We further demonstrate features such as scalability and validate our approach with field results from a team of large autonomous vehicles performing constrained exploration in an outdoor environment

This paper presents a learning-enhanced marketbased task allocation approach for oversubscribed domains. In oversubscribed domains all tasks cannot be completed within the required deadlines due to a lack of resources. We focus specifically on domains where tasks can be generated throughout the mission, tasks can have different levels of importance and urgency, and penalties are assessed for failed commitments. Therefore, agents must reason about potential future events before making task commitments. Within these constraints, existing market-based approaches to task allocation can handle task importance and urgency, but do a poor job of anticipating future tasks, and are hence assessed a high number of penalties. In this work, we enhance a baseline market-based task allocation approach using regression-based learning to reduce overall incurred penalties. We illustrate the effectiveness of our approach in a simulated disaster response scenario by comparing performance with a baseline market-approach.

This paper addresses the problem of planning for goal directed navigation in the environment that contains a number of possible adversary locations. It first shows that commonly used approaches such as assumptive planning can result in very long and costly robot traverses. It then shows how one can solve the same problem using a general probabilistic planner we have recently developed called PPCP (Probabilistic Planning with Clear Preferences). The paper also introduces two optimizations to the PPCP algorithm that make it run up to five times faster for our domain. The experimental results show that solving the problem with PPCP can substantially reduce the expected execution cost as compared to assumptive planning.

We present a replanning algorithm for repairing rapidly-exploring random trees when changes are made to the configuration space. Instead of abandoning the current RRT, our algorithm efficiently removes just the newly-invalid parts and maintains the rest. It then grows the resulting tree until a new solution is found. We use this algorithm to create a probabilistic analog to the widely-used D* family of deterministic algorithms, and demonstrate its effectiveness in a multirobot planning domain

As we progress towards a world where robots play an integral role in society, a critical problem that remains to be solved is the pickup team challenge; that is, dynamically formed heterogeneous robot teams executing coordinated tasks where little information is known a priori about the tasks, the robots, and the environments in which they would operate. Successful solutions to forming pickup teams would enable researchers to experiment with larger numbers of robots and enable industry to efficiently and cost-effectively integrate new robot technology with existing legacy teams. In this paper, we define the challenge of pickup teams and propose the treasure hunt domain for evaluating the performance of pickup teams. Additionally, we describe a basic implementation of a pickup team that can search and discover treasure in a previously unknown environment. We build on prior approaches in market-based task allocation and plays for synchronized task execution, to allocate roles amongst robots in the pickup team, and to execute synchronized team actions to accomplish the treasure hunt task

We present an interpolation-based planning and replanning algorithm that is able to produce direct, low-cost paths through three-dimensional environments. Our algorithm builds upon recent advances in 2D grid-based path planning and extends these techniques to 3D grids. It is often the case for robots navigating in full three-dimensional environments that moving in some directions is significantly more difficult than others (e.g. moving upwards is more expensive for most aerial vehicles). Thus, we also provide a facility to incorporate such characteristics into the planning process. Along with the derivation of the 3D interpolation function used by our planner, we present a number of results demonstrating its advantages and real-time capabilities

We present an anytime algorithm for planning paths through high-dimensional, non-uniform cost search spaces. Our approach works by generating a series of rapidly-exploring random trees (RRTs), where each tree reuses information from previous trees to improve its growth and the quality of its resulting path. We also present a number of modifications to the RRT algorithm that we use to bias the search in favor of less costly solutions. The resulting approach is able to produce an initial solution very quickly, then improve the quality of this solution while deliberation time allows. It is also able to guarantee that subsequent solutions will be better than all previous ones by a user-defined improvement bound. We demonstrate the effectiveness of the algorithm on both single robot and multirobot planning domains

Long range navigation by unmanned ground vehicles continues to challenge the robotics community. Efficient navigation requires not only intelligent on-board perception and planning systems, but also the effective use of prior knowledge of the vehicle's environment. This paper describes a system for supporting unmanned ground vehicle navigation through the use of heterogeneous overhead data. Semantic information is obtained through supervised classification, and vehicle mobility is predicted from available geometric data. This approach is demonstrated and validated through over 50 kilometers of autonomous traversal through complex natural environments

Market-based multirobot coordination approaches have received significant attention and are growing in popularity within the robotics research community. They have been successfully implemented in a variety of domains ranging from mapping and exploration to robot soccer. The research literature on market-based approaches to coordination has now reached a critical mass that warrants a survey and analysis. This paper addresses this need for a survey of the relevant literature by providing an introduction to market-based multirobot coordination, a review and analysis of the state of the art in the field, and a discussion of remaining research challenges

Mobile robots are often required to navigate environments for which prior maps are incomplete or inaccurate. In such cases, initial paths generated for the robots may need to be amended as new information is received that is in conflict with the original maps. The most widely used algorithm for performing this path replanning is Focussed Dynamic A* (D*), which is a generalization of A* for dynamic environments. D* has been shown to be up to two orders of magnitude faster than planning from scratch. In this paper, we present a new replanning algorithm that generates equivalent paths to D* while requiring about half its computation time. Like D*, our algorithm incrementally repairs previous paths and focusses these repairs towards the current robot position. However, it performs these repairs in a novel way that leads to improved efficiency.

In this paper we address tasks for multirobot teams that require solving a distributed multi-agent planning problem in which the actions of robots are tightly coupled. The uncertainty inherent in these tasks also necessitates persistent tight coordination between teammates throughout execution. Existing approaches to coordination cannot adequately meet the technical demands of such tasks. In response, we have developed a market-based framework, Hoplites, that consists of two novel coordination mechanisms. Passive coordination quickly produces locally-developed solutions while active coordination produces complex team solutions via negotiation between teammates. Robots use the market to efficiently vet candidate solutions and to choose the coordination mechanism that best matches the current demands of the task. In experiments, Hoplites significantly outperforms even its nearest competitors, particularly in the most complex instances of a domain. We also present implementation results on a team of mobile robots.

Recent research trends and technology developments are bringing us closer to the realization of autonomous multirobot systems performing increasingly complex missions. However, existing multirobot task allocation mechanisms treat tasks as simple, indivisible entities and ignore any inherent structure and semantics that such complex tasks might have. These properties can be exploited to produce more efficient team plans by giving individual robots the ability to come up with new ways to perform a task, or by allowing multiple robots to cooperate by sharing the subcomponents of a task, or both. In this paper, we introduce the complex task allocation problem and describe a distributed solution for efficiently allocating a set of complex tasks to a robot team. The advantages of explicitly modeling complex tasks during the allocation process is demonstrated by a comparison of our approach with existing task allocation algorithms in an area reconnaissance scenario. An implementation on a team of outdoor robots further validates our approach.

While market-based approaches, such as TraderBots, have shown much promise for efficient coordination of multirobot teams, the cost estimation mechanism and its impact on solution efficiency has not been investigated. This paper provides a first analysis of the cost estimation process in the TraderBots approach applied to a distributed sensing task. In the presented implementation, path costs are estimated using the D* path planning algorithm with optimistic costing of unknown map cells. The reported results show increased team efficiency when cost estimates reflect different environmental and mission characteristics. Thus, this paper demonstrates that market-based approaches can improve team efficiency if cost estimates take into account environmental and mission characteristics. These findings encourage future research on applying learning techniques for online modification of cost estimation and in market-based coordination.

We introduce a resolution-optimal path planner that considers uncertainty while optimizing any monotonic objective function such as mobility cost, risk, or energy expended. The resulting path minimizes the expected cost of the objective function, while ensuring that the uncertainty in the position of the robot does not compromise the safety of the robot or the reachability of the goal. Although the problem domain is stochastic in nature, our algorithm takes advantage of deterministic path-planning techniques to achieve significant performance improvements.

Many problems are easily expressed as an attempt to fulfill some goal while laboring under some set of constraints. Prior planning algorithms have addressed this in part, but there are few fast ways of working with more than just a few constraints. Extending algorithms designed for one constraint to multiple constraints is difficult due to the NP complete nature of the problem, prompting a switch to an approximation algorithm. This paper presents K2, a multiply-constrained planning algorithm which is an amalgamation of parts of H/spl I.bar/MCOP and Focussed D*. It accepts additive constraints over the path or over any fixed length section of the path. K2 operates quickly and produces results of acceptable quality.

Robustness is crucial for any robot team, especially when operating in dynamic environments. The physicality of robotic systems and their interactions with the environment make them highly prone to malfunctions of many kinds. Three principal categories in the possible space of robot malfunctions are communication failures, partial failure of robot resources necessary for task execution (or partial robot malfunction), and complete robot failure (or robot death). This paper addresses these three categories and explores means by which the TraderBots approach ensures robustness and promotes graceful degradation in team performance when faced with malfunctions.

Autonomous navigation in outdoor, off-road environments requires solving complex classification problems. Obstacle detection, road following and terrain classification are examples of tasks which have been successfully approached using supervised machine learning techniques for classification. Large amounts of training data are usually necessary in order to achieve satisfactory generalization. In such cases, manually labeling data becomes an expensive and tedious process. This work describes a method for reducing the amount of data that needs to be presented to a human trainer. The algorithm relies on kernel density estimation in order to identify "interesting" scenes in a dataset. Our method does not require any interaction with a human expert for selecting the images, and only minimal amounts of tuning are necessary. We demonstrate its effectiveness in several experiments using data collected with two different vehicles. We first show that our method automatically selects those scenes from a large dataset that a person would consider "important" for classification tasks. Secondly, we show that by labeling only few of the images selected by our method, we obtain classification performance that is comparable to the one reached after labeling hundreds of images from the same dataset.

We describe a heuristic search algorithm for generating optimal plans in a new class of decision problem, characterised by the incorporation of hidden state. The approach exploits the nature of the hidden state to reduce the state space by orders of magnitude. It then interleaves heuristic expansion of the reduced space with forwards and backwards propagation phases to produce a solution in a fraction of the time required by other techniques. Results are provided on an outdoor path planning application.

Autonomous navigation in vegetation is challenging because the vegetation often hides the load-bearing surface, which is used for evaluating the safety of potential actions. It is difficult to design rules for finding the true ground height in vegetation from forward looking sensor data, so we use an online adaptive method to automatically learn this mapping through experience with the world. This approach has been implemented on an autonomous tractor and has been tested in a farm setting. We describe the system and provide examples of finding obstacles and improving roll predictions in the presence of vegetation. We also show that the system can adapt to new vegetation conditions.

We present a heuristic-based algorithm for solving restricted Markov decision processes (MDPs). Our approach, which combines ideas from deterministic search and recent dynamic programming methods, focusses computation towards promising areas of the state space. It is thus able to significantly reduce the amount of processing required to produce a solution. We demonstrate this improvement by comparing the performance of our approach to the performance of several existing algorithms on a robotic path planning domain.

We describe an efficient method for planning in environments for which prior maps are plagued with uncertainty. Our approach processes the map to determine key areas whose uncertainty is crucial to the planning task. It then incorporates the uncertainty associated with these areas using the recently developed PAO algorithm to produce a fast, robust solution to the original planning task.

This paper presents a comparative study between three multirobot coordination schemes that span the spectrum of coordination approaches; a fully centralized approach that can produce optimal solutions, a fully distributed behavioral approach with minimal planned interaction between robots, and a market approach which sits in the middle of the spectrum. Several dimensions for comparison are proposed based on characteristics identified as important to multirobot application domains. Furthermore, simulation results are presented for comparisons along two of the suggested dimension: Number of robots in the team and Heterogeneity of the team. Results spanning different team sizes indicate that the market method compares favorably to the optimal solutions generated by the centralized approach in terms of cost, and compares favorably to the behavioral method in terms of computation time. All three methods are able to improve global cost by accounting for the heterogeneity of the robot team.

Describes TEMPEST, a planner that enables a solar-powered rover to reason about path selection and event placement in terms of available solar energy and anticipated power draw. Unlike previous path planners, TEMPEST solves the coupled path, path timing and resource management problem. It combines information about mission objectives, operational constraints, the planetary environment and rover performance, and employs the Incremental Search Engine, a search algorithm that produces optimal paths through high-dimensional spaces. In July 2001, TEMPEST supported the Sun-Synchronous Navigation Field Experiment on Devon Island in the Canadian Arctic. The planner successfully selected time-sequenced, closed-circuit paths that enabled a solar-powered planetary rover prototype to traverse a multi-kilometer path over 24 hours with battery energy reserve. The field trial results motivate future work in mission re-planning, multiple resource constraint analysis and improved speed and memory performance. Our objective is to fulfill a need for resource-cognizant autonomy that is critical for future long-distance planetary surface missions.

Presents an approach to efficient multirobot mapping and exploration which exploits a market architecture in order to maximize information gain while minimizing incurred costs. This system is reliable and robust in that it can accommodate dynamic introduction and loss of team members in addition to being able to withstand communication interruptions and failures. Results showing the capabilities of our system on a team of exploring autonomous robots are given.

Multirobot coordination, if made efficient and robust, promises high impact on automation. The challenge is to enable robots to work together in an intelligent manner to execute a global task. The market approach has had considerable success in the multirobot coordination domain. This paper investigates the effects of introducing opportunistic optimization with leaders to enhance market-based multirobot coordination. Leaders are able to optimize within subgroups of robots by collecting information about their tasks and status, and re-allocating the tasks within the subgroup in a more profitable manner. The presented work considers the effects of a leader optimizing a single subgroup, and some effects of multiple leaders optimizing overlapping subgroups. The implementations were tested on a variation of the distributed traveling salesman problem. Presented results show that global costs can be reduced, and hence task allocation can be improved, utilizing leaders.

Autonomous planetary rovers operating in vast unknown environments must operate efficiently because of size, power and computing limitations. Recently, we have developed a rover capable of efficient obstacle avoidance and path planning. The rover uses binocular stereo vision to sense potentially cluttered outdoor environments. Navigation is performed by a combination of several modules that each "vote" for the next best action for the robot to execute. The key distinction of our system is that it produces globally intelligent behavior with a small computational resource - all processing and decision making are done on a single processor. These algorithms have been tested on our outdoor prototype rover, Bullwinkle, and have recently driven the rover 100 m at a speed of 15 cm/sec. In this paper we report on the extension on the systems that we have previously developed that were necessary to achieve autonomous navigation in this domain.

For a system of cooperative mobile robots to be effective in real-world applications it must be able to efficiently execute a wide class of complex tasks in potentially unknown and unstructured environments. Previous research in multi-robot systems has either been limited to relatively structured domains or to small classes of feasible missions. This paper describes a field-capable system called GRAMMPS which addresses this problem by coupling a general-purpose interpreted grammar for task definition with dynamic planning techniques. GRAMMPS supports a general class of local navigation systems and heterogeneous groups of robots, providing optimal execution of missions given current world knowledge. Simulations illustrating the capabilities of this system are provided. Results showing successful runs of this system on two autonomous off-road vehicles are also given.

Mobile robots operating in vast outdoor unstructured environments often only have incomplete maps and must deal with new objects found during traversal. Path planning in such sparsely occupied regions must be incremental to accommodate new information, and, must use efficient representations. In previous work we have developed an optimal method D* to plan paths when the environment is not known ahead of time, but, rather is discovered as the robot moves around. To date, D* has been applied to a uniform grid representation for obstacles and free space. In this paper we propose the use of D* with framed quadtrees to improve the efficiency of planning paths in sparse environments. The new system has been tested in simulation as well on an autonomous jeep, equipped with local obstacle avoidance capabilities. We show how the use of framed quadtrees improves performance in terms of path length, computation speed, and memory requirements.

Excavators are used for the rapid removal of soil and other materials in mines, quarries, and construction sites. The automation of these machines offers promise for increasing productivity and improving safety. To date, most research in this area has focused on selected parts of the problem. In this paper we present a system that completely automates the truck loading task. The excavator uses two scanning laser rangefinders to recognize and localize the truck, measure the soil face, and detect obstacles. The excavator's software decides where to dig in the soil, where to dump in the truck, and how to quickly move between these points while detecting and stopping for obstacles. The system was fully implemented and was demonstrated to load trucks as fast as human operators.

For autonomously navigating vehicles, the automatic generation of dense geometric models of the environment is a computationally expensive process. Using first principles, it is possible to quantify the relationship between the raw throughput required of the perception system and the maximum safely achievable speed of the vehicle. We show that terrain mapping perception is of polynomial complexity in the response distance. To the degree that geometric perception consumes time, it also degrades real-time response characteristics. Given this relationship, several strategies of adaptive geometric perception arise which are practical for autonomous vehicles.

A basic requirement of autonomous vehicles is that of guaranteeing the safety of the vehicle by avoiding hazardous situations. This paper analyses this requirement in general terms of real-time response, and throughput. Several nondimensional expressions emerge which characterize requirements in canonical form.

A basic requirement of autonomous vehicles is that of guaranteeing the safety of the vehicle by avoiding hazardous situations. This paper analyses this requirement in general terms of the resolution and accuracy of sensors and computations. Several nondimensional expressions emerge which characterize requirements in canonical form.

For autonomously navigating vehicles, the automatic generation of dense geometric models of the environment is a computationally expensive process. Yet, analysis suggests that some approaches to mapping the environment in mobility scenarios can waste significant computational resources. This paper proposes a relatively simple method of approaching the minimum required perceptual throughput in a terrain mapping system, and hence the fastest possible update of the environmental model. We accomplish this by exploiting the constraints of typical mobility scenarios. The technique proposed will be applicable to any application that models the environment with a terrain map or other 2-1/2 D representation.

This paper describes a vision-based perception system which has been used to guide an automated harvester cutting fields of alfalfa hay. The system tracks the boundary between cut and uncut crop; indicates when the end of a crop row has been reached; and identifies obstacles in the harvester's path. The system adapts to local variations in lighting and crop conditions, and explicitly models and removes noise due to shadow. In field tests, the machine has successfully operated in four different locations, at sites in Pennsylvania, Kansas, and California. Using the vision system as the sole means of guidance, over 60 acres have been cut at speeds of up to 4.5 mph (typical human operating speeds range from 3-6 mph). Future work largely centers around combining vision and GPS based navigation techniques to produce a commercially viable product for use either as a navigation aid or for a completely autonomous system.

Presents an approach for real time planning and execution of the motions of complicated robotic systems. The approach is motivated by the observation that a robot's task can be described as a series of simple steps, or a script. The script is a general template which encodes knowledge for a class of tasks and is fitted to a specific instance of a task. The script receives information about its environment in the form of parameters, which it uses to bind variables in the template and allows it to deal with the current task conditions. Changes or variations in the robot's environment can be easily handled with this parameterized script approach. New tasks for the robot to perform can be added in the form of subscripts, which could handle exceptional cases. We apply this approach to the task of autonomous excavation, and demonstrate its validity on an actual hydraulic excavator. We obtain good results, with the autonomous system approaching the performance of an expert human operator.

Planning for multiple mobile robots in dynamic environments involves determining the optimal path each robot should follow to accomplish the goals of the mission, given the current knowledge available about the world. As knowledge increases or improves, the planning system should dynamically reassign robots to goals in order to continually minimize the time to complete the mission. In this paper, an example problem in this domain is explored and performance results of such a dynamic planning system are presented. The system was able to dynamically optimize the motion of 3 robots toward 6 goals in real time, improving the average overall mission performance compared to a static planner by 25%. A preliminary design for a practical solution to a wider class of problems is also discussed.

Automation of agricultural harvesting equipment in the near term appears both economically viable and technically feasible. This paper describes a vision-based algorithm which guides a harvester by tracking the line between cut and uncut crop. Using this algorithm, a harvester has successfully cut roughly one acre of crop to date, at speeds of up to 4.5 miles an hour in an actual alfalfa field. A broad range of methods for detecting the crop cut boundary were considered, including both range-based and vision-based techniques; several of these methods were implemented and evaluated on data from an alfalfa field. The final crop-line detection algorithm is presented, which operates by computing the best-fit step function of a normalized-color measure of each row of an RGB image. Results of the algorithm on some sample crop images are shown, and potential improvements are discussed.

For many navigation tasks, a single sensing modality is sufficiently rich to accomplish the desired motion control goals; for practical autonomous outdoor navigation, a single sensing modality is a crippling limitation on what tasks can be undertaken. Using a neural network paradigm particularly well suited to sensor fusion the authors have successfully performed simulated and real-world navigation tasks that required the use of multiple sensing modalities.

Most autonomous outdoor navigation systems tested on actual robots have centered on local navigation tasks such as avoiding obstacles or following roads. Global navigation has been limited to simple wandering, path tracking, straight-line goal seeking behaviors, or executing a sequence of scripted local behaviors. These capabilities are insufficient for unstructured and unknown environments, where replanning may be needed to account for new information discovered in every sensor image. To address these problems, the authors developed a complete system that integrates local and global navigation. The local system uses a scanning laser rangefinder to detect and avoid obstacles. The global system uses an incremental path planning algorithm to optimally replan the global path for each detected obstacle. A control arbiter steers the robot to achieve the proper balance between safety and goal acquisition. This system was tested on a real robot and successfully drove it 1.4 kilometers to find a goal given no a priori map of the environment.

The task of planning trajectories for a mobile robot has received considerable attention in the research literature. Most of the work assumes the robot has a complete and accurate model of its environment before it begins to move; less attention has been paid to the problem of partially known environments. This situation occurs for an exploratory robot or one that must move to a goal location without the benefit of a floorplan or terrain map. Existing approaches plan an initial path based on known information and then modify the plan locally or replan the entire path as the robot discovers obstacles with its sensors, sacrificing optimality or computational efficiency respectively. This paper introduces a new algorithm, D*, capable of planning paths in unknown, partially known, and changing environments in an efficient, optimal, and complete manner.>

The authors present an iconic approach for estimating the pose of a mobile robot equipped with a radial laser rangefinder that requires minimal structure in the environment. The algorithm uses a connected set of short line segments to approximate the shape of any environment and can easily be constructed by the rangefinder itself. The authors describe techniques for efficiently managing the environment map, matching the sensor data to the map and computing the robot's position. Accuracy and runtime results for the implementation are included.>

The authors describe a system that automates a continuous miner, enabling it to maneuver in highly constrained environments and cut coal without a human operator onboard. The system consists of a modified continuous miner, a laser range sensor, a SPARCstation, and control software. To date, the system has been tested on a mobile robot and on a continuous miner both above ground and in a real coal mine. The authors note that this system is the first instance of an intelligent robotic system for cutting coal.>

This paper describes the current status of the Autonomous Land Vehicle research at Carnegie-Mellon University's Robotics Institute, focusing primarily on the system architecture. We begin with a discussion of the issues concerning outdoor navigation, then describe the various perception, planning, and control components of our system that address these issues. We describe the CODGER software system for integrating these components into a single system, synchronizing the data flow between them in order to maximize parallelism. Our system is able to drive a robot vehicle continuously with two sensors, a color camera and a laser rangefinder, on a network of sidewalks, up a bicycle slope, and through a curved road through an area populated with trees. Finally, we discuss the results of our experiments, as well as problems uncovered in the process and our plans for addressing them.

This paper describes sensor fusion in the context of an autonomous mobile robot. The requirements of a complex mission, real-world operation, and real-time control dictate many facets of the system architecture. The hardware architecture must include both general-purpose and special-purpose computers, and multiple sensors of various modalities (vision, range, etc.). The software architecture must allow modular development of a parallel system that supports many perceptual modalities and navigation planning tasks, but at the same time enforces global consistency regarding position and orientation of the vehicle and sensors. We are building such a system at CMU, called the NAVLAB system, based on a commercial truck with computer controls and studded with cameras and other sensors. This paper describes the software architecture of the NAVLAB, consisting of two parts: a "whiteboard" system called CODGER that is similar to a blackboard but supports parallelism in the knowledge source modules, and an organized collection of perceptual and navigational modules tied together by the CODGER system. In general, the system philosophy is to provide as much top-down guidance as possible, and to exploit sensor modality differences to produce complementary rather than competing perceptual processes in the system. In this way, the limitations of each sensor modality are compensated for as much as possible by other sensors or by higher level knowledge. The NAVLAB is being produced as part of the DARPA Strategic Computing Initiative, in conjunction with the Autonomous Land Vehicle project.