Введение к работе
Актуальность темы исследования. В настоящее время автономные роботы
находят все более широкое применение в различных сферах человеческой
деятельности. Групповое применение малоразмерных автономных роботов
позволяет значительно расширить их функциональные возможности. Научными
исследованиями в области группового управления роботами в нашей стране
занимались и продолжают заниматься такие известные ученые, как
Варшавский В.И., Поспелов Д.А., Юревич Е.И., Каляев И.А., Капустян С.Г.,
Гайдук А.Р., Павловский В.Е., Городецкий В.И., Кирильченко А.А., Истомин В.В.,
Карпов В.Э., Воробьев В.В., Меркулов В.И., Амелин К.С., Илюхин Ю.В.
Пшихопов В.Х., Веселов Е.Г. и многие другие. За рубежом выдающиеся достижения в этой области принадлежат К. Рейнольдсу (C.W. Reynolds), М. Дориго (M. Dorigo), М.А. Льюису (M.A. Lewis), Ф. Хиггинсу (F. Higgins) и другим.
Наиболее распространенным на текущий момент типом мобильных автономных роботов, применяемых в группах, являются беспилотные летательные аппараты (БЛА). Одним из наиболее перспективных для группового применения видов малоразмерных БЛА являются квадрокоптеры, которые в настоящий момент находят все более широкое применение для решения различных практически важных задач, таких как формирование мобильных телекоммуникационных сетей и радиолокационных комплексов быстрого развертывания, формирование ложных целей, разведка и мониторинг территорий и др. Эти задачи требуют, чтобы аппараты группы могли быть размещены в пространстве строго определенным образом и имели возможность быстрого перестроения в соответствии с особенностями выполняемой задачи.
Например, при создании мобильных радиолокационных комплексов
квадрокоптеры группы, на каждом из которых расположен один из элементов
антенной решетки, должны располагаться в пространстве строго определенным
образом. При формировании ложных целей необходимо, чтобы группа
квадрокоптеров располагалась в пространстве таким образом, чтобы имитировать
форму цели, и имела возможность быстрого перестроения для уклонения от
средств противодействия. При создании телекоммуникационных сетей быстрого
развертывания необходимо, чтобы пространственное положение квадрокоптеров в
группе в каждый момент времени соответствовало текущей топологии сети. При
решении задач мониторинга территорий квадрокоптеры группы должны
осуществлять перестроения таким образом, чтобы обеспечивать максимальный охват территории при минимальном перекрытии кадров, либо таким образом, чтобы обеспечить наиболее качественную съемку интересующего объекта, в том числе, с различных ракурсов. Во всех перечисленных выше задачах строевые перестроения квадрокоптеров группы необходимо осуществлять как можно быстрее.
Требуемое расположение автономных мобильных роботов в пространстве называется строем или формацией (англ. formation). Задача формирования строя в группе мобильных роботов называется строевой задачей (англ. formation task).
В зависимости от того, каким образом задан целевой строй, строевая задача может иметь различную постановку. В простейшем случае целевой строй может быть задан в виде координат целевых положений квадрокоптеров в пространстве. В этом случае решение строевой задачи сводится к решению задачи о назначениях,
т.е. распределению квадрокоптеров группы по целевым положениям в пространстве. Решение данной задачи не представляет существенных трудностей.
В более сложном варианте целевой строй может быть задан в виде матрицы расстояний между квадрокоптерами. При этом заданному таким образом целевому строю может в принципе соответствовать бесконечное множество наборов точек пространства. При такой постановке строевая задача сводится к задаче нахождения точек пространства, удовлетворяющих заданной матрице расстояний между квадрокоптерами группы в целевом строю, и последующему назначению (распределению) квадрокоптеров по этим точкам таким образом, чтобы минимизировать общее время перестроения (формирования нового строя). Именно решение строевой задачи в данной постановке рассматривается в настоящей диссертации.
Проведенный анализ показывает, что в настоящее время отсутствуют методы решения задачи формирования целевого строя произвольной конфигурации в группах БЛА, заданного в виде матрицы расстояний. Известные подходы к решению строевых задач в группах БЛА ориентированы в основном на решение частных случаев данной задачи: формирование строя определенной конфигурации, поддержание сформированного строя, формирование строя при заданных координатах целевых положений и т.п.
Еще одной особенностью строевой задачи в группе автономных
квадрокоптеров является то, что она должна решаться с помощью бортовых вычислительных устройств квадрокоптеров группы, которые имеют ограниченную вычислительную мощность. Данное обстоятельство не позволяет использовать для решения строевой задачи в группе квадрокоптеров традиционные методы теории управления вследствие их высокой вычислительной сложности. Поэтому разрабатываемые методы решения строевой задачи в группе квадрокоптеров должны обеспечивать возможность их распределенной (децентрализованной) реализации с помощью множества вычислительно-управляющих устройств всех квадрокоптеров группы.
Таким образом, актуальной является задача разработки методов и алгоритмов формирования строя произвольной конфигурации в группах автономных квадрокоптеров, задаваемого матрицей расстояний между ними и реализуемых с помощью распределенной вычислительной сети, состоящей из вычислительных устройств отдельных квадрокоптеров группы.
Объектом исследования является группа автономных БЛА квадрокоптерного типа, участвующих в формировании пространственного строя.
Предметом исследования являются методы формирования строя
произвольной конфигурации, задаваемого матрицей расстояний, в группах автономных квадрокоптеров.
Целью диссертационного исследования является минимизация времени
формирования целевого строя произвольной конфигурации в группе
квадрокоптеров.
Научная задача, решаемая в диссертации, заключается в разработке методов
формирования целевого строя произвольной конфигурации в группе
квадрокоптеров, задаваемого матрицей расстояний, реализуемых на основе
распределенного множества вычислительных устройств отдельных квадрокоптеров группы и минимизирующих время формирования строя.
Для решения поставленной научной задачи необходимо решить следующие частные задачи:
дать формальную постановку строевой задачи в группе квадрокоптеров и провести анализ известных подходов к ее решению;
провести анализ возможных стратегий группового управления квадрокоптерами и выбрать стратегию, отвечающую условиям их автономного применения;
разработать методы формирования строя произвольной конфигурации, задаваемого матрицей расстояний, в небольших группах квадрокоптеров, в которых информационный обмен может осуществляться по принципу «каждый с каждым»;
разработать алгоритмы решения строевой задачи в небольшой группе квадрокоптеров, реализуемые с помощью распределенного множества их бортовых вычислительных устройств;
разработать методы формирования строя в больших группах квадрокоптеров, в которых существуют ограничения на информационный обмен между отдельными квадрокоптерами группы;
разработать алгоритм формирования строя в больших группах квадрокоптеров, реализуемый с помощью их бортовых вычислительных устройств;
разработать программную модель для проведения компьютерного моделирования методов решения строевых задач в группах квадрокоптеров;
провести исследования работоспособности и эффективности разработанных методов формирования строя в группах квадрокоптеров на программной модели;
провести серию натурных экспериментальных исследований разработанных алгоритмов формирования строя с помощью группы реальных квадрокоптеров.
Методологическую основу работы составили методы исследования операций, методы вычислительной математики, методы линейной алгебры, методы аналитической геометрии, методы теории управления, методы теории группового управления роботами, методы компьютерного моделирования. В работе использованы элементы теории графов.
Достоверность полученных в диссертационной работе результатов
подтверждается полнотой и корректностью исходных посылок,
непротиворечивостью математических выкладок. Теоретические исследования
подтверждены вычислительными экспериментами с использованием
разработанного программного обеспечения, а также натурными экспериментами с группой квадрокоптеров. Полученные результаты согласуются с опубликованными результатами научных исследований и экспериментов других авторов.
Научная новизна исследования заключается в том, что:
впервые сформулирована задача формирования в группе квадрокоптеров строя произвольной конфигурации, задаваемого матрицей расстояний;
разработаны методы окружностей и сфер для решения задач формирования в группе квадрокоптеров строя произвольной конфигурации в плоскости и пространстве соответственно, отличающиеся совмещением процедур определения координат целевых положений и назначений квадрокоптеров по ним;
разработан метод совмещения центров для решения строевой задачи в группе квадрокоптеров, отличающийся процедурой поиска координат целевых положений, при которых обеспечивается минимум максимального расстояния между текущими положениями квадрокоптеров группы и целевыми положениями формируемого строя, в том числе с учетом ориентации строя в пространстве;
разработан метод паттернов для формирования строя в большой группе квадрокоптеров, отличающийся двухэтапным формированием целевого строя: на первом этапе происходит формирование паттернов; на втором этапе сформированные паттерны перемещаются друг относительно друга таким образом, чтобы сформировать целевой строй;
разработаны алгоритмы децентрализованной реализации предложенных методов формирования строя на базе распределенной сети вычислительных устройств отдельных квадрокоптеров группы, отличающиеся применением стратегий коллективного и роевого управления.
Положения, выдвигаемые на защиту:
методы окружностей и сфер минимизируют максимальную длину перемещения квадрокоптеров группы в целевые положения при формировании целевого строя, задаваемого матрицей расстояний, в плоскости и в пространстве;
метод паттернов обеспечивает формирование периодического строя произвольной конфигурации в больших группах квадрокоптеров в условиях ограничений на информационное взаимодействие между ними;
- алгоритмическая реализация предложенных методов формирования строя
произвольной конфигурации возможна на базе распределенной сети бортовых
вычислительных устройств отдельных квадрокоптеров группы.
Научные результаты, выдвигаемые на защиту:
метод окружностей для формирования плоского строя произвольной конфигурации в группе квадрокоптеров;
метод сфер для формирования пространственного строя произвольной конфигурации в группе квадрокоптеров;
метод совмещения центров, минимизирующий максимальное расстояние между текущими положениями квадрокоптеров группы и целевыми положениями формируемого строя, в том числе с учетом ориентации строя в пространстве;
метод паттернов для решения строевых задач в больших группах квадрокоптеров;
алгоритмы управления квадрокоптерами, входящими в группу, реализующие разработанные методы формирования строя произвольной конфигурации.
Практическая ценность работы заключается в том, что полученные научные
результаты могут быть использованы при создании систем управления группами
БЛА, в том числе квадрокоптеров, участвующих в решении таких задач, как
разведка местности, формирование ложных целей, формирование мобильных
телекоммуникационных сетей, формирование пространственных антенных
решеток, видеомониторинг, формирование распределенных мобильных сетей датчиков и др.
При этом разработанные в диссертации алгоритмы формирования строя обеспечивают возможность их децентрализованной реализации с помощью
распределенного множества бортовых вычислительных устройств отдельных квадрокоптеров, входящих в группу.
Разработанные методы и алгоритмы решения строевой задачи могут быть также использованы при разработке систем управления группами мобильных роботов различного базирования (наземного, водного, космического).
Научная значимость работы заключается в развитии теоретических основ группового управления автономными роботами при решении задач формирования строев произвольных конфигураций с помощью распределенного множества бортовых вычислительных устройств.
Апробация работы.
Основные результаты работы докладывались и обсуждались на 29 научно-технических конференциях и семинарах, в том числе 9 международных (из них 3 зарубежных) и 9 всероссийских.
Наиболее важные из них: «18th International Conference on Speech and Computer
(SPECOM-2016)» (Будапешт, Венгрия, 24-26 августа 2016 г), «The 3rd International
Conference on Robot Intelligence Technology and Applications 2014 (RITA-2014)»
(Китай, г. Пекин, 6-8 ноября 2014 г.); «2nd International Conference on Systems and
Informatics (ICSAI 2014)» (Китай, г. Шанхай, 15-17 ноября 2014 г.); The 5th IEEE
International Conference on Cybernetics and Intelligent Systems and The 5th IEEE
International Conference on Robotics, Automation and Mechatronics, September 17-19,
2011, Qingdao, China; Международная научно-техническая конференция
«Экстремальная робототехника» (Санкт-Петербург, 2010, 2011, 2012 гг.); XXI Международная научно-техническая конференция: «Экстремальная робототехника» (Москва), 18-20 мая 2010; Международный научно-технический семинар: «Робототехника. Взгляд в будущее» (Санкт-Петербург, 2010); XII Всероссийское совещание по проблемам управления ВСПУ-2014. (Москва, 16-19 июня 2014 г.); 4-я, 5-я, 6-я, 8-я Всероссийские мультиконференции по проблемам управления (МКПУ) в 2011– 2015 гг.; Пятая Всероссийская научно-практическая конференция «Перспективные системы и задачи управления» 2010; Вторая молодежная школа-семинар «Управление и обработка информации в технических системах» 2010; «Конгресс по интеллектуальным системам и информационным технологиям «AIS-IT’10» 2010; Научно-технический семинар «Управление в распределенных сетецентрических и мультиагентных системах». Санкт-Петербург, 2010; V, VI, VII, VIII и IX Ежегодные научные конференции студентов и аспирантов базовых кафедр Южного научного центра РАН в 2009-2013 гг.; Молодежная школа-семинар «Адаптивные и интеллектуальные роботы» АИР-2009. Представленные доклады неоднократно были отмечены оргкомитетами конференций и занимали призовые места.
Реализация и внедрение результатов работы. Теоретические и
практические результаты, полученные в рамках работы, использованы при выполнении НИР:
- НИР «Разработка и исследование методов управления роевым поведением массово-применяемых микророботов на принципах самоорганизации и роевого интеллекта» (№ госрегистрации 01201255495) в НИИ Многопроцессорных вычислительных систем ЮФУ;
НИР «Разработка и исследование методов и средств повышения безопасности и эффективности функционирования распределенных информационно-управляющих систем сложных технических объектов» (№ госрегистрации 01200852907) в НИИ Многопроцессорных вычислительных систем ЮФУ;
НИР «Разработка научно-технических основ построения самоорганизующихся распределенных систем управления коллективным поведением роботов на базе биомиметических принципов» (№ госрегистрации 01200404537) в НИИ Многопроцессорных вычислительных систем ЮФУ;
НИР «Создание теоретических основ построения алгоритмов информационно-управляющего интерфейса обмена данными и знаниями, не контролируемого человеком, в робототехнических комплексах авиационного базирования» (№ госрегистрации АААА-А16-116040700085-6) в АО «Концерн «Вега»;
НИР по проекту №0256-2015-0079 «Разработка методологических основ самоорганизующегося управления группами мобильных роботов» (№ госрегистрации АААА-А15-115102010121-1) в рамках Программы фундаментальных исследований Президиума РАН № I.31 П «Фундаментальные основы технологий двойного назначения в интересах национальной безопасности. Фундаментальные исследования процессов горения и взрыва. Актуальные проблемы робототехники» (тема 00-16-14) в Южном научном центре Российской академии наук.
Результаты также использовались в ЮФУ при выполнении проектов при финансовой поддержке РФФИ:
проект № 16-29-04194 офи_м «Разработка методов и алгоритмов децентрализованного управления сетецентрическими группировками гетерогенных роботов при выполнения сложных заданий» (№ госрегистрации АААА-А16-116042110007-5);
проект №16-58-00226-Бел_а «Разработка алгоритмов адаптивного управления робототехническими механизмами параллельной структуры на основе принципов самоорганизации многоагентных систем» (№ госрегистрации АААА-А16-116060810081-2);
проект №16-08-00875-а «Синерго-кибернетический подход к синтезу роевых стратегий группового управления мобильными роботами» (№ госрегистрации АААА-А16-116011300276-2);
- проект №14-08-01176-а «Исследования и разработка методов группового
управления беспилотными летательными аппаратами при решении строевых задач с
использованием принципов роевого интеллекта» (№ госрегистрации 01201452500);
проект №13-08-00794-а «Самоорганизующиеся стратегии группового управления робототехническими системами» (№ госрегистрации 01201359118);
проект №12-08-90050-Бел_а «Исследование и разработка теоретических основ сложных динамических систем в приложениях к самоорганизующимся распределнным системам управления группами робототехнических устройств» (№ госрегистрации 01201264896);
проект №11-08-01196-а «Разработка научных основ организации и функционирования систем группового управления беспилотными летательными аппаратами при решении задач мониторинга» (№ госрегистрации 01201164290);
проект №10-07-00235-а «Разработка научно-технических основ построения интеллектуальных систем управления роботами нового поколения» (№ госрегистрации 0120116489).
Полученные в ходе диссертационного исследования результаты
использовались при выполнении НИР «Разработка системы видеомониторинга на
базе группы беспилотных квадрокоптеров» по договору №4487ГУ2/2014 по
программе «УМНИК-2013 при финансовой поддержке «Фонда содействия развитию малых форм предприятий в научно-технической сфере».
Соответствующие акты об использовании результатов полученных научных результатов приведены в диссертации.
Публикации. По теме диссертации опубликовано 36 печатных работ, из них
13 статей, в том числе: 4 – в ведущих научных изданиях, рекомендованных ВАК для
публикации результатов работ по диссертациям на соискание ученой степени
кандидата технических наук, 4 – в иностранных научных изданиях, включенных в
систему цитирования Scopus, 5 – в других изданиях, входящих в систему
цитирования РИНЦ. А также 22 – в сборниках трудов и материалов научных
конференций. Получено 1 свидетельство о государственной регистрации
программы для ЭВМ.
Личный вклад автора. Все научные результаты диссертации, выдвигаемые для защиты, получены автором лично.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 207 наименований, содержания и 2 приложений. Основная часть работы изложена на 216 страницах и включает в себя 77 рисунков и 13 таблиц.