Fast Sequence Rejection for Multi-Goal Planning with Dubins Vehicle
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Fast Sequence Rejection for Multi-Goal Planning with Dubins Vehicle
Original language description
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.
Czech name
—
Czech description
—
Classification
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)
Result continuities
Project
<a href="/en/project/GA19-20238S" target="_blank" >GA19-20238S: Multi-Robot Persistent Monitoring of Dynamic Environments</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
2020 IEEE/RSJ International Conference on Intelligent Robots and Systems
ISBN
978-1-7281-6212-6
ISSN
2153-0858
e-ISSN
2153-0866
Number of pages
8
Pages from-to
6773-6780
Publisher name
IEEE Robotics and Automation Society
Place of publication
Piscataway
Event location
Las Vegas
Event date
Oct 25, 2020
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—