автореферат диссертации по машиностроению и машиноведению, 05.02.05, диссертация на тему:Система управления коллективом мобильных роботов

На правах рукописи

Рыжова Татьяна Павловна

СИСТЕМА УПРАВЛЕНИЯ КОЛЛЕКТИВОМ МОБИЛЬНЫХ

РОБОТОВ

Специальность 05.02.05 Роботы, мехатроника и робототехнические системы

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

МОСКВА-2013

005058760

Работа выполнена в Московском государственном техническом университете им Н.Э. Баумана

Научный руководитель:

кандидат технических наук, доцент Назарова Анаид Вартановна

Официальные оппоненты: - доктор технических наук, профессор

кафедры «Проблемы управления»

МГТУ МИРЭА

Манько Сергей Викторович

- доктор физико-математических наук, профессор, главный научный сотрудник ИПМ им. М.В. Келдыша РАН Павловский Владимир Евгеньевич

Ведущая организация:

ФБГУ ВНИИПО МЧС России

Защита состоится 11 июня 2013 года в 14 часов 30 минут на заседании диссертационного совета Д 212.141.02 при Московском государственном техническом университете им. Н.Э. Баумана по адресу: 105005, г. Москва, Госпитальный пер., д. 10, ауд. 613м.

Отзыв на автореферат в двух экземплярах, заверенный печатью организации, просим высылать по адресу: 105005, г. Москва, 2-я Бауманская ул., д. 5, МГТУ им. Н.Э. Баумана, учёному секретарю совета Д212.141.02.

С диссертацией можно ознакомиться в библиотеке МГТУ им. Н.Э. Баумана.

Телефон для справок: (499) 267-09-63

Автореферат разослан «_»_ 2013 г.

Учёный секретарь

диссертационного совета кандидат технических наук, доцент

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

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

Сегодня в России проблемами мультиагентного управления занимаются такие известные ученые, как: проф. В.И. Городецкий, проф. A.B. Тимофеев, проф. C.B. Манько, проф. В.М. Лохин, а также член-корр. РАН И.А. Каляев и проф. С.Г. Капустян. За рубежом наиболее известны работы В. Jleccepa, К. Декера и Ф. Коэна.

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

— анализ существующих подходов к решению проблемы группового управления мобильными роботами;

— выбор принципа построения МРТС, формирование ее состава и структуры системы управления;

— разработка методов и алгоритмов мультиагентного и централизованного управления коллективом роботов, выполняющим поисково-спасательные и ликвидационные операции;

— разработка алгоритмов формирования траекторий движения роботов;

— построение навигационной системы мобильного робота;

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

Методы исследования. В работе использованы методы современной теории автоматического управления, бионические алгоритмы, методы группового управления, методы рекуррентной фильтрации Калмана; математическое и имитационное моделирование. На защиту выносятся

1. Модульный подход к построению системы управления МРТС.

2. Мультиагентный алгоритм разбиения коллектива роботов на группы.

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

4. Метод определения параметров зон химического заражения.

5. Алгоритм построения безопасных маршрутов эвакуации.

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

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

Реализация результатов работы. Материалы диссертации использованы в рамках НИР, проходившей в НУЦ «Робототехника» МГТУ им. Н.Э. Баумана. Создан программный пакет, реализующий разработанные методы и алгоритмы управления коллективом мобильных роботов.

Апробация работы. Основные результаты работы докладывались и получили положительную оценку на научных форумах: 12-й Всероссийской научно-практической конференции «Экстремальная робототехника» (Санкт-Петербург, 1 - 3 апреля 2009 г.); Международной конференции с элементами научной школы для молодежи «Экстремальная Робототехника» (Санкт-Петербург, 12 - 14 октября 2010 г.); 22-й Международной научно-технической конференции «Экстремальная робототехника» (Санкт-Петербург, 23 - 25 ноября 2011 г.); Российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» (Москва, 16— 19 апреля 2012 г.).

Публикации. Основное содержание работы отражено в 5 публикациях, из них 2 статьи опубликованы в журналах, входящих в перечень ВАК РФ.

