Anthony Stentz

IROS Conference 2021 Conference Paper

Multiclass Terrain Classification using Sound and Vibration from Mobile Robot Terrain Interaction

• Jacqueline Libby
• Anthony Stentz

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.

IJCAI Conference 2016 Conference Paper

Learning Qualitative Spatial Relations for Robotic Navigation

• Abdeslam Boularias
• Felix Duvallet
• Jean Oh
• Anthony Stentz

We consider the problem of robots following natural language commands through previously unknown outdoor environments. A robot receives commands in natural language, such as Navigate around the building to the car left of the fire hydrant and near the tree. The 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 or car, with varying degrees of confidence. Then, the robot needs to ground the nouns in the command, i. e. , mapping each noun in the command into a physical object in the environment. The robot needs also to ground a specified navigation mode, such as navigate quickly or navigate covertly, as a cost map. In this work, we show how to ground nouns and navigation modes by learning from examples demonstrated by humans.

ICRA Conference 2015 Conference Paper

Grounding spatial relations for outdoor robot navigation

• Abdeslam Boularias
• Felix Duvallet
• Jean Oh
• Anthony Stentz

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.

IROS Conference 2015 Conference Paper

Inferring door locations from a teammate's trajectory in stealth human-robot team operations

• Jean Oh
• Luis Ernesto Navarro-Serment
• Arne Suppé
• Anthony Stentz
• Martial Hebert

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.

IROS Conference 2015 Conference Paper

Leader tracking for a walking logistics robot

• Michal Perdoch
• David M. Bradley
• Jonathan K. Chang
• Herman Herman
• Peter Rander
• Anthony Stentz

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.

ICRA Conference 2015 Conference Paper

Learning models for following natural language directions in unknown environments

• Sachithra Hemachandra
• Felix Duvallet
• Thomas M. Howard
• Nicholas Roy
• Anthony Stentz
• Matthew R. Walter

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.

AAAI Conference 2015 Conference Paper

Learning to Manipulate Unknown Objects in Clutter by Reinforcement

• Abdeslam Boularias
• James Bagnell
• Anthony Stentz

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

IROS Conference 2015 Conference Paper

Scene understanding for a high-mobility walking robot

• David M. Bradley
• Jonathan K. Chang
• David Silver 0002
• Matthew Powers
• Herman Herman
• Peter Rander
• Anthony Stentz

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.

AAAI Conference 2015 Conference Paper

Toward Mobile Robots Reasoning Like Humans

• Jean Oh
• Arne Suppé
• Felix Duvallet
• Abdeslam Boularias
• Luis Navarro-Serment
• Martial Hebert
• Anthony Stentz
• Jerry Vinokurov

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.

AAAI Conference 2014 Conference Paper

Efficient Optimization for Autonomous Robotic Manipulation of Natural Objects

• Abdeslam Boularias
• James Bagnell
• Anthony Stentz

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.

ICRA Conference 2013 Conference Paper

Clearing a pile of unknown objects using interactive perception

• Dov Katz
• Moslem Kazemi
• J. Andrew Bagnell
• Anthony Stentz

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.

AAMAS Conference 2013 Conference Paper

Enhancing Robot Perception Using Human Teammates

• Jean Oh
• Arne Suppe
• Anthony Stentz
• Martial Hebert

In robotics research, perception is one of the most challenging tasks. In contrast to existing approaches that rely only on computer vision, we propose an alternative method for improving perception by learning from human teammates. To evaluate, we apply this idea to a door detection problem. A set of preliminary experiments has been completed using software agents with real vision data. Our results demonstrate that information inferred from teammate observations significantly improves the perception precision.

ICRA Conference 2013 Conference Paper

Imitation learning for natural language direction following through unknown environments

• Felix Duvallet
• Thomas Kollar
• Anthony Stentz

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.

ICRA Conference 2013 Conference Paper

Interactive segmentation, tracking, and kinematic modeling of unknown 3D articulated objects

• Dov Katz
• Moslem Kazemi
• J. Andrew Bagnell
• Anthony Stentz

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.

ICRA Conference 2012 Conference Paper

Active learning from demonstration for robust autonomous navigation

• David Silver 0002
• J. Andrew Bagnell
• Anthony Stentz

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.

IROS Conference 2012 Conference Paper

Anytime policy planning in large dynamic environments with interactive uncertainty

