A Scalable Motion Planner for High-Dimensional Kinematic Systems

R. Luna, M. Moll, J. M. Badger, and L. E. Kavraki, “A Scalable Motion Planner for High-Dimensional Kinematic Systems,” International Journal of Robotics Research, vol. 39, no. 4, pp. 361–388, Apr. 2020.


Sampling-based algorithms are known for their ability to effectively compute paths for high-dimensional robots in relatively short times. The same algorithms, however, are also notorious for poor quality solution paths, particularly as the dimensionality of the system grows. This work proposes a new probabilistically complete sampling-based algorithm, XXL, specially designed to plan the motions of high-dimensional mobile manipulators and related platforms. Using a novel sampling and connection strategy that guides a set of points mapped on the robot through the workspace, XXL scales to realistic manipulator platforms with dozens of joints by focusing the search of the robot’s configuration space to specific degrees-of-freedom that affect motion in particular portions of the workspace. Simulated planning scenarios with the Robonaut2 platform and planar kinematic chains confirm that XXL exhibits competitive solution times relative to many existing works while obtaining execution-quality solution paths. Solutions from XXL are of comparable quality to costaware methods even though XXL does not explicitly optimize over any particular criteria, and are computed in an order of magnitude less time. Furthermore, observations about the performance of sampling-based algorithms on high-dimensional manipulator planning problems are presented that reveal a cautionary tale regarding two popular guiding heuristics used in these algorithms, indicating that a nearly random search may outperform the state-of-the-art when defining such heuristics is known to be difficult.

Publisher: http://dx.doi.org/10.1177/0278364919890408

PDF preprint: http://kavrakilab.org/publications/luna2020a-scalable-motion-planner-for-high-dimensional.pdf