Skip navigation.

Realtime Contextual Path Set Generation

Modern robotic motion planners typically split their work into three areas:

  1. Path sampling
  2. Path collision testing
  3. Simulation of robot/world interaction.

The path sampling process is usually completely uninformed, either sampling paths at random or using a predetermined low-dispersion sequence. By feeding back the results of earlier collision tests into the path sampling process, we can produce planners that are more both more efficient and more effective.

Work in this project is concentrated in several areas.

Path Equivalence

Paths may be classified according to the route by which they avoid obstacles. This notion is similar to the topological property of homotopy, but it is a local property of paths in the neighborhood of the robot. By classifying paths, we can realize a number of advantages. First, we can exploit groups of paths in the same class to implicitly collision-test paths much more rapidly than would be possible through the normal, explicit collision test. Second, we can reason about each class as a group of paths that moves toward the goal in the same way with respect to obstacles. Within the class, the robot is free to "switch paths" at a later time. So the decision process becomes a two-stage process:

  1. Select a class that makes process toward the goal
  2. Select a path within the class that optimizes other criteria such as safety and visibility.

This work appeared at WAFR 2010.

Reducing Collision-Test Failures

It is assumed that the planner has a costmap that describes the workspace in the vicinity of the robot. If we already know where obstacles are located, then we could discover paths from the freespace in the costmap. Why is it necessary to perform collision tests? This question has many answers. One is that many robots have constrained mobility, such as wheeled vehicles that cannot translate sideways. Thus, any arbitrary path produced from the costmap is unlikely to be feasible to follow. Another possibility is that we are interested in optimizing over several variables, such as safety, visibility, uncertainty, and total path length. Thus, it is often less expensive to sample in the action space and find out where these paths lead. One advantage of this approach is that such path sets can be precomputed and stored in look-up tables based on the current state of the robot. Once we have the ability to precompute properties of the search space, it is reasonable to organize the paths according to possible collision locations. These locations are represented in the space of paths, not the workspace or configuration space. By informing the path selection process based on the outcomes of earlier collision tests, we can select future paths for test that will succeed with high probability. We can also optimize for testing paths that search in unexplored parts of the space to produce high-quality coverage optimized to the current configuration of obstacles.


  • Ross A. Knepper and Matthew T. Mason. “Realtime Informed Path Sampling for Motion Planning Search,” International Journal of Robotics Research (IJRR), 31(11):1231-1250, September 2012. [PDF]
  • Ross A. Knepper, Siddhartha S. Srinivasa, and Matthew T. Mason, “Toward a Deeper Understanding of Motion Alternatives,” International Journal of Robotics Research (IJRR), 31(2):168–187, February 2012. [PDF]
  • Ross A. Knepper, Siddhartha S. Srinivasa, and Matthew T. Mason, “An Equivalence Relation for Local Path Sets”, in Proceedings of the Ninth International Workshop on the Algorithmic Foundations of Robotics (WAFR), Singapore, December 2010. [PDF]
  • Ross A. Knepper, Siddhartha S. Srinivasa, and Matthew T. Mason. “Curvature bounds on the weighted Voronoi diagram of two proximal paths with shape constraints”. Technical Report CMU-RI-TR-10-25, Robotics Institute, Carnegie Mellon University, 2010.