Space-filling forest for multi-goal path planning

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F19%3A00335538" target="_blank" >RIV/68407700:21230/19:00335538 - isvavai.cz</a>

Result on the web

<a href="https://ieeexplore.ieee.org/document/8869521" target="_blank" >https://ieeexplore.ieee.org/document/8869521</a>

DOI - Digital Object Identifier

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

Result language

angličtina

Original language name

Space-filling forest for multi-goal path planning

Original language description

In multi-goal path planning, the task is to find a sequence to visit a set of target locations in an environment. The combinatorial part of the problem (finding the sequence) can be solved as an instance of Traveling Salesman Problem, which requires knowledge about collision-free paths (and distances) between the individual targets. Finding the collision-free paths between the targets is essential in this task. Sampling-based planners like Probabilistic Roadmaps (PRM) and Rapidly-exploring Random Tree (RRT) can be used to find these paths. However, PRM can be computationally demanding, as it attempts to connect each node in the roadmap to its neighbors, regardless of their later usage in the solution. Contrary, RRT is a tree-based planner, and one run can only provide paths starting in the root of the tree (a single target). In this paper, we propose a novel planner for multi-goal path planning. Multiple trees (forest) are constructed simultaneously from the targets and expanded by collision-free configurations until they touch each other or obstacles. Each tree, therefore, does not explore the whole configuration space (as in the case of RRT), and its construction is faster than PRM, as it uses lower number of edges. The efficiency of this new planning approach is demonstrated in the multi-goal path planning in 2D environment with tens of targets and with narrow passages.

Czech name

—

Czech description

—

Type

D - Article in proceedings

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

2019

Confidentiality

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

Article name in the collection

24th IEEE Conference on Emerging Technologies and Factory Automation

ISBN

978-1-7281-0303-7

ISSN

—

e-ISSN

1946-0759

Number of pages

4

Pages from-to

1587-1590

Publisher name

IEEE

Place of publication

Piscataway, NJ

Event location

Zaragoza

Event date

Sep 10, 2019

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—