Fast Sequence Rejection for Multi-Goal Planning with Dubins Vehicle

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00347638" target="_blank" >RIV/68407700:21230/20:00347638 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1109/IROS45743.2020.9340644" target="_blank" >https://doi.org/10.1109/IROS45743.2020.9340644</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Fast Sequence Rejection for Multi-Goal Planning with Dubins Vehicle

Popis výsledku v původním jazyce

Multi-goal curvature-constrained planning such as the Dubins Traveling Salesman Problem (DTSP) combines NP-hard combinatorial routing with continuous optimization to determine the optimal vehicle heading angle for each target location. The problem can be addressed as combinatorial routing using a finite set of heading samples at target locations. In such a case, optimal heading samples can be determined for a sequence of targets in polynomial time, and the DTSP can be solved as searching for a sequence with the minimal cost. However, the examination of sequences can be computationally demanding for high numbers of heading samples and target locations. A fast rejection schema is proposed to quickly examine unfavorable sequences using lower bound estimation of Dubins tour cost based on windowing technique that evaluates short subtours of the sequences. Furthermore, the computation using small problem instances can benefit from reusing stored results and thus speed up the search. The reported results indicate that the computational burden is decreased about two orders of magnitude, and the proposed approach supports finding high-quality solutions of routing problems with Dubins vehicle.

Název v anglickém jazyce

Fast Sequence Rejection for Multi-Goal Planning with Dubins Vehicle

Popis výsledku anglicky

Multi-goal curvature-constrained planning such as the Dubins Traveling Salesman Problem (DTSP) combines NP-hard combinatorial routing with continuous optimization to determine the optimal vehicle heading angle for each target location. The problem can be addressed as combinatorial routing using a finite set of heading samples at target locations. In such a case, optimal heading samples can be determined for a sequence of targets in polynomial time, and the DTSP can be solved as searching for a sequence with the minimal cost. However, the examination of sequences can be computationally demanding for high numbers of heading samples and target locations. A fast rejection schema is proposed to quickly examine unfavorable sequences using lower bound estimation of Dubins tour cost based on windowing technique that evaluates short subtours of the sequences. Furthermore, the computation using small problem instances can benefit from reusing stored results and thus speed up the search. The reported results indicate that the computational burden is decreased about two orders of magnitude, and the proposed approach supports finding high-quality solutions of routing problems with Dubins vehicle.

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/GA19-20238S" target="_blank" >GA19-20238S: Multi-robotické monitorování dynamických prostředí</a><br>

Návaznosti

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

Rok uplatnění

2020

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

2020 IEEE/RSJ International Conference on Intelligent Robots and Systems

ISBN

978-1-7281-6212-6

ISSN

2153-0858

e-ISSN

2153-0866

Počet stran výsledku

8

Strana od-do

6773-6780

Název nakladatele

IEEE Robotics and Automation Society

Místo vydání

Piscataway

Místo konání akce

Las Vegas

Datum konání akce

25. 10. 2020

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

WRD - Celosvětová akce

Kód UT WoS článku

—