Author name cluster

Dave Ferguson 0001

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

25 papers

1 author row

ICRA Conference 2009 Conference Paper

Combining search and action for mobile robots

Geoffrey A. Hollinger
Dave Ferguson 0001
Siddhartha S. Srinivasa
Sanjiv Singh

We explore the interconnection between search and action in the context of mobile robotics. The task of searching for an object and then performing some action with that object is important in many applications. Of particular interest to us is the idea of a robot assistant capable of performing worthwhile tasks around the home and office (e. g. , fetching coffee, washing dirty dishes, etc.). We prove that some tasks allow for search and action to be completely decoupled and solved separately, while other tasks require the problems to be analyzed together. We complement our theoretical results with the design of a combined search/action approximation algorithm that draws on prior work in search. We show the effectiveness of our algorithm by comparing it to state-of-the-art solvers, and we give empirical evidence showing that search and action can be decoupled for some useful tasks. Finally, we demonstrate our algorithm on an autonomous mobile robot performing object search and delivery in an office environment.

ICRA Conference 2009 Conference Paper

Efficient C-space and cost function updates in 3D for unmanned aerial vehicles

Sebastian A. Scherer
Dave Ferguson 0001
Sanjiv Singh

When operating in partially-known environments, autonomous vehicles must constantly update their maps and plans based on new sensor information. Much focus has been placed on developing efficient incremental planning algorithms that are able to efficiently replan when the map and associated cost function changes. However, much less attention has been placed on efficiently updating the cost function used by these planners, which can represent a significant portion of the time spent replanning. In this paper, we present the limited incremental distance transform algorithm, which can be used to efficiently update the cost function used for planning when changes in the environment are observed. Using this algorithm it is possible to plan paths in a completely incremental way starting from a list of changed obstacle classifications. We present results comparing the algorithm to the Euclidean distance transform and a mask-based incremental distance transform algorithm. Computation time is reduced by an order of magnitude for a UAV application. We also provide example results from an autonomous micro aerial vehicle with on-board sensing and computing.

ICRA Conference 2009 Conference Paper

GATMO: A Generalized Approach to Tracking Movable Objects

Garratt Gallagher
Siddhartha S. Srinivasa
J. Andrew Bagnell
Dave Ferguson 0001

We present GATMO (Generalized Approach to Tracking Movable Objects), a system for localization and mapping that incorporates the dynamic nature of the environment while maintaining semantic labels. Objects in the environment are broken down into multiple mobility levels, from static (walls) to highly mobile (people), by maintaining a history of object movement. Object classification is accomplished through a multi-layer, multi-hypothesis approach that does not rely on any static features such as shape or size. Maps are stored in an efficient manner that incorporates a history of previous orientations of each object. GATMO is initialized with a static map; it subsequently changes the map over time as objects in the map change position.

ICRA Conference 2009 Conference Paper

Manipulation planning on constraint manifolds

Dmitry Berenson
Siddhartha S. Srinivasa
Dave Ferguson 0001
James J. Kuffner

We present the Constrained Bi-directional Rapidly-Exploring Random Tree (CBiRRT) algorithm for planning paths in configuration spaces with multiple constraints. This algorithm provides a general framework for handling a variety of constraints in manipulation planning including torque limits, constraints on the pose of an object held by a robot, and constraints for following workspace surfaces. CBiRRT extends the Bi-directional RRT (BiRRT) algorithm by using projection techniques to explore the configuration space manifolds that correspond to constraints and to find bridges between them. Consequently, CBiRRT can solve many problems that the BiRRT cannot, and only requires one additional parameter: the allowable error for meeting a constraint. We demonstrate the CBiRRT on a 7DOF WAM arm with a 4DOF Barrett hand on a mobile base. The planner allows this robot to perform household tasks, solve puzzles, and lift heavy objects.

ICRA Conference 2009 Conference Paper

Manipulation planning with Workspace Goal Regions

Dmitry Berenson
Siddhartha S. Srinivasa
Dave Ferguson 0001
Alvaro Collet
James J. Kuffner

