Multi-Goal Path Planning Using Multiple Random Trees

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F21%3A00349691" target="_blank" >RIV/68407700:21230/21:00349691 - isvavai.cz</a>

Result on the web

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

DOI - Digital Object Identifier

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

Result language

angličtina

Original language name

Multi-Goal Path Planning Using Multiple Random Trees

Original language description

In this letter, we propose a novel sampling-based planner for multi-goal path planning among obstacles, where the objective is to visit predefined target locations while minimizing the travel costs. The order of visiting the targets is often achieved by solving the Traveling Salesman Problem (TSP) or its variants. TSP requires to define costs between the individual targets, which — in a map with obstacles — requires to compute mutual paths between the targets. These paths, found by path planning, are used both to define the costs (e.g., based on their length or time-to-traverse) and also they define paths that are later used in the final solution. To enable TSP finding a good-quality solution, it is necessary to find these target-to-target paths as short as possible. We propose a sampling-based planner called Space-Filling Forest (SFF*) that solves the part of finding collision-free paths. SFF* uses multiple trees (forest) constructed gradually and simultaneously from the targets and attempts to find connections with other trees to form the paths. Unlike Rapidly-exploring Random Tree (RRT), which uses the nearest-neighbor rule for selecting nodes for expansion, SFF* maintains an explicit list of nodes for expansion. Individual trees are grown in a RRT* manner, i.e., with rewiring the nodes to minimize their cost. Computational results show that SFF* provides shorter target-to-target paths than existing approaches, and consequently, the final TSP solutions also have a lower cost.

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

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GJ19-22555Y" target="_blank" >GJ19-22555Y: Sampling-based planning of actions and motions using approximate solutions</a><br>

Continuities

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

Publication year

2021

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

6

Issue of the periodical within the volume

2

Country of publishing house

US - UNITED STATES

Number of pages

8

Pages from-to

4201-4208

UT code for WoS article

000639767600009

EID of the result in the Scopus database

2-s2.0-85103263558