Проанализировать существующие методы к организации группового взаимодействия дронов, а также смоделировать поведение группы поддерживающей заданный строй

Оглавление
ВВЕДЕНИЕ	4
ГЛАВА 1.	6
1.1	Применение БПЛА	6
1.2	Сравнение квадрокоптера с другими беспилотными летательными аппаратами	6
1.3	Групповая робототехника	7
1.4	Стратегии управления	8
1.5	Принципы организации систем группового управления роботами	9
1.5.1	Централизованные системы	9
1.5.2	Децентрализованные системы. Коллективное управление	11
1.5.3	Децентрализованные системы. Стайное управление	13
1.5.4	Комбинированные системы. Иерархическое централизованное управление.	15
1.5.5	Комбинированные системы. Иерархическое распределённое управление.	16
1.6	Сравнение стратегий	18
1.7	Результаты сравнения	19
ГЛАВА 2	20
2.1	Задача формирования строя в группах квадрокоптеров	20
2.2	Формальная постановка задачи формирования строя в группе квадрокоптеров	22
2.3	Известные подходу к решению строевых задач	24
2.3.1	Метод теории оптимального управления для решения строевой задачи	25
2.3.2	Метод потенциальных полей	25
2.3.3	Бионический подход к решению строевой задачи	27
2.3.4	Метод «ведущий-ведомый» для решения строевой задачи	29
2.3.5	Метод «Виртуальных структур» для решения строевой задачи	30
2.3.6	Основа теории игр для решения строевой задачи	32
ГЛАВА 3	33
3.1	Декомпозиция строевой задачи на подзадачи	33
3.2	Метод окружностей для решения «плоских» строевых задач в группе квадрокоптеров	36
3.2.1	Принцип решения строевой задачи методом окружностей	37
3.3	Метод совмещения центров для решения строевой задачи	46
СПИСОКЛИТЕРАТУРЫ	53



ВВЕДЕНИЕ
      Роботы уже давно вошли в привычную жизнь человека. Существует большое количество типов роботов, которых разделяют в зависимости от функционального назначения. Роботы находят своё применение в медицине, в промышленности, в быту. Применяясь пожарными, спасателями, полицейскими они обеспечивают безопасность гражданского населения. Военные также активно применяют их в разведке, в операциях по разминированию. Роботы способны нести на себе атакующие вооружение, создавать ложные цели, приводить технику противника в неработоспособное состояние и многое другое. Квадрокоптер это летательный аппарат с четырьмя винтами, иногда называемый дроном, впервые был построен в 1922 году, но не получил популярности из-за сложно устроенной трансмиссии. В наше время квадрокоптер получил новый толчок своего развитие как летающий робот или беспилотный летательный аппарат. К преимуществам квадрокоптеров можно отнести: простоту конструкции, способность зависать в воздухе на одном месте, вертикальные взлет и посадку, большую манёвренность. Но существенным недостаток на данный момент является малое время нахождения в полёте зависящим от времени работы аккумулятора. Именно поэтому их сейчас в основном используют для видео- и фотосъемок, либо просто для своего развлечения. Потенциально квадрокоптер может быть применён для контроля возникновения лесного пожара и выполнения поисково-спасательных операций. С их помощью возможно организовывать удобную доставку почты и груза. Квадрокоптер может без риска для человека обследовать здания, находящиеся в аварийном состоянии, производить разведку местности, обеспечивать сопровождение выбранной цели.
      Коллективное взаимодействие квадрокоптеров в группе могло бы значительно увеличить их эффективность и даже предоставить такойфункционал, которыйтруднодостижим при выполнении задачи одним квадрокоптером. Так, например, уже сейчас группы квадрокоптеров применяются при проведении световых шоу, рекламных акций и мониторинге местности. Ведутся работы по применению групп квадрокоптеров для формирования мобильных фазированных антенных решеток, мобильных телекоммуникационных сетей быстрого развертывания, формированию ложных целей для средств радиоэлектронной разведки противника и др.
      Исследования методов формирования и поддержания строя квадрокоптеров является основой для успешного выполнения поставленной задачи группой квадрокоптеров. В данной работе поставлена цель проанализировать существующие методы к организации группового взаимодействия дронов, а также смоделировать поведение группы поддерживающей заданный строй.


ГЛАВА 1.
 Применение БПЛА