We present an approach to path planning for manipulators that uses Workspace Goal Regions (WGRs) to specify goal end-effector poses. Instead of specifying a discrete set of goals in the manipulator's configuration space, we specify goals more intuitively as volumes in the manipulator's workspace. We show that WGRs provide a common framework for describing goal regions that are useful for grasping and manipulation. We also describe two randomized planning algorithms capable of planning with WGRs. The first is an extension of RRT-JT that interleaves exploration using a Rapidly-exploring Random Tree (RRT) with exploitation using Jacobian-based gradient descent toward WGR samples. The second is the IKBiRRT algorithm, which uses a forward-searching tree rooted at the start and a backward-searching tree that is seeded by WGR samples. We demonstrate both simulation and experimental results for a 7DOF WAM arm with a mobile base performing reaching and pick-and-place tasks. Our results show that planning with WGRs provides an intuitive and powerful method of specifying goals for a variety of tasks without sacrificing efficiency or desirable completeness properties.

ICRA Conference 2009 Conference Paper

Object recognition and full pose registration from a single image for robotic manipulation

Alvaro Collet
Dmitry Berenson
Siddhartha S. Srinivasa
Dave Ferguson 0001

Robust perception is a vital capability for robotic manipulation in unstructured scenes. In this context, full pose estimation of relevant objects in a scene is a critical step towards the introduction of robots into household environments. In this paper, we present an approach for building metric 3D models of objects using local descriptors from several images. Each model is optimized to fit a set of calibrated training images, thus obtaining the best possible alignment between the 3D model and the real object. Given a new test image, we match the local descriptors to our stored models online, using a novel combination of the RANSAC and Mean Shift algorithms to register multiple instances of each object. A robust initialization step allows for arbitrary rotation, translation and scaling of objects in the test images. The resulting system provides markerless 6-DOF pose estimation for complex objects in cluttered scenes. We provide experimental results demonstrating orientation and translation accuracy, as well a physical implementation of the pose output being used by an autonomous robot to perform grasping in highly cluttered scenes.

ICRA Conference 2009 Conference Paper

Smooth path planning in constrained environments

Martin Rufli
Dave Ferguson 0001
Roland Siegwart

In this paper we describe a novel path planning approach for mobile robots operating in indoor environments. In such scenarios, robots must be able to maneuver in crowded spaces, partially filled with static and dynamic obstacles (such as people). Our approach produces smooth, complex maneuvers over large distances through the use of an anytime graph search algorithm applied to a novel multi-resolution state lattice, where the resolution is adapted based on both environmental characteristics and task characteristics. In addition, we present a novel approach for generating fast globally optimal trajectories in constrained spaces (i. e. rooms connected via doors and hallways). This approach exploits offline precomputation to provide extremely efficient online performance and is applicable to a wide range of both indoor and outdoor navigation scenarios. By combining an anytime, multi-resolution lattice-based search algorithm with our precomputation technique, globally optimal trajectories in up to four dimensions (2D position, heading and velocity) are obtained in real-time.

IROS Conference 2008 Conference Paper

Motion planning in urban environments: Part I

Dave Ferguson 0001
Thomas M. Howard
Maxim Likhachev

We present the motion planning framework for an autonomous vehicle navigating through urban environments. Such environments present a number of motion planning challenges, including ultra-reliability, high-speed operation, complex inter-vehicle interaction, parking in large unstructured lots, and constrained maneuvers. Our approach combines a model-predictive trajectory generation algorithm for computing dynamically-feasible actions with two higher-level planners for generating long range plans in both on-road and unstructured areas of the environment. In this Part I of a two-part paper, we describe the underlying trajectory generator and the on-road planning component of this system. We provide examples and results from ldquoBossrdquo, an autonomous SUV that has driven itself over 3000 kilometers and competed in, and won, the Urban Challenge.

IROS Conference 2008 Conference Paper

Motion planning in urban environments: Part II

Dave Ferguson 0001
Thomas M. Howard
Maxim Likhachev

We present the motion planning framework for an autonomous vehicle navigating through urban environments. Such environments present a number of motion planning challenges, including ultra-reliability, high-speed operation, complex inter-vehicle interaction, parking in large unstructured lots, and constrained maneuvers. Our approach combines a model-predictive trajectory generation algorithm for computing dynamically-feasible actions with two higher-level planners for generating long range plans in both on-road and unstructured areas of the environment. In this Part II of a two-part paper, we describe the unstructured planning component of this system used for navigating through parking lots and recovering from anomalous on-road scenarios. We provide examples and results from ldquoBossrdquo, an autonomous SUV that has driven itself over 3000 kilometers and competed in, and won, the Urban Challenge.

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

ICRA Conference 2006 Conference Paper

