Алгоритмы предполетного квазиоптимального определения маршрутов группы беспилотных летательных аппаратов тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Норсеев, Сергей Александрович

• Норсеев, Сергей Александрович
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Норсеев, Сергей Александрович

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. Анализ современных методов и алгоритмов распределенного

исследования территории

1.1. Методы организации взаимодействия членов группы

1.2. Разбиение территории

1.2.1. Алгоритмы кластеризации территории

1.2.2. Алгоритм наложения прямоугольной сетки

1.2.3. Структуры данных для представления информации о зонах

1.3. Задача о назначениях

1.3.1. Алгоритмы решения задачи о назначениях

1.3.2. Алгоритм последовательного выбора

1.4. Задача коммивояжёра

1.5. Выводы

ГЛАВА 2. Разработка математической модели БПЛА с видеодатчиком

на борту

2.1. Состояния БПЛА и видеодатчика

2.1.1. Состояния БПЛА

2.1.2. Состояния видеодатчика

2.1.3. Состояния БПЛА с видеодатчиком

2.2. БПЛА с видеодатчиками на борту

2.2.1. БПЛА с одним видеодатчиком

2.2.2. Описание кадра

2.2.3. БПЛА с несколькими видеодатчиками

2.3. Сведение задачи обследования территории к задаче о

назначениях

2.3.1. Требования к разбиению территории на зоны

2.3.2 Сведение задачи обследования территории к задаче о назначениях

2.4. Выводы

ГЛАВА 3. Разработка системы предполетного квазиоптимального

определения маршрутов группы БПЛА

3.1. Алгоритм последовательного выбора

3.1.1. Представление территории в виде клеточного автомата

3.1.2. Время работы БПЛА

3.1.3. Расход энергоресурса

3.1.4. Алгоритм последовательного выбора

3.2. Сравнение функций приемлемости

3.2.1. Максимизация ценности

3.2.2. Минимизация расстояния

3.2.3. Обобщенная функция приемлемости

3.3. Двухэтапная оптимизация

3.3.1. Идея метода

3.3.2. Сначала ценность потом расстояние

3.3.3. Сначала расстояние потом ценность

3.3.4. Сравнение методов

3.4. Минимизация пересечений траекторий

3.4.1. Недопущение пересечения траекторий

3.4.2. Недопущение прохождения через реперные точки других БПЛА

3.4.3. Модифицированный алгоритм последовательного выбора

3.5. Метод идентификации столкновений

3.5.1. Определение положения БПЛА в произвольный момент времени

3.5.2. Идея метода

3.5.3. Реализация метода

3.6. Алгоритм синхронизации

3.7. Обобщенный алгоритм предполетного определения маршрутов

группы БПЛА

3.8. Структура системы предполетнего определения маршрутов

3.9. Выводы

ГЛАВА 4. Проверка системы предполетного определения маршрутов

группы БПЛА

4.1. Логическая структура системы моделирования

4.2. Функциональная модель системы

4.3. Программное моделирование системы

4.4. Моделирование алгоритмов

4.5. Экспериментальная проверка

4.6. Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ

Приложение А. Листинг программы представления и обработки

информации об исследуемой территории

Приложение Б. Листинг программы моделирования поведения БПЛА

группы и самой группы

Приложение В. Акты о внедрении

Приложение Г. Свидетельство о государственной регистрации

программы для ЭВМ

Введение диссертации (часть автореферата) на тему «Алгоритмы предполетного квазиоптимального определения маршрутов группы беспилотных летательных аппаратов»

ВВЕДЕНИЕ

Актуальность темы исследования и степень ее разработанности

С развитием информационных технологий, в частности кибернетики, человечество всё активнее использует роботов для выполнения различных задач, часто связанных с риском для жизни и здоровья. Как в России, так и за рубежом роботизация идет по двум основным направлениям:

• создание универсальных роботизированных комплексов, решающих широкий спектр задач;

• создание групп роботов, взаимодействующих друг с другом для решения общей задачи.

Разработка универсальных комплексов сопряжена с рядом неразрешимых проблем: ограничения, накладываемые массогабаритными характеристиками роботов; ограниченность систем технического зрения отдельного робота; низкая живучесть получаемой в результате системы; плохая масштабируемость. Эти причины делают неперспективным дальнейшее развитие универсальных робототехнических комплексов. Тем не менее, и сейчас ведутся работы по улучшению алгоритмов управления одиночным роботом в условиях недетерминированных сред [16, 53, 6].

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

Степень разработанности темы исследования. Проблеме группового применения роботов посвящен ряд крупных научно-исследовательских проектов, выполняемых в наиболее развитых в технологическом отношении странах мира, таких как США, Япония, Германия, Китай и Россия. Анализ результатов этих проектов показывает, что в настоящее время отсутствуют достаточно общие подходы к решению проблемы группового управления

роботами при их функционировании в заранее неизвестной, недетерминированной среде. Приведем несколько примеров таких проектов.

Проект «MARTHA» выполнялся в лаборатории Анализа системных архитектур Франции [65]. Целью данного проекта являлась разработка методов организации группового взаимодействия роботов (от 10 до 100 шт.), предназначенных для транспортировки грузов в складских терминалах. В проекте «MARTHA» используется централизованное управление группой роботов, при котором планирование действий каждого робота группы осуществляется одним центральным устройством управления.