С момента своего создания БПЛА нашли своё применение в военном деле. Они позволяют выполнять миссии без угрозы жизни для личного состава. БПЛА осуществляют разведку местности, собирая видео- и фотоматериалы, осуществляют наводку ракет, выступают в качестве ретрансляторов. Крупно габаритные БПЛА сами способны нести вооружение и наносить удары по противнику. Последние десятилетия растет спрос на БПЛА и в гражданском секторе. В Amazon существует проект по доставке грузов до клиентов при помощи мультикоптеров[2]. Пиццерия Dodoо пробовала доставку пиццы[3] заказчику за 30 минут. Компания Интертелеком использовала дронов для инспектирования базовых станций своих сетей[4]. Беспилотный летательный аппарат SenseFly eBee успешно используют для задач геодезии[5]. Но на данный момент применение БПЛА и квадрокоптеров в частности ограничивается в основном контрольными функциями, съемкой видео, либо их используют просто для развлечения.
      Сравнение квадрокоптера с другими беспилотными летательными аппаратами
      Все беспилотные летательные аппараты можно разнести на две категории: летательные аппараты легче воздуха и летательные аппараты тяжелее воздуха. Основная классификация воздушных судов, в зависимости от их принципов полёта и режима движения представлена на рис. 1.2. В работе[1] автор сравнивает различные типы воздушных аппаратов по таким параметрам, как: стоимость одного аппарата, отношения полезной нагрузки к объему, манёвренность, полёт с зависанием на одном месте, низко скоростной полёт, уязвимость, вертикальный взлёт и посадка, продолжительность полёта, использование в внутри помещений и некоторые другие. Результаты сравнения БЛА различных принципов полёта приведены в таблице 1.1.
	Рисунок 1.2 – Классификация летательных аппаратов
      В таблице 1.2 приведены более подробно рассмотрены показавшие себя хорошо БЛА вертолётного и дирижабельного типа, а так же БЛА на основе машущего крыла.
      
      
      
Наименование параметра
Значение оценки параметра для различных типов ЛА 

Самолёт
Вертолёт
Машущее крыло
Автожир
Дирижабль
Стоимость производства 
2 
1 
2 
2 
3 
Стоимость эксплуатации 
2 
1 
1 
2 
3 
Полезная нагрузка/объем 
3 
2 
2 
2 
1 
Маневренность 
2 
3 
3 
2 
1 
Зависание в полете 
1 
3 
2 
1 
3 
Полет на малой скорости 
1 
3 
2 
2 
3 
Защищенность 
2 
2 
3 
2 
2 
Вертикальный взлет/посадка 
1 
3 
2 
1 
3 
Прочность 
2 
1 
2 
1 
3 
Миниатюрность 
2 
3 
3 
2 
1 
Использование в помещениях 
1 
3 
2 
1 
2 
Итого: 
19 
25 
24 
18 
25 
      Таблица 1.1 - Сравнение принципов полета (1 – плохо, 2 – удовлетворительно, 3 – хорошо)
      Приведенные в таблице 1.2 результаты сравнения принципов полета, применимых для малоразмерных летательных аппаратов, показывают универсальность квадрокоптеров – летательных аппаратов, относящихся к классу мультикоптеров.


Наименование параметра
Значение оценки параметра для малоразмерных БЛА

