Optimal solution of the Generalized Dubins Interval Problem: finding the shortest curvature-constrained path through a s
- PDF / 2,319,951 Bytes
- 18 Pages / 595.276 x 790.866 pts Page_size
- 109 Downloads / 207 Views
Optimal solution of the Generalized Dubins Interval Problem: finding the shortest curvature-constrained path through a set of regions Petr Vána ˇ 1
· Jan Faigl1
Received: 15 December 2018 / Accepted: 14 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The Generalized Dubins Interval Problem (GDIP) stands to determine the minimal length path connecting two disk-shaped regions where the departure and terminal headings of Dubins vehicle are within the specified angle intervals. The GDIP is a generalization of the existing point-to-point planning problem for Dubins vehicle with a single heading angle per particular location that can be solved optimally using closed-form expression. For the GDIP, both the heading angles and locations need to be chosen from continuous sets which makes the problem challenging because of infinite possibilities how to connect the regions by Dubins path. We provide the optimal solution of the introduced GDIP based on detailed problem analysis. Moreover, we propose to employ the GDIP to provide the first tight lower bound for the Dubins Touring Regions Problem which stands to find the shortest curvature-constrained path through a set of regions in the prescribed order. Keywords Dubins vehicle · Multi-goal planning · Generalized Dubins Interval Problem · Dubins Touring Regions Problem
1 Introduction Surveillance missions are frequent tasks for unmanned aerial vehicles in which the vehicles are requested to visit a given set of target locations and collect the required data. If the sequence of visits to the locations is known a priori, the problem can be formulated as the Dubins Touring Problem (DTP) (Faigl et al. 2017) in which the movement of the vehicle is restricted by the motion constraints of Dubins vehicle (Dubins 1957). Thus, a solution of the DTP is the This is one of the several papers published in Autonomous Robots comprising the Special Issue on Robotics: Science and Systems. The presented work has been supported by the Czech Science ˇ under research Project No. 19-20238S. Foundation (GACR) Electronic supplementary material The online version of this article (https://doi.org/10.1007/s10514-020-09932-x) contains supplementary material, which is available to authorized users.
B
Petr Váˇna [email protected] Jan Faigl [email protected]
1
Department of Computer Science, Faculty of Electrical Engineering, Czech Technical University in Prague, Technická 2, 166 27 Prague, Czech Republic
shortest curvature-constrained multi-goal path connecting the requested target locations in the prescribed order. Moreover, a target location can be considered visited if the vehicle is within a specified distance from it, e.g., using remote data collection or range measurements, and we formulate the problem as the Dubins Touring Regions Problem (DTRP). The solution of the problem is described by visiting locations to the given regions and the corresponding heading angles. The final path is constructing by the shortest curvature-constrained segments for Dub
Data Loading...
