Содержание к диссертации
Введение
1. Анализ проблем и задач мультиагентного управления. Общая концепция построения МРТС 13
1.1. Обзор существующих МРТС 13
1.2. Общие принципы построения мультиагентных систем 16
1.3. Управление коллективом роботов
1.3.1. Стратегии группового управления 19
1.3.2. Методы глобального планирования в централизованных системах 21
1.3.3. Методы глобального планирования в децентрализованных системах 24
1.3.4. Методы локального планирования 25
1.4. Применение РТС при проведении поисково-спасательных работ 27
1.5. Общая концепция построения МРТС 33
1.5.1. Состав МРТС 33
1.5.2. Структура системы управления МРТС 35
1.5.3. Организация информационного обмена 37
Выводы...: 41
2. Глобальное планирование 43
2.1. Задачи, решаемые МРТС 44
2.1.1. Маркировка безопасных маршрутов эвакуации. Постановка задачи 45
2.1.2. Нейтрализация очагов химического заражения. Постановка задачи 45
2.2. Централизованное распределение задач в коллективе роботов Стр.
2.2.1. «Ценовой» алгоритм распределения задач в коллективе роботов 46
2.2.2. Генетический алгоритм распределения задач в коллективе роботов 51
2.2.3. Сравнительный анализ алгоритмов централизованного распределения задач в коллективе роботов 58
2.3. Мультиагентное распределение задач в коллективе роботов 59
2.4. Мультиагентное разбиение коллектива роботов на группы 72
Выводы 77
3. Локальное планирование 80
3.1. Формирование траекторий движения роботов 80
3.1.1. Метод «потенциалов» 81
3.1.2. Перемещение роботов к целевым точкам в среде с препятствиями 83
3.1.3. Равномерное распределение роботов в рабочей зоне 87
3.1.4. Исследование устойчивости решения при равномерном распределении роботов в рабочей зоне 89
3.2. Навигационная система МРТС 92
3.2.1. Определение координат робота. Интегрирование уравнений кинематики 93
3.2.2. Определение координат робота. Метод триангуляции 94
3.2.3. Использование рекуррентного фильтра Калмана 96
Выводы 103
4. Управляющий центр МРТС 105
4.1. Блок формирования команд 106
4.2. Блок обработки данных 108
4.3. Построение картограммы заражения рабочей зоны 109
4.4. Определение параметров очагов химического заражения 113 Стр.
4.5. Правила составления прогнозов 114
4.6. Построение безопасных маршрутов эвакуации 119
Выводы 121
5. Экспериментальные исследования 123
5.1. Программная модель МРТС. Реализация разработанных алгоритмов 123
5.2. Твердотельная динамическая модель МРТС с учетом сенсорной системы роботов 130
5.3. Рекомендации по проведению натурного эксперимента 135
5.4. Перспективы использования полученных результатов 143
Выводы 146
Основные результаты и выводы 148
Список литературы
- Стратегии группового управления
- Генетический алгоритм распределения задач в коллективе роботов
- Перемещение роботов к целевым точкам в среде с препятствиями
- Построение картограммы заражения рабочей зоны
Введение к работе
Актуальность. В настоящее время роботы и робототехнические системы находят широкое применение в областях, связанных с риском для человека, например, в химической и атомной промышленности при техногенных и природных катастрофах и др. Мобильные роботы могут использоваться при решении таких задач, как инспекция и исследование труднодоступных помещений, наблюдение за различными объектами, построение карты загрязнения рабочего пространства и т.п.
Как правило, отдельный мобильный робот (агент) владеет лишь частичным представлением о глобальной проблеме, а значит, может решить только некоторую часть общей задачи. В связи с этим, для решения сложных задач необходимо иметь некоторое множество роботов-агентов различной «специализации», организовать между ними эффективное взаимодействие и построить на их основе единую мультиагентную робототехническую систему (МРТС). К настоящему времени в мире для решения поисково-спасательных и ликвидационных операций в условиях аварий на химически опасных объектах используются либо отдельные мобильные роботы, либо централизованные РТС. Такие системы не могут эффективно и быстро решать поставленные задачи. Необходимо использовать коллективы взаимодействующих роботов. Таким образом, научная тема мультиагентного управления коллективом мобильных роботов, автономно функционирующим в условиях химического заражения, является актуальной. Решение данной проблемы направлено на практическую реализацию применения МРТС, что позволит в значительной степени снизить риск для жизни и здоровья человека при работе в неблагоприятных или опасных условиях.
Сегодня в России проблемами мультиагентного управления занимаются такие известные ученые, как: проф. В.И. Городецкий, проф. А.В. Тимофеев, проф. С.В. Манько, проф. В.М. Лохин, а также член-корр. РАН И.А. Каляев и проф. С.Г. Капустян. За рубежом наиболее известны работы В. Лессера, К. Декера и Ф. Коэна.
Цели и задачи. Целью диссертационной работы является построение модульной системы управления МРТС, предназначенной для работы на химически опасных объектах, а также разработка методов и алгоритмов мультиагентного и централизованного управления коллективом мобильных роботов. В соответствии с этим, в работе поставлены и решены следующие задачи:
анализ существующих подходов к решению проблемы группового управления мобильными роботами;
выбор принципа построения МРТС, формирование ее состава и структуры системы управления;
разработка методов и алгоритмов мультиагентного и централизованного управления коллективом роботов, выполняющим поисково-спасательные и ликвидационные операции;
разработка алгоритмов формирования траекторий движения роботов;
построение навигационной системы мобильного робота;
разработка методов и алгоритмов обработки данных, получаемых роботами при выполнении поисково-спасательные и ликвидационные операций.
Методы исследования. В работе использованы методы современной теории автоматического управления, бионические алгоритмы, методы группового управления, методы рекуррентной фильтрации Калмана; математическое и имитационное моделирование. На защиту выносятся
-
-
Модульный подход к построению системы управления МРТС.
-
Мультиагентный алгоритм разбиения коллектива роботов на группы.
-
Мультиагентный алгоритм распределения задач в группе роботов.
-
Метод определения параметров зон химического заражения.
-
Алгоритм построения безопасных маршрутов эвакуации.
Научная новизна. Разработаны новые базовые мультиагентные алгоритмы управления коллективом мобильных роботов: алгоритм распределения задач в группе роботов и алгоритм разбиения коллектива роботов на группы. Кроме того, разработаны новые методы обработки сенсорной информации, получаемой роботами в процессе выполнения задач: метод определения параметров очагов заражения и алгоритм построения безопасных маршрутов эвакуации людей из зоны заражения.
Практическая ценность. Разработанные методы и алгоритмы управления коллективом мобильных роботов могут быть применены в ситуациях, опасных для человека. Модульный подход к построению системы управления и универсальность разработанных методов и алгоритмов позволяют использовать данные принципы в мультиагентных системах различного назначения.
Реализация результатов работы. Материалы диссертации использованы в рамках НИР, проходившей в НУЦ «Робототехника» МГТУ им. Н.Э. Баумана. Создан программный пакет, реализующий разработанные методы и алгоритмы управления коллективом мобильных роботов.
Апробация работы. Основные результаты работы докладывались и получили положительную оценку на научных форумах: 12-й Всероссийской научно-практической конференции «Экстремальная робототехника» (Санкт- Петербург, 1 - 3 апреля 2009 г.); Международной конференции с элементами научной школы для молодежи «Экстремальная Робототехника» (Санкт- Петербург, 12 - 14 октября 2010 г.); 22-й Международной научно- технической конференции «Экстремальная робототехника» (Санкт- Петербург, 23 - 25 ноября 2011 г.); Российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» (Москва, 16 - 19 апреля 2012 г.).
Публикации. Основное содержание работы отражено в 5 публикациях, из них 2 статьи опубликованы в журналах, входящих в перечень ВАК РФ.
Структура и объем работы. Диссертационная работа состоит из введения, 5 глав, заключения, библиографического списка, включающего 111 наименований, и приложений. Работа изложена на 184 листах машинописного текста, содержит 112 рисунков и 31 таблицу.
Стратегии группового управления
Как уже было сказано, мультиагентная система - это система, образованная несколькими взаимодействующими агентами, сообща решающими общую задачу. Мультиагентные системы обладают следующими свойствами: - способность к самоорганизации и самовосстановлению; - гибкость; - устойчивость к сбоям. Все агенты по физической природе можно разделить на натуральные (человек, животное, коллектив людей, стадо животных и т.п.) и искусственные (робот, коллектив автоматов, сложная компьютерная программа) [3]. Искусственные агенты подразделяются на: - материальные - физически существующие и работающие в реальном пространстве; - виртуальные - существующие в некоторой программной среде (виртуальном пространстве).
Ядром агента является блок управления, который содержит процессор и блок памяти. Процессор обеспечивает объединение и обработку разнородных данных, выработку соответствующих реакций на информацию о состоянии среды, принятие решений о выполнении тех или иных действий. Блок памяти включает два основных компонента: модель внешней среды и модель самого агента.
Сенсорная система - это система датчиков агента, обеспечивающая прием и первичную обработку информации, которая поступает к нему из среды (как внешней, так и внутренней).
Эффекторы - это средства воздействия на внешнюю среду и на самого агента. Это, например, механизм перемещения робота или манипулятор, предназначенный для перемещения каких-либо предметов. Источник ресурсов (в частном случае, источник питания) - это устройство, которое обеспечивает все необходимые условия для поддержания жизненного цикла агента.
Взаимодействие задач мультиагентного управления Под стратегией группового управления понимается общий принцип организации управления агентами. Стратегия определяет, кто и на каком уровне управления решает задачи глобального и локального планирования, выполняет обработку получаемой информации. Стратегия группового управления выбирается в зависимости от количества агентов, входящих в состав мультиагентной системы, и исходя из скорости изменения параметров рабочей среды.
Глобальное планирование - это декомпозиция сложной глобальной задачи на более простые задачи, а также распределение среди агентов задач, полученных в результате декомпозиции. Причем это распределение должно удовлетворять некоторому заданному критерию оптимальности.
Локальное планирование включает решение комплекса проблем, связанных с выполнением агентами задач, сформированных и распределенных на этапе глобального планирования. Например, планирование траектории движения мобильных роботов при их перемещении к заданным целевым точкам.
В процессе выполнения задач агенты получают полезную информацию, которую необходимо обработать. На основании полученных данных может быть сформировано новое задание для коллектива агентов.
При построении мультиагентной системы наиболее важной и сложной задачей является разработка системы управления, способной решать задачи глобального и локального планирования в соответствии с выбранной стратегией группового управления и получаемой агентами информацией.
В зависимости от используемой стратегии группового управления выделяют три типа распределенных систем - централизованные, децентрализованные и гибридные [9]. В централизованных системах процессы декомпозиции глобальной задачи и обработки полученной агентами информации происходят под управлением единого управляющего центра. В децентрализованных системах такой центр отсутствует, распределение заданий происходит в процессе взаимодействия агентов, обработка полученной информации также осуществляется агентами. Гибридная система - это комбинация централизованной и децентрализованной систем. Здесь декомпозиция глобальной задачи выполняется за счет обмена информацией между агентами, а обработка данных осуществляется управляющим центром.
Генетический алгоритм распределения задач в коллективе роботов
Разработанная МРТС может быть использована для решения ряда задач, среди которых обследование рабочей зоны, поиск объектов в рабочем пространстве, выполнение различных технологических и транспортных операций. Реализацию перечисленных задач обеспечивают три базовых мультиагентных алгоритма: - разбиение коллектива роботов на группы; - распределение задач в группе роботов (декомпозиция); - перемещение роботов к целевым точкам в среде с препятствиями; - равномерное размещение роботов в рабочей зоне. 1.5.3. Организация информационного обмена
Одним из наиболее важных аспектов успешного функционирования системы в реальном времени является организация информационного обмена между элементами, входящими в состав МРТС, т.е. построение коммуникационной системы.
Коммуникационная система должна обеспечивать возможность ведения переговоров между агентами МРТС и удовлетворять децентрализованному принципу построения, при котором все переговоры осуществляются напрямую, без централизованного управления.
Ведение переговоров, направленных на достижение взаимовыгодных соглашений меду агентами, является одним из необходимых условий возникновения кооперации. При этом обычно предполагается, что правила ведения переговоров установлены заранее и известны всем агентам. Для реализации переговоров необходим специальный протокол, к которому предъявляются следующие требования [35]: - простота; - симметричность (все агенты являются равноправными участниками переговоров); - эффективность (как по отношению к отдельным агентам, так и по отношению к коллективу в целом). Один из удобных и наиболее перспективных способов коммуникации агентов - это организация МРТС в виде беспроводной сенсорной сети (БСС).
Беспроводные сенсорные сети состоят из множества узлов, которые собирают данные о физическом мире, обрабатывают и передают информацию посредством радиосвязи и используются для наблюдения за какими-либо объектами. Каждый узел представляет собой миниатюрное вычислительно-коммуникационное устройство [36], в состав которого входят: - плата управления (микропроцессор, флэш-память, оперативная память, цифроаналоговые и аналого-цифровые преобразователи, радиочастотный приемопередатчик); - источник питания; - датчики (сенсоры). В зависимости от решаемых сенсорной сетью задач, в состав ее узлов могут входить различные сенсоры. Это могут быть датчики температуры, давления, влажности, освещенности, вибрации, а также магнитоэлектрические, химические, звуковые и другие. Сенсоры подключаются с помощью цифровых и аналоговых коннекторов.
Как правило, узел сети должен иметь возможность самостоятельно определять свое местоположение в рабочем пространстве или, по крайней мере, относительно того узла или шлюза, которому он будет передавать данные. Поэтому сначала происходит идентификация всех узлов сети, а затем формируется схема маршрутизации.
В настоящее время широко используются две основные топологии БСС: сенсорная сеть с кластерной архитектурой и одноранговая ячеистая сенсорная сеть [37].
В БСС с кластерной архитектурой все узлы сети по уровню сложности можно разделить на три класса: координатор, маршрутизатор и обычный узел. Высший из них - координатор - управляет работой сети, хранит данные о ее топологии и служит шлюзом для передачи данных, собираемых всей беспроводной сенсорной сетью. В сенсорных сетях обычно используется один координатор, однако могут быть исключения. Средний по сложности узел является маршрутизатором. Он может принимать и передавать данные, а также определять направление передачи. Самый простой узел может только передавать данные ближайшему маршрутизатору. В качестве примера можно назвать стандарт ZigBee, поддерживающий сеть с кластерной архитектурой. Кластер образуют маршрутизатор и простейшие узлы, у которых он запрашивает сенсорные данные. Маршрутизаторы кластеров ретранслируют данные друг другу, и, в конечном итоге, информация передается координатору. Координатор обычно имеет связь с IP-сетью, куда и направляются данные для окончательной обработки. Схема сети с кластерной архитектурой показана на рисунке 1.18.
Перемещение роботов к целевым точкам в среде с препятствиями
Проведенные исследования показали, что все централизованные методы (на рисунке 2.18, а, б указаны штриховыми линиями) имеют большую вычислительную сложность, чем мультиагентные. При этом алгоритм распределения задач, разработанный на базе модели переговоров «Аукцион», обладает значительно меньшей вычислительной сложностью, чем метод коллективного улучшения плана (в 0.12 п раз).
Из рисунка 2.18, а видно, что метод полного перебора целесообразно использовать при п 7. А рисунок 2.18, б показывает, что если п 10, генетический алгоритм значительно эффективнее, чем метод полного перебора.
Недостатком разработанных централизованных и мультиагентных алгоритмов является зависимость получаемого результата от порядка нумерации агентов и задач. Кроме того, данные алгоритмы позволяют находить «хорошее», но не оптимальное решение. Метод полного перебора лишен этих недостатков, но при большом количестве роботов (п 7) обладает высокой вычислительной сложностью.
При большом количестве роботов (п 30) мультиагентный алгоритм, основанный на модели переговоров «Аукцион», по сравнению с другими алгоритмами является более эффективным с точки зрения вычислительной сложности.
Максимальное число роботов, при котором возможно использовать централизованный подход, определяется вычислительной сложностью централизованных алгоритмов и производительностью компьютера управляющего центра.
Например, тактовая частота процессора центрального компьютера составляет 3,4 ГГц (3,4 109 операций в секунду). Время расчета не должно превышать 300 с. В этом случае метод полного перебора является эффективным, если число роботов п 15.
Применение разработанного мультиагентного алгоритма распределения задач имеет ограничение. Каждый агент-робот должен иметь возможность обмениваться информацией со всеми остальными роботами, входящими в состав коллектива. Это условие выполняется, если дальность радиопередачи каждого робота превышает размеры рабочей зоны. Кроме того, в пределах рабочей зоны не должно быть препятствий, нарушающих информационный обмен. В реальных условиях не всегда удается выполнить эти требования.
Решением данной проблемы является разработанный мультиагентный алгоритм разбиения коллектива роботов на отдельные группы. Группы должны быть сформированы таким образом, чтобы в каждой из них был агент-лидер, способный обмениваться информацией со всеми остальными агентами группы, при этом число лидеров должно быть минимальным. По сути, поставленная задача - это задача мультиагентной кластеризации. В настоящее время известно множество алгоритмов кластеризации, среди которых бионические алгоритмы, методы исключающей кластеризации (метод -средних), алгоритмы перекрывающей кластеризации (метод нечетких С-средних), иерархические и вероятностные методы и др. Основным недостатком большинства известных методов является необходимость предварительного задания количества кластеров [55, 56]. Все эти методы являются централизованными и неприменимы для мультиагентных систем. В связи с этим, разработан новый метод мультиагентной кластеризации, позволяющий «разбивать» коллектив роботов на отдельные группы (кластеры), причем число этих кластеров заранее неизвестно.
Разработанный алгоритм содержит несколько шагов. Шаг 1. Каждый агент с помощью сообщения-запроса определяет свих «соседей» и подсчитывает их количество. Для данного агента «соседями» являются те агенты, с которыми он может обмениваться информацией. Шаг 2. Каждый агент-робот выбирает из списка своих «соседей» лидера - агента с наибольшим количеством «соседей». В частном случае агент может стать лидером сам для себя. Шаг 3. Если агент является лидером хотя бы для одного агента за исключением себя, то он сам для себя становится лидером. Шаг 4. Если агент является лидером только для себя, но имеет «соседей»-лидеров, то для него лидером становится тот «сосед», который является лидером для большего числа агентов. В результате коллектив роботов разбивается на группы, в каждой из которых определен агент-лидер. Тогда внутри каждой сформированной группы можно использовать разработанный мультиагентный алгоритм распределения задач.
Построение картограммы заражения рабочей зоны
Здесь X - оценка фазового вектора X на этапе экстраполяции, Р ковариационная матрица ошибки на этапе экстраполяции, Хк - оценка фазового вектора X на этапе коррекции, Рк - ковариационная матрица ошибки на этапе коррекции. В начальный момент времени координаты фазового вектора определяются методом триангуляции. Этап экстраполяции выполняется по показаниям энкодеров ведущих колес.
Этап коррекции в момент измерений ( = tk): отклонение полученного на шаге к наблюдения от наблюдения, ожидаемого при произведенной экстраполяции: Zk = Zk — Н Хк; ковариационная матрица для вектора отклонения: Sk = Н Рк НТ + N; оптимальная по Калману матрица коэффициентов усиления, формирующаяся на основании ковариационных матриц имеющейся экстраполяции вектора состояния и полученных измерений (посредством ковариационной матрицы вектора отклонения): Kk = Pk-H-S1; коррекция ранее полученной экстраполяции вектора состояния -получение оценки вектора состояния системы: Хк = Хк + Кк Zk; расчет ковариационной матрицы оценки вектора состояния системы: Рк = (I — Кк - Н)Рк.
Фильтр Калмана в данном случае работает следующим образом. Между отдельными измерениями оценка фазового вектора робота определяется интегрированием уравнений объекта (этап экстраполяции). А в моменты измерения происходит скачкообразное изменение оценки (этап корректировки). Это значение используется в качестве начального условия на следующем этапе экстраполяции.
В качестве уравнений объекта использованы уравнения (3.5) кинематики мобильного робота без учета проскальзывания. Системы уравнений (3.5) и (3.6) являются нелинейными. Данную проблему можно решить разными способами: представить систему как линейную или использовать расширенный фильтр Калмана, где вместо матриц объекта и измерений используются их матрицы Якоби в момент измерений.
В данной работе предложен альтернативный вариант. Курсовой угол робота измеряется установленным на борту электронным компасом, обладающим высокой точностью. Погрешность компаса настолько мала (± 0.5 ), что измеряемое им в каждый момент времени значение курсового угла можно считать истинным. В этом случае кинематика робота описывается двумя линейными дифференциальными уравнениями: х = (а)г + а)1)С(р г (3-7) у = - (а)г + (tiuSy Здесь фазовый вектор X(t) = ( , . I; матрица объекта А = ( J; вектор функция F(t) = г ; коэффициенты С , 5ф это соответственно косинус и синус измеренного значения курсового угла ср. Погрешность полученных теоретических значений X(t) координат определяется погрешностью тг энкодеров, установленных на борту робота. Матрица Q (t) имеет вид: г2 2 г2 — ,г 2 Q(t) = а, Г2 г2 : Триангуляционные измерения (3.6) являются нелинейными функциями координат робота. Вектор измерений: Zk = h(Xk) + rjk, где вектор h(Xk) = іі( ,у)\ І. В связи с этим решено использовать расширенный фильтр Кал мана. Тогда матрица измерений имеет вид: dhx(x,y) \ як дУ dhm(x,y) Хк к fdh x.y) дх Нъ = dhm(x,y) ду xj \ дх Таким образом, получены все данные, необходимые для построения фильтра.
Одна из проблем, возникающих при построении такой навигационной системы, - это определение числа измерений, необходимого для обеспечения требуемой точности вычисления координат. Для решения этой задачи проведено моделирование работы фильтра с различным числом измерений {т = 3...10). Оценивание координат робота проводилось в течение 10 с. Измерения выполнялись с интервалом 0.5 с. Точность измерений Jg=2м. На рисунках 3.12-3.17 приведены результаты моделирования. Синим цветом представлено теоретическое значение координат робота, полученное 100 интефированием уравнений (3.7), красным - оценки координат, полученные с помощью фильтра Калмана (рис. 3.12, 3.13, 3.15, 3.16). На рис. 3.14 и 3.17 приведены фафики ошибок оценок координат роботов при т = 3 и т — 10 соответственно.
Похожие диссертации на Система управления коллективом мобильных роботов
-
