dif : Research

Research Projects

Over the last couple years I've been involved in a few different research projects at Intel Research Pittsburgh and CMU. They have all been great fun. I've included a brief introduction to most of them below. Caveat: There is quite a bit of information here - the navigation bar on the left is useful for jumping to a particular area of interest.

If you are interested in collaborating with me or Intel Research or CMU in general - Great! We work closely with several researchers around the world, both faculty and students, and I would be happy to hear from you. However, we have a limited number of fellowship/intern opportunities at the lab so unfortunately can't always accommodate everyone.

Manipulation in Uncertain Environments

The Personal Robotics project at Intel Research Pittsburgh, in collaboration with CMU, is developing a mobile robotic indoor assistant intended to perform common manipulation tasks. We currently have a Barrett WAM arm and Segway RMP that we have coordinating to act as a Robotic Busboy, collecting dirty mugs from around the office and then loading them into a dishwasher rack.

The idea behind this project is to create general, useful robotic systems that are able to handle all the uncertainty associated with natural human environments. We have been focusing on the challenges associated with high-speed planning for grasping and trajectory generation, as well as intelligent navigation in highly-populated environments and robust perception of common objects. For more details (along with cool videos), see our Personal Robotics website.

Driverless Cars and the Urban Challenge

I was the planning lead for Boss, CMU's winning entry in the Urban Grand Challenge robot race. In this competition, autonomous robotic vehicles had to successfully navigate for 60 miles in an urban environment containing several other robotic vehicles and 50 human driven cars. Urban environments present a number of motion planning challenges, including high-speed operation, complex inter-vehicle interaction, parking in large unstructured lots, and highly constrained maneuvers. Our motion planning approach combined a local planner that utilized a model-based trajectory generation algorithm for computing dynamically feasible actions with two global planners for efficiently generating long range plans in both on-road and unstructured areas of the environment.

The final competition was held in November 3, 2007, with 11 teams taking part. 6 of these teams successfully completed the course, representing a fantastic accomplishment for robotics. CMU took roughly 4 hours to finish the race and was awarded first place (with second and third going to Stanford and Virginia Tech).

Efficient Planning and Replanning Algorithms

We've spent a bit of time developing efficient path planners and replanners for mobile robots navigating unknown or dynamic environments. Since we rarely have perfect maps of the areas we'd like our agents to traverse, it's important that the agents can replan when new information is observed. Tony Stentz and I have looked at how we can do this replanning quicksmart.

We've also tried to improve the quality of paths returned by current grid-based path planners. Specifically, rather than restricting the successors of a particular grid cell center to be just its 8 neighboring grid cell centers, we've developed an approach that allows the paths to go through arbitrary positions on each grid cell edge. In order to do this efficiently, we use linear interpolation to approximate the path costs of points on grid cell edges, and a closed-form solution to the subsequent minimization problem. The result is the Field D* algorithm, and very direct, low-cost paths through grids. The two left images below show paths produced by Field D* through grid environments (the second shows the corresponding path produced by a classic grid-based planner in red, with the Field D* path in blue). The third image (when clicked on) shows an animation of Field D* being used to guide an agent through an unknown environment. Obstacles are shown in red, observed obstacles in blue, and the path in green. Notice that the path segments are straight lines with widely-varying headings.

This algorithm is currently used by a wide range of fielded robotic systems, ranging from indoor robots to very rugged outdoor vehicles. The picture below shows some of the platforms using the algorithm for navigation. It is also being incorporated onto the onboard planning of the Mars Exploration Rovers (with Art Rankin, Joseph Carsten, and Mark Maimone from JPL). Click on the image below to see an animation showing one of these rovers in the sandpit at NASA's Jet Propulsion Lab using Field D* to plan a path to a goal location that is behind a double culdesac; it turns out that the goal is unreachable in this case but the rover is able to successfully navigate in and out of the two culdesacs and realise that there is no path. Here, the rover began with no map and as it moved it used stereo vision to build a map and plan (shown on the right in the animation). We have also developed a version of the algorithm able to plan over non-uniform grids (for when memory is limited) and Joseph Carsten has developed a version capable of planning through three-dimensional grids for aerial and underwater vehicles.