Другим примером является проект, выполнявшийся в Центре распределенных робототехнических систем Университета Миннесоты (США) при поддержке управления DARPA (Defense Advanced Research Projects Agency) Министерства обороны США. Проект был связан с разработкой программного обеспечения и аппаратных средств системы управления группой миниатюрных роботов-разведчиков («Scout»), предназначенных для решения задач охраны, разведки и наблюдения за обстановкой в различных помещениях [77, 78, 69].

Целью проекта «AMADEUS», предложенного японскими разработчиками [73], является создание группы роботов, обеспечивающих подвоз и вывоз изделий для конвейерных линий. В нём используются два типа роботов: транспортный робот (ТР), выполняющий непосредственную перевозку изделий, и стационарный погрузочный робот (СПР), расположенный в непосредственной близости от конвейерной линии и выполняющий разгрузочно-погрузочные работы с ТР на конвейер и наоборот.

В Японии работы в области систем группового взаимодействия роботов активно ведутся в университете г. Нагоя. Здесь разработана система DARS (Distributed Autonomous Robotic System), с помощью которой отрабатываются алгоритмы и методы планирования и управления скоординированными действиями группы роботов, функционирующих в

естественной неорганизованной среде [72], из единого мобильного командного центра.

Управлением DARPA Министерства обороны США также финансировалась разработка тактических мобильных микророботов для группового применения в городских условиях, выполнявшаяся в рамках программы «Тактические мобильные робототехнические системы» [74]. Исследования были направлены на отработку командного взаимодействия группы, состоящей из людей и роботов.

В России наиболее заметными работами в области группового применения роботов являются работы Каляева И.А. [18-22], Капустяна С.Г. [25-29], Станкевича Л.А. [34, 58, 59], Юревича Е.И. [16, 63, 64], Коршунова Ю.М. [37] и других исследователей [1, 3, 8, 14, 15, 51]. В данных работах предлагаются и развиваются алгоритм коллективного улучшения плана, алгоритм последовательного выбора целей, многоагентный подход к построению систем управления, системы управления на основе нейронных сетей и когнитивных моделей и др.

Проблемами автоматизации обработки и анализа получаемых изображений в России занимаются Алпатов Б.А. [2, 37], Денисов Д.А. [13], Колмогоров Г.С. [5], Крыловецкий А.А., Костоусов В.Б., Кулешов С.В., Путятин Е.П. [52], Бакут П.А. и другие исследователи.

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

Все большую популярность набирает использование беспилотных летательных аппаратов (БПЛА) [47]. Преимуществами БПЛА по сравнению с наземными РБТС являются мобильность, большая область видимости, применимость при исследовании труднодоступных областей, дешевизна.

Однако у БПЛА есть и ряд недостатков. Среди них - невысокий запас энергоресурса, применимость только при благоприятных метеоусловиях.

Диссертационная работа посвящена разработке новых и улучшению существующих алгоритмов и методов применения группы БПЛА, занимающихся сбором информации о заданной территории с динамически изменяющейся оперативной обстановкой. Задача сбора информации является общей при решении таких узконаправленных задач, как, например, картографирование местности, проведение поисково-спасательных операций, проведение контртеррористических и военных операций и т.д. Поскольку выполнение этих операций часто требует охвата больших территорий и, подчас, сопряжено с риском для жизни и здоровья, то представляется разумным её автоматизированное выполнение с помощью группы РБТС. Применение БПЛА позволит увеличить обследуемую территорию и снизить стоимость реализации группы.

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

Для достижения поставленной цели необходимо решить следующие задачи.

• Провести анализ существующих алгоритмов разбиения территории на зоны и методов группового взаимодействия РБТС.

• Разработать математическую модель БПЛА с видеодатчиком на борту.

• Модифицировать алгоритм последовательного выбора с целью недопущения прохождения по реперным точкам двух или более различных БПЛА при минимальном расходе энергоресурса и

обеспечения минимального времени сбора информации об оперативной обстановке на близлежащей территории.

• Разработать метод идентификации столкновений БПЛА в воздухе.

• Разработать алгоритм синхронизации движения БПЛА, не допускающий их столкновений.

Научная новизна работы.

1. Математическая модель БПЛА с видеодатчиком высокого разрешения на его борту.

2. Модифицирован алгоритм последовательного выбора. Модифицированный вариант отличается тем, что он минимизирует прохождение по реперным точкам двух или более различных БПЛА.

3. Предложен метод идентификации столкновений БПЛА в воздухе, основанный на проверке минимального расстояния между БПЛА во время работы.

4. Разработан алгоритм синхронизации движения БПЛА, не допускающий их столкновения. При использовании данного алгоритма вероятность столкновения между двумя БПЛА не превышает 0.05%.

Объектом исследования является группа БПЛА, осуществляющая сбор информации об оперативной обстановке на заданной ограниченной территории. Предметом исследования являются алгоритмы предполетного квазиоптимального определения маршрутов, не допускающие столкновений между членами группы и обеспечивающие сбор информации об оперативной обстановке на близлежащей территории за минимальное время.

Теоретическая значимость работы заключается в её вкладе в развитие группового взаимодействия РБТС.

Практическая значимость работы заключается в том, что разработанные и исследованные в диссертационной работе алгоритмы и методы могут быть использованы при проектировании и построении систем управления группой РБТС, осуществляющих сбор информации об ограниченной территории.