• Bradford Neuman
• Anthony Stentz

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.

AAAI Conference 2012 Conference Paper

Using Expectations to Drive Cognitive Behavior

• Unmesh Kurup
• Christian Lebiere
• Anthony Stentz
• Martial Hebert

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.

ICRA Conference 2012 Conference Paper

Using sound to classify vehicle-terrain interactions in outdoor environments

• Jacqueline Libby
• Anthony Stentz

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.

ICRA Conference 2012 Conference Paper

xBots: An approach to generating and executing optimal multi-robot plans with cross-schedule dependencies

• G. Ayorkor Mills-Tettey
• Balajee Kannan
• Brett Browning
• Anthony Stentz
• M. Bernardine Dias

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.

ICRA Conference 2011 Conference Paper

An efficient algorithm for environmental coverage with multiple robots

• Ling Xu
• Anthony Stentz

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.

AAMAS Conference 2011 Conference Paper

Bounded Optimal Team Coordination with Temporal Constraints and Delay Penalties

• G. Ayorkor Korsah
• Anthony Stentz
• M. Bernardine Dias

We address the problem of optimally assigning spatially distributed tasks to a team of heterogeneous mobile agents in domains with inter-task temporal constraints, such as precedence constraints. Due to delay penalties, satisfying the temporal constraints impacts the overall team cost. We present a mathematical model of the problem, a benchmark anytime bounded optimal solution process, and an analysis of the impact of delay penalties on problem difficulty.

IROS Conference 2011 Conference Paper

Market-based coordination of coupled robot systems

• Ling Xu
• Anthony Stentz

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.

IROS Conference 2011 Conference Paper

Monte Carlo Localization and registration to prior data for outdoor navigation

• David Silver 0002
• Anthony Stentz

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.

ICRA Conference 2011 Conference Paper

Segmentation-based online change detection for mobile robots

• Bradford Neuman
• Boris Sofman
• Anthony Stentz
• J. Andrew Bagnell

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.

IROS Conference 2010 Conference Paper

A new approach to vision-aided inertial navigation

• Jean-Philippe Tardif
• Michael David George
• Michel Laverne
• Alonzo Kelly
• Anthony Stentz

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.

ICRA Conference 2010 Conference Paper

Anytime online novelty detection for vehicle safeguarding

• Boris Sofman
• J. Andrew Bagnell
• Anthony Stentz

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 robotics 1.

IROS Conference 2010 Conference Paper

Imitation learning for task allocation

• Felix Duvallet
• Anthony Stentz

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.

AIJ Journal 2009 Journal Article

Probabilistic planning with clear preferences on missing information

• Maxim Likhachev
• Anthony Stentz

For many real-world problems, environments at the time of planning are only partially-known. For example, robots often have to navigate partially-known terrains, planes often have to be scheduled under changing weather conditions, and car route-finders often have to figure out paths with only partial knowledge of traffic congestions. While general decision-theoretic planning that takes into account the uncertainty about the environment is hard to scale to large problems, many such problems exhibit a special property: one can clearly identify beforehand the best (called clearly preferred) values for the variables that represent the unknowns in the environment. For example, in the robot navigation problem, it is always preferred to find out that an initially unknown location is traversable rather than not, in the plane scheduling problem, it is always preferred for the weather to remain a good flying weather, and in route-finding problem, it is always preferred for the road of interest to be clear of traffic. It turns out that the existence of the clear preferences can be used to construct an efficient planner, called PPCP (Probabilistic Planning with Clear Preferences), that solves these planning problems by running a series of deterministic low-dimensional A*-like searches. In this paper, we formally define the notion of clear preferences on missing information, present the PPCP algorithm together with its extensive theoretical analysis, describe several useful extensions and optimizations of the algorithm and demonstrate the usefulness of PPCP on several applications in robotics. The theoretical analysis shows that once converged, the plan returned by PPCP is guaranteed to be optimal under certain conditions. The experimental analysis shows that running a series of fast low-dimensional searches turns out to be much faster than solving the full problem at once since memory requirements are much lower and deterministic searches are orders of magnitude faster than probabilistic planning.

IROS Conference 2009 Conference Paper

Using linear landmarks for path planning with uncertainty in outdoor environments

• Juan Pablo Gonzalez
• Anthony Stentz

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.

AIJ Journal 2008 Journal Article

Anytime search in dynamic graphs

