Using path-length localized RRT-like search to solve challenging planning problems

Sampling-based planning algorithms of a variety of types have demonstrated pathologically poorly-performing cases, ranging from narrow passages for PRM-based roadmap methods to bug traps for RRT-based tree search methods. This paper introduces an algorithm rooted in the expansion scheme of the RRT that uses local trees to improve performance in difficult cases without sacrificing it in straightforward ones. This method interconnects these local trees, forming a roadmap that is useable for future queries. Additionally, a viable path can be trivially extracted by treating the output as a tree, or one of improved quality can be obtained via discrete search. Experimental data demonstrate performance equal to or better than several other single-query algorithms on two-dimensional test problems and significantly better on two common SE(3) benchmark problems, the flange and the alpha puzzle.