Path Deformation Roadmaps

This paper describes a new approach to sampling-based motion planning with PRM methods. Our aim is to compute good quality roadmaps that encode the multiply connectedness of the Cspace inside low redundancy graphs, yet representative of the different varieties of free paths. The proposed approach relies on a notion of path deformability indicating whether or not a given path can be continuously deformed to another existing one. By considering a simpler form of deformation than the one allowed between homotopic paths, we propose a method that extends the Visibility-PRM technique [12] to construct compact roadmaps that encode a richer and more suitable information than representative paths of the homotopy classes. The Path Deformation Roadmaps also contain additional useful cycles between paths in the same homotopy class that can be hardly deformed into each other. First experiments presented in the paper show that our technique enables small roadmaps to reliably and efficiently capture the multiply-connectedness of the space in various problems