KRRF: Kinodynamic Rapidly-exploring Random Forest algorithm for multi-goal motion planning

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00377429" target="_blank" >RIV/68407700:21230/24:00377429 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

KRRF: Kinodynamic Rapidly-exploring Random Forest algorithm for multi-goal motion planning

Popis výsledku v původním jazyce

The problem of kinodynamic multi-goal motion planning is to find a trajectory over multiple target locations with an apriori unknown sequence of visits. The objective is to minimize the cost of the trajectory planned in a cluttered environment for a robot with a kinodynamic motion model. This problem has yet to be efficiently solved as it combines two NP-hard problems, the Traveling Salesman Problem (TSP) and the kinodynamic motion planning problem. We propose a novel approximate method called Kinodynamic Rapidly-exploring Ran- dom Forest (KRRF) to find a collision-free multi-goal trajectory that satisfies the motion constraints of the robot. KRRF simul- taneously grows kinodynamic trees from all targets towards all other targets while using the other trees as a heuristic to boost the growth. Once the target-to-target trajectories are planned, their cost is used to solve the TSP to find the sequence of targets. The final multi-goal trajectory satisfying kinodynamic constraints is planned by guiding the RRT-based planner along the target-to- target trajectories in the TSP sequence. Compared with existing approaches, KRRF provides shorter target-to-target trajectories and final multi-goal trajectories with 1.1 - 2 times lower costs while being computationally faster in most test cases. The method will be published as an open-source library.

Název v anglickém jazyce

KRRF: Kinodynamic Rapidly-exploring Random Forest algorithm for multi-goal motion planning

Popis výsledku anglicky

The problem of kinodynamic multi-goal motion planning is to find a trajectory over multiple target locations with an apriori unknown sequence of visits. The objective is to minimize the cost of the trajectory planned in a cluttered environment for a robot with a kinodynamic motion model. This problem has yet to be efficiently solved as it combines two NP-hard problems, the Traveling Salesman Problem (TSP) and the kinodynamic motion planning problem. We propose a novel approximate method called Kinodynamic Rapidly-exploring Ran- dom Forest (KRRF) to find a collision-free multi-goal trajectory that satisfies the motion constraints of the robot. KRRF simul- taneously grows kinodynamic trees from all targets towards all other targets while using the other trees as a heuristic to boost the growth. Once the target-to-target trajectories are planned, their cost is used to solve the TSP to find the sequence of targets. The final multi-goal trajectory satisfying kinodynamic constraints is planned by guiding the RRT-based planner along the target-to- target trajectories in the TSP sequence. Compared with existing approaches, KRRF provides shorter target-to-target trajectories and final multi-goal trajectories with 1.1 - 2 times lower costs while being computationally faster in most test cases. The method will be published as an open-source library.

Druh

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

CEP obor

—

OECD FORD obor

20204 - Robotics and automatic control

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2024

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

9

Číslo periodika v rámci svazku

12

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

8

Strana od-do

10724-10731

Kód UT WoS článku

001466141700001

EID výsledku v databázi Scopus

2-s2.0-85207037891