Path Deformation Roadmaps

Abstract

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 multiple connectedness of the Cspace inside small but yet representative graphs, that capture well 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 into 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 constructing 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 multiple connectedness of the space in various problems.