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

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

Віталій Геннадійович Михалько, Ігор Володимирович Круш

Аннотация


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


Ключевые слова


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

Полный текст:

PDF (Українська)

Литература


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


Пристатейная библиография ГОСТ


Dijkstra, E. W. A note on two problems in connexion with graphs [Text] / E. W. Dijkstra // Numerische Mathematik. – 1959. – Vol. 1, Issue 1. – P. 269–271. doi: 10.1007/bf01386390 

Sniedovich, M. Dijkstra’s algorithm revisited: the dynamic programming connexion [Text] / M. Sniedovich // Journal of Control and Cybernetics. – 2006. – Vol. 35, Issue 3. – P. 599–620.

Delling, D. Engineering route planning algorithms [Text] / D. Delling, P. Sanders, D. Schultes, D. Wagner // Lecture Notes in Computer Science, 2009. – P. 117–139. doi: 10.1007/978-3-642-02094-0_7 

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

Russell, S. Artificial Intelligence: A Modern Approach; 3rd ed. [Text] / S. Russell, P. Norvig. – Prentice Hall, 2009. – 1152 p.

Theta*: Any-Angle Path Planning for Smoother Trajectories in Continuous Environments [Electronic resource]. – 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 [Electronic resource] / S. M. LaValle. – Available at: http://msl.cs.uiuc.edu/~lavalle/papers/Lav98c.pdf

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

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

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

Krause, E. F. Taxicab Geometry [Text] / E. F. Krause. – Dover, 1987. – 96 p.

Car simulator and pathfinding algorithm, source code [Electronic resource]. – Available at: https://github.com/vmykh/car-model






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

Creative Commons License
Эта работа лицензирована Creative Commons Attribution 4.0 International License.

ISSN 2313-8416 (Online), ISSN 2313-6286 (Print)