ВДОСКОНАЛЕНИЙ МЕТОД ПЛАНУВАННЯ ШЛЯХУ АВТОНОМНОГО НАЗЕМНОГО РОБОТА З ВИКОРИСТАННЯМ АЛГОРИТМУ MBD-RRT*FFT

Анотація

В дослідженні проведено аналіз проблем, пов’язаних із плануванням шляху переміщення роботів і підвищення точності та надійності їх наведення у режимі реального часу. Задля вирішення цієї проблеми досліджено, проведено вдосконалення модифікації асимптотично оптимального алгоритму BD-RRT*FT. Розроблений алгоритм MBD-RRT*FFТ при застосуванні в динамічних середовищах завдяки використанню багатопотокового обчислення має кращі можливості динамічного планування. Використання Fitch’s-алгоритму вибору оптимального результату пошуку надає спрямованості вибору оптимального прямолінійного шляху.

Задля перевірки ефективності запропонованого методу вдосконалення алгоритму проведено імітаційне моделювання з використанням власної програми моделювання. Проведено порівняння алгоритму MBD-RRT*FFТ з іншими алгоритмами за трьома картами з оцінюванням показників продуктивності.

З метою оцінки поведінки програми, а також ідентифікації вузьких місць виконання алгоритму на всіх етапах перевірки проводився контроль навантаження на пам’ять системи прийняття рішення.
Це дозволило побачити підвищення споживання ресурсів пам’яті на 12–15 %, але враховуючи отримані результати щодо оптимальності та швидкості обчислень, зроблено висновки щодо мінімальності впливу. Це надало додаткове розуміння необхідності уважного вибору апаратної складової систем прийняття рішень.

Наукова новизна методу полягає у застосуванні науково-методичного апарату з вдосконалення алгоритму BD-RRT*FT, що надало подальший розвиток щодо розширення та доповнення відомих даних про алгоритми з плануванням шляху робота і підвищення точності та надійності його наведення у режимі реального часу. Метод охоплює способи дослідження, систематизацію, коригування нових і отриманих раніше знань.

Посилання

1. Бернацький А. П. Метод планування шляху автономного наземного робота з використанням модифікації динамічного двонаправленого RRT-алгоритму // Системи і технології зв’язку, інформатизації та кібербезпеки. 2023. №  4. С. 16–31. DOI: 10.58254/viti.4.2023.02.16.
2. Бернацький А. П. Основи робототехніки військового призначення / А. П. Бернацький, І. В.  Панченко, О. І. Восколович. Київ: ВІТІ, 2021. 496 с.
3. Бернацький А. П., Панченко І. В., Восколович О. І. Розширена математична модель руху автономного наземного робота розвідника в умовах бойових дій в урбанізованому просторі // Озброєння та військова техніка. 2021. № 30 (2). С. 121–129.
4. Бідюк П. І. Cистеми і методи підтримки прийняття рішень / П. І. Бідюк, О. Л. Тимощук. Київ: КПІ ім. Ігоря Сікорського, 2022.
5. Про нарощування спроможностей сил оборони: Указ Президента України від 06.02.2024 № 51/2024. URL: https://www.president.gov.ua/documents/512024-49625.
6. Про рішення Ради національної безпеки і оборони України від 25 березня 2021 року «Про Стратегію воєнної безпеки України»: Указ Президента України від 21.03.2021 № 121.
7. 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. URL: https://doi:10.1109/ICMA.2017.8016024.
8. Black, Paul E. Greedy algorithm. Dictionary of Algorithms and Data Structures, US National Institute of Standards and Technology* PE Black. 2010. URL: http://www.nist. gov/dads/HTML/greedyalgo.html.
9. Cormen T., Leiserson C., Rivest R., Stein C. Introduction to Algorithms 3rd ed. Cambridge, London: The MIT Press, 2009. 1312 p.
10. 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. URL:https://doi.org/10.1109/IROS.2014.6942976.
11. 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. URL:https://doi:10.1016/j.eswa.2019.01.032.
12. 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. URL: https://doi.org/10.3991/ijoe.v16i08.14243.
13. Kagan E., Ben-Gal I. A Group-Testing Algorithm with Online Informational Learning // IIE Transactions (Institute of Industrial Engineers). No. 46 (2). P. 164–184. URL: https://doi.org/10.1080/0740817X.2013.803639.
14. Klemm S., Oberländer J., Hermann A., Roennau A., Schamm T., Zollner J. M., Dillmann R. RT-Connect: Faster, asymptotically optimal motion planning // 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO 2015) At: Zhuhai, China. Volume12. URL: https://doi.org/10.1109/
    ROBIO.2015.7419012.
15. LiB., Chen B. An Adaptive Rapidly-Exploring Random Tree // IEEE/САА Journal of Automatica Sinica. 2021. URL: https://doi.org/10.1109/JAS.2021.1004252.
16. Majeed A, Hwang SO. Path planning method for UAVs based on constrained polygonal space and an extremely sparse waypoint graph // Applied Sciences. 2021. No. 11 (12). Р. 5340. URL: https://doi.org/10.3390/app11125340.
17. MawA. 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. No. 11 (9). P. 1–18. URL: https://doi.org/10.3390/app11093948.
18. Schapire R., Freund Y. Boosting: Foundations and Algorithms. MIT, 2012.
19. 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, pp. 53–57. URL: https://doi:10.1109/URAI.2015.7358927.
20. Taheri E., Ferdowsi M. H., Danesh M. Fuzzy greedy RRT path planning algorithm in a complex configuration space // Int. J. Control. Autom. Syst. 2018. No. 16. P. 3026–3035. URL: https://doi:10.1007/
    s12555-018-0037-6.
21. Thomas H. Corman, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algorithms: construction and analysis. Introduction to Algorithms. Michigan U.: Williams, 2006.
22. 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.
23. Wirth N. Algorithms + Data Structures = Programs (Prentice-Hall Series in Automatic Computation) / N. Wirth. Hoboken: Prentice Hall, 1976. 366 p.
24. Zhang L., Shen J., Yang J., Li G. Analyzing the fitch method for reconstructing ancestral states on ultrametric phylogenetic trees // Bulletin of Mathematical Biology. 2010. P. 1760–1782. DOI: 10.1007/s11538-010-9505-8.