Практическое использование результатов подтверждено тремя актами о внедрении. Материалы диссертации внедрены в процесс разработки систем группового управления роботами в ПАО «НПО «Андроидная техника» и в АО «ВНИИ «Сигнал». Результаты исследования внедрены в учебный процесс ФГБОУ ВПО «КГТА им. В.А. Дегтярева». Соответствующие акты внедрения приведены в приложении В.

Методология и методы исследования. При выполнении исследований и разработок в диссертационной работе были использованы методы, основанные на элементах теории множеств, аналитической геометрии, теории алгоритмов, теории вероятностей, а также имитационного моделирования.

Положения, выносимые на защиту.

1. Математическая модель БПЛА с видеодатчиком на борту.

2. Модифицированный алгоритм последовательного выбора, не допускающий прохождения по реперным точкам двух или более различных БПЛА при минимальном расходе времени на обследование близлежащих участков территории.

3. Метод идентификации столкновений БПЛА в воздухе.

4. Алгоритм синхронизации движения БПЛА, не допускающий их столкновения.

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

Апробация результатов. Основные положения и результаты диссертационного исследования докладывались и обсуждались на международной конференции ^А1РАР'2013) «Робототехника и искусственный интеллект проблемы и перспективы» (Брест, 2013); международной школе-конференции «Тараповские чтения-2013» «Современные проблемы математики, механики, информатики» (Харьков,

2013); на международной научно-технической конференции «Современные технологии в системах управления и вооружения» (Ковров, 2013).

Публикации. Основное содержание работы изложено в 13 печатных работах. Из них семь работ представлены в периодических научных изданиях, включенных в перечень российских рецензируемых научных журналов и изданий, рекомендованных ВАК России для опубликования основных научных результатов диссертации на соискание ученой степени кандидата наук. Получено одно свидетельство об официальной регистрации программы для ЭВМ. Результаты, изложенные в работах, получены при определяющем личном участии автора.

Соответствие паспорту специальности. Содержание диссертационной работы соответствует паспорту специальности 05.13.01 -«Системный анализ, управление и обработка информации»: п. 1 «Теоретические основы и методы системного анализа, оптимизации, управления, принятия решений и обработка информации»; п. 2 «Формализация и постановка задач системного анализа, оптимизации, управления, принятия решений и обработки информации»; п. 4 «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации»; п. 9 «Разработка проблемно-ориентированных систем управления, принятия решений и оптимизации технических, экономических, биологических, медицинских и социальных объектов».

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

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

Во второй главе разрабатывается математическая модель БПЛА с видеодатчиком на борту. Вначале главы подробно рассматривается представление БПЛА с видеодатчиком на борту в виде конечного автомата. Такой подход дает упрощенное математическое описание БПЛА с видеодатчиком на борту. В данном описании БПЛА и видеодатчик представляются в виде вектора параметров и состояний, а также рассматриваются соотношения между этими параметрами.

После упрощенного описания представляется вывод математических соотношений между параметрами БПЛА, видеодатчиков на его борту и получаемого ими кадра. В главе рассматриваются различные варианты размещения на борту БПЛА как одного, так и нескольких видеодатчиков. Выведенные соотношения ложатся в основу разрабатываемой математической модели.

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

В конце главы дается описание разработанной математической модели, состоящей из выведенных математических соотношений между параметрами БПЛА, видеодатчика (-ов) и получаемых кадров, а также алгоритма наложения прямоугольной сетки. Данная модель позволяет свести задачу обследования территории к задаче о назначениях. Результатом его применения является представление территории в виде множества реперных точек, то есть точек, в которых БПЛА должны сделать снимок для того, чтобы охватить всю территорию.

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

Первоначально осуществляется вывод математических выражений для расчета времени работы БПЛА и расхода энергоресурса на основе назначенных ему реперных точек.

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

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

Первоначально разрабатывается метод идентификации столкновений. В основе данного метода лежит решение системы неравенств. Само решение системы неравенств является КР-трудной задачей [36]. Однако гипотетическое решение данной системы может быть легко проверено. Это используется в разрабатываемом далее алгоритме синхронизации.

Для разработанного метода идентификации столкновений дается оценка его надежности. Показано, что вероятность столкновения между двумя БПЛА при использовании этого метода не превышает 0.051%.

Разработанный метод идентификации столкновений лежит в основе разрабатываемого алгоритма синхронизации. Данный алгоритм путём корректировки временных задержек БПЛА не допускает столкновений между БПЛА во время их работы. Идея алгоритма состоит в просмотре

относительного положения БПЛА в воздухе во время их работы и проверке столкновений между ними. Для обнаружения столкновений используется разработанный ранее метод идентификации столкновений. Если столкновение обнаружено, то для одного из его участников корректируется длительность его остановки в последней реперной точке. Для данного алгоритма синхронизации доказывается его конечность и оценивается вычислительная сложность. Также приводятся рекомендации по выбору значений коэффициентов, используемых в данном алгоритме.

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

В конце главы предлагается структура системы, построенной на базе обобщенного алгоритма предполетного квазиоптимального определения маршрутов группы БПЛА.

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

