МЕТОД ПЛАНУВАННЯ ШЛЯХУ АВТОНОМНОГО НАЗЕМНОГО РОБОТА З ВИКОРИСТАННЯМ МОДИФІКАЦІЇ ДИНАМІЧНОГО ДВОНАПРАВЛЕНОГО RRT-АЛГОРИТМУ

Анотація

Проблема планування шляху безпілотних автономних наземних засобів завжди була гострою проблемою в галузі досліджень автономних наземних робототехнічних систем. З погляду на складність завдань під час проведення бойових дій в урбанізованому просторі щільної забудови міста з постійною зміною ландшафту, завдання, які покладаються на безпілотні автономні наземні засоби, постійно ускладнюються, а сценарії використання безпілотних автономних наземних засобів демонструють диверсифіковану тенденцію розвитку нових систем прийняття рішень безпілотних автономних наземних засобів. Швидкоплинність ведення сучасних бойових дій в урбанізованому просторі постає як складне і багатопланове завдання. Враховуючи складність процесу руху безпілотних автономних наземних засобів, на сучасному етапі розвитку робототехнічних систем, загальною тенденцією є відмова від дистанційного керування роботизованими комплексами з переходом до автоматичних режимів, що вимагає розробки, впровадження алгоритмів автоматичної взаємодії та руху військових мобільних робототехнічних систем. Задля вирішення проблеми пришвидшення отримання рішень пошуку шляхів без зіткнень у режимі реального часу у двовимірному просторі пропонується застосувати модифікований динамічний двонаправлений алгоритм «швидке дослідження випадкового дерева із зірочкою» з реперними вузлами. Запропонований алгоритм є модифікацією алгоритму «швидке дослідження випадкового дерева із зірочкою» з реперними вузлами, з використанням методу двонаправленого жадібного пошуку для прискорення та вирішення проблеми односпрямованого алгоритму «швидке дослідження випадкового дерева» щодо його повільної швидкості пошуку, а також труднощів прийняття рішення у вузькому середовищі, викликаних сліпою випадковою вибіркою. В разі динамічного переміщення перешкоди така модифікація завдяки перевазі, що реперні вузли не потребують багато обчислень під час планування, у процесі ітераційної оптимізації шляху виконує оновлення інформації карти в режимі реального часу та відновлює пошкоджений вихідний шлях для завершення динамічного планування шляху.


Посилання

1. Бернацький А. П., Панченко І. В., Восколович О. І. Розширена математична модель руху автономного наземного робота розвідника в умовах бойових дій в урбанізованому просторі // Озброєння та військова техніка. 2021. № 30 (2). С. 121–129.

2. Winnfield J. A. Unmanned Systems Integrated Roadmap FY2011-2036 / Winnfield J. A. Jr., Kendall F.-Washington, DC: U. S. Department of Defense, March 9, 2012.

3. Бернацький А., Панченко І., Восколович О. Основи робототехніки військового призначення: конспект лекцій. Київ: ВІТІ, 2021.

4. Thomas H. Corman, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algorithms: construction and analysis. Introduction to Algorithms. Michigan U.: Williams, 2006. ISBN 978-0-262-53305-8.

5. Robert Schapire, Yoav Freund. Boosting: Foundations and Algorithms. MIT, 2012. ISBN 10: 0262526034; ISBN 13: 9780262526036.

6. Maw A. A., Tyan M., Nguyen T. A. et al. iADA*-RL: Anytime graph-based path planning with deep reinforcement learning for an autonomous UAV // Applied Sciences. 2021. № 11 (9). Р. 1–18. DOI: https://doi.org/10.3390/app11093948.

7. Kadry S., Alferov G., Fedorov V. D-Star Algorithm Modification // International Journal of Online and Biomedical Engineering (iJOE). 2020. Vol. 16. Nо. 8. Р. 108–113. DOI: https://doi.org/10.3991/
ijoe.v16i08.14243.

8. Majeed A., Hwang SO. Path planning method for UAVs based on constrained polygonal space and an extremely sparse waypoint graph // Applied Sciences. 2021. № 11 (12). Р. 5340. DOI: https://doi.org/
10.3390/app11125340.

9. Kagan E. and Ben-Gal I. A Group-Testing Algorithm with Online Informational Learning. IIE Transactions // Institute of Industrial Engineers. № 46 (2). Р. 164–184. DOI: https://doi.org/10.1080/
0740817X.2013.803639.

10. Jeong I. B., Lee S. J., Kim J. H. Quick-RRT*: Triangular inequality-based implementation of RRT* with improved initial solution and convergence rate // Expert Syst. Appl. 2019. № 123. Р. 82–90. DOI: https://doi: 10.1016/j.eswa.2019.01.032.

11. Black, Paul E. Greedy algorithm. Dictionary of Algorithms and Data Structures, US National Institute of Standards and Technology* PE Black. URL: http://www.nist.gov/dads/HTML/greedyalgo.html.

12. Gammell J. D., Srinivasa S. S., Barfoot T. D. Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic; Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems; Chicago, IL, USA. 14–18 September 2014. DOI: https://doi.org/10.1109/IROS.2014.6942976.

13. Taheri E., Ferdowsi M. H., Danesh M. Fuzzy greedy RRT path planning algorithm in a complex configuration space. Int. J. Control. Autom. Syst. 2018. № 16. Р. 3026–3035. DOI: https://doi:10.1007/
s12555-018-0037-6.

14. Adiyatov, Olzhas; Varol, Huseyin Atakan. A novel RRT-based algorithm for motion planning in Dynamic environments. In Mechatronics and Automation (ICMA), 2017 IEEE International Conference on, 2017. Р. 1416–1421. DOI: https://doi:10.1109/ICMA.2017.8016024.

15. Spanogianopoulos, Sotirios and Sirlantzis, Konstantinos Non-holonomic Path Planning of Car-like Robot using RRT*FN. In: 2015 12th International Conference on Ubiquitous Robots and Ambient Intelligence (URAI). 2015. IEEE. Р. 53–57. E-ISBN 978-1-4673-7971-7. DOI: https://doi:10.1109/URAI.2015.7358927.

16. Бідюк П. І., Тимощук О. Л. та ін. Cистеми і методи підтримки прийняття рішень. Київ: КПІ ім. Ігоря Сікорського, 2022.

17. Li B., Chen B. An Adaptive Rapidly-Exploring Random Tree, Journal of Automatica Sinica. 2021. IEEE. DOI: https://doi.org/10.1109/JAS.2021.1004252.

18. Klemm S., Oberländer J., Hermann A., Roennau A., Schamm T., Zollner J. M., Dillmann R. RT-Connect: Faster, asymptotically optimal motion planning / Conference: 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO 2015). At: Zhuhai, ChinaVolume: 12. DOI: https://doi.org/10.1109/
ROBIO.2015.7419012.