nach oben

Autonomous Robots

Erschienen in:

05.08.2020

Optimal solution of the Generalized Dubins Interval Problem: finding the shortest curvature-constrained path through a set of regions

verfasst von: Petr Váňa, Jan Faigl

Erschienen in: Autonomous Robots | Ausgabe 7/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel An analysis of RelaxedIK: an optimization-based framework for generating accurate and feasible robot arm motions

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Source codes are available at https://github.com/comrob/gdip.

The instances have been generated with the relative density \(d=0.3\) and possibly overlapping regions where the region centers are randomly placed with the squared bounding box with the size \(s={\rho \sqrt{n}}/{d}\).

Applegate, D., Bixby, R., Chvátal, V., Cook, W., Espioza, D., Goycoolea, M., & Helsgaun, K. (2003). Concorde TSP Solver. https://www.tsp.gatech.edu/concorde.html. [cited: July 2, 2019].

Bertsekas, D. P. (2014). Constrained optimization and Lagrange multiplier methods. New York: Academic Press. https://doi.org/10.1016/C2013-0-10366-2.CrossRefMATH

Bui, X. N., Boissonnat, J. D., Soueres, P., & Laumond, J. P. (1994). Shortest path synthesis for Dubins non-holonomic robot. In IEEE international conference on robotics and automation (ICRA). https://doi.org/10.1109/ROBOT.1994.351019.

Cohen, I., Epstein, C., & Shima, T. (2017). On the discretized Dubins traveling salesman problem. IISE Transactions, 49(2), 238–254. https://doi.org/10.1080/0740817X.2016.1217101.CrossRef

Dubins, L. E. (1957). On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. American Journal of Mathematics,. https://doi.org/10.2307/2372560.MathSciNetCrossRefMATH

Faigl, J., Váňa, P., Saska, M., Báča, T., & Spurný, V. (2017). On solution of the Dubins touring problem. In European conference on mobile robots (ECMR) (pp. 1–6). IEEE. https://doi.org/10.1109/ECMR.2017.8098685.

Goaoc, X., Kim, H. S., & Lazard, S. (2013). Bounded-curvature shortest paths through a sequence of points using convex optimization. SIAM Journal on Computing, 42(2), 662–684. https://doi.org/10.1137/100816079.MathSciNetCrossRefMATH

Isaacs, J. T., Klein, D. J., & Hespanha, J. P. (2011). Algorithms for the traveling salesman problem with neighborhoods involving a Dubins vehicle. In American Control Conference (pp. 1704–1709). IEEE. https://doi.org/10.1109/ACC.2011.5991501.

Le Ny, J., Frazzoli, E., & Feron, E. (2007). The curvature-constrained traveling salesman problem for high point densities. In 46th conference on decision and control (pp. 5985–5990). IEEE. https://doi.org/10.1109/CDC.2007.4434503.

Macharet, D. G., & Campos, M. F. M. (2018). A survey on routing problems and robotic systems. Robotica, 36(12), 1–23. https://doi.org/10.1017/S0263574718000735.CrossRef

Macharet, D. G., Neto, A. A., da Camara Neto, V. F., & Campos, M. F. (2011). Nonholonomic path planning optimization for Dubins’ vehicles. In IEEE international conference on robotics and automation (ICRA) (pp. 4208–4213). https://doi.org/10.1109/ICRA.2011.5980239.

Manyam, S. G., & Rathinam, S. (2018). On tightly bounding the Dubins traveling salesman’s optimum. Journal of Dynamic Systems, Measurement, and Control, 140(7), 071013. https://doi.org/10.1115/1.4039099.CrossRef

Manyam, S. G., Rathinam, S., Casbeer, D., & Garcia, E. (2017). Tightly bounding the shortest Dubins paths through a sequence of points. Journal of Intelligent & Robotic Systems,. https://doi.org/10.1007/s10846-016-0459-4.CrossRef

Oberlin, P., Rathinam, S., & Darbha, S. (2010). Today’s traveling salesman problem. IEEE Robotics & Automation Magazine, 17(4), 70–77. https://doi.org/10.1109/MRA.2010.938844.CrossRef

Obermeyer, K.J. (2009). Path planning for a UAV performing reconnaissance of static ground targets in terrain. In AIAA guidance, navigation, and control conference (pp. 10–13). https://doi.org/10.2514/6.2009-5888.

Pěnička, R., Faigl, J., Váňa, P., & Saska, M. (2017). Dubins orienteering problem. Robotics and Automation Letters, 2(2), 1210–1217. https://doi.org/10.1109/LRA.2017.2666261.CrossRef

Savla, K., Frazzoli, E., & Bullo, F. (2005). On the point-to-point and traveling salesperson problems for Dubins’ vehicle. In American control conference (pp. 786–791) IEEE. https://doi.org/10.1109/ACC.2005.1470055.

Yu, X., & Hung, J. (2012). Optimal path planning for an autonomous robot-trailer system. In Industrial electronics society, 38th annual conference on (IECON) (pp. 2762–2767). IEEE. https://doi.org/10.1109/IECON.2012.6389140.

Titel: Optimal solution of the Generalized Dubins Interval Problem: finding the shortest curvature-constrained path through a set of regions
verfasst von: Petr Váňa
Jan Faigl
Publikationsdatum: 05.08.2020
Verlag: Springer US
Erschienen in: Autonomous Robots / Ausgabe 7/2020
Print ISSN: 0929-5593
Elektronische ISSN: 1573-7527
DOI: https://doi.org/10.1007/s10514-020-09932-x

Neuer Inhalt

Bildnachweise

VDI-Icon, Profil Icon, inhalt2, Springer Professional Modul/© Springer Fachmedien Wiesbaden GmbH, Nachhaltigkeitsaward Key Visual/© Cometis AG/Global ESG Monitor | Daniel Rupp | Generiert mit KI, Search Icon, Banner Hanser, Jonas Klose/© Pine Valley Capital GmbH, Carina Kießling von der Strategieberatung Roland Berger/© Monika Walther Fotografie | ATZ, Beijing Auto Show 2024: Deutsche Hersteller wollen angreifen./© EKH-Pictures / Generated with AI / Stock.adobe.com, Zeitschrift Wissensmanagement Cover, PatentFit-Logo/© Springer Fachmedien Wiesbaden GmbH, Zukunftswerkstatt Sales Excellence 2024/© AndreyPopov / Getty Images / iStock, 2023_Antrieb/© supervisuell, ATZ-Webinar: Prototypenfreie Entwicklung durch Offline- und Driver-in-the-Loop-HiL-Tests /© (c) VI-grade

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 7/2020

A unified kinematics modeling, optimization and control of universal robots: from serial and parallel manipulators to walking, rolling and hybrid robots

Iterative residual tuning for system identification and sim-to-real robot learning

High precision control and deep learning-based corn stand counting algorithms for agricultural robot

Plug-and-play supervisory control using muscle and brain signals for real-time gesture and error detection

Wind disturbance rejection for unmanned aerial vehicles using acceleration feedback enhanced method

An analysis of RelaxedIK: an optimization-based framework for generating accurate and feasible robot arm motions

Neuer Inhalt

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.