WiSM: Windowing Surrogate Model for Evaluation of Curvature-Constrained Tours With Dubins Vehicle

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00356027" target="_blank" >RIV/68407700:21230/22:00356027 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1109/TCYB.2020.3000465" target="_blank" >https://doi.org/10.1109/TCYB.2020.3000465</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

WiSM: Windowing Surrogate Model for Evaluation of Curvature-Constrained Tours With Dubins Vehicle

Popis výsledku v původním jazyce

Dubins tours represent a solution of the Dubins traveling salesman problem (DTSP) that is a variant of the optimization routing problem to determine a curvature-constrained shortest path to visit a set of locations such that the path is feasible for Dubins vehicle, which moves only forward and has a limited turning radius. The DTSP combines the NP-hard combinatorial optimization to determine the optimal sequence of visits to the locations, as in the regular TSP, with the continuous optimization of the heading angles at the locations, where the optimal heading values depend on the sequence of visits and vice versa. We address the computationally challenging DTSP by fast evaluation of the sequence of visits by the proposed windowing surrogate model (WiSM), which estimates the length of the optimal Dubins path connecting a sequence of locations in a Dubins tour. The estimation is sped up by a regression model trained using close to optimum solutions of small Dubins tours that are generalized for large-scale instances of the addressed DTSP utilizing the sliding-window technique and a cache for already computed results. The reported results support that the proposed WiSM enables fast convergence of a relatively simple evolutionary algorithm to high-quality solutions of the DTSP. We show that with an increasing number of locations, our algorithm scales significantly better than other state-of-the-art DTSP solvers.

Název v anglickém jazyce

WiSM: Windowing Surrogate Model for Evaluation of Curvature-Constrained Tours With Dubins Vehicle

Popis výsledku anglicky

Dubins tours represent a solution of the Dubins traveling salesman problem (DTSP) that is a variant of the optimization routing problem to determine a curvature-constrained shortest path to visit a set of locations such that the path is feasible for Dubins vehicle, which moves only forward and has a limited turning radius. The DTSP combines the NP-hard combinatorial optimization to determine the optimal sequence of visits to the locations, as in the regular TSP, with the continuous optimization of the heading angles at the locations, where the optimal heading values depend on the sequence of visits and vice versa. We address the computationally challenging DTSP by fast evaluation of the sequence of visits by the proposed windowing surrogate model (WiSM), which estimates the length of the optimal Dubins path connecting a sequence of locations in a Dubins tour. The estimation is sped up by a regression model trained using close to optimum solutions of small Dubins tours that are generalized for large-scale instances of the addressed DTSP utilizing the sliding-window technique and a cache for already computed results. The reported results support that the proposed WiSM enables fast convergence of a relatively simple evolutionary algorithm to high-quality solutions of the DTSP. We show that with an increasing number of locations, our algorithm scales significantly better than other state-of-the-art DTSP solvers.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2022

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 periodika

IEEE Transactions on Cybernetics

ISSN

2168-2267

e-ISSN

2168-2275

Svazek periodika

52

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

10

Strana od-do

1302-1311

Kód UT WoS článku

000756813500051

EID výsledku v databázi Scopus

2-s2.0-85124805783