Skip navigation.
Home

Path Diversity

Suppose you are designing a robot motion planner for a vehicle with highly sophisticated motion constraints. You want to precompute possible actions for the vehicle over short distances. Each action turns into a path describing where the robot moves. Although each path is a fixed length, the robot will compose paths at runtime to construct motions of arbitrary length. To stay responsive, the robot only has time to consider, say, 25 paths before committing to one alternative. What are the best 25 paths to choose from?

The paths should all be as different from each other as possible, since having two very similar paths is in some sense redundant. Since we are discretely sampling paths, there are gaps in path space which contain no paths. Path space is a metric space of high dimension, where each path is represented as a single point. The choice of metric in defining path space describes your notion of how "redundant" two paths are with respect to each other. For instance, you might ask, given that path p1 collides with an obstacle at a given location, what is the probability that path p2 collides with the same obstacle? This metric incorporates many assumptions about the nature of obstacles. A simpler metric is the Hausdorff metric, which describes the maximal Euclidean separation distance between two paths. So far, it is not known which metric is the best to use in designing a diverse path set.

It is clear, however, that the mode in which the path set is employed plays a factor in that design. One variable is whether the path set is fixed to the robot or the workspace. In the former case, the root of the set of paths moves with the robot so that only the start of each path is executed before a new path is commanded to replace it. In the latter case, the entire length of the path is followed, with a new path being concatenated at the end. This distinction matters because the robot is actively avoiding obstacles. If it is a wheeled vehicle, then the planner's job is to position the robot such that there are no obstacles immediately in front of it so that it can continue to make forward progress. Thus, for the robot-fixed case, we expect to see a significantly lower probability of occupancy directly in front of the robot and elevated probability to either side. My paper at ICRA 2009 examines this issue.

Two earlier papers at ICRA 2008 and ISER 2008 examine the foundations of path set generation from a principled perspective and an experimental perspective, respectively.

Publications

  • Ross A. Knepper and Matthew T. Mason, “Path Diversity is Only Part of the Problem,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Kobe, Japan, May 2009. [PDF]
  • Ross A. Knepper and Matthew T. Mason, “Empirical Sampling of Path Sets for Local Area Motion Planning,” in Proceedings of the International Symposium on Experimental Robotics (ISER), Athens, Greece, July 2008. [PDF]
  • Michael S. Branicky, Ross A. Knepper, and James J. Kuffner, “Path and Trajectory Diversity: Theory and Algorithms,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Pasadena, USA, May 2008.[PDF]