Один винт
Осевой винт
Соосные винты
Тандемные винты
Квадрокоптер
Дирижабль
Машущее крыло (птицеподобное)
Машущее крыло (насекомоподобное)
Стоимость производства 
2
2
2
2
1
4
3
3
Стоимость эксплуатации 
1
1
4
2
3
3
2
1
Полезная нагрузка/объем 
2
2
4
3
3
1
2
1
Маневренность 
4
3
2
2
3
1
3
3
Простота конструкции 
1
2
3
1
4
4
1
1
Аэродинамическая сложность 
1
1
1
1
4
3
1
1
Полет на низкой скорости 
4
3
4
3
4
4
2
2
Полет на высокой скорости 
2
4
1
2
3
1
3
3
Миниатюрность 
2
3
4
2
3
1
2
4
Живучесть 
1
3
3
1
1
3
2
3
Зависание в полете 
4
4
4
4
4
3
1
2
Итого 
24
28
32
23
33
28
22
24
Таблица 1.2 – Сравнение малоразмерных вертолетов, дирижаблей и аппаратов с машущим крылом (1 – плохо, 2 – удовлетворительно, 3– хорошо, 4 – очень хорошо).
 Групповая робототехника
    В последние годы роботы находят всё более широкое применение, причем не только в промышленности и машиностроении, но и во многих других сферах человеческой деятельности, отличающихся неопределённостью окружающей среды. Современные тенденции развития робототехники требуют от роботов все большей автономности и адаптируемости к изменениям внешних факторов.
      Одиночный робот ограничен в своих возможностях имеющимся набором бортовых функциональных и сенсорных устройств, имеющих ограниченный радиус видимости, а также небольшой запас бортовых энергоресурсов. Особенно остро эти проблемы стоят для малоразмерных роботов. 
      В то же время групповое применение роботов позволяет значительно расширить область применения малоразмерных роботов за счет того, что совместными усилиями роботы группы способны собрать больше информации об окружающей среде, распределение функциональных устройств между различными участниками группы позволяет решать широкий спектр задач, суммарный энергоресурс группы позволяет выполнить большее количество работ.
 Стратегии управления
      Задачу управления группой квадрокоптеров можно рассматривать как частный случай управления группой роботов. Все существующие стратегии управления группой роботов можно разделить на две диаметрально противоположные[6]. Первая стратегия подразумевает под собой, что все роботы в группе подчиняются одному центральному устройству управления, которое решает поставленную задачу. Вторая стратегия основывается на том, что поставленная задача решается либо на всех вычислительных устройствах группы, либо на некоторых из них. Первый подход называется – централизованным групповым управлением, второй – децентрализованным.
 Принципы организации систем группового управления роботами
Структурная организация системы группового управления роботами определяется выбранной стратегией. В зависимости от выбранной стратегии управления можно выделить три типа организации системы представленных на рис. 2.1.
Рисунок 2.1 – Стратегии управления

 Централизованные системы
При централизованном подходе движение всех членов в группе просчитывается центральным устройством управления. Схематично, описание элементов может быть представлено как на рис. 2.2. 
Рисунок 2.2 – Централизованнаясистема.
      Здесь СГУР – система группового управления роботом,A_i –вектор, содержащий некоторые действия, которые необходимо выполнить i-ому роботу,E_i – вектор, содержащий информацию о текущем состоянии окружающего его участка среды,S_i –вектор, содержащий информацию о i-ом роботе и векторE_i.

При таком подходе по каналам связи каждый робот постоянно передаёт информацию о себе и о окружающем его участке среды на СГУР. Обрабатывая всю полученную информацию СГУР формирует, для всей группы роботов, действия A, направленные на достижения оптимального решения общей задачи. Таким образом, от каждого робота в группе требует лишь выполнения заданий, поставленных СГУР.
	Преимущества:
 Простота организации и алгоритмизации;
 Наибольшая оптимальность среди всех подходов.
   Недостатки:
 Центральный узел должен обладать большими вычислительными мощностями;
 Сложность вычислений экспоненциально зависит от количества членов в группе;
 Длительное время принятия решения;
 Решение задачи группового управления роботами стараются получить заранее, без учёта возможных изменений среды;
 Низкая живучесть. При уничтожении главного элемента перестаёт функционировать вся система.
 Децентрализованные системы. Коллективное управление
Коллективное управление является одним из типов децентрализованной системы. В его основе лежит стратегия коллективного управления. Каждый элемент этой системы принимает решение по поводу своих дальнейших действий самостоятельно, но делается это только после анализа данных полученных по информационному каналу. Такая стратегия позволяет уменьшить время реагирования на произошедшие событие в окружающей среде, но уменьшает качество принимаемого при таком реагировании решения. Схематично представляется в виде, как на рис. 2.3.
Рисунок 2.3 – Децентрализованная система. Коллективное управление.
Здесь? СУ?_i– система управления, которая есть у каждого робота. С помощью информационного канала система?СУ?_i может сообщить свои действия A_iсистемам управления друг роботов. Которые в свою очередь координируют свои движения на основании полученной информации для достижения лучших результатов для всей группы.



      Преимущества:
 Высокий порог живучести;
 Оптимизация групповых действий за счёт обмена информацией по общему каналу связи;
 Высокая скорость принятия решения;
 Сложность решения для одного робота не высока.
      Недостатки:
 Высокая сложность алгоритмизации;
 Необходимо наличие высоконадёжного канала связи.
 Децентрализованные системы. Стайное управление
      К другому типу децентрализованной системы можно отнести структура распределенной системы реализующую стратегию со стайным управлением. Решение относительно дальнейших действий здесь тоже принимается каждым роботов в отдельности, с намерением добиться лучшего результата для всей группы. Главное отличие от коллективного управления заключается в отсутствии информационного канала. Всю информацию о действиях членов стаи робот получает, анализируя изменения окружающей его среды. Это убирает необходимость в установлении надёжного канала связи между отдельными членами стаи, но в свою очередь усложняет алгоритмизацию организации взаимодействия. Общий вид представлен на рис. 2.4.

 Рисунок 2.4 – Децентрализованная система. Стайное управление.
