Ефективна побудова шляху для чотириколісних роботів на основі поєднання алгоритмів Theta* і гібридного A*

Auteurs-es

  • Віталій Геннадійович Михалько Національний технічний університет України “Київський політехнічний інститут” пр. Перемоги, 37, м. Київ, Україна, 03056, Ukraine https://orcid.org/0000-0002-1811-8344
  • Ігор Володимирович Круш Національний технічний університет України “Київський політехнічний інститут” пр. Перемоги, 37, м. Київ, Україна, 03056, Ukraine https://orcid.org/0000-0001-7083-1799

DOI :

https://doi.org/10.15587/2313-8416.2016.73625

Mots-clés :

робототехніка, чотириколісні роботи, штучний інтелект, алгоритм пошуку шляху, Theta*, гібридний A*

Résumé

Запропоновано алгоритм ефективної побудови шляху для чотириколісних роботів на основі поєднання алгоритмів Theta* і гібридного A*. Наведено і пояснено псевдокод для алгоритму . Реалізовано запропонований алгоритм і симулятор чотириколісного робота на мові програмування Java. Протестовано роботу алгоритму для U-подібних перешкод, складних карт і для вирішення задачі паркування

Bibliographies de l'auteur-e

Віталій Геннадійович Михалько, Національний технічний університет України “Київський політехнічний інститут” пр. Перемоги, 37, м. Київ, Україна, 03056

Кафедра системного проектування

Ігор Володимирович Круш, Національний технічний університет України “Київський політехнічний інститут” пр. Перемоги, 37, м. Київ, Україна, 03056

Кафедра системного проектування

Références

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1 (1), 269–271. doi: 10.1007/bf01386390

Sniedovich, M. (2006). Dijkstra’s algorithm revisited: the dynamic programming connexion. Journal of Control and Cybernetics, 35 (3), 599–620.

Delling, D., Sanders, P., Schultes, D., Wagner, D. (2009). Engineering Route Planning Algorithms. Lecture Notes in Computer Science, 117–139. doi: 10.1007/978-3-642-02094-0_7

Zeng, W., Church, R. L. (2009). Finding shortest paths on real road networks: the case for A*. International Journal of Geographical Information Science, 23 (4), 531–543. doi: 10.1080/13658810801949850

Russell, S, Norvig, P. (2009). Artificial Intelligence: A Modern Approach. 3rd ed. Prentice Hall, 1152.

Theta*: Any-Angle Path Planning for Smoother Trajectories in Continuous Environments. Available at: http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/

LaValle, S. M. Rapidly-exploring random trees: A new tool for path planning. Available at: http://msl.cs.uiuc.edu/~lavalle/papers/Lav98c.pdf

Practical Search Techniques in Autonomous Driving. Available at: http://ai.stanford.edu/~ddolgov/papers/dolgov_gpp_stair08.pdf

Junior: The Stanford Entry in the Urban Challenge. Available at: http://robots.stanford.edu/papers/junior08.pdf

rcTek – Ackerman Steering Principle. Available at: http://www.rctek.com/technical/handling/ackerman_steering_principle.html

Krause, E. F. (1987). Taxicab Geometry. Dover, 96.

Car simulator and path finding algorithm, source code. Available at: https://github.com/vmykh/car-model

Téléchargements

Publié-e

2016-07-30

Numéro

Vol. 7 No. 2 (24) (2016)

Rubrique

Technical Sciences

Licence

(c) Tous droits réservés Віталій Геннадійович Михалько, Ігор Володимирович Круш 2016

Licence Creative Commons

Cette œuvre est sous licence Creative Commons Attribution 4.0 International.

Our journal abides by the Creative Commons CC BY copyright rights and permissions for open access journals.

Authors, who are published in this journal, agree to the following conditions:

1. The authors reserve the right to authorship of the work and pass the first publication right of this work to the journal under the terms of a Creative Commons CC BY, which allows others to freely distribute the published research with the obligatory reference to the authors of the original work and the first publication of the work in this journal.

 2. The authors have the right to conclude separate supplement agreements that relate to non-exclusive work distribution in the form in which it has been published by the journal (for example, to upload the work to the online storage of the journal or publish it as part of a monograph), provided that the reference to the first publication of the work in this journal is included.