СИСТЕМЫ АНАЛИЗА И ОБРАБОТКИ ДАННЫХ

Сегодня беспилотная авиация используется для решения самых разных задач. Одна из проблем, возникающих при использовании беспилотных летательных аппаратов (БПЛА), – это проблема навигации, в частности установление их точного местоположения в пространстве. Сегодня существуют различные методы решения этой проблемы. Перспективным способом ее решения в условиях невозможности использования спутниковой системы навигации являются системы видеонавигации, использующие для установления местоположения визуальные ориентиры. В настоящей работе проведен обзор существующих типов систем видеонавигации БПЛА, выделены особенности работы систем видеонавигации, использующих сопоставление визуальных ориентиров со спутниковыми картами, поставлена задача поиска маршрута в условиях недостатка визуальных ориентиров, при которых возможно возникновение проблемы потери опорных точек. Описан используемый графовый формат данных, хранящий значения метрики разнообразия подстилающей поверхности, которая характеризует величину вероятности возникновения проблемы потери опорных точек. Рассмотрены существующие алгоритмы поиска пути в графе и обоснована необходимость разработки нового алгоритма.

Предложено теоретическое описание алгоритма, в котором процесс поиска пути делится на два этапа: вначале производится поиск варианта решения с максимальным значением метрики разнообразия подстилающей поверхности, а затем выбор маршрута с минимальной длиной. Приведено несколько вариантов реализации предложенного алгоритма и выполнена оценка их асимптотической сложности. На основании теоретического описания разработана программная реализация предложенного алгоритма и выполнена экспериментальная проверка корректности его работы на тестовой карте с различными полетными заданиями. По результатам тестирования предложенный алгоритм показал свою работоспособность, корректно построив маршруты во всех тестовых примерах. В дальнейшем этот алгоритм может быть использован как часть системы видеонавигации БПЛА. Также в статье описаны основные преимущества и недостатки алгоритма и предложены пути для его дальнейшего усовершенствования.

1. Khachatryan T.B. A review of visual odometry for UAV autonomous navigation // Вестник Национального политехнического университета Армении. Информационные технологии, электроника, радиотехника. – 2023. – № 1. – С. 9–17. – DOI: 10.53297/18293336-2023.1-9.

2. Durrant-Whyte H., Bailey T. Simultaneous localization and mapping(SLAM): Part I // IEEE Robotics and Automation Magazine. – 2006. – Vol. 13 (2). – P. 99–110. – DOI: 10.1109/MRA.2006.1638022.

3. Durrant-Whyte H., Bailey T. Simultaneous localization and mapping (SLAM): Part II // IEEE Robotics and Automation Magazine. – 2006. – Vol. 13 (3). – P. 108–117. – DOI: 10.1109/MRA.2006.1678144.

4. Жук Р.С., Залесский Б.А., Троцкий Ф.С. Визуальная навигация автономно летящего БПЛА с целью его возвращения в точку старта // Информатика. – 2020. – Т. 17, № 2. – С. 17–24. – DOI: 10.37661/1816-0301-2020-17-2-17-24.

5. Антюфеев В.И., Быков В.Н. Сравнительный анализ алгоритмов совмещения изображений в корреляционно-экстремальных системах навигации летательных аппаратов // Авиационно-космическая техника и технология. – 2008. – № 1 (48). – С. 70–74.

6. Троицкий В.И. Критерии информативности эталонных радиотепловых полей, используемых в КЭСН // Известия высших учебных заведений. Геодезия и аэрофотосъемка. – 2013. – № 3. – С. 61–64.

7. Троицкий В.И. Анализ влияния основных параметров и условий функционирования КЭСН летательных аппаратов по микроволновому излучению покровов земной поверхности на эффективность их использования // Научный вестник Московского государственного технического университета гражданской авиации. – 2018. – Т. 21, № 2. – С. 171–180. – DOI: 10.26467/2079-0619-2018-21-2-171-180.

8. Титаренко А.А., Козлов В.А., Белинский А.В. Результаты экспериментальных исследований точностных характеристик корреляционно-экстремальной системы навигации по малоинформативным поверхностным геофизическим полям // Шарыгинские чтения: Всероссийская научная конференция ведущих научных школ в области радиолокации, радионавигации и радиоэлектронных систем передачи информации. – 2019. – № 1 (1). – С. 117–122.

9. Кулешов С.В., Зайцева А.А. Варианты реализации системы технического зрения для автовзлета и автопосадки БАС // Известия ЮФУ. Технические науки. – 2018. – № 1 (195). – С. 284–293. – DOI: 10.23683/2311-3103-2018-1-284-293.

10. Коновалов К.Д., Кулешов С.В. Общая структура системы визуальной навигации БПЛА по видеоданным // Экстремальная робототехника. – 2024. – № 1 (34). – С. 456–460.

11. Донцов А.А., Тонконогов О.Ю., Нагалин Д.А. Оптимизация расположения опорных точек для повышения точности определения координат летательного аппарата // Информатика: проблемы, методология, технологии: сборник материалов XVIII Международной научно-методической конференции. – Воронеж, 2018. – Т. 2. – С. 134–139.

12. Kaehler A., Bradski G. Learning OpenCV 3. – USA: O'Reilly Media, 2016. – 1024 p.

13. Dijkstra E.W. A note on two problems in connexion with graphs // Numerische Mathematik. – 1959. – Vol. 1 (1). – P. 269–271. – DOI: 10.1007/BF01386390.

14. Bellman R. On a routing problem // Quarterly of Applied Mathematics. – 1958. – Vol. 16 (1). – P. 87–90. – DOI: 10.1090/QAM/102435.

15. Близнякова Е.А., Куликов А.А., Куликов А.В. Сравнительный анализ методов поиска кратчайшего пути в графе // Архитектура, строительство, транспорт. – 2022. – № 1 (99). – С. 80–87. – DOI: 10.31660/2782-232X-2022-1-80-87.

16. Goldberg A.V., Radzik T. A heuristic improvement of the Bellman-Ford algorithm // Applied Mathematics Letters. – 1993. – Vol. 6 (3). – P. 3–6. – DOI: 10.1016/0893-9659(93)90022-F.

17. Harabor D., Grastien A. Online graph pruning for pathfinding on grid maps // Proceedings of the AAAI Conference on Artificial Intelligence. – 2011. – Vol. 25 (1). – P. 1114–1119. – DOI. 10.1609/aaai.v25i1.7994.

18. Hart P.E., Nilsson N.J., Raphael B. A formal basis for the heuristic determination of minimum cost paths // IEEE Transactions on Systems Science and Cybernetics. – 1968. – Vol. 4 (2). – P. 100—107. – DOI: 10.1109/TSSC.1968.300136.

19. Lawrence M.F., Tarjan R.E. Fibonacci heaps and their uses in improved network optimization algorithms // Journal of the Association for Computing Machinery. – 1987. – Vol. 34 (3). – P. 596–615. – DOI: 10.1145/28869.28874.