Space-filling forest for multi-goal path planning

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

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Space-filling forest for multi-goal path planning

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Space-filling forest for multi-goal path planning

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/GJ19-22555Y" target="_blank" >GJ19-22555Y: Vzorkovací techniky plánování pohybu a akcí s využitím aproximačních řešení</a><br>

Návaznosti

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

Rok uplatnění

2019

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 statě ve sborníku

24th IEEE Conference on Emerging Technologies and Factory Automation

ISBN

978-1-7281-0303-7

ISSN

—

e-ISSN

1946-0759

Počet stran výsledku

4

Strana od-do

1587-1590

Název nakladatele

IEEE

Místo vydání

Piscataway, NJ

Místo konání akce

Zaragoza

Datum konání akce

10. 9. 2019

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—