• Maxim Likhachev
• Dave Ferguson
• Geoff Gordon
• Anthony Stentz
• Sebastian Thrun

Agents operating in the real world often have limited time available for planning their next actions. Producing optimal plans is infeasible in these scenarios. Instead, agents must be satisfied with the best plans they can generate within the time available. One class of planners well-suited to this task are anytime planners, which quickly find an initial, highly suboptimal plan, and then improve this plan until time runs out. A second challenge associated with planning in the real world is that models are usually imperfect and environments are often dynamic. Thus, agents need to update their models and consequently plans over time. Incremental planners, which make use of the results of previous planning efforts to generate a new plan, can substantially speed up each planning episode in such cases. In this paper, we present an A∗-based anytime search algorithm that produces significantly better solutions than current approaches, while also providing suboptimality bounds on the quality of the solution at any point in time. We also present an extension of this algorithm that is both anytime and incremental. This extension improves its current solution while deliberation time allows and is able to incrementally repair its solution when changes to the world model occur. We provide a number of theoretical and experimental results and demonstrate the effectiveness of the approaches in a robot navigation domain involving two physical systems. We believe that the simplicity, theoretical properties, and generality of the presented methods make them well suited to a range of search problems involving dynamic graphs.

IROS Conference 2008 Conference Paper

Blended local planning for generating safe and feasible paths

• Ling Xu
• Anthony Stentz

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.

ICRA Conference 2008 Conference Paper

Information value-driven approach to path clearance with multiple scout robots

• Maxim Likhachev
• Anthony Stentz

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.

ICRA Conference 2008 Conference Paper

Replanning with uncertainty in position: Sensor updates vs. prior map updates

• Juan Pablo Gonzalez
• Anthony Stentz

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.

ICRA Conference 2007 Conference Paper

A Generalized Framework for Solving Tightly-coupled Multirobot Planning Problems

• Nidhi Kalra
• Dave Ferguson 0001
• Anthony Stentz

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

ICRA Conference 2007 Conference Paper

Anytime, Dynamic Planning in High-dimensional Search Spaces

• Dave Ferguson 0001
• Anthony Stentz

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

IROS Conference 2007 Conference Paper

Goal directed navigation with uncertainty in adversary locations

• Maxim Likhachev
• Anthony Stentz

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.

IROS Conference 2007 Conference Paper

Learning-enhanced market-based task allocation for oversubscribed domains

• Edward Gil Jones
• M. Bernardine Dias
• Anthony Stentz

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.

ICRA Conference 2007 Conference Paper

Planning with Uncertainty in Position Using High-Resolution Maps

• Juan Pablo Gonzalez
• Anthony Stentz

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.

IROS Conference 2006 Conference Paper

3D Field D: Improved Path Planning and Replanning in Three Dimensions

• Joseph Carsten
• Dave Ferguson 0001
• Anthony Stentz

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

IROS Conference 2006 Conference Paper

Anytime RRTs

• Dave Ferguson 0001
• Anthony Stentz

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

ICRA Conference 2006 Conference Paper

Dynamically formed Heterogeneous Robot Teams Performing Tightly-coordinated Tasks

• Edward Gil Jones
• Brett Browning
• M. Bernardine Dias
• Brenna Argall
• Manuela Veloso
• Anthony Stentz

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

IROS Conference 2006 Conference Paper

Experimental Analysis of Overhead Data Processing To Support Long Range Navigation

• David Silver 0002
• Boris Sofman
• Nicolas Vandapel
• J. Andrew Bagnell
• Anthony Stentz

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

ICRA Conference 2006 Conference Paper

Replanning with RRTs

• Dave Ferguson 0001
• Nidhi Kalra
• Anthony Stentz

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

ICAPS Conference 2005 Conference Paper

Anytime Dynamic A*: An Anytime, Replanning Algorithm

• Maxim Likhachev
• Dave Ferguson 0001
• Geoffrey J. Gordon
• Anthony Stentz
• Sebastian Thrun

We present a graph-based planning and replanning algorithm able to produce bounded suboptimal solutions in an anytime fashion. Our algorithm tunes the quality of its solution based on available search time, at every step reusing previous search efforts. When updated information regarding the underlying graph is received, the algorithm incrementally repairs its previous solution. The result is an approach that combines the benefits of anytime and incremental planners to provide efficient solutions to complex, dynamic search problems. We present theoretical analysis of the algorithm, experimental results on a simulated robot kinematic arm, and two current applications in dynamic path planning for outdoor mobile robots.