Структура и объем работы. Диссертационная работа состоит из введения, 5 глав, заключения, библиографического списка, включающего 111 наименований, и приложений. Работа изложена на 184 листах машинописного текста, содержит 112 рисунков и 31 таблицу.

Краткое содержание работы

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

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

Выбран принцип построения МРТС, предназначенной для проведения поисково-спасательных и ликвидационных работ на химически опасных объектах. В настоящее время укрупнено выделяют три типа распределенных РТС - централизованные, децентрализованные и гибридные. Гибридная система - это комбинация централизованной и децентрализованной систем. Здесь декомпозиция глобальной задачи выполняется за счет обмена информацией между агентами, а обработка данных осуществляется управляющим центром. Гибридная система обладает достоинствами централизованных и децентрализованных систем и лишена большинства их недостатков. В связи с этим, разработанная МРТС построена по гибридному принципу.

Очерчен круг задач, решаемых данной робототехнической системой. МРТС должна повышать уровень безопасности персонала химически опасных объектов. Система проводит обследование рабочей зоны с целью выявления очагов химического заражения и определения их параметров, выполняет маркировку безопасных маршрутов эвакуации людей из зоны заражения (установку специальных опознавательных знаков - маркеров в узловых точках маршрута) и нейтрализует найденные очаги заражения.

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

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

управляющий |

ПШТР |

Мтктмми

— Бд»к формирования

Ллг*р1тии глаЛа.тым* (ыянкрииянмя

Бал и мтритчи

ворйСотъ-я

■ифарчяима

Ь^ИВ Ц«рПЙД1КИ 1Ш1Ш

я ■э»яге<шимной мпфврмшша

КыраСяньа >ы|»ш1»,и>|1*

Сясииальвес

Иаяткямимяыг ■

ГШОНПК!

НПМППНЯПЧ-К

Рис. 1. Структура системы управления МРТС В функции человека-оператора входят выбор и назначение команд управления, а также наблюдение за состоянием системы.

Верхний уровень — управляющий центр включает блок формирования команд и блок обработки данных. Первый формирует последовательность команд в соответствии с указаниями оператора и текущим состоянием системы и передает их роботам. Блок обработки данных содержит базу данных и библиотеку методов и алгоритмов обработки информации. Информация, получаемая агентами-роботами и вспомогательным информационно-измерительным оборудованием, поступает в базу данных и обрабатывается с помощью библиотеки методов и алгоритмов. В результате формируется новая информация, которая заносится в базу данных. Это различные картограммы, прогнозы изменения состояния окружающей среды и т.п. На основе этих данных УЦ может сформировать новое задание для коллектива роботов.

Второй уровень отвечает за декомпозицию глобальных задач, решаемых МРТС, на более простые задачи и распределение этих задач между роботами. В основе разработанных мультиагентных алгоритмов декомпозиции лежит модель переговоров «аукцион», позволяющая агентам-роботам обмениваться информацией. Результатом работы такого алгоритма является выбор задания для каждого робота.

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

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

Четвертый уровень - исполнительный. Здесь осуществляется выработка управляющих сигналов для роботов, навигационных датчиков, специального и вспомогательного оборудования.

Во второй главе представлены разработанные алгоритмы глобального планирования - алгоритмы разбиения коллектива роботов на группы и распределения задач в группах роботов. Эти алгоритмы реализуют второй уровень системы управления МРТС (рис. 1) и необходимы для решения задач обследования рабочей зоны, маркировки безопасных маршрутов эвакуации и нейтрализации очагов химического заражения.

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

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

Суть «ценового» алгоритма заключается в следующем. Предположим, что в состав МРТС входит п одинаковых роботов; т — число задач. Для решения -й задачи требуется п;-(/ = 1...т) роботов. Например, Пу = 1V/ € [1,тп] (в случае, если п^ > 1, распределение задач выполняется аналогично). Каждой /-й задаче, выполняемой 1-м роботом, ¿ = 1 ...л; } = 1...Тп, ставится в соответствие величина <Г1; - «стоимость» (или «цена») выполнения этим роботом данной задачи, например, время выполнения или энергозатраты. Управляющий центр должен распределить задачи в коллективе роботов таким образом, чтобы соответствующие значения «цен» стремились к минимально возможным значениям (рис. 2). Для каждого робота управляющий центр формирует «ценовой» массив, включающий «стоимости» выполнения данным роботом каждой задачи. В результате формируется таблица 1, характеризующая возможности коллектива роботов.