Вначале осуществляется программное моделирование. Для этого первоначально разрабатываются логическая и функциональная модели системы. Данные модели ложатся в основу системы моделирования. Для реализации системы моделирования решено использовать язык программирования С++. Программная модель системы представляется в виде ЦМЬ-диаграммы классов. В приложениях А и Б приводятся исходные коды основных компонентов данной программы.

Для экспериментальной проверки используются два БПЛА и специальное программное обеспечение.

Проведенное моделирование и эксперимент доказали работоспособность и применимость разработанных алгоритмов.

ГЛАВА 1. Анализ современных методов и алгоритмов распределенного исследования территории

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

1.1. Методы организации взаимодействия членов группы

Способы решения задачи обследования территории во многом зависят от того, по какой архитектуре будет строиться система взаимодействия членов группы. Выделяют три архитектуры [18, 42]: децентрализованная, централизованная и иерархическая. На рисунке 1.1 показаны принципиальные схемы этих архитектур.

Узел 1 Узел 2 Центральный узел

Узел 3 Узел 4 Узел 1 Узел 2 Узел 3

Центральный узел

Вспомогательный узел 1

Вспомогательный узел 2

Узел 1 Узел 2

Узел 4 Узел 5

а б в

Рис. 1.1. Схемы архитектур систем взаимодействия:

а - децентрализованная; б - централизованная; в - иерархическая

В случае централизованной архитектуры задача построения маршрутов целиком и полностью решается центральным узлом. Результат её решения

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

В централизованной системе взаимодействие между членами группы строится по модели «клиент-сервер» (запрос-ответ). Центральный узел отправляет команды и запросы подчиненным узлам, а те, по мере выполнения команд, поступивших от центрального узла, отправляют ему уведомительные сообщения, тем самым ставя его в известность о ходе выполнения тех или иных действий.

Централизованная архитектура предъявляет высокие требования к надежности и производительности центрального узла. Его надежность определяет живучесть всей системы: если в нём произойдет сбой, то система не сможет функционировать надлежащим образом. Производительность центрального узла обусловливается необходимостью быстрого решения задачи построения маршрутов. Причем данный порядок возрастает с увеличением количества членов в группе и размера обследуемой территории. Иногда центральный узел ради повышения производительности строят с использованием облачных технологий.

Иерархическая система (рис. 1.1(в)) похожа на централизованную. В ней агенты взаимодействуют только с вспомогательными или центральным узлами (в зависимости от того, на каком уровне иерархии они находятся). Агенты, находящиеся на одном уровне иерархии, между собой не взаимодействуют.

При децентрализованной архитектуре задача распределяется между отдельными членами группы. При этом каждый из них решает свою частную задачу [19,16]. После определения своих текущих действий агент уведомляет о своём решении других членов группы. Благодаря этому каждый агент выбирает свои действия, основываясь на информации о текущем состоянии

внешней среды, задаче, поставленной перед группой, состоянии и текущих действиях других членов группы. На рисунке 1.2 представлена обобщенная схема этого алгоритма.

Рис. 1.2. Алгоритм принятия решений в децентрализованной системе

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

Рис. 1.3. Взаимодействие агентов в случае равноправной архитектуры

Переход к децентрализованной модели позволяет во-первых, повысить надежность системы, во-вторых, упростить задачу. Упрощение достигается за счет того, что решение задачи ищется не для всей группы сразу, а для каждого агента в отдельности. Это позволяет значительно уменьшить порядок решаемой задачи.

Тем не менее, такой подход не лишен недостатков:

• порядок решаемой задачи может оставаться довольно большим;

• частые обмены информацией между членами группы (каждый агент в любой момент времени должен знать о состоянии и текущих действиях других членов группы) создает большую нагрузку на каналы передачи информации и предъявляет высокие требования по надежности этих каналов. При увеличении количества агентов в группе интенсивность и объемы информационного обмена будут увеличиваться.

Решение этих проблем видится в построении децентрализованных систем группового взаимодействия на основе модели роя (стаи) [19,15]. Отличительной особенностью такой модели является то, что в ней ни один член группы не «знает» о других членах той же группы. Примеры таких алгоритмов приведены в работах [44, 45]. В работе [24] описывается процесс автоматического приведения роя к централизованной или децентрализованной архитектуре. Тем не менее, теоретические и

практические основы создания роевых систем в настоящее время слабо разработаны.

Механизм взаимодействия агентов в случае модели рой (рис. 1.5) похож на механизм взаимодействия в случае равноправной архитектуры. Единственное отличие состоит в том, что у агентов нет единой среды передачи информации, к которой могли бы иметь доступ все члены роя. Вместо этого у каждого агента своя ограниченная (как правило, по территориальному признаку) среда передачи информации. И эти среды пересекаются друг с другом, когда агенты находятся в достаточной близости друг к другу.

В результате сравнительного анализа была выбрана централизованная архитектура взаимодействия. Данный выбор обусловлен следующими причинами:

• сравнительно невысокие вычислительные ресурсы отдельного БПЛА не позволяют применять ресурсоемкие алгоритмы. Предлагается более разумным, возложить задачу поиска решения на один высокопроизводительный центр. Тем более что нам обычно требуется однократное решение;

• ограниченный запас энергоресурса вынуждает отказаться от постоянного обмена сообщениями между БПЛА в целях координации.

1.2. Разбиение территории

1.2.1. Алгоритмы кластеризации территории