Anytime Algorithms

When the deliberation time available to an agent is limited and the planning problem is complex, optimal solutions are often infeasible. Instead, we have to be happy with the best solution we can generate in the time we have. Together with Max Likhachev I've looked at how we can quickly generate initial, suboptimal solutions, then improve the quality of these solutions as time allows (known as `anytime' planning). We've also created an anytime replanning algorithm, Anytime Dynamic A*, that combines both anytime and replanning capabilities.

Anytime Dynamic A* exhibits anytime behavior (it generates initial suboptimal solutions very quickly, then works on improving these solutions while deliberation time allows) and replanning behavior (when changes occur to the environment, it efficiently repairs the previous solution). We've used this algorithm to perform 4D path planning for mobile vehicles, as well as for robot arms. The animations below show the path planned for a 3 link arm manipulating an end-effector through two cluttered environments (the one on the left is small, the one on the right is large). Here, imagine the arm is working above a conveyor belt, with the end-effector pointing down onto the belt. We also randomly added obstacles along the path of the arm to test the replanning portion of the algorithm (but not for these animations).

Jur van den Berg, James Kuffner, and I have also applied this algorithm to the problem of planning in dynamic environments. As an example, the three images below were taken from an outdoor environment (left) from which a 3D model was constructed (center) and used to create a 2D Probabilistic Roadmap (PRM) for path planning (right). This roadmap is a graph that can be used for planning paths between any two locations in the environment. We then added 12 dynamic obstacles (shown as red circles) and planned a path for an agent navigating from the lower-right to the top-left of the environment. The agent minimized the combined cost of traverse and the time of traverse, while avoiding the dynamic obstacles. It didn't have perfect information regarding the trajectories of these obstacles, however, so it estimated their behavior then updated its estimates and plan when new observations were received. Below the three images is an animation showing the agent moving through the environment, using Anytime D* for improving and repairing its path as new information is received. In this animation, time extends in the vertical axis and as the agent moves, its path `comes down' to meet it.

Planning with Imperfect Information

Another area we have been interested in is planning under uncertainty. Our robots aren't given perfect maps of their environments and it can pay to take this into account when planning paths for navigation. I've been looking at how we can extend classical planning techniques to incorporate uncertain information without surrendering too much in terms of efficiency.

As an example of planning in environments with limited uncertainty, consider mapping an outdoor environment with a helicopter then using that map to aid a ground vehicle. Often, certain portions of the map will be unclear: from an aerial view it is difficult to tell if there is enough room under tree canopy for a vehicle to squeeze by.

