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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

20204 - Robotics and automatic control

Projekt

<a href="/cs/project/GA22-24425S" target="_blank" >GA22-24425S: Techniky plánování pohybu v úzkých prostorech</a><br>

Návaznosti

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

Rok uplatnění

2023

Kód důvěrnosti údajů

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

Název periodika

IEEE Robotics and Automation Letters

ISSN

2377-3766

e-ISSN

2377-3766

Svazek periodika

8

Číslo periodika v rámci svazku

11

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

8

Strana od-do

7336-7343

Kód UT WoS článku

001181344900001

EID výsledku v databázi Scopus

2-s2.0-85171592657