При исследовании большой территории её удобно разбить на небольшие зоны и последовательно изучить их. Существует несколько алгоритмов разбиения территории на зоны [43]. Мы остановимся на следующих: алгоритм кластеризации Ллойда на основе разбиения Вороного [1, 75], алгоритм Morse Decomposition [66] и наложение прямоугольной сетки на исследуемую территорию [25, 27]. Рассмотрим их подробнее.

Алгоритм кластеризации Ллойда является итерационным алгоритмом. Первоначально для исходной территории строится диаграмма Вороного [50], которая разбивает исходную территорию на конечное число непересекающихся зон. Затем данное разбиение последовательно улучшается. На рисунке 1.5 представлена схема этого алгоритма.

Рис. 1.5. Алгоритм кластеризации Ллойда

Главным достоинством этого алгоритма является возможность разбиения исходной территории на количество зон, соответствующее числу агентов в группе. При этом зоны не будут пересекаться.

Недостатки алгоритма Ллойда [43]:

Список литературы диссертационного исследования кандидат наук Норсеев, Сергей Александрович, 2016 год

СПИСОК ЛИТЕРАТУРЫ

1. Александров, В.А. Коллективный алгоритм выделения операционных подпространств для группы роботов при решении задачи покрытия территории [Текст] / В.А. Александров, А.И. Кобрин // Известия высших учебных заведений. Машиностроение. - 2011. - № 618(9). - С. 65-69.

2. Алпатов, Б.А. Алгоритм оценки местоположения объекта на двумерном изображении [Текст] / Б.А. Алпатов, А.А. Селяев // Изв. вузов. Сер. «Приборостроение». - 1988. - №5. - С. 3-5.

3. Ахапкин, С.В. К проблеме принятия решений в системе группового управления мобильными роботами [Текст] / С.В. Ахапкин // Экстремальная робототехника-2003: материалы науч. молодеж. школы. -Таганрог: Изд-во ТРТУ, 2003. - С. 199-206.

4. Ахо. Структуры данных и алгоритмы [Текст] / Ахо, В. Альфред, Хопкрофт, Джон, Ульман, Д. Джеффри; пер. с англ. - М.: Издательский дом «Вильямс», 2003. - 384 с.

5. Бакут, П.А. Сегментация изображений: методы выделения границ областей [Текст] / П.А. Бакут, Г.С. Колмогоров, И.Э. Ворновицкий //Зарубежная радиоэлектроника. - 1987. - №10 - С. 25-47.

6. Бройнль, Т. Встраиваемые робототехнические системы: проектирование и применение мобильных роботов со встроенными системами управления [Текст] / Т. Бройнль - М.; Ижевск: Ижевский институт компьютерных исследований, 2012. - 520 с.

7. Вайсфельд, М. Объектно-ориентированное мышление [Текст] / М. Вайсфельд. - СПб.: Питер, 2014. - 304 с.

8. Ванаг, В.К. Исследование пространственно распределённых динамических систем методами вероятностного клеточного автомата [Текст] / В.К. Ванаг // Успехи физических наук. Обзоры актуальных проблем. - 1999. - Т. 169. - №5. - С. 481-505.

9. Васильев, В.И. Интеллектуальные системы управления. Теория и практика [Текст]: учеб. пособие / В.И. Васильев, Б.Г. Ильясов. - М.: Радиотехника, 2009. - 392 с.

10. Васильев, К.К. Теория автоматического управления (следящие системы) [Текст]: учебное пособие / К.К. Васильев. - 2-е изд. - Ульяновск, 2001. - 98 с.

11. Васильев, С.Н. Интеллектное управление динамическими системами [Текст] / С.Н. Васильев, А.К. Жернов, Е.А. Федосов, Федунов Б.Е.

- М.: Физматлит, 2000. - 352 с.

12. Гладков, Л.А. Генетические алгоритмы [Текст] / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик; под ред. В.М. Курейчика. - 2-е изд., испр. и доп. - М.: ФИЗМАТЛИТ, 2006. - 320 с.

13. Денисов, Д.А. Сегментация изображений на ЭВМ [Текст] / Д.А. Денисов, В.А. Низовкин //Зарубежная радиоэлектроника. - 1985. - №10.

- С.5-30.

14. Зенкевич, С.Л. Планирование задания и управление группой роботов [Текст] / С.Л. Зенкевич, А.В. Назарова, И.А. Сандлер // Искусственный инеллект-2002: материалы Междунар. науч.-техн. конф. Т.2.

- Таганрог: Изд-во ТРТУ, 2002. - С. 241-244.

15. Иванов, Д.Я. Использование принципов роевого интеллекта для управления целенаправленным поведением массово-применяемых микророботов в экстремальных условиях [Текст] / Д.Я. Иванов // Известия высших учебных заведений. Машиностроение. - 2011. - № 618(9). - С. 70-78.

16. Интеллектуальные роботы [Текст]: учеб. пособие для вузов / И.А. Каляев, В.М. Лохин, И.М. Макаров; под общ. ред. Е.И. Юревича. - М.: Машиностроение, 2007. - 360 с.

17. Искусственный интеллект и интеллектуальные системы управления [Текст] / И.М. Макаров, В.М. Лохин, С.В. Манько, М.П. Романов, Отделение информ. технологий и вычислит. систем РАН; под ред. И.М. Макарова. - М.: Наука, 2006. - 333 с.