ICRA Conference 2005 Conference Paper

Complex Task Allocation For Multiple Robots

• Robert Zlot
• Anthony Stentz

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.

ICRA Conference 2005 Conference Paper

Hoplites: A Market-Based Framework for Planned Tight Coordination in Multirobot Teams

• Nidhi Kalra
• Dave Ferguson 0001
• Anthony Stentz

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.

IROS Conference 2005 Conference Paper

Improving cost estimation in market-based coordination of a distributed sensing task

• M. Bernardine Dias
• Bernard Ghanem
• Anthony Stentz

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.

IROS Conference 2005 Conference Paper

K2: an efficient approximation algorithm for globally and locally multiply-constrained planning problems

• Andrés Santiago Pérez-Bergquist
• Anthony Stentz

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.

IROS Conference 2005 Conference Paper

Planning with uncertainty in position an optimal and efficient planner

• Juan Pablo Gonzalez
• Anthony Stentz

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.

ICRA Conference 2005 Conference Paper

The Delayed D* Algorithm for Efficient Path Replanning

• Dave Ferguson 0001
• Anthony Stentz

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.

ICRA Conference 2004 Conference Paper

Enabling Learning from Large Datasets: Applying Active Learning to Mobile Robotics

• Cristian Dima
• Martial Hebert
• Anthony Stentz

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.

ICRA Conference 2004 Conference Paper

Online Adaptive Rough-terrain Navigation Vegetation

• Carl K. Wellington
• Anthony Stentz

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.

ICRA Conference 2004 Conference Paper

PAO for Planning with Hidden State

• Dave Ferguson 0001
• Anthony Stentz
• Sebastian Thrun

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.

IROS Conference 2004 Conference Paper

Planning with imperfect information

• Dave Ferguson 0001
• Anthony Stentz

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.

ICRA Conference 2004 Conference Paper

Robust Multirobot Coordination in Dynamic Environments

• M. Bernardine Dias
• Marc Zinck
• Robert Zlot
• Anthony Stentz

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.

IROS Conference 2003 Conference Paper

A comparative study between centralized, market-based, and behavioral multirobot coordination approaches

• M. Bernardine Dias
• Anthony Stentz

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.

AAMAS Conference 2003 Conference Paper

Task Allocation Using a Distributed Market-Based Planning Mechanism

• Dani Goldberg
• Vincent Cicirello
• M. Bernardine Dias
• Reid Simmons
• Stephen Smith
• Anthony Stentz

AAAI Conference 2002 Conference Paper

CD*: A Real-Time Resolution Optimal Re-Planner for Globally Constrained Problems

• Anthony Stentz

Many problems in robotics and AI, such as the find-path problem, call for optimal solutions that satisfy global constraints. The problem is complicated when the cost information is unknown, uncertain, or changing during execution of the solution. Such problems call for efficient re-planning during execution to account for the new information acquired. This paper presents a novel real-time algorithm, Constrained D* (CD*), that re-plans resolution optimal solutions subject to a global constraint. CD* performs a binary search on a weight parameter that sets the balance between the optimality and feasibility cost metrics. In each stage of the search, CD* uses Dynamic A* (D*) to update the weight selection for that stage. On average, CD* updates a feasible and resolution optimal plan in less than a second, enabling it to be used in a real-time robot controller. Results are presented for simulated problems. To the author’s knowledge, CD* is the fastest algorithm to solve this class of problems.

ICRA Conference 2002 Conference Paper

Mission Planning for the Sun-Synchronous Navigation Field Experiment

• Paul Tompkins
• Anthony Stentz
• William Whittaker

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.

ICRA Conference 2002 Conference Paper

Multi-Robot Exploration Controlled by a Market Economy

• Robert Zlot
• Anthony Stentz
• M. Bernardine Dias
• Scott Thayer

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.

IROS Conference 2002 Conference Paper

Opportunistic optimization for market-based multirobot control

• M. Bernardine Dias
• Anthony Stentz

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.

ICRA Conference 2000 Conference Paper

Recent Progress in Local and Global Traversability for Planetary Rovers

• Sanjiv Singh
• Reid G. Simmons
• Trey Smith
• Anthony Stentz
• Vandi Verma
• Alex Yahja
• Kurt Schwehr

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.

