An Empirical Study of Optimal Motion Planning

Jingru Luo and Kris Hauser. IROS 2014

Abstract. This paper presents a systematic benchmarking comparison between optimal motion planners. Six planners representing the categories of sampling-based, grid-based, and trajectory optimization methods are compared on synthetic problems of varying dimensionality, number of homotopy classes, and width and length of narrow passages. Performance statistics are gathered on success and convergence rates, and performance variations with respect to geometric characteristics are analyzed. Based on this analysis, we recommend planners that are likely to perform well for certain problem classes, and make recommendations for future planning research.

Download PDF

Planners compared

1. FMM*: a resolution complete version of the Fast Marching Method (Sethian, 1996)
2. CE: the Cross Entropy trajectory optimization method (Kobilarov, 2011)
3. RRT*: the asymptotically optimal Rapidly-exploring Random Tree algorithm (Karaman and Frazzoli, 2011)
4. L-PRM*: the Lazy-PRM*, a lazy, asymptotically optimal version of the PRM* algorithm (Hauser 2015)
5. M-RRT: multiple-restart Rapidly-exploring Random Tree (LaValle and Kuffner, 1999), keeping the best solution found so far.
6. M-RRT-S: M-RRT interleaved with solution shortcutting (Luna, Sucan, Moll, and Kavraki, 2013).

Detailed Results, sorted by problem parameter (click to view)

Detailed Results, sorted by problem (click to view)