ОБ ОДНОМ ПОДХОДЕ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА ДЛЯ ПЛАНИРОВАНИЯ АВТОНОМНЫМ БЕСПИЛОТНЫМ ЛЕТАТЕЛЬНЫМ АППАРАТОМ МАРШРУТОВ ОБЛЕТА ЦЕЛЕЙ

Цель. Разработать принцип построения инструментальных средств и процедур оптимальной маршрутизации облета целей автономным беспилотным летательным аппаратом,  обладающих приемлемой для реализации на бортовой ЭВМ сложностью.

Методы. Сформулированы правила оптимизации карты местности с расположенными на ней целями, создание матрицы штрафов, позволяющей учитывать в процессе планирования  возмущающие факторы нестабильной воздушной среды, и построение опорного дерева поиска минимального по принятой стоимости маршрута облета целей.

Результаты. Предложен принцип, позволяющий разработать эффективные процедуры  планирования минимальных по принятой стоимости маршрутов облета целей в нестабильной  воздушной среде. В основу планирования поведения закладывается  оптимизация формального описания заданной карты местности, приводящая к  существенному сокращению количества сравниваемых между собой альтернатив в процессе поиска минимального маршрута облета целей. Это, в свою очередь, обеспечивает возможность реализации процедур планирования на бортовой вычислительной системе автономного беспилотного летательного аппарата. Доказано  утверждение, позволяющее обосновать наличие минимального по принятой стоимости  маршрута облета целей в формальном описании карты местности, полученном в результате преобразования исходного ее представления на основе разработанных правил оптимизации. 

Вывод. Рассмотренный подход позволяет эффективным образом решать различного вида  задачи, сводящиеся к задаче о коммивояжере, в том числе планировать и минимальный  маршрут облета целей автономным беспилотным летательным аппаратом в нестабильной  воздушной среде в условиях неопределенности.

1. Абросимов В. К. Коллективы интеллектуальных летательных аппаратов. М., Наука, 2017, 304 с.

2. Рондан У. Б., Тимоти У. М. Малые беспилотные летательные аппараты. Теория и практика. М., Техносфера, 2016, 312 с.

3. Семенов С.С., Педан А.В., Воловиков В.С., Климов И.С. Анализ трудоемкости различных алгоритмических подходов для решения задачи коммивояжера//Системы управления, связи и безопасности. 2017. №1. С. 116 – 131.

4. La Valle S.M. Planning Algorithms. Cambridge, Cambridge University Press, 2006. 844 p.

5. Костик Ю.Л. Задача коммивояжера: приближенные алгоритмы по методу ветвей и границ с гарантированной точностью // Прикладная дискретная математика. 2019. № 45. С. 104 – 112.

6. Мамонов Н.В. Исследование влияния ассиметрии на сложность решения задачи коммивояжера методом ветвей и границ // Современные информационные технологии и ИТ образование. 2019. Т.15. №1. С. 99 – 106.

7. Колесников А.В., Кириков И.А., Листопад С.В., Румовская С.Б., Доманицкий А.А. Решение сложных задач коммивояжера методами функциональных гибридных интеллектуальных систем / Под ред. А.В. Колесникова. М.: ИПИ РАН, 2011. 295 с.

8. Герпов А.В., Шаталов Д.А., Митасов Р.А. Практическая польза использования генетических алгоритмов на примере решения задачи коммивояжера//Труды Ростовского университета путей сообщения, 1917, № 4, с. 93 – 97.

9. Курейчик В.В., Курейчик В.М. Генетический алгоритм определения пути коммивояжера // Известия РАН. Теория и системы управления, 2006, № 1, с. 94-100.

10. Dorigo M., Stützle T. Ant colony optimization: overview and recent advances. Handbook of metaheuristics. Berlin: Springer - Cham, 2019, pp. 311 – 351.

11. Кубил В.Н., Мохов В.А. Многоколониальный муравьиный алгоритм с модификациями для решения многокритериальных задач маршрутизации транспорта//Известия высших учебных заведений. Электромеханика. Т. 61, № 6. 2018. С. 94 – 109.

12. Лиго Тань, Фомичёв А.В. Планирование пространственного маршрута беспилотных летательных аппаратов с использованием методов частичного целочисленного линейного программирования // Вестник МГТУ им Н.Э. Баумана. Сер. Приборостроение, 2016, №2, с. 53 – 66.

13. Лебедев Г.Н., Ефимов А.В. Применение динамического программирования для маршрутизации облета мобильных объектов в контролируемом регионе// Вестник Самарского государственного аэрокосмического университета, 2011, №6, с. 234 – 241.

14. Хачай М.Ю., Огородников Ю.Ю. Эффективная аппроксимация задачи об оптимальной маршрутизации в метрических пространствах фиксированной размерности // Доклады Российской академии наук. Математика, информатика, процессы управления. 2020, Т. 493, №1, с. 74 – 80.

15. Kaluder H., Brezak M., Petrovic I. A visibility graph based method for path planning in dynamic environments. MIPRO, 2011, Proceedings of the 34 th International Convention, Opatija, Croatia, 2011, pp. 717 –721.

16. Kelly A. Mobile Robotics: Mathematics, Models, and Methods. Cambridge, Cambridge University Press, 2013. 808 p.

17. Мелехин В.Б., Хачумов М.В. Планирование автономным беспилотным летательным аппаратом эффективных маршрутов облета целей // Авиакосмическое приборостроение, 2020, № 4, с. 3 – 14.

18. Черный М. А., Кораблин В. И. Воздушная навигация. М., Транспорт, 1991, 432 с.

19. Мелехин В.Б., Хачумов В.М. Управление эффективной реализацией технологических процессов механической обработки деталей в машиностроении // Проблемы управления, 2020, № 1, с. 71 – 82.

20. Курейчик В.М., Лагунова Ю.А. Задачи о коммивояжере. Обзор и методы решения. Palmarium Academic Publishing, 2019. 60 c.