Click on the image below to see a traversability map of an outdoor environment generated by a helicopter. In green are several `pinch points' which may or may not turn out to be blocked. Below this map, there are three images corresponding to animated paths. Click on any to view the corresponding AVI file (note: these are big: ~20M). The first animation shows the path traversed by a robot that takes into account the probability each pinch point is blocked and uses these values to compute an optimal expected-cost path through the environment. The second shows the path traversed by a robot that assumed each pinch point was blocked. The final animation shows the path traversed by a robot that assumed each pinch point was clear. We have randomly generated true values for each pinch point according to prior probability distributions. The idea is that by incorporating the agent's uncertainty we can generate better paths for our agent to traverse.

Planning for Multi-Robot Teams

When faced with very high dimensional search spaces, for example as encountered when planning for teams of agents, sampling-based planners can perform much more favorably than deterministic algorithms (like A* or D*). Sampling-based approaches work by growing a search tree out from an initial location and using (random) sampling of the search space to bias the growth of the tree. We have applied one such algorithm, Rapidly-exploring Random Trees (RRTs), developed by Steve LaValle and James Kuffner, to the problem of Constrained Exploration. In this problem, we have a team of agents that we wish to explore some areas of an environment, while maintaining some team constraints (such as line-of-sight connectivity at all times). We have also developed extensions to this algorithm that can efficiently repair solutions when new information is received (like replanning algorithms such as D*), and can improve the quality of the solution as time allows (like anytime algorithms such as ARA*). Finally, we have combined these ideas to produce a sampling-based analog to the Anytime D* algorithm, that can both improve and repair its solution when new information is received.

Click on the image below to see an animation of our Dynamic RRT algorithm planning a path for three agents from the bottom to the top of an environment. Here, the grey areas represent communication obstacles: these areas prevent line-of-sight communication. As the agents navigate through the environment, navigation obstacles are observed in black - these can be thought of as rocks or ditches that must be avoided by the agents, potentially requiring the previous solution to be repaired. On the left panel is the RRT being grown and re-grown as the solution is invalidated due to new information (the 6-dimensional tree is split into three 2-dimensional trees for visualization), in the center panel the current solution is shown, and on the right the line-of-sight links are shown between the team members.

Multi-Robot Coordination

Several members of Tony Stentz's group do great stuff with robot teams, using market-based approaches to coordinate multiple agents to accomplish useful tasks. Bernardine, Rob, and Nidhi have each gotten groups of robots to work together to complete tasks requiring various levels of coordination. I've been involved in Nidhi's project, which is focused on problems requiring tight coordination (such as robots combining to carry heavy objects or sweep out areas looking for objects of interest). She has come up with quite a cool method for getting the robots to work together appropriately. Her approach uses some of our multi-robot planning algorithms to compute sub-team solutions, then combines these to produce good results for the entire team. For more details, along with some cool videos, see her webpage.

Planning with Imperfect Actuation

The robots we have around today are orders of magnitude more accurate than their predecessors. Even so, when a robot tries to move to a certain position, there is still a chance it will not end up where it wants to be. This imperfection can also be incorporated into the planning phase to produce more robust paths. I'm looking at how we can do this while still holding on to some of the great properties of deterministic planners.

To this end, we've developed a fast method to solve path planning Markov Decision Processes (an extension of the classical path planning framework which incorporates actuation uncertainty). We've also been looking at how we can update our plans when new information arrives through sensors. Below are 3 animations showing the traverse of an agent through an environment to a specified goal. The first simulation has the agent start out with no prior map information. In this case, it initialises its map to be completely clear. The second and third simulations have the agent begin with a low resolution map which it uses to plan an initial path. The third animation represents the terrain of the environment in 3D. In each case, the agent is equipped with an omnidirectional sensor with a 10-cell field of view and its actuation uncertainty is modelled as a stochastic transition function, with actions producing their desired effect 85% of the time and being off (by a single cell) 15% of the time.

Animations: No Prior Map Information Low Resolution Prior Map Low Resolution Prior Map, 3D display

Mine Mapping

For the last couple years I've been working on Groundhog, a robot developed at the Robotics Institute to autonomously map abandoned mines. The idea is to plonk him down at a mine portal and flick him on, then let him descend into the mine on his own and return with a full 2D and 3D map of the traversed area.
To this end, I've been dealing with the autonomy side of things, issues like:
Given a local scan of the environment and some history of where he's been, where should Groundhog try to go next?
How can we safely generate a path to a desired destination, given the 3D nature of the environment?
How can we detect intersections and use these features to perform high-level navigation and loop closure?

It has been good fun. On May 30th, 2003, we sent him into the Mathies Mine, an abandoned coal mine 45 mins outside of Pittsburgh, PA. He successfully navigated 310 metres into the mine before he came across a collapsed ceiling beam. At this point, he sensibly decided he had endured enough and began to reverse back out of the mine. During his return journey he was plagued with a couple hardware problems and eventually died about 130 metres from the entrance. Two swell miners then went in and turned him back on for us and he was tele-operated back to safety. It was a pretty exciting day for the team, none of whom had gotten more than about 5 hours sleep in the three days prior. The event generated a fair bit of press interest; over 400 publications reproduced the associated press article.

During October, we sent him back into Mathies 7 more times. We were able to produce some nice 2D and 3D maps of sizeable chunks of the mine, including the preparation plant side which was partially submerged. See the ICRA 04 paper below for details (and a couple nice images).

We're currently looking at general exploration and the use of topological maps to aid in this task.

If interested, the results of the Mathies run, along with a video showing what the robot saw inside the abandoned mine, can be found here. Finally, click on any of the tidbits below to go to the original Mine Mapping Website.

Publications

	M. Likhachev and D. Ferguson. Planning Long Dynamically-Feasible Maneuvers for Autonomous Vehicles. In Proc. Robotics: Science and Systems. Zurich, Switzerland. 2008.
	R. Diankov, N. Ratliff, D. Ferguson, S. Srinivasa, and J. Kuffner. BiSpace Planning: Concurrent Multi-Space Exploration. In Proc. Robotics: Science and Systems. Zurich, Switzerland. 2008.
	C. Baker, D. Ferguson, and J. Dolan. Robust Mission Execution for Autonomous Urban Driving. In Proc. International Conference on Intelligent Autonomous Systems. Baden Baden, Germany. 2008.
	S. Srinivasa, D. Ferguson, M. Vande Weghe, R. Diankov, D. Berenson, C. Helfrich, and H. Strasdat The Robotic Busboy: Steps Towards Developing a Mobile Robotic Home Assistant In Proc. International Conference on Intelligent Autonomous Systems. Baden Baden, Germany. 2008.
	D. Ferguson, C. Baker, M. Likhachev, and J. Dolan. A Reasoning Framework for Autonomous Urban Driving. In Proc. IEEE Intelligent Vehicles Conference. Eindhoven, The Netherlands. 2008.
	D. Ferguson, M. Darms, C. Urmson, and S. Kolski. Detection, Prediction, and Avoidance of Dynamic Obstacles in Urban Environments. In Proc. IEEE Intelligent Vehicles Conference. Eindhoven, The Netherlands. 2008.
	D. Ferguson and M. Likhachev. Efficiently using Cost Maps for Planning Complex Maneuvers. In Proc. Workshop on Planning with Cost Maps, IEEE International Conference on Robotics and Automation. Pasadena, USA. 2008.
	T. Howard, C. Green, A. Kelly, and D. Ferguson. State-space Sampling of Feasible Motions for High Performance Mobile Robot Navigation in Complex Environments. Journal of Field Robotics. To appear.
	M. Vande Weghe, D. Ferguson and S. Srinivasa. Randomized Path Planning for Redundant Manipulators without Inverse Kinematics. In Proc. IEEE International Conference on Humanoid Robots. Pittsburgh, USA. 2007.
	M. Likhachev, D. Ferguson, G. Gordon, A. Stentz, and S. Thrun. Anytime Planning in Large, Dynamic Graphs. Artificial Intelligence. To appear.
	N. Kalra, D. Ferguson, and A. Stentz. Hoplites: A Generalized Framework for Solving Tightly-coupled Multirobot Planning Problems. Journal of Autonomous Robots. To appear.
	D. Ferguson. Autonomous Automobiles: Developing Cars That Drive Themselves. In Proc. ACM/IEEE Design Automation Conference (DAC). San Diego, USA. 2007.
	N. Kalra, D. Ferguson, and A. Stentz. Incremental Reconstruction of Generalized Voronoi Diagrams on Grids. Robotics and Autonomous Systems. To appear.
	N. Kalra, D. Ferguson, and A. Stentz. A Generalized Framework for Solving Tightly-coupled Multirobot Planning Problems. In Proc. IEEE International Conference on Robotics and Automation (ICRA). Rome, Italy. 2007.
	D. Ferguson and A. Stentz. Anytime, Dynamic Planning in High-dimensional Search Spaces. In Proc. IEEE International Conference on Robotics and Automation (ICRA). Rome, Italy. 2007.
	J. Carsten, A. Rankin, D. Ferguson, and A. Stentz. Global Path Planning on-board the Mars Exploration Rovers. In Proc. IEEE Aerospace Conference. Big Sky, USA. 2007.
	D. Ferguson and A. Stentz. Anytime RRTs. In Proc. IEEE International Conference on Intelligent Robots and Systems (IROS). Beijing, China. 2006.
	S. Kolski, D. Ferguson, C. Stachniss, and R. Siegwart. Autonomous Driving in Dynamic Environments. In Proc. Workshop on Safe Navigation in Open and Dynamic Environments, IEEE International Conference on Intelligent Robots and Systems (IROS). Beijing, China. 2006.
	J. Carsten, D. Ferguson, and A. Stentz. 3D Field D*: Improved Path Planning and Replanning in Three Dimensions. In Proc. IEEE International Conference on Intelligent Robots and Systems (IROS). Beijing, China. 2006.
	S. Srinivasa and D. Ferguson. Meet Point Planning for Multirobot Coordination. In Proc. IEEE International Symposium on Robotics and Automation.. Hidalgo, Mexico. 2006.
	D. Silver, D. Ferguson, A. Morris, and S. Thayer. Topological Exploration of Subterranean Environments. Journal of Field Robotics 23(6): 395--415. July, 2006.
	S. Kolski, D. Ferguson, M. Bellino, and R. Siegwart. Autonomous Driving in Structured and Unstructured Environments. In Proc. IEEE Intelligent Vehicles Symposium. Tokyo, Japan. 2006.
	D. Ferguson and A. Stentz. Replanning with RRTs. In Proc. IEEE International Conference on Robotics and Automation (ICRA). Florida, USA. 2006.
	J. van den Berg, D. Ferguson, and J. Kuffner. Anytime Path Planning and Replanning in Dynamic Environments. In Proc. IEEE International Conference on Robotics and Automation (ICRA). Florida, USA. 2006.
	N. Kalra, D. Ferguson, and A. Stentz. Constrained Exploration for Studies in Multirobot Coordination. In Proc. IEEE International Conference on Robotics and Automation (ICRA). Florida, USA. 2006.
	D. Ferguson and A. Stentz. Using Interpolation to Improve Path Planning: The Field D* Algorithm. Journal of Field Robotics 23(2): 79 - 101. February, 2006. NOTE: The pseudocode in this version appears a little grainy - This preprint has crisper pseudocode for implementation purposes.
	D. Ferguson and A. Stentz. Multi-resolution Field D*. In Proc. International Conference on Intelligent Autonomous Systems (IAS). Tokyo, Japan. 2006.
	N. Kalra, D. Ferguson, and A. Stentz. Incremental Reconstruction of Generalized Voronoi Diagrams on Grids. In Proc. International Conference on Intelligent Autonomous Systems (IAS). Tokyo, Japan. 2006.
	A. Morris, D. Ferguson, et al. Recent Developments in Subterranean Robotics. Journal of Field Robotics 23(1): 35 - 57. January, 2006.
	D. Ferguson and A. Stentz. Field D*: An Interpolation-based Path Planner and Replanner. In Proc. International Symposium on Robotics Research (ISRR). San Francisco, California, USA. 2005.
	D. Ferguson and A. Stentz. The Field D* Algorithm for Improved Path Planning and Replanning in Uniform and Non-uniform Cost Environments. Technical Report CMU-RI-TR-05-19, Robotics Institute, June 2005.
	D. Ferguson, M. Likhachev, and A. Stentz. A Guide to Heuristic-based Path Planning. In Proc. International Workshop on Planning under Uncertainty for Autonomous Systems, International Conference on Automated Planning and Scheduling (ICAPS). Monterey, California, USA. 2005.
	M. Likhachev, D. Ferguson, G. Gordon, A. Stentz, and S. Thrun. Anytime Dynamic A*: An Anytime, Replanning Algorithm. In Proc. International Conference on Automated Planning and Scheduling (ICAPS). Monterey, California, USA. 2005.
	M. Likhachev, D. Ferguson, G. Gordon, A. Stentz, and S. Thrun. Anytime Dynamic A*: The Proofs. Technical Report CMU-RI-TR-05-12, Robotics Institute, April 2005.
	D. Ferguson and A. Stentz. The Delayed D* Algorithm for Efficient Path Replanning. In Proc. IEEE International Conference on Robotics and Automation (ICRA). Barcelona, Spain. 2005.
	N. Kalra, D. Ferguson, and A. Stentz. Hoplites: A Market-Based Framework for Planned Tight Coordination in Multirobot Teams. In Proc. IEEE International Conference on Robotics and Automation (ICRA). Barcelona, Spain. 2005.
	A. Morris, D. Silver, D. Ferguson, and S. Thayer. Towards Topological Exploration of Abandoned Mines. In Proc. IEEE International Conference on Robotics and Automation (ICRA). Barcelona, Spain. 2005.
	D. Ferguson and A. Stentz. Delayed D*: The Proofs. Technical Report CMU-RI-TR-04-51, Robotics Institute, September 2004.
	D. Ferguson and A. Stentz. Planning with Imperfect Information. In Proc. IEEE International Conference on Intelligent Robots and Systems (IROS). Sendai, Japan. 2004.
	D. Silver, D. Ferguson, A. Morris, and S. Thayer. Feature Extraction for Topological Mine Maps. In Proc. IEEE International Conference on Intelligent Robots and Systems (IROS). Sendai, Japan. 2004.
	D. Ferguson and A. Stentz. Focussed Processing of MDPs for Path Planning. In Proc. IEEE International Conference on Tools with Artificial Intelligence (ICTAI). Boca Raton, Florida, USA. 2004.
	D. Ferguson and A. Stentz. Robust Path Planning with Imperfect Maps. In Proc. Army Science Conference. Orlando, Florida, USA. 2004.
	D. Ferguson and A. Stentz. Focussed Dynamic Programming: Extensive Comparative Results. Technical Report CMU-RI-TR-04-13, Robotics Institute, March 2004.
	S. Thrun, S. Thayer, W. Whittaker, C. Baker, W. Burgard, D. Ferguson, D. Hähnel, M. Montemerlo, A. Morris, Z. Omohundro, C. Reverte, and W. Whittaker. Autonomous exploration and mapping of abandoned mines. IEEE Robotics and Automation Magazine, volume 11, number 4, pages 79 - 91, December 2004.
	D. Ferguson, A. Stentz, and S. Thrun. PAO* for Planning with Hidden State. In Proc. IEEE International Conference on Robotics and Automation (ICRA). New Orleans, LA. 2004.
	C. Baker, A. Morris, D. Ferguson, S. Thayer, W. Whittaker, Z. Omohundro, C. Reverte, W. Whittaker, D. Hähnel, and S. Thrun. A Campaign in Autonomous Mine Mapping. In Proc. IEEE International Conference on Robotics and Automation (ICRA). New Orleans, LA. 2004.
	D. Ferguson, A. Morris, D. Hähnel, C. Baker, Z. Omohundro, C. Reverte, S. Thayer, W. Whittaker, W. Whittaker, W. Burgard, and S. Thrun. An Autonomous Robotic System for Mapping Abandoned Mines. In Proc. Neural Information Processing Systems (NIPS). Vancouver, Canada, 2003.
	S. Thrun, D. Hähnel, D. Ferguson, M. Montemerlo, R. Triebel, W. Burgard, C. Baker, Z. Omohundro, S. Thayer, and W. Whittaker. A system for volumetric robotic mapping of underground mines. In Proc. IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan, 2003.
	D. Ferguson. Volumetric Mine Mapping with 3D Registration. Technical Report, Robotics Institute, November 2002.
	D. Ferguson and W. Labuschagne. Information-theoretic semantics for epistemic logic. In Proc. LOFT5 Fifth Conference on Logic and the Foundations of Game and Decision Theory, Torino, Italy, June 2002.
	D. Ferguson and W. Labuschagne. A Preferential Semantics for Epistemic Logic. Technical Report OUCS-2001-09, University of Otago, Department of Computer Science, Dunedin, NZ, 2001.
	Jefferies, M.E., Yeap, W.K., Smith, L. and Ferguson, D. Building a Map for robot navigation using a theory of cognitive maps. In Proc. IASTED International Conference on Artificial Intelligence and Applications, Marbella, Spain, 2001.
	Jefferies M. E., Yeap, W.K., Smith, L. and Ferguson, D. Computing individual local spaces for a mobile robot: An initial algorithm. In Proc. International Conference on Cognitive Science, Beijing, China, 2001.