Таблица 1. Возможности коллектива роботов

Рис. 2. Централизованное распределение задач в коллективе

Робот\ Задача 1 2 т

1 Си — -

2 С.2, с„ -

3 С31 - С*3т

п - - г

Если число роботов меньше количества задач (п < т)у то управляющий центр для каждого робота выбирает наименее «затратную» задачу. При этом оставшиеся т — п задач распределяются между освободившимися роботами после того, как они выполнят задания.

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

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

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

Предположим, коллектив состоит из п роботов. Каждый робот может выполнять одну или несколько задач из заданного списка типов задач 7. Глобальная задача разделена на т более простых задач. Для решения каждой /-Й задачи требуется ¡у роботов, где у = 1 ...т. Су- «стоимость» выполнения /"м роботом /-й задачи, /' - 1...п. В качестве «стоимости» может рассматриваться, например, время, затраченное роботом на выполнение данной задачи (рис. 3).

Каждый агент-робот формирует свой ценовой массив. Один из роботов коллектива на каждом этапе аукциона становится лидером. Он выставляет на «торги» свою наилучшую (т.е. наименее затратную) задачу и посылает запрос остальным роботам «У кого эта задача также является наилучшей?».

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

распределение задач в коллективе

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

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

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

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

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

д Л простои агент ©

Ы! «С»с*ёи»

2.4 2

2 1.3, 9 3

3 2,4, *, 6. ? 3

4 1,3, ь 3

^ 3. 1 3 3

* 3,4, Т ¿ 3

* 3.3. С 3 3

1 5 1 5

9 г 1 2

Рис. 4. Разбиение коллектива роботов на группы В результате внутри каждой сформированной группы можно использовать рассмотренный ранее мультиагентный алгоритм распределения задач.

Третья глава посвящена разработке алгоритмов формирования траекторий движения роботов при выполнении поисково-спасательных и

ликвидационных работ. Это алгоритмы перемещения роботов к целевым точкам в среде с препятствиями и равномерного распределения коллектива роботов в рабочей зоне (третий уровень системы управления МРТС, рис. 1).

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

Пусть п — число роботов, входящих в состав системы; т - количество целевых точек рабочего пространства; г — число статических препятствий в рабочей зоне. Каждый робот системы должен перемещаться к одной из целевых точек (у нескольких роботов может быть одна и та же целевая точка), избегая столкновений с другими роботами и статическими препятствиями. С рабочим пространством связана абсолютная система координат ХОУ. Координаты всех роботов и статических препятствий в каждый момент времени известны. Метод «потенциалов» в данной задаче использован в следующем виде. Роботам и статическим препятствиям приписаны отрицательные заряды, а целевым точкам - положительные. Вектор скорости притяжения /-го робота к целевой точке: У{, 1 = 1—71, векторы скоростей отталкивания /-го иу'-го роботов друг от друга: и Уц, / = 1 ...п, и вектор скорости отталкивания -го робота от р-го статического препятствия: р = 1 — Т, показаны на рис. 5.

Целевая тоича робота}

