Path Planning on Costmaps
A half day workshop for ICRA 2008
Schedule | Organizers | Motivations | Call for contributions | Importrant dates
Overview
Path planning on costmaps for outdoor mobile robots is different from traditional motion planning in a number of ways — there is a continuum of terrain cost instead of discrete obstacles, these terrain costs change over the course of a run, the environment is only partially-known, and the path planner must run repeatedly and in real-time.

Techniques from the traditional motion planning community have begun to be adopted for path planning on costmaps, for example: sampling-based methods, nonholonomic path planning, and incorporation of vehicle dynamics.

This half-day workshop aims to bring together researchers working in traditional path planning and in path planning for field robotic systems in order to foster work in this area.

Schedule:
2:00 - 2:05 Introduction
2:05 - 2:25 G. Ayorkor Mills-Tettey, Carnegie Mellon

"Continuous-field path planning with constrained path-dependent state variables," by G. Ayorkor Mills-Tettey, Anthony Stentz, and M. Bernadine Dias.

2:25 - 2:45 Jinhan Lee, Georgia Tech

"Cost-Based Planning with RRT in Outdoor Environments," by Jinhan Lee, Charles Pippin, and Tucker Balch.

2:45 - 3:05 Roland Phillipsen, Stanford

"Mobile Robot Planning in Dynamic Environments and on Growable Costmaps," by Roland Philippsen, Sascha Kolski, Kristijan Macek, and Bjoern Jensen.

3:05 - 3:25 Mike Montemerlo, Stanford
3:25 - 3:50 Discussion

3:40 - 4:00 Coffee break

4:00 - 4:10 Introduction
4:10 - 4:30 Kurt Konolige, Willow Garage

"Planning and Control in Unstructured Terrain," by Brian P. Gerkey and Kurt Konolige.

4:30 - 4:50 Barbara Frank, University of Freiburg

"Learning Cost Maps for Navigation of Mobile Robots in Environments with Deformable Objects," by Barbara Frank, Markus Becker, Cyrill Stachniss, Wolfram Burgard, and Matthias Teschner.

4:50 - 5:10 Brian Gerkey, Willow Garage

"Break on through: Tunnel-based exploration to learn about outdoor terrain," by Brian Gerkey and Motilal Agrawal.

5:10 - 5:30 Maxim Likhachev

"Efficiently Using Cost Maps for Planning Complex Maneuvers," by Dave Ferguson and Maxim Likhachev.

5:30 - 6:00 Discussion & conclusion

Organizers:
Wes Huang
Applied Perception, Inc. 		        Dave Ferguson
Intel Research Pittsburgh

Contact: ppoc@weshuang.com

Motivations
Most field robotic systems generate costmaps from their sensor information. Costmaps represent the world using a grid with a “terrain cost” for each cell which. This terrain cost may indicate the presence of rough or undesirable terrain that is slower to traverse, or it can be interpreted as the probability of an obstacle (or part of an obstacle) in that cell.

Path planning on costmaps is different from traditional motion planning in a number of ways:

  • Traditional motion planning operates in a binary world consisting of impassible discrete obstacles and free space, whereas costmaps represent a continuum of traversability in the terrain costs. In addition, the terrain costs may change as additional sensor data become available.
  • Traditional motion planning assumes a complete world representation, whereas many field robotic systems have a significant amount of “unknown” terrain in their costmaps, corresponding to areas that have not (yet) been observed by the robot‘s sensors.
  • Traditional motion planning has recently focused on high dimensional problems and on finding feasible (rather than optimal) paths. In contrast, field robotic systems produce relatively low dimensional path planning problems and require good (though not necessarily optimal) solutions. Additionally, field robotic systems typically require plans to be produced under real-time constraints.

While research in path planning on costmaps dates back more than 10 years, e.g., the D* algorithm (Stentz, 1995), there have been many advances in motion planning that are just starting to be applied to path planning on costmaps. These include:

  • Sampling-based motion planning (e.g., RRTs and PRMs)
  • Planning curvature-limited paths for nonholonomic robots
  • Incorporating dynamic vehicle models into the planner
  • Planning for multiple mobile robots
This workshop will examine research on the frontier of using and adapting these methods to path planning on costmaps and will discuss avenues for further research and development in this area.
 
Call for contributions
We solicit contributions for presentation at the workshop on one or more of the following topics:
  • Path planning on costmaps
  • Sampling-based algorithms on costmaps
  • Curvature-limited (or nonholonomic) path planning on costmaps
  • Planning using vehicle dynamics
  • Anytime algorithms
  • Planning on costmaps for multiple mobile robots
Submissions should be in the IEEE conference style (same as regular conference papers) and up to 6–10 pages in length.

Please email your submission (in PDF format) to ppoc@weshuang.com

 
Important dates
  • January 15, 2008 — submission deadline
  • February 15, 2008 — final program announced
  • February 29, 2008 — final version of accepted contributions due
 
last updated February 13, 2008