IROS Conference 1998 Conference Paper

A robotic excavator for autonomous truck loading

• Anthony Stentz
• John Bares
• Sanjiv Singh
• Patrick Rowe

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.

ICRA Conference 1998 Conference Paper

Framed-Quadtree Path Planning for Mobile Robots Operating in Sparse Environments

• Alex Yahja
• Anthony Stentz
• Sanjiv Singh
• Barry Brumitt

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.

ICRA Conference 1998 Conference Paper

GRAMMPS: A Generalized Mission Planner for Multiple Mobile Robots in Unstructured Environments

• Barry Brumitt
• Anthony Stentz

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.

ICRA Conference 1997 Conference Paper

Analysis of requirements for high speed rough terrain autonomous mobility. I. Throughput and response

• Alonzo Kelly
• Anthony Stentz

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.

ICRA Conference 1997 Conference Paper

Analysis of requirements for high speed rough terrain autonomous mobility. II. Resolution and accuracy

• Alonzo Kelly
• Anthony Stentz

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.

ICRA Conference 1997 Conference Paper

Computational complexity of terrain mapping perception in autonomous mobility

• Alonzo Kelly
• Anthony Stentz

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.

IROS Conference 1997 Conference Paper

Minimum throughput adaptive perception for high speed mobility

• Alonzo Kelly
• Anthony Stentz

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.

IROS Conference 1997 Conference Paper

Parameterized scripts for motion planning

• Patrick Rowe
• Anthony Stentz

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.

IROS Conference 1997 Conference Paper

Vision-based perception for an automated harvester

• Mark Ollis
• Anthony Stentz

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.

ICRA Conference 1996 Conference Paper

Dynamic mission planning for multiple mobile robots

• Barry Brumitt
• Anthony Stentz

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.

ICRA Conference 1996 Conference Paper

First results in vision-based crop line tracking

• Mark Ollis
• Anthony Stentz

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.

IROS Conference 1995 Conference Paper

A complete navigation system for goal acquisition in unknown environments

• Anthony Stentz
• Martial Hebert

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.

IROS Conference 1995 Conference Paper

Sensor fusion for autonomous outdoor navigation using neural networks

• Ian Lane Davis
• Anthony Stentz

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.

IJCAI Conference 1995 Conference Paper

The Focussed D" Algorithm for Real-Time Replannig

• Anthony Stentz

Finding the lowest-cost path through a graph is central to many problems including route planning for a mobile robot If arc costs change during the traverse then the remainder of the path may need to be replanned This is the case for a sensor-equipped mobile robot with imperfect information about its environment As the robot acquires additional information via its sensors it can revise its plan to reduce the total cost of the traverse If the prior information is grossly incomplete the robot may discover useful information in every piece of sensor data. During replanning, the robot must either wait for the new path to be computed or move in Lhe wrong direction therefore rapid replanning is essential The D* algorithm (Dynamic A*) plans optimal traverses ID real-time by incrementally repairing paths to the robot s state as new information is discovered This paper describes an extension to D* that focusses the repairs to significantly reduce the total time required for the initial path calculation and subsequent replanning operations This extension completes the development of the D* algorithm as a f u l l generalizaUon of A* for dynamic environments where arc costs can change during the traverse of the solution path 1

ICRA Conference 1994 Conference Paper

Optimal and Efficient Path Planning for Partially-Known Environments

• Anthony Stentz

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

ICRA Conference 1992 Conference Paper

A robotic system for underground coal mining

• Gary Shaffer
• Anthony Stentz

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

ICRA Conference 1992 Conference Paper

An iconic position estimator for a 2D laser rangefinder

• Javier González Jiménez 0001
• Anthony Stentz
• Aníbal Ollero

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

ICRA Conference 1987 Conference Paper

The CMU system for mobile robot navigation

• Yoshimasa Goto
• Anthony Stentz

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.

ICRA Conference 1986 Conference Paper

An architecture for sensor fusion in a mobile robot

• Steven A. Shafer
• Anthony Stentz
• Charles E. Thorpe

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.

IJCAI Conference 1985 Conference Paper

First Results in Robot Road-Following

• Richard Wallace
• Anthony Stentz
• Charles Thorpe
• Hans Maravec
• William Whittaker
• Takeo Kanade