Здесь? СУ?_iне связана с системами управления других роботов и не осуществляет обмен информацией, вместо этого информацию о других роботах в группе она берёт на основании анализа изменения среды посредством специальных сенсоров.
	Преимущества:
 Наибольшая надёжность и живучесть;
 Хорошо противостоит прерываниям и сбоям;
 Сложность решения задачи для отдельного робота не высока;
 Высокая скорость принятия решения.
Недостатки:
 Высокая сложность алгоритмизации;
 Тяжело найти оптимальное решение, поскольку каждый робот принимает решение самостоятельно.
 Комбинированные системы. Иерархическое централизованное управление.
	Данный подход наиболее целесообразен, когда группа роботов неоднородна, т.е. имеются подгруппы роботов имеющих различную конструкцию и ориентированных на выполнение различных задач. Комбинированная или иерархическая организация включает в себя элементы как централизованной, так и децентрализованной стратегии управления.
      Иерархическая централизованная СГУР применима при четко организованном и детерминированном техническом процессе. Для снятия нагрузки, в группе роботов определяются подгруппы. Команды с центрального устройства управления передаются на главные узлы подуровней. При данном подходе уменьшается требование к вычислительной мощности центрально узла всей системы, но предъявляются повышенные требования к главным узлам подгрупп. Так же существует необходимость в поддержании стабильной связи с центральным элементом управления для координации коллективного выполнения задачи. Структура данной системы представлена на рис. 2.5.

Рисунок 2.5 – Иерархическая централизованная система.
	Преимущества:
 Более высокая надёжность и живучесть по сравнению с чисто централизованной структурой;
 Управление группами разнотипных роботов.
Недостатки:
 Более сложный информационный обмен между элементами подсистемы;
 Большие вычислительные требования к системам управления подгруппами системы.
 Комбинированные системы. Иерархическое распределённое управление.

      Когда постановка задачи подразумевает разбиение самими роботами на подзадачи целесообразно использовать иерархические распределенные СГУР, в которых внутри и между подгруппами осуществляется децентрализованный подход к управлению между роботами. Общая структура показана на рис 2.6.
Рисунок 2.6 Иерархическая распределённая система.
	Преимущества:
 Более высокая живучесть и надёжность по сравнению с централизованными системами;
 Меньшие вычислительные требования по сравнению с централизованным подходом;
 Скорость принятия решения больше, чем в централизованном подходе.
Недостатки:
 Сложный или совсем отсутствует информационный обмен между элементами системы;
 Сложность алгоритмизации.
 Сравнение стратегий
      Коллективное взаимодействие квадрокоптеров обладает следующими свойствами:
 Окружающая среда недетерминированная, изменяющаяся, а также возможно активно противодействующая; 
 Группа гомогенна, т.е. состоит из роботов одинаковой конструкции и строения, за исключением отличия в датчиках которые они имеют на борту; 
 Поддержание стабильного информационного канала с центром управления на всем протяжении выполнения миссии не гарантируется; 
 Вычислительные мощности бортового компьютера отдельного квадрокоптера не велики по причине малых размеров. 
      Проведём сравнительный анализ всех пяти стратегий поведения в группах квадрокоптеров. Будут рассмотрены следующие критерии стратегии:
     1.Независимость от канала связи с центральным устройством управления; 
     2. Оптимальность найденного решения при заранее известных условиях; 
     3. Способность адаптироваться к изменяющимся условиям; 
     4. Возможность выполнить миссию при выходе из строя части квадрокоптеров; 
     5. Способность организации группового взаимодействия при поддержании однородности группы; 
     6. Быстрота группового решения 
      Каждый критерий будет оценён по шкале от одного до трёх. Один означает, что стратегия управления по данному критерию плохо применима к организации группового взаимодействия дронов. В свою очередь три хорошо. Для более компактной записи таблицы используем следующие обозначения для названия стратегий:
     A. Централизованная; 
     B. Децентрализованная. Коллективная стратегия; 
     C. Децентрализованная. Стайная стратегия; 
     D. Иерархическая централизованная; 
     E. Иерархическая децентрализованная. 
	Результаты выполнения сравнения занесены вы таблицу 1.3.

