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

On 2024-02-27 11:00:00 at E112, Karlovo náměstí 13, Praha 2
During the seminar, we will present our recently published method called
Clustering Topological PRM (CTopPRM) for finding multiple topologically
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, it is necessary for optimization-based trajectory planners where found
trajectories are restricted to only a single topological class of a given path.
Distinct paths can also be used to guide sampling-based motion planning and
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
CTopPRM which creates a sparse graph by clustering an initially sampled dense
roadmap. Such a reduced roadmap allows fast identification of topologically
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.

M. Novosad, R. Penicka and V. Vonasek, "CTopPRM: Clustering Topological PRM for
Planning Multiple Distinct Paths in 3D Environments," in IEEE Robotics and
Automation Letters, vol. 8, no. 11, pp. 7336-7343, Nov. 2023, doi:

The seminar will be of a short length (20 minutes + 10 minutes discussion).
Responsible person: Petr Pošík