CTopPRM: Clustering Topological PRM for Planning Multiple Distinct Paths in 3D Environments

In this paper, we propose a new method called Clustering Topological PRM (CTopPRM) for finding multiple homotopically distinct paths in 3D cluttered environments. Finding such distinct paths, e.g. going around an obstacle from a different side, is useful in many applications. Among others, using multiple distinct paths is necessary for optimization-based trajectory planners where found trajectories are restricted to only a single homotopy class of a given path. Distinct paths can also be used to guide high-dimensional motion planning and thus increase the effectiveness of planning in environments with narrow passages. Graph-based representation called roadmap is a common representation for path planning and also for finding multiple distinct paths. However, challenging environments with multiple narrow passages require a densely sampled roadmap to capture the connectivity of the environment. Searching such a dense roadmap for multiple paths is computationally too expensive. Therefore, the majority of existing methods construct only a sparse roadmap which, however, struggles to find all distinct paths in challenging environments. To this end, we propose the CTopPRM which creates a sparse graph by clustering an initially sampled dense roadmap. Such a reduced roadmap allows fast path searching while capturing all homotopy classes of the dense roadmap. We show, that compared to the existing methods the CTopPRM improves the probability of finding all distinct paths by almost 20% in tested environments, during same run-time. The source code of our method is released as an open-source package.

Reference:
Matej Novosad, Robert Penicka, Vojtech Vonasek, "CTopPRM: Clustering Topological PRM for Planning Multiple Distinct Paths in 3D Environments," in IEEE Robotics and Automation Letters, doi: 10.1109/LRA.2023.3315539.
Preprint: https://arxiv.org/pdf/2305.13969.pdf
Code: https://github.com/ctu-mrs/CTopPRM

For more about our research check our pages http://mrs.felk.cvut.cz/

Affiliations:
Matej Novosad, Robert Penicka, Vojtech Vonasek are with Multi-robot Systems Group, Faculty of Electrical Engineering, Czech Technical University in Prague, Czech Republic.
http://mrs.felk.cvut.cz/