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


https://doi.org/10.21822/2073-6185-2021-48-1-108-118

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


Аннотация

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

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

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

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


Об авторах

В. Б. Мелехин
Дагестанский государственный технический университет
Россия


367026, г. Махачкала, пр. Имама Шамиля, 70, Россия



М. В. Хачумов
Федеральный исследовательский центр «Информатика и управление» Российской академии наук; Российский университет дружбы народов (РУДН)
Россия


119333, Москва, ул. Вавилова, д.44, кор.2, Россия,

117198, г. Москва, ул. Миклухо-Маклая, 6, Россия



Список литературы

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.


Дополнительные файлы

Для цитирования: Мелехин В.Б., Хачумов М.В. ОБ ОДНОМ ПОДХОДЕ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА ДЛЯ ПЛАНИРОВАНИЯ АВТОНОМНЫМ БЕСПИЛОТНЫМ ЛЕТАТЕЛЬНЫМ АППАРАТОМ МАРШРУТОВ ОБЛЕТА ЦЕЛЕЙ. Вестник Дагестанского государственного технического университета. Технические науки. 2021;48(1):108-118. https://doi.org/10.21822/2073-6185-2021-48-1-108-118

For citation: Melekhin V.B., Khachumov M.V. ON ONE APPROACH TO SOLVING THE TRAVELING SALESMAN PROBLEM FOR AUTONOMOUS UNMANNED AERIAL VEHICLE PLANNING OF TARGET FLIGHT PATHS. Herald of Dagestan State Technical University. Technical Sciences. 2021;48(1):108-118. (In Russ.) https://doi.org/10.21822/2073-6185-2021-48-1-108-118

Просмотров: 27

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2073-6185 (Print)
ISSN 2542-095X (Online)