18. Каляев, И.А. Децентрализованные системы компьютерного управления [Текст] / И.А. Каляев, Э.В. Мельник. - Ростов н/Д: Издательство ЮНЦ РАН, 2011. - 196 с.

19. Каляев, И.А. Модели и алгоритмы коллективного управления в группах роботов [Текст] / И.А. Каляев, А.Р. Гайдук, С.Г. Капустян. - М.: ФИЗМАТЛИТ, 2009. - 280 с.

20. Каляев, И.А. Однородные нейроподобные структуры в системах выбора действий интеллектуальных роботов [Текст] / И.А. Каляев, А.Р. Гайдук - М.: Янус-К, 2000. - С. 280.

21. Каляев, И.А. Принципы коллективного принятия решения и управления при групповом взаимодействии роботов [Текст] / И.А. Каляев // Мобильные роботы и мехатронные системы: материалы науч. школы-конф. -М.: Изд-во МГУ, 2000. - С. 204-221.

22. Каляев, И.А. Принципы организации систем управления интеллектуальных мобильных роботов на базе многопроцессорных и нейропроцессорных структур [Текст] / И.А. Каляев // Мобильные роботы и мехатронные системы: сб. докл. науч. школы-конференции (с междунар. участием). - М.: Изд-во ИПМ РАН, 1998. - С. 86-106.

23. Каляев, И.А. Проблемы группового управления роботами [Текст] / И.А. Каляев, С.Г. Капустян // Мехатроника, автоматизация, управление. - 2009. - № 6. - С. 33-40.

24. Каляев, И.А. Самоорганизующиеся системы управления группами интеллектуальных роботов, построенные на основе сетевой модели [Текст] / И.А. Каляев, С.Г. Капустян, А.Р. Гайдук // Управление большими системами. Специальный выпуск 30.1 «Сетевые модели в управлении». - М.: ИПУ РАН, 2010. - С. 605-639.

25. Капустян, С.Г. Алгоритм и имитационная модель решения задачи оптимального покрытия поверхности группой роботов [Текст] / С.Г. Капустян, Р.Н. Кулиничев // Искусственный интеллект.

Интеллектуальные и многопроцессорные системы-2004: материалы Междунар. науч. конф. Т.2. - Таганрог: Изд-во ТРТУ, 2004. - С. 396-400.

26. Капустян, С.Г. Децентрализованный метод коллективного распределения целей в группе роботов [Текст] / С.Г. Капустян // Известия высших учебных заведений. Электроника. - 2006. - № 2. - С. 84-91.

27. Капустян, С.Г. Метод организации мультиагентного взаимодействия в распределенных системах управления группой роботов при решении задачи покрытия площади [Текст] / С.Г. Капустян // Искусственный интеллект. - 2004. - № 3. - С. 715-727.

28. Капустян, С.Г. Распределенная система управления группой складских роботов-штабелеров [Текст] / С.Г. Капустян // Экстремальная робототехника-2003: материалы науч. молодеж. школы. - Таганрог: Изд-во ТРТУ, 2003. - С. 190-199.

29. Капустян, С.Г. Склад, где ничего не теряется [Текст] / С.Г. Капустян // Промышленный еженедельник. - 2004. - № 35(84). - С.9.

30. Кирильченко, А.А. Свойство виртуальности в информационных системах робототехники [Текст] / А.А. Кирильченко, А.А. Петрин // Препринты ИПМ им. М.В. Келдыша. - 2003. - № 41. - 22 с.

31. Кондратьев, А.И. Нейросетевое адаптивное отказоустойчивое управление движением маневренного самолета [Текст] / А.И. Кондратьев, Ю.В. Тюменцев // XII Всероссийская научно-техническая конференция «Нейроинформатика - 2010»: Часть 2. - М.: НИЯУ МИФИ, 2010. - С. 262-273.

32. Кормен. Алгоритмы: построение и анализ [Текст] /Кормен, Х. Томас, Лейзерсон, И. Чарльз, Ривест, Л. Рональд, Штайн, Клиффорд; пер. с англ. - 2-е изд. - М.: Издательский дом «Вильямс», 2013. - 1296 с.

33. Коршунов, Ю.М. Математические основы кибернетики: учебное пособие для втузов [Текст] / Ю.М. Коршунов. - М.: Энергия, 1972.

34. Котенко, И.В. Командная работа агентов в условиях временных ограничений [Текст] / И.В. Котенко, Л.А. Станкевич // Искусственный

интеллект-2002: материалы Междунар. науч.-техн. конф. Т.2. - Таганрог: Изд-во ТРТУ, 2002. - С. 249-253.

35. Красовский, Н.Н. Управление динамической системой. Задача о минимуме гарантированного результата [Текст] / Н.Н. Красовский - М.: Наука, Глав. ред. физ.-мат. лит., 1985. - 520 с.

36. Крупский, В.Н. Сложность вычислений [Текст]: курс лекций /

B.Н. Крупский. - М.: Москва, 2003. - 2005.

37. Методы автоматического обнаружения и сопровождения объектов. Обработка изображений и управление [Текст] / Б.А. Алпатов, П.В. Бабаян, О.Е. Балашов, А.И. Степашкин. - М.: Радиотехника, 2008. - 176 с.

