Path and Trajectory Diversity: Theory and Algorithms

Michael S. Branicky, Ross Alan Knepper, and James Kuffner
International Conference on Robotics and Automation, May, 2008.

  • Adobe portable document format (pdf) (628KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

We present heuristic algorithms for pruning large sets of candidate paths or trajectories down to smaller subsets that maintain desirable characteristics in terms of overall reachability and path length. Consider the example of a set of candidate paths in an environment that is the result of a forward search tree built over a set of actions or behaviors. The tree is precomputed and stored in memory to be used online to compute collision-free paths from the root of the tree to a particular goal node. In general, such a set of paths may be quite large, growing exponentially in the depth of the search tree. In practice, however, many of these paths may be close together and could be pruned without a loss to the overall problem of path-finding. The best such pruning for a given resulting tree size is the one that maximizes path diversity, which is quantified as the probability of the survival of paths, averaged over all possible obstacle environments. We formalize this notion and provide formulas for computing it exactly. We also present experimental results for two approximate algorithms for path set reduction that are efficient and yield desirable properties in terms of overall path diversity. The exact formulas and approximate algorithms generalize to the computation and maximization of spatio-temporal diversity for trajectories.

motion planning, nonholonomic, trajectory, path

Associated Center(s) / Consortia: Center for the Foundations of Robotics
Associated Lab(s) / Group(s): Planning and Autonomy Lab and Manipulation Lab
Number of pages: 6

Text Reference
Michael S. Branicky, Ross Alan Knepper, and James Kuffner, "Path and Trajectory Diversity: Theory and Algorithms," International Conference on Robotics and Automation, May, 2008.

BibTeX Reference
   author = "Michael S. Branicky and Ross Alan Knepper and James Kuffner",
   title = "Path and Trajectory Diversity: Theory and Algorithms",
   booktitle = "International Conference on Robotics and Automation",
   publisher = "IEEE RAS",
   month = "May",
   year = "2008",