ЭВОЛЮЦИОННЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ГРУППЫ КВАДРОКОПТЕРОВ ДЛЯ ПОВЫШЕНИЯ
КАЧЕСТВА МОНИТОРИНГА ОБЛАСТИ 

Дивеев Асхат Ибрагимович, доктор технических наук, начальник сектора отдела безопасности и нелинейного анализа, Федеральный исследовательский центр «Информатика и Управление» Российской Академии Наук, (Вычислительный центр им. А. А. Дородницына РАН) (119333, Россия, г. Москва, ул. Вавилова, 40); профессор департамента механики и мехатроники Инженерной академии Российского университета дружбы народов, aidiveev@mail.ru
Конырбаев Нурбек Беркинбайулы, стажер, департамент механики и мехатроники, Инженерная академия Российского университета дружбы народов (115419, Россия, г. Москва, ул. Миклухо-Маклая, 6), n.konyrbaev@mail.ru

519.618

DOI

10.21685/2307-4205-2017-4-9

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

Ключевые слова

трехмерная задача коммивояжера, группа квадрокоптеров, вариационный генетический алгоритм, NP-трудная задача

 Скачать статью в формате PDF

1. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М. : Мир, 1982.–168 с.
2. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. – М : Мир, 1978. – 189с.
3. Кормен, Т. Алгоритмы. Построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. – 2-е изд. –М. : Вильямс, 2009. – 257 с.
4. Пападимитриу, Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х. Пападимитриу,К. Стайглиц. – М. : Мир, 1985. – 216 с.
5. Дивеев, А. И. Вариационный генетический алгоритм для решения задачи оптимального управления /А. И. Дивеев, Е. Ю. Шмалько // Современные проблемы науки и образования. – 2014. – № 1. –URL: http://www.science-education.ru/115-11474
6. Diveev, A. I. Small Variations of Basic Solution Method for Non-numerical Optimization / A. I. Diveev // Proceedings of 16th IFAC Workshop on Control Applications of Optimization, CAO’ 2015 (October 6th–9th). –Garmisch-Partenkirchen, 2015. – P. 28–33.
7. Дивеев, А. И. Вариационный генетический алгоритм для поиска оптимального управления космическим аппаратом / А. И. Дивеев, Е. Ю. Шмалько // Труды одиннадцатого международного симпозиума Интеллектуальные системы INTELS’2014 (Москва, 30 июня – 4 июля) ; под ред. К. А. Пупкова. – М., 2014. –С. 83–88.
8. Diveev, A. I. Synthesis of Control for Group of Quadrotors in Task of Area Monitoring / A. I. Diveev,S. I. Ibadulla, N. B. Konyrbaev, E. Yu. Shmalko // Proceedings The 11th IEEE International Conference on Application of Information and Communication Technologies (AICT 2017) (20–22 September). – Moscow, 2017. – Vol. 1. – P. 365–370.