Skip to Main content Skip to Navigation
Journal articles

Path Deformation Roadmaps: Compact Graphs with Useful Cycles for Motion Planning

Léonard Jaillet 1 Thierry Simeon 1
1 LAAS-RIS - Équipe Robotique et InteractionS
LAAS - Laboratoire d'analyse et d'architecture des systèmes
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 configuration space inside small but yet representative graphs that capture well the different varieties of free paths. The proposed Path Deformation Roadmaps (PDR) rely 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 (Siméon et al., 2000) to constructing compact roadmaps that encode a richer and more suitable information than representative paths of the homotopy classes. Path Deformation Roadmaps contain additional useful cycles between paths in the same homotopy class that can be hardly deformed into each other. Experimental results provided in the paper show that the technique enables small roadmaps to reliably capture the multiple connectedness of complex spaces in various problems involving free-flying and articulated robots in both 2D and 3D environments.
Document type :
Journal articles
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download
Contributor : Thierry Simeon <>
Submitted on : Friday, January 18, 2019 - 4:51:51 PM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM


Files produced by the author(s)


  • HAL Id : hal-01986326, version 1


Léonard Jaillet, Thierry Simeon. Path Deformation Roadmaps: Compact Graphs with Useful Cycles for Motion Planning. The International Journal of Robotics Research, SAGE Publications, 2008, 27 (11-12), pp.1175-1188. ⟨hal-01986326⟩



Record views


Files downloads