Номер критерия 
A 
B
C 
D 
E 
1 
1 
3 
3 
2 
2 
2 
3 
2 
1 
3 
2 
3 
1 
3 
3 
1 
3 
4 
3 
3 
3 
2 
3 
5 
3 
3 
3 
2 
2 
6 
1 
3 
3 
2 
3 
Сумма 
12 
17 
16 
12 
15 
Таблица 1.3 – Результаты сравнения подходов
 Результаты сравнения
      По полученным результатам можно сделать вывод, что наиболее целесообразно, для организации взаимодействия в группе квадрокоптеров, использовать децентрализованный подход, реализующий стратегию коллективного управления. Данный подход отвечает большинству критериев необходимых для успешного выполнения задачи группой квадрокоптеров.
ГЛАВА 2
 Задача формирования строя в группах квадрокоптеров
   В большинстве случаев практического применения групп квадрокоптеров, квадрокоптерам группы необходимо формировать определенные пространственные положения. Требуемое (целевое) расположение квадрокоптеров в пространстве называют строем (англ. formation), а задачу формирования группой квадрокоптеров заданного строя называют строевой задачей (англ. formation task).
   В ряде практических применений, таких как формирования мобильных фазированных антенных решеток, ложных целей, мобильных телекоммуникационных сетей быстрого развертывания и т.п., строевая задача занимает приоритетное значение, от решения которой зависит возможность выполнения задания. В ряде других применений, таких как видеомониторинг, рекогносцировка, постановка радиопомех, эффективное решение строевой задачи позволяет несколько повысить эффективность решения группой поставленных задач за счет снижений площади перекрытия рабочих зон роботов группы. 
   Например, при решении задачи видеомониторинга группой роботов, роботам необходимо располагаться таким образом, чтобы избегать «мертвых зон» в формируемом видеоизображении, не попадающих в объектив ни одной из видеокамер группы, и в то же время избегать чрезмерного перекрытия видеокадров.
   При формировании ложных целей имеют значения очертания группы и средняя плотность расположения роботов внутри этого контура, необходимые для обеспечения отражающей способности подобной имитируемому объекту.
   При формировании мобильных фазированных антенных решеток роботы группы должны строго поддерживать одинаковые интервалы друг между другом.
    Задача формирования строя в группе квадрокоптеров имеет ряд особенностей.
   В отличие от наземных мобильных роботов, пространственное положение которых мало зависит от внешних факторов, на положение летающих роботов, к которым относятся квадрокоптеры, в пространстве значительное влияние оказывают ветер, вертикальные воздушные потоки и прочие атмосферные явления. 
   При этом решение ряда практических задач, таких как видеомониторинг, формирование ложных целей, фазированных антенных решеток или мобильных телекоммуникационных сетей не всегда требует точного позиционирования БЛА в пространстве. Гораздо большее значение имеет задача поддержания точных дистанций между БЛА группы. 
   Еще одним отличием малоразмерных БЛА в целом и квадрокоптеров в частности является наличие на борту лишь относительно небольших вычислительных устройств, обладающих небольшой производительностью. Таким образом, использование вычислительно сложных алгоритмов затруднительно, так как за время решения может измениться состояние окружающей среды. К тому же алгоритмы решения строевой задачи должны решаться средствами распределенной вычислительной сети, состоящей из бортовых вычислительных устройств квадрокоптеров.
   С учетом вышесказанного можно сформулировать задачу формирования строя в группе квадрокоптеров и выделить особенности ее решения.
 Формальная постановка задачи формирования строя в группе квадрокоптеров
   Задача формирования строя группой квадрокоптеров или строевая задача является частным случаем строевой задачи в группе мобильных роботов, которая, в свою очередь, является частным случаем задачи группового управления роботами.
   Исходные данные.
   Пусть существует однородная группа R из N одинаковых квадрокоптеров, при этом:
      - каждый квадрокоптер оснащен бортовым устройством управления и бортовым телекоммуникационным устройством;
      - каждый квадрокоптер R имеет индивидуальный номер –идентификатор (ID) и, следовательно, может быть идентифицирован другими квадрокоптерам группы;
      - каждый квадрокоптер может определять свое собственное состояние и текущее положение в пространстве;
      - каждый квадрокоптер может получать информацию о координатах других квадрокоптеров группы.
      Состояние каждого квадрокоптераr_iописывается вектор-функцией
      		s_i (t)=?[s_(i,1) (t),s_(i,2) (t),…,s_(i,h) (t)]?^T.				(2.1)
	Под переменными состояния s_(i,h) (t)в случае со строевой задачей в группе квадрокоптеров, как правило, имеют значение только координаты x_i (t)=x_i (t),y_i (t),z_i (t)положения квадрокоптера в пространстве.
	На основе данных о собственном состоянии и координатах других квадрокоптеров группы, каждый квадрокоптер может определить расстояния до других квадрокоптеров группы.


0
d_(v_1 v_2 )
d_(v_1 v_3 )
…
d_(v_1 v_M )




-
0
d_(v_2 v_3 )
…
d_(v_2 v_M )


D_v=

-
-
0
…
…

,


-
-
-
0
d_(v_(M-1) v_M )




-
-
-
-
0


      Пусть также существует множество V из Mцелевых положений, которое будем называть целевым строем группы. Целевой строй группы задается матрицейD_vрасстояний между целевыми положениями квадрокоптеров в строю
      
      
      
      		    (2.2)
      
   где каждый элементd_(v_? v_k ) матрицы представляет собой расстояние между целевыми положениямиv_? иv_k в искомом строю. При этом координаты целевых положений в пространстве в явном виде не заданы. Также не указаны соответствия между квадрокоптерами группы и целевыми положениями в строю.
   Ориентация целевого строя в пространстве может быть задана в виде угла ?_(i.j)между направлением на север и направлением от целевого положенияv_i к целевому положениюv_j. 
   Пусть количество целевых положений в строю равно количеству квадрокоптеров в группе.


   С целью предотвращения столкновений и взаимных помех квадрокоптеров, вводятся ограничения на положение квадрокоптеров вида:
      |x_i (t)-x_j (t)|??_r,				(2.3)
где?_r – минимально допустимая дистанция между квадрокоптерами, при которой влияние воздушных потоков от винтов одного квадрокоптера на стабильность полёта другого квадрокоптера некритично.  
   Задача формирования строя в группе квадрокоптеров сводится к осуществлению таких перемещений квадрокоптеров группы в пространстве, которые позволят перевести группу из начального положения, в целевое положение, заданное матрицей расстояний (2.2), с учетом ограничений (2.3),за минимально возможное время формирования строя.
 Известные подходу к решению строевых задач
Проблеме решения строевых задач посвящен ряд исследований. Известные подходы к решению строевой задачи в группах мобильных роботов можно разделить на группы:
 методы теории оптимального управления [7, 8];
 метод потенциальных полей (Potential Field Approach);
 бионический (биомиметический) подход [10, 11, 12, 13];
 подход по принципу «ведущий–ведомый» (leader–follower) [14, 16];
 подход по принципу «виртуальная структура/виртуальный лидер» (virtual structure/virtual leader) [17, 18];
 подход на основе теории игр [19].
Рассмотрим их подробнее и оценим области их практического применения.
 
Метод теории оптимального управления для решения строевой задачи
      В настоящее время известен ряд работ, посвященных вопросам управления группой БЛА с использованием теории оптимального управления. Так в работе [7] рассмотрено управление группой БЛА с ограничением на управления и переменные состояния. В этой работе рассмотрено управление группы с ведущим. 
      Также подход к решению задачи управления движением группы БЛА на примере задачи автономного безопасного маневрирования группы БЛА на постоянной высоте при выходе на заданные параллельные курсы описан в работе [8]. 
      Преимущества данных методов заключаются в возможности формирования строев произвольной конфигурации.
      Недостатки заключаются в том, что вычислительная сложность предложенных в этих работах алгоритмов достаточно высока. Эти подходы могут успешно применяться для управления группами полноразмерных БЛА, на борту которых имеются мощные вычислительные устройства. Однако бортовые вычислительные устройства квадрокоптеров и других малоразмерных БЛА являются слабыми. Решение сложных вычислительных задач с помощью слабых бортовых вычислительных устройств может занять слишком много времени, за это время ситуация может сильно измениться.
 Метод потенциальных полей
      Метод потенциальных полей (Potential Field Approach) также имеет другие названия: метод потенциалов, метод виртуальных полей. 
      В основу данного подхода положена следующая идея: все действующие объекты (роботы группы, цели, препятствия) наделяются некоторыми виртуальными полями, физическим аналогом которых являются потенциальные поля. Те объекты, которые должны избегать чрезмерного сближения и столкновения наделяются полями одного «заряда», а те объекты, которые должны двигаться друг к другу – наделяются полями противоположного «заряда» (понятие «заряд» при этом тоже принято условно). Движение каждого робота определяется влиянием результирующей силы, полученной суммированием векторов всех сил притяжения и отталкивания, действующих на этого робота. Известные модификации метода потенциальных полей позволяют осуществлять следующие сценарии управления группой роботов: 
 «ведущий-ведомый» - когда к цели притягивается только ведущий робот, а остальные роботы притягиваются к ведущему (также встречается название «гонка за лидером»); 
 «движение по схеме цепь» - когда к цели притягивается первый робот, а каждый последующий притягивается к предыдущему; 
 «расхождение» – на всех ведомых роботов группы действует сила отталкивания от ведущего. В итоге группа рассредоточивается с целью изучения окружающей области; 
 «схождение» - на всех ведомых роботов группы действует сила притяжения к ведущему роботу; 
 «свободный поиск» - этот сценарий применяется для мониторинга замкнутых помещений. На роботов действуют лишь силы отталкивания от препятствий и от других роботов группы при чрезмерном сближении, а роботы выбирают свои траектории в случайном или квазислучайном порядке. Отталкивание от препятствий и других роботов группы предотвращает столкновения, а недетерминированность маршрута роботов во время мониторинга затрудняет злоумышленникам осуществление несанкционированного доступа. 
      Достоинства метода в простоте вычислений, которые могут быть легко реализованы даже на относительно слабых бортовых вычислительных устройствах, типичных для малоразмерных роботов. 
      Одним из главных недостатков метода потенциальных полей является то, что он обеспечивает формирование только равноудаленного строя и не предназначен для более сложных пространственных построений.
      В связи с этим метод потенциальных полей далеко не всегда подходит для решения задачи формирования строя, однако может применяться для решения задачи поддержания уже сформированного строя. 
 Бионический подход к решению строевой задачи
   В природе строевые задачи наблюдаются в стаях животных и роях насекомых, а также в косяках рыб. Определенные виды построений позволяют животным минимизировать потери от нападения крупных хищников [9]. Исследования стай и роев показывают, что поведение каждой особи сочетает желание оставаться в группе и в то же время стремление соблюдать некоторую дистанцию от других членов группы [10]. Современные технические системы (компьютерные модели или роботы) способны довольно точно имитировать поведенческие тактики живых организмов, что привело к широкому распространению бионических подходов к решению различных технических задач, в том числе и строевых. Первые работы в этом направлении заключались в имитировании поведения живых организмов в косяках рыб и стаях птиц для компьютерной графики. Пионерской работой в этом направлении считается работа Крейга Рейнольдса [11]. Он разработал простую эгоцентрическую модель поведения для роения и продемонстрировал ее работу моделью роения стаи птиц (модель «Biods», это название расшифровывается как «bird-like object», то есть «птица как объект»). Рейнольдс исследовал поведение птиц в стае и вывел три правила поведения: 
 правило разделения – каждая птица старается предотвратить чрезмерное сближение с другими птицами стаи, чтобы избежать столкновений; 
 правило выравнивания – каждая птица в стае выбирает направление движения, ориентируясь на усредненное направление соседних с ней птиц; 
 правило сплоченности – птицы в стае стремятся поддерживать одинаковые расстояния между собой. 

      На основе этих трех правил Рейнольдс создал алгоритм поведения объекта в стае. Результаты компьютерного моделирования показали очень хорошие результаты - поведение объектов «Biods» было очень похоже на поведение птиц в стае. 
      Модель поведения преследует несколько различных целей, таких как соблюдение дистанций, предотвращение столкновений, согласование скоростей и центрирование роя. Важным вкладом Рейнольдса является успешное моделирование поведения группы в целом, в то время как каждый член группы обладает информацией только о небольшой окружающей области и нескольких других соседних участниках группы. 
      Работа Рейнольдса была продолжена. В работе [12] предложена более реалистичная симуляция косяка рыб за счет точного моделирования мышечной системы и поведения рыб в косяке. В работе [13] рассмотрена стая небольших мобильных роботов, учтена динамика их движения. Результаты обоих описанных выше работ визуально более реалистичны, чем у Рейнольдса, потому что учитывают механику движения.
      Достоинства: низкая вычислительная сложность алгоритмов, реализующих эти методы, высокая точность решения строевой задачи. 
      Недостатки: бионические методы позволяют получить некоторое ограниченное множество строевых положений в группах роботов, однако формирование других построений не предусмотрено. Также ряд бионических методов нацелен на поддержание, а не формирование строя. 
      С практической точки зрения эти алгоритмы находят применение в тех областях, где необходимо сымитировать поведение живых стаи птиц или других живых организмов (например - спецэффекты в кино), но плохо подходят для управления роботами. 

 Метод «ведущий-ведомый» для решения строевой задачи
      Подход «ведущий–ведомый» рассматривается многими авторами (например, в работах [14, 16]). В работе [14] продемонстрирован подход «ведущий-ведомый» для управления группой квадрокоптеров с использованием подходов синергетической теории управления [15]. Также подход «ведущий–ведомый» для решения строевых задач группой микроспутников рассмотрен в работе [16]. При таком подходе «ведущие» и «ведомые» устройства часто имеют различное устройство. «Ведущие» прокладывают желаемую траекторию, а «ведомые» прокладывают вариации траекторий, опираясь на состояние ближайших соседей в группе.
      Достоинства подхода «ведущий-ведомый» заключаются в простоте организации взаимодействия внутри группы, а также в возможности формирования строев некоторого множества различных предусмотренных заранее конфигураций. 
      К недостаткам подхода «ведущий-ведомый» относится наличие «слабого звена», то есть тех узлов иерархии, выход из строя которых, или потеря связи с которыми дестабилизирует всю группу, или значительную ее часть. Также формирование строя определенной формы требует определенной структуры связей «ведущий-ведомый» между роботами группы. Без изменения структуры возможно формирование только некоторого ограниченного набора строевых положений, а изменение структуры связей «в реальном времени» не предусмотрено. Данный подход не подходит для тех задач, в которых роботам группы заранее не назначены целевые положения в строю.
 Метод «Виртуальных структур» для решения строевой задачи
   Подход по принципу «виртуальная структура/виртуальный лидер» предложен в работе [17], дальнейшее развитие метода изложено в работе [18]. В этом случае все мобильные роботы группы рассматриваются как единая структура, одно жесткое тело. Виртуальная структура – это некоторая геометрическая фигура, в вершинах которой находятся целевые положения роботов группы. При этом каждому роботу группы соотнесена своя вершина в «виртуальной структуре». 
   Суть метода сводится к тому, чтобы последовательно рассчитывать перемещения «виртуальной структуры», а потом рассчитывать маршруты перемещения каждого робота в «свою» вершину. Когда все роботы группы достигают своих вершин, процесс повторяется. 
   В общем виде, алгоритм управления строем роботов на основе «виртуальной структуры» можно представить следующим образом:
   
1) роботы выстраиваются в соответствии с «виртуальной структурой»; 
   2) «виртуальная структура» перемещается на ?x и поворачивается на ??;
   3) рассчитывается индивидуальная траектория движения для каждого робота для достижения соответствующей точки в «виртуальной структуре»; 
4) рассчитываются управления для движителей каждого робота для следования по траектории; 
   5) переход к пункту №1. 
      Следует отметить, что данный подход находит широкое применение в тех задачах, где траектория движения группы заранее известна и имеется возможность расс.......................