38. Миндалёв, И.В. Моделирование бизнес-процессов: электронный учебно-методический комплекс [Электронный ресурс] // КрасГАУ. - 2009. -Режим доступа: http://www.kgau.ru/istiki/umk/mbp/.

39. Новиков, Д.А. Математические модели формирования и функционирования команд [Текст] / Д.А. Новиков. - М.: Физматлит, 2008. - 188с.

40. Ногин, В.Д. Принятие решений в многокритериальной среде: количественный подход [Текст] / В.Д. Ногин. - М.: ФИЗМАТЛИТ, 2002. - 144 с.

41. Норсеев, С.А. Алгоритмы исследования неизвестной области с большим числом препятствий [Текст] / С.А. Норсеев, Д.В. Багаев // Системы управления и информационные технологии. - 2014. - №2.1(56) - С. 166-168.

42. Норсеев, С.А. Архитектуры многоагентных систем [Текст] /

C.А. Норсеев, Д.В. Багаев // Современные технологии в системах управления и вооружения: сборник статей международной научно-технической конференции, посвященной 60-летию высшего образования в г. Коврове. -Ковров: ФГБОУ ВПО «КГТА им. В.А. Дегтярёва», 2013. - С.81-86.

43. Норсеев, С.А. Задача исследования неизвестной местности и методы её решения с применением многоагентной системы [Текст] / С.А. Норсеев, Д.В. Багаев // Информационные технологии моделирования и управления. - 2014. - № 2(86). - С. 110-117.

44. Норсеев, С.А. Обзор алгоритмов группового управления [Текст] / С.А. Норсеев, Д.В. Багаев // Современные проблемы математики, механики, информатики: сборник тезисов докладов междунар. школы-конф. «Тараповские чтения - 2013»; под ред. Н.Н. Кизиловой, Г.Н. Жолткевича. -Харьков: Изд-во Цифровая типография № 1, 2013. - С. 134.

45. Норсеев, С.А. Обзор алгоритмов группового управления робототехническими комплексами. [Текст] / С.А. Норсеев, Д.В. Багаев // Электротехнические системы и комплексы: междунар. сб. науч. трудов. Вып. 21; под ред. Г.К. Корнилова, Е.А. Пановой. - Магнитогорск: Изд-во Магнитогорск. гос. техн. ун-та. им. Г.И. Носова, 2013. - С. 137-145.

46. Норсеев, С.А. Разработка алгоритма распределенного исследования неизвестной местности с помощью группы мобильных роботов [Текст] / С.А. Норсеев, Д.В. Багаев // Автоматизация процессов управления. -№2(36) - 2014. - С. 67-71.

47. Павлушенко, М. Беспилотные летательные аппараты: история, применение, угроза распространения и перспективы развития [Текст] / М. Павлушенко, Г. Евстафьев, И. Макаренко // Научные записки ПИР-центра: национальная и глобальная безопасность №26(2004). - М.: Издательство «Права человека», 2005. - 611 с.

48. Платонов, А.К. Концепция виртуальных датчиков в задачах управления мобильными мехатронными системами [Текст] / А.К. Платонов, А.А. Кирильченко, И.Г. Ладынин, В.В. Ястребов // Труды 3-ей Международной научно-технической конференции «Современные методы и средства океанологических исследований». - М.: ИО им. П.П. Ширшова РАН, 1997. - С. 137-143.

49. Поликарпова, Н.И. Автоматное программирование [Текст] / Н.И. Поликарпова, А.А. Шалыто. - СПб.: НИУ ИТМО, 2008. - 167 с.

50. Препарата, Ф. Вычислительная геометрия: Введение [Текст] / Ф. Препарата, М. Шеймос; пер. с англ. - М.: Мир, 1989. - 478 с.

51. Проталинский, И.О. Алгоритмизация процесса нахождения паретто-оптимального управления для группы мобильных роботов [Текст] / И.О. Проталинский // Наука вчера, сегодня, завтра: сборник статей по материалам V международной научно-практической конференции. -Новосибирск: Изд-во «СибАК», 2013. - №5(5) - С. 35-40.

52. Путятин, Е.П. Обработка изображений в робототехнике [Текст] / Е.П. Путятин, С.И. Аверин. - М.: Машиностроение, 1990.

53. Пшихопов, В.Х. Управление подвижными объектами в определенных и неопределенных средах [Текст] / В.Х. Пшихопов, М.Ю. Медведев. - М.: Наука, 2011. - 350 с.

54. Рэндл, У. Биард Малые беспилотные летательные аппараты: теория и практика [Текст] / У. Биард Рэндл, Тимоти У. МаклЛэйн. - М.: ТЕХНОСФЕРА, 2015. - 312 с.

55. Свидетельство о регистрации ПО для ЭВМ «SwarmProtocol». №2014660765.

56. Сигеру, Омтау Нейроуправление и его приложения [Текст] / Омтау Сигеру. - М.: ИПРЖР, 2000. - 272 с.

57. Способы управления распределенной мобильной системой в условиях неопределенности [Текст] / А.В. Ахтеров [и др.] // Препринты ИПМ им. М.В. Келдыша. - 2012. - № 67. - 32 с.

58. Станкевич, Л.А. Мультиагентная технология в когнитивных системах управления автономными роботами [Текст] / Л.А. Станкевич // Экстремальная робототехника: материалы X науч.-техн. конф. - СПб.: Изд-во СПбГТУ, 1999. - С. 62-70.

59. Станкевич, Л.А. Онлайн обучение агентов командной работе с использованием модели иммунологических сетей [Текст] / Л.А. Станкевич, Д.А. Троцкий // Второй международный семинар AIS-ADM 2007, С-Петербург, Россия, июнь 2007: труды семинара; под ред. В.И. Городецкого и др., LNAI 4476, Springer, 2007. - С. 243-255.

60. Тоффоли, Т. Машины клеточных автоматов [Текст] / Т. Тоффоли, Н. Марголус. - М.: Мир, 1991. - 280 с.

61. Филиппов, С.И. Метод комплексирования навигационных данных с прогнозированием [Текст] / С.И. Филиппов, Д.Ю. Тютюгин, С.А. Норсеев // Оборонная техника. - 2015. - №11-12. - С. 78-82.

62. Чернодуб, А.Н. Обзор методов нейроуправления [Текст] / А.Н. Чернодуб, Д.А. Дзюба // Проблемы программирования. - 2011. - №2. -С. 79-94.

63. Юревич, Е.И. О проблеме группового управления роботами [Текст] / Е.И. Юревич // Мехатроника, автоматизация, управление. - 2004. - № 2. - С. 9-13.

64. Юревич, Е.И. Принципы группового управления роботами [Текст] / Е.И. Юревич // Экстремальная робототехника-2003: материалы научной молодежной школы. - Таганрог: Изд-во ТРТУ, 2003. - С. 165-171.

65. Alami, R. Multi-robot Cooperation in the MARTHA Project / R. Alami, S. Fleury, M. Herrb, F. Ingred, F. Robert // IEEE robotics & Automation magazine. - 1998. - V.5, No 1. - P. 36-47.

66. Choset, H. Principles of robot motion: theory, algorithms, and implementations / H. Choset, K.M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L.E. Kavraki, S. Thrum. - MIT Press, Boston, 2005. - 632 p.

67. Dechter, R. Generalized best-first search strategies and the optimality of A* / R. Dechter, J. Pearl // Journal of the ACM. - 1985. - T. 32. - №3. - P. 505-536.

68. Dias, M.B. Market-Based multirobot coordination: a survey and analysis / M.B. Dias, R. Zlot, N. Kalra, A. Stentz// Proceedings of the IEEE. - Vol. 94, Issue 7. - 2006. - P. 1257-1270.

69. Drenner, A. Mobility Enhancements to the Scout Robot Platform / A. Drenner, I. Burt, T. Dahlin, B. Kratovchi, C.P. McMillen, B. Nelson, N. Papanikolopoulos, P.E. Rybski, K. Stubbs, D. Waletzko, K.B. Yesin // Proc. of the 2002 IEEE Intern. Conf. on Robotics and Automation, Washington, DC, May 2002. - P. 1069-1074.

70. Goldberg, D.E. Genetic algorithms in search, optimization and machine learning: Addison Wesley, New York, 1989. - 412 p.

71. Hoeing, M. Dynamic pricing algorithms for market based distributed task selection in multi-agent swarms / M. Hoeing, P. Dasgupta // Proc. IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT'06), Hong Kong. - 2006. - P. 113-116.

72. Kaga, T. An Oscillation Analysis on Distributed Automations Robotic System / T. Kaga, T. Fukuda // IEEE of Intern. Conf. on Robotics and Automation, Leuven, Belgium, May 16-20, 1998. - V.4. - P. 2846-2851.

73. Kamada, T. AMADEUS: A Mobile, Autonomous Decentralized Utility System for Indoor Transportation / T. Kamada, K. Oikawa // IEEE Intern. Conf. on Robotics and Automation, Leuven Belgium, May 16-20, 1998. - V.4 - P. 2229-2236.

74. Kawamura, K. Supervisory Control of Mobile Robots using Sensory EgoSphere / K. Kawamura, R.A. Peters, C. Johnson, P. Nilas, S. Thongchai // Proc. of 2001 IEEE Intern. Symposium on Computational Intelligence in Robotics and Automation, Banff, Alberta, Canada, July 29-Aug. 1, 2001. - P. 523-529.

75. Qiang, D. Convergence of the Lloyd algorithm for computing centroidal Voronoi teselations / D. Qiang, M. Emelianenko, L. Ju // SIAM Journal on Numerical Analysis 44. - 2006. - P. 102-119.

76. Rowland, J.J. A virtual sensor implementation for assembly machine. / J.J. Rowland, H.R. Nickols // "Robotica" - 1995. - V. 13. - P. 195-199.

77. Rybski, P.E. System Architecture for Versatile Autonomous and Teleoperated Control of Multiple Miniature Robots / P.E. Rybski, I. Burt, T. Dahlin, M. Gini, D.F. Hougen, D.G. Krantz, F. Nageotte, N. Papanikolopoulos, S.A. Stoeter // Proc. of the 2001 IEEE Intern. Conf. on Robotics and Automation, Seoul, Korea, May 2001.

78. Stoeter, S.A. Scout Robot Motion Model / S.A. Stoeter, I.T. Burt, N. Papanikolopoulos // Proc. of the IEEE Intern. Conf. on Robotics and Automation, Taipei, Taiwan, May 2003.

155