High-Dimensional Winding-Augmented Motion Planning with 2D Topological Task Projections and Persistent Homology

F. T. Pokorny, D. Kragic, L. E. Kavraki, and K. Goldberg, “High-Dimensional Winding-Augmented Motion Planning with 2D Topological Task Projections and Persistent Homology,” in Proceedings of the IEEE International Conference on Robotics and Automation, 2016, pp. 24–31.


Recent progress in motion planning has made it possible to determine homotopy inequivalent trajectories between an initial and terminal configuration in a robot configuration space. Current approaches have however either assumed the knowledge of differential one-forms related to a skeletonization of the collision space, or have relied on a simplicial representation of the free space. Both of these approaches are currently however not yet practical for higher dimensional configuration spaces. We propose 2D topological task projections (TTPs): mappings from the configuration space to 2-dimensional spaces where simplicial complex filtrations and persistent homology can identify topological properties of the high-dimensional free configuration space. Our approach only requires the availability of collision free samples to identify winding centers that can be used to determine homotopy inequivalent trajectories. We propose the Winding Augmented RRT and RRT* (WA-RRT/RRT*) algorithms using which homotopy inequivalent trajectories can be found. We evaluate our approach in experiments with configuration spaces of planar linkages with 2-10 degrees of freedom. Results indicate that our approach can reliably identify suitable topological task projections and our proposed WA-RRT and WA-RRT* algorithms were able to identify a collection of homotopy inequivalent trajectories in each considered configuration space dimension.

Publisher: http://dx.doi.org/10.1109/ICRA.2016.7487113

PDF preprint: http://kavrakilab.org/publications/pokorny2016warrt.pdf