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

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00368077" target="_blank" >RIV/68407700:21230/23:00368077 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1109/LRA.2023.3315539" target="_blank" >https://doi.org/10.1109/LRA.2023.3315539</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/LRA.2023.3315539" target="_blank" >10.1109/LRA.2023.3315539</a>

Result language

angličtina

Original language name

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

Original language description

In this paper, we propose a new method called Clustering Topological PRM (CTopPRM) for finding multiple topologically 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, 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 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 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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

20204 - Robotics and automatic control

Project

<a href="/en/project/GA22-24425S" target="_blank" >GA22-24425S: Sampling-based motion planning in scenarios with narrow passages</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

IEEE Robotics and Automation Letters

ISSN

2377-3766

e-ISSN

2377-3766

Volume of the periodical

8

Issue of the periodical within the volume

11

Country of publishing house

US - UNITED STATES

Number of pages

8

Pages from-to

7336-7343

UT code for WoS article

001181344900001

EID of the result in the Scopus database

2-s2.0-85171592657