  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 sampling-based 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
identification of homotopically distinct paths captured in 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.
