Fundamental Sampling Issues in Motion Planning

Steven M. Lavalle

Abstract

For more than a decade randomized algorithms have dominated much of the motion planning literature. One of the most influential frameworks within this context had been the probabilistic roadmap (PRM), which generates a network of paths by random sampling over the configuration space. In our work, we have carefully assessed the value of randomization in this context. By building on discrepancy and dispersion ideas from quasi-Monte Carlo literature, we have determined both theoretically and experimentally that randomization in the original PRM offers no advantages over certain deterministic schemes. In fact, even some forms of grid search offer advantages over the original PRM. In addition to comparisons between PRMs and deterministic alternatives, we present our current progress on developing general-purpose sampling algorithms, and on our efforts to derandomize Rapidly-exploring Random Trees (RRTs). We hope that the insights gained from this research will lead to the development of better sampling-based motion planning algorithms. Parts of this work are in collaboration with Michael Branicky, Stephen Lindemann, and Libo Yang.

Presentation Slides

Pdf (2.5Mb)

 

Speaker Appointments

For appointments, please contact Jean Harpley (jean@cs.cmu.edu).