Anytime Path Planning and Replanning in Dynamic Environments

Jur van den Berg
Dave Ferguson 0001
James J. Kuffner

We present an efficient, anytime method for path planning in dynamic environments. Current approaches to planning in such domains either assume that the environment is static and replan when changes are observed, or assume that the dynamics of the environment are perfectly known a priori. Our approach takes into account all prior information about both the static and dynamic elements of the environment, and efficiently updates the solution when changes to either are observed. As a result, it is well suited to robotic path planning in known or unknown environments in which there are mobile objects, agents or adversaries

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

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

IROS Conference 2006 Conference Paper

SMART Navigation in Structured and Unstructured Environments

Sascha Kolski
Kristijan Macek
Dave Ferguson 0001
Roland Siegwart

Recently, intelligent transportation systems have been introduced for tasks like automated parking and highway driving. This is one of many contact points between human and robot intelligence, in that a human driver is sharing the driving task with intelligent computer systems. In this video we present an automated passenger vehicle that is able to autonomously navigate through both structured and unstructured B23environments without relying on prior environmental information or known waypoints. The system uses ego motion estimation based on an inertial measurement unit and internal vehicle sensors, and combines this with a laser range finder to map its environment. It uses a combination of global planning and local planning to safely navigate through the environment to a desired goal location.

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

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.

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 2005 Conference Paper

Towards Topological Exploration of Abandoned Mines

Aaron Morris
David Silver 0002
Dave Ferguson 0001
Scott Thayer

The need for reliable maps of subterranean spaces too hazardous for humans to occupy has motivated the use of robotic technology as mapping tools. As such, we present a systemic approach to autonomous topological exploration of a mine environment to facilitate the process of mapping. This approach focuses upon the interaction of three high-level processes: topological planning, intersection identification and local navigation. Topological planning tasks the robot to investigate stretches of mine corridor for the purpose of collecting data. Intersection identification converts sensory input into topological components used to construct an online topological map and provide the robot with a global sense of position. Local navigation transforms topological exploration objectives into robot actuation enabling traversal of mine corridors. These processes are described in detail with results presented from experiments conducted at a research coal mine near Pittsburgh, PA.

ICRA Conference 2004 Conference Paper

A Campaign in Autonomous Mine Mapping

Christopher R. Baker
Aaron Morris
Dave Ferguson 0001
Scott Thayer
Warren Whittaker
Zachary Omohundro
Carlos F. Reverte
Dirk Hähnel

Unknown, unexplored and abandoned subterranean voids threaten mining operations, surface developments and the environment. Hazards within these spaces preclude human access to create and verify extensive maps or to characterize and analyze the environment. To that end, we have developed a mobile robot capable of autonomously exploring and mapping abandoned mines. To operate without communications in a harsh environment with little chance of rescue, this robot must have a robust electro-mechanical platform, a reliable software system, and a dependable means of failure recovery. Presented are the mechanisms, algorithms, and analysis tools that enable autonomous mine exploration and mapping along with extensive experimental results from eight successful deployments into the abandoned Mathies coal mine near Pittsburgh, PA.

IROS Conference 2004 Conference Paper

Feature extraction for topological mine maps

David Silver 0002
Dave Ferguson 0001
Aaron Morris
Scott Thayer

We present a robust method for detecting and recognizing topological features in underground mines. Our method involves performing Delaunay triangulations on range scans to extract points of interest, such as intersecting corridors. By combining these interest points into a topological map, we have a valuable tool for navigation and localization in large scale, highly cyclic environments. We present results from a research coal mine near Pittsburgh, PA.

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 2003 Conference Paper

A system for volumetric robotic mapping of abandoned mines

Sebastian Thrun
Dirk Hähnel
Dave Ferguson 0001
Michael Montemerlo
Rudolph Triebel
Wolfram Burgard
Christopher R. Baker
Zachary Omohundro

This paper describes two robotic systems developed for acquiring accurate volumetric maps of underground mines. One system is based on a cart instrumented by laser range finders, pushed through a mine by people. Another is a remotely controlled mobile robot equipped with laser range finders. To build consistent maps of large mines with many cycles, we describe an algorithm for estimating global correspondences and aligning robot paths. This algorithm enables us to recover consistent maps several hundreds of meters in diameter, without odometric information. We report results obtained in two mines, a research mine in Bruceton, PA, and an abandoned coal mine in Burgettstown, PA.