^ (?$> с— (Ш) ¿/-расстояние между /-м ' пртятстшг^^ц/ р0б0Х0м и его целевой

/ / точкой; - расстояние

/' между 7-м иJ-м роботами;

1 ровот/ п6'т1 расстояние между ;-м

роботом и р-м статическим Рис. 5. Скорости отталкивания и притяжения препятствием.

Таким образом, для /-го робота в каждый момент времени формируется значение V,- и направление его скорости 1р{.

п г

]=1 р=1

(1)

Модуль скорости У( определяется по формуле: V/ = Ут ■ где \гт -

максимальная скорость робота; д/- коэффициент относительного расстояния

f

между роботом / и его целевой точкой: д' = , где йтах - максимально

¿тах

возможное расстояние между объектами рабочей зоны (определяется геометрией рабочего пространства).

Аналогичным образом определяются модули скоростей и причем

( 0, если с1и > Я [ 0,если >

К - рекомендуемое безопасное расстояние между двумя роботами (определяется габаритами и скоростными характеристиками роботов).

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

При превышении рекомендуемого расстояния между двумя роботами или между роботом и статическим препятствием соответствующие скоростные составляющие равны нулю.

Проекции вектора скорости (1) робота на координатные оси рабочей

зоны:

= /и%х1'У1'х2'Уг> •••> г'пО'п)

Л = /"^О-Ч.У!, *2,3'2» -.*п<УгЛ хиУ( ~ координаты /-го робота в рабочей зоне. Величины и - это скоростные функции /-го робота, зависящие от координат всех роботов, входящих в состав коллектива.

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

г = ^ (2)

где 1 - 2X71 - матрица, 2= где ^ = - вектор

координат г-го робота; Р„ - 2Xп - матрица, Г,. = (/V,,Р^.-.-.Г,^)7", где Гп- = - вектор скоростных функций робота.

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

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

Роботы при их равномерном распределении должны стремиться к нахождению на расстоянии Я друг от друга. То есть, каждый робот должен либо отталкиваться от других роботов, либо притягиваться к ним, в зависимости от расстояния между ними (рис. 6).

Робот }

Ф

Робот1

/

/й> Робот >

У й;

ст(

^ \____у Робот/

Рис. 6. Взаимодействие роботов между собой Для г-го робота в каждый момент времени формируется значение и направление вектора его скорости как векторная сумма:

_ (3)

}=г Р=1

Модуль скорости = Ут ■ где ¥т - максимальная скорость робота;

коэффициент Цц относительного расстояния между роботами / и у зависит от расстояния между роботами:

гк ~ ¿а

-¿-.ест а1}<К

Я

¿1/-Д

К

, если (¿^ > Д

0,естй^ = /?

Для определения положения и ориентации роботов в неподвижной системе координат, связанной с рабочей зоной, разработана комбинированная навигационная система (третий уровень системы управления МРТС, рис. 1). В разработанной навигационной системе для повышения точности определения координат роботов применены методы рекуррентной фильтрации Калмана, где на этапе экстраполяции используются результаты интегрирования уравнений кинематики робота, а на этапе коррекции - измерения, полученные методом триангуляции.

В состав разработанной РТС входят четырехколесные мобильные роботы с двумя ведущими колесами. Предполагается, что проскальзывание колес отсутствует. Кинематическая модель мобильного робота представлена на рис. 7. Здесь (р - курсовой угол.

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

Рис. 7. Кинематическая модель мобильного робота

х = —(cor + «,) cos <p

Система уравнений (4) является нелинейной. В работе предложено следующее решение проблемы нелинейности. Курсовой угол робота измеряется установленным на борту электронным компасом, обладающим высокой точностью. Измеряемое им в каждый момент времени значение курсового угла можно считать истинным. В этом случае кинематика робота описывается двумя линейными дифференциальными уравнениями:

(у = + b>i)Sp

Тогда уравнения (5) - это уравнения объекта X(t) = A(t)-X(t) + F (t) + <f (t), где фазовый вектор X(t) = j; матрица объекта А = (jj ^ j; вектор-

/^(üJrC^ + OiC фСЛ функция F(t) = ; коэффициенты С, S - это

\"(wr(t) + (¿¡CtySyJ

соответственно косинус и синус измеренного значения курсового угла <р; <f(t) - случайное возмущение, которое воздействует на систему и имеет следующие характеристики:

(0)) = О, ЕЦ(О • f (т)т) = <2(0 • 5(t - г) Погрешность полученных теоретических значений X(t) координат определяется погрешностью о"( энкодеров, установленных на борту робота.

На этапе коррекции координаты робота

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

установленных в рабочем пространстве. Принцип метода триангуляции представлен на рис. 7.

Basotuii моЭуль 1

Вазовый модуль 2

Базовый модуль ;

Рис. 7. Определение координат робота методом триангуляции Координаты г'-го робота (хи у.) и координаты базовых модулей (хЬ1, З'ы, Ч2, Уьг, хьз. 3'ьз) связаны следующими уравнениями: ((*! ~ *м)2 + Су( - З'ы)2 =

| С*! - хЬ2)2 + ö-f - yb2)2 =

(б)

Решая эту систему уравнений, можно определить положение робота в неподвижной системе координат ХОУ, связанной с рабочей зоной. Точность вычисления координат повышается, если измерять расстояния между исследуемым роботом и большим количеством базовых модулей. При этом повышается вычислительная сложность процедуры определения координат. В реальных условиях система (6) не имеет решений, поскольку расстояния та, га, г(7 измеряются с некоторой погрешностью.

Из системы уравнений (6) видно, что триангуляционные измерения являются нелинейными функциями координат робота. Вектор измерений:

(К (*,у)\

=к(Хь) + т]к, где вектор = | ... I. В связи с этим решено

использовать расширенный фильтр Калмана. Тогда матрица измерений имеет вид:

/Э^Ся-.з-) Э/ц (х,зО[ \

Яь =

дх

дКОс.у) \ дх

ду д11т{х,у)

■Ч

к

д\>

СП

и

пч >¡0

I

М

Шум измерений представляет собой случайную 5-кореллированную нормально распределенную последовательность со следующими характеристиками:

ЕШ = 0, ' = N

Таким образом, получены все данные, необходимые для построения фильтра.

Одна из проблем, возникающих при построении такой навигационной системы, - это определение числа измерений, необходимого для обеспечения требуемой точности вычисления координат. Для решения этой задачи проведено моделирование работы фильтра с различным числом измерений (ти = 3...10). Оценивание координат робота проводилось в течение 10 с. Измерения выполнялись с интервалом 0.5 с. Точность измерений ад=2 м. На рис. 8 приведен результат работы фильтра Калмана при т = 3 (рис. 8, а) и при т = 10 (рис. 8, б).

Результаты моделирования

показали, что с ростом числа измерений т увеличивается точность оценки координат робота. При т = 3 в момент времени / = 10 с точность оценки координат составляет ±0.38 м.

1 1

4 1 /

1 1

1 !

Рис. 8. Оценка координаты у робота

В случае, когда т = 10, в момент времени / = 10 с точность оценки координат составляет ±0.198 м. Кроме того, проведенное моделирование показало, что фильтр Калмана сходится тем быстрее, чем больше значение т.

Таким образом, для обеспечения требуемой точности оценки координат робота (±0.3 м) достаточно шести измерений.

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

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

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

Основной принцип двумерной интерполяции по неупорядоченному набору данных заключается в следующем. На плоскости (ХОУ) задано п узловых точек, координаты которых =1...Я. Значения измерений

концентрации отравляющего вещества в этих точках - Р, (см. рис. 9). Необходимо определить значения концентрации = в каждой

точке заданной области (здесь т - число точек, в которых необходимо определить значение концентрации).

Значение концентрации отравляющих веществ в у'-й точке заданной области определяется по формуле:

^"(¿(^-гОЧС^-у,)2)2)

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

Полученную картограмму,

представляющую собой некую

поверхность 2 = /(х, у), необходимо предоставить оператору в удобной для понимания форме. В работе предложено строить двумерную цветную

(градиентную) картограмму.

*п

Рис. 9. Двумерная интерполяция по неупорядоченному набору данных

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

а б в

Рис. 10. Построение картограммы заражения по 100 узловым точкам

По полученной картограмме блок обработки данных управляющего центра определяет количество к и параметры очагов химического заражения: координаты эпицентров хг,уг (г = 1 ...к) очагов и площадь поверхности Бг.

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

Создается два массива: массив узловых точек картограммы (измеренные значения), в которых значение концентрации превышает заданное критическое значение Р^., и массив точек картограммы (значения, полученные в результате интерполяции), в которых значение концентрации превышает заданное критическое значение — Ркр). Второй массив

разбивается на кластеры, центры которых - это узловые точки из первого массива. Точка относится к тому кластеру, к центру которого она находится ближе всего. Если несколько узловых точек из первого массива являются соседними, то соответствующие кластеры объединяются. Соседними следует считать точки измерения, расстояние между которыми равно заданному шагу измерений Я. Каждый такой кластер - это очаг заражения. Его эпицентр находится как центр тяжести фигуры, образованной точками кластера.

На рис. 11 приведен результат работы алгоритма.

■г' шИ

■ • * * ДЩ.....

Картограмма заражения

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

превышена ни в одной точке найденного маршрута) основан на алгоритме Беллмана-Форда поиска кратчайшего пути во взвешенном графе.

В данном случае вершины графа - это узловые точки картограммы, в которых концентрация не превышает значение Р/-. Матрица В = {Ъу} -квадратная матрица s х s (,s - число вершин графа), которая характеризует перемещение из одной вершины графа в другую. Элементы этой матрицы определяются по формуле:

(dtj, если вершины, графа inj — соседние узловые точки картограммы

4 10,еыи вершины графа i и ¡не являются соседними узловыми точками Здесь d.j - расстояние между /-й и /-й узловыми точками картограммы.

На рис. 12 показан результат работы алгоритма. Найден кратчайший безопасный маршрут с гарантированной степенью безопасности Рк = 1.5. Найденные параметры очагов заражения и координаты точек безопасного маршрута являются исходными данными, необходимыми для выполнения коллективом роботов маркировки безопасных маршрутов эвакуации и нейтрализации очагов химического Рис. 12. Кратчайший заражения. безопасный маршрут

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

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

Вторая модель разработана в программном комплексе «V-Rep». Она представляет собой твердотельную динамическую модель коллектива мобильных роботов, входящих в состав МРТС. С помощью данной модели, учитывающей сенсорную систему роботов, на примере задачи

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

Кроме того, в главе

Рис. 13. Структура программной модели МРТС приведены аппаратные средства, которыми необходимо оснастить роботы, входящие в состав МРТС.

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

Основные результаты и выводы.

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

- Разработаны базовые алгоритмы централизованного и мультиагентного управления коллективом мобильных роботов: алгоритм разбиения коллектива роботов на группы и алгоритмы распределения задач в группе роботов.

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

- Построена комбинированная навигационная система, определяющая координаты роботов в рабочей зоне.

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

- Проведены экспериментальные исследования на компьютерных моделях. Эксперименты подтвердили работоспособность предложенных методов и алгоритмов.

Публикации.

1. Назарова A.B., Рыжова Т.П. Методы и алгоритмы мультиагентного управления робототехнической системой // Вестник МГТУ им. Н.Э. Баумана. Приборостроение. 2012. №6. С. 93 - 105.

2. Рыжова Т.П., Очкасов А.Е. Миниатюрная распределенная мобильная робототехническая система // Актуальные проблемы защиты и безопасности. Экстремальная робототехника: Труды XII Всероссийской научно-практической конференции. СПб., 2009. Т. 5., С. 174 - 176.

3. Рыжова Т.П. Миниатюрная распределенная робототехническая система. Алгоритмы управления коллективом роботов // Комплексная безопасность. Экстремальная робототехника: Труды XXI Международной научно-технической конференции. М., 2010. С. 189- 196.

4. Рыжова Т.П. Управление коллективом мобильных роботов // Экстремальная робототехника: Труды Международной научно-технической конференции. СПб., 2011. С. 281 - 287.

5. Рыжова Т.П. Мультиагентная робототехническая система. Формирование траекторий мобильных роботов // Технические и программные средства систем управления, контроля и измерения: Труды Российской конференции с международным участием. М., 2012. С. 1490 - 1498.

Подписано в печать 19.04.2013г.

Усл.п.л. - 1.0 Заказ №13320 Тираж: 100 экз.

Копицентр «ЧЕРТЕЖ.ру» ИНН 7701723201 107023, Москва, ул.Б.Семеновская 11, стр.12 (495) 542-7389 www.chertez.ru

Московский государственный технический университет им. Н.Э. Баумана

04201357634 На правах рукописи

Рыжова Татьяна Павловна Система управления коллективом мобильных роботов

Специальность 05.02.05 - роботы, мехатроника и робототехнические

системы

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель -кандидат технических наук, доцент Назарова А.В.

Москва-2013

Оглавление

Введение....................................................................................................................6

1. Анализ проблем и задач мультиагентного управления. Общая концепция построения МРТС...........................................................................13

1.1. Обзор существующих МРТС....................................................................13

1.2. Общие принципы построения мультиагентных систем........................16

1.3. Управление коллективом роботов...........................................................18

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. Централизованное распределение задач в коллективе роботов...........46

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

Список литературы..............................................................................................151

Приложение А. Мультиагентное распределение задач в группе

роботов. Программный код модели, разработанной в ПК AnyLogic.............162

Приложение Б. Исходный код программной модели МРТС..........................171

Приложение В. ПК «V-Rep». Твердотельная динамическая модель

МРТС. Скрипты...................................................................................................179

Приложение Г. Акты использования результатов работы..............................182

Список сокращений

РТС - робототехническая система

МРТС - мультиагентная робототехническая система

СУ - система управления

НИР - научно-исследовательская работа

ГА - генетический алгоритм

МРК - мобильный робототехнический комплекс

ПДК - предельно допустимая концентрация

БСС - беспроводная сенсорная сеть

БФК - блок формирования команд

БОД - блок обработки данных

Введение

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

Отдельный мобильный робот обладает ограниченными возможностями. У него малый радиус действия и небольшое число выполняемых функций. Поэтому, при решении сложных задач, целесообразным является одновременное применение нескольких роботов, т.е. распределенной робототехнической системы. Преимущества использования группы роботов очевидны. Во-первых, это больший радиус действия, во-вторых, расширенный набор выполняемых функций, и, наконец, более высокая вероятность выполнения задания, достигаемая за счет возможности перераспределения целей между роботами группы в случае выхода из строя некоторых из них [1].

При выполнении поисково-спасательных и ликвидационных операций требуется использовать робототехнические системы (РТС), в состав которых входит множество роботов различной «специализации». При этом должна быть организована их согласованная работа.

Проблемы группового управления и коммуникации, связанные с организацией "коллективного" поведения роботов, в настоящее время решаются с помощью мультиагентного управления [2].

Мультиагентные системы - это системы, состоящие из множества взаимодействующих агентов, коллективно решающих общую задачу. Понятие «агент» включает любые физические или виртуальные единицы, обладающие следующими свойствами [3]:

- коммуникабельность - способность обмениваться информацией с другими агентами;

- целенаправленность - направленность на достижение какой-либо цели;

- наличие ряда выполняемых функций;

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

- реактивность - способность к восприятию окружающей среды и способность строить частичные представления об этой среде на основе воспринимаемой информации;

- способность к самоорганизации.

Принцип действия мультиагентных систем основывается на декомпозиции общей задачи на ряд более простых задач, возлагаемых на агентов РТС - роботов, распределении этих задач между системами управления (СУ) агентов, планировании коллективного поведения агентов, координации взаимодействия агентов на основе кооперации, реконфигурации, коммуникации и разрешения конфликтных ситуаций [3].

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

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

В настоящее время в России в области мультиагентного управления работают такие известные ученые, как д.т.н., проф. В.И. Городецкий, д.т.н., проф. A.B. Тимофеев (Санкт-Петербургский институт информатики и автоматизации РАН), д.т.н., проф. C.B. Манько, д.т.н., проф. В.М. Лохин (Московский государственный технический университет радиотехники, электроники и автоматики), член-корреспондент РАН H.A. Каляев, д.т.н., проф. С.Г. Капустян (Научно-исследовательский институт многопроцессорных вычислительных систем им. Академика A.B. Каляева Южного федерального университета, г. Таганрог Ростовской области), к.т.н., доц. И.Е. Бурдун (Новосибирский государственный технический университет). За рубежом наиболее известными специалистами в области мультиагентных систем являются В. Лессер (Массачусетский технологический университет, США), К. Декер (Делаверский университет, США), Ф. Коэн (Орегонский университет здоровья и науки, США), Э. Дерфи (Мичиганский университет, США).

Целью данной диссертационной работы является разработка методов и алгоритмов мультиагентного и централизованного управления коллективом мобильных роботов, а также построение модульной системы управления МРТС, предназначенной для работы на химически опасных объектах.

Для решения сформулированной научной проблемы в работе поставлены и решены следующие задачи:

- анализ существующих подходов к решению проблемы группового управления мобильными роботами;

- выбор принципа построения МРТС;

- выработка требований к составу МРТС, предназначенной для выполнения поисково-спасательных и ликвидационных операций;

- построение системы управления МРТС;

- разработка алгоритмов мультиагентного и централизованного управления коллективом мобильных роботов;

- разработка алгоритмов формирования траекторий движения роботов;

- построение навигационной системы мобильного робота;

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

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

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

Во второй главе представлены разработанные мультиагентные и централизованные алгоритмы управления коллективом мобильных роботов (алгоритмы глобального планирования): алгоритмы распределения задач в группе роботов (мультиагентный алгоритм основан на модели переговоров «Аукцион») и алгоритм разбиения коллектива роботов на группы. Для проверки работоспособности проведено моделирование предложенных алгоритмов. Рассмотрено их практическое применение при решении коллективом роботов поисково-спасательных и ликвидационных задач на химически опасных объектах.

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

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

Пятая глава содержит материалы, подтверждающие результаты теоретических исследований. Разработан программный пакет, реализующий предложенные алгоритмы централизованного и мультиагентного управления коллективом роботов, алгоритмы формирования траекторий движения роботов, а также методы обработки получаемой роботами информации. В программном комплексе «У-Яер» разработана динамическая модель коллектива мобильных роботов, входящих в состав МРТС. С помощью данной модели проверена работоспособность предложенных алгоритмов локального планирования.

В заключении приведены основные результаты диссертационной работы.

На защиту выносятся:

- модульный подход к построению системы управления коллективом мобильных роботов;

- мультиагентный алгоритм разбиения коллектива роботов на группы;

- мультиагентный алгоритм распределения задач в группе роботов;

- централизованный алгоритм распределения задач в группе роботов;

- метод определения количества и параметров очагов химического заражения;

- алгоритм построения безопасных маршрутов эвакуации.

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

Практическая ценность. Разработанные методы и алгоритмы управления коллективом мобильных роботов могут быть применены в ситуациях, опасных для человека. Эти алгоритмы являются универсальными, обеспечивают высокое быстродействие системы. За счет перераспределения заданий и мониторинга текущей ситуации достигается «живучесть» всей МРТС в целом и устойчивость к изменению внешних условий. Модульный подход к построению системы управления и универсальность разработанных методов и алгоритмов позволяют использовать данные принципы в мультиагентных системах различного назначения.

Реализация результатов работы. Материалы диссертации использованы в рамках НИР, проходивших в НУЦ «Робототехника» МГТУ им. Н.Э. Баумана и в ООО «НПИП «Юнит» (акты об использовании результатов диссертационной работы приведены в приложении Г). Создан

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

Апробация работы. Основные результаты работы докладывались и получили положительную оценку на научных форумах: 12-й Всероссийской научно-практической конференции «Экстремальная робототехника» (Санкт-Петербург, 1 - 3 апреля 2009 г.); Международной конференции с элементами научной школы для молодежи «Экстремальная Робототехника» (Санкт-Петербург, 12 - 14 октября 2010 г.); 22-й Международной научно-технической конференции «Экстремальн