On solution of the Dubins touring problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F17%3A00315446" target="_blank" >RIV/68407700:21230/17:00315446 - isvavai.cz</a>

Výsledek na webu

<a href="http://ieeexplore.ieee.org/document/8098685/" target="_blank" >http://ieeexplore.ieee.org/document/8098685/</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

On solution of the Dubins touring problem

Popis výsledku v původním jazyce

The Dubins traveling salesman problem (DTSP) combines the combinatorial optimization of the optimal sequence of waypoints to visit the required target locations with the continuous optimization to determine the optimal headings at the waypoints. Existing decoupled approaches to the DTSP are based on an independent solution of the sequencing part as the Euclidean TSP and finding the optimal headings of the waypoints in the sequence. In this work, we focus on the determination of the optimal headings in a given sequence of waypoints and formulate the problem as the Dubins touring problem (DTP). The DTP can be solved by a uniform sampling of possible headings; however, we propose a new informed sampling strategy to find approximate solution of the DTP. Based on the presented results, the proposed algorithm quickly converges to a high-quality solution, which is less than 0.1% from the optimum. Besides, the proposed approach also improves the solution of the DTSP, and its feasibility has been experimentally verified in a real practical deployment.

Název v anglickém jazyce

On solution of the Dubins touring problem

Popis výsledku anglicky

The Dubins traveling salesman problem (DTSP) combines the combinatorial optimization of the optimal sequence of waypoints to visit the required target locations with the continuous optimization to determine the optimal headings at the waypoints. Existing decoupled approaches to the DTSP are based on an independent solution of the sequencing part as the Euclidean TSP and finding the optimal headings of the waypoints in the sequence. In this work, we focus on the determination of the optimal headings in a given sequence of waypoints and formulate the problem as the Dubins touring problem (DTP). The DTP can be solved by a uniform sampling of possible headings; however, we propose a new informed sampling strategy to find approximate solution of the DTP. Based on the presented results, the proposed algorithm quickly converges to a high-quality solution, which is less than 0.1% from the optimum. Besides, the proposed approach also improves the solution of the DTSP, and its feasibility has been experimentally verified in a real practical deployment.

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/GA16-24206S" target="_blank" >GA16-24206S: Metody informatického plánování cest pro neholonomní mobilní roboty v úlohách monitorování a dohledu</a><br>

Návaznosti

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

Rok uplatnění

2017

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

Proceedings of ECMR 2017

ISBN

978-1-5386-1096-1

ISSN

—

e-ISSN

—

Počet stran výsledku

6

Strana od-do

—

Název nakladatele

IEEE

Místo vydání

Marseille

Místo konání akce

Paris

Datum konání akce

6. 9. 2017

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

WRD - Celosvětová akce

Kód UT WoS článku

000426455100032