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

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

04201 451 925

ПРОТАЛИНСКИЙ ИГОРЬ ОЛЕГОВИЧ

МОДЕЛИ И АЛГОРИТМЫ УПРАВЛЕНИЯ ГРУППОЙ МОБИЛЬНЫХ

РОБОТОВ

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

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель: кандидат технических наук доцент Щербатов И. А.

Саратов - 2013

Содержание

ВВЕДЕНИЕ.................................................................................................................................4

ГЛАВА 1. СИСТЕМНЫЙ АНАЛИЗ ПРОЦЕССА УПРАВЛЕНИЯ ГРУППАМИ РОБОТОВ В СТАЦИОНАРНЫХ УСЛОВИЯХ....................................................................10

1.1 .Описание процесса управления группами мобильных роботов...........................10

1.2. Теоретико-множественное системное моделирование группы мобильных роботов...................................................................................................................................14

1.3. Модели, алгоритмы и методы группового управления роботами.........................17

1.4. Постановка задачи исследования..............................................................................29

Выводы и результаты по первой главы..............................................................................31

ГЛАВА 2. РАЗРАБОТКА МЕТОДИКИ ПОСТРОЕНИЯ МАТЕМАТИЧЕСКОЙ МОДЕЛИ РАБОЧЕЙ ЗОНЫ ГРУППЫ МОБИЛЬНЫХ РОБОТОВ...................................32

2.1. Разработка структуры математической модели рабочей зоны группы роботов.....32

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

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

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

Выводы и результаты по второй главе...............................................................................52

ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМОВ УПРАВЛЕНИЯ ГРУППОЙ МОБИЛЬНЫХ

РОБОТОВ ДЛЯ РЕШЕНИЯ МНОЖЕСТВА ВЗАИМОСВЯЗАННЫХ ЗАДАЧ С

ИСПОЛЬЗОВАНИЕМ МНОГОКОМПОНЕНТНОЙ МАТЕМАТИЧЕСКОЙ МОДЕЛИ.... 53

3.1.Исследование показателей эффективности управления группой мобильных роботов...................................................................................................................................53

3.2 Алгоритмизация процесса формирования управляющего воздействия для группы мобильных роботов...............................................................................................................56

3.2.1 Анализ методов многокритериальной оптимизация для решения задачи управления группой роботов...........................................................................................57

3.2.2 Система ограничений процесса поиска Парето-оптимального управления........58

3.2.3. Построение множества стратегий для группы мобильных роботов.................63

3.2.4. Решение задачи оптимизации управления группой мобильных роботов.........66

3.3. Алгоритмы процесса поиска Парето-оптимального управляющего воздействия группы мобильных роботов.................................................................................................69

3.4. Формализация взаимодействия роботов в группе при поиске Парето-оптимального

множества стратегий............................................................................................................72

3.5 Разработка архитектуры системы управления группой роботов...............................76

Выводы и результаты по третьей главе..............................................................................79

4. РАЗРАБОТКА СИСТЕМЫ УПРАВЛЕНИЯ ГРУППОЙ МОБИЛЬНЫХ РОБОТОВ........80

4.1. Техническая реализация системы управления группы роботов...............................80

4.2 Реализация взаимодействия роботов группы...............................................................83

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

4.4. Оценка эффективности системы управления группой мобильных роботов...........90

Выводы и результаты по четвертой главе..........................................................................94

ЗАКЛЮЧЕНИЕ........................................................................................................................95

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

ПРИЛОЖЕНИЯ......................................................................................................................105

ПРИЛОЖЕНИЕ 1.ХАРАКТЕРИСТИКИ ЭЛЕМЕНТНОЙ БАЗЫ АРХИТЕКТУРЫ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ РОБОТА..................................................................106

ПРИЛОЖЕНИЕ 2. МАТЕРИАЛЫ ОБ ИСПОЛЬЗОВАНИИ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОГО ИССЛЕДОВАНИЯ.................................................................108

ПРИЛОЖЕНИЕ 3.Свидетельство о государственной регистрации программы..........111

ВВЕДЕНИЕ

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

20,00 18,00 16,00 14,00 12,00 10,00 8,00 6,00 4,00 2,00 0,00

■ промышленные роботы ■ Бытовые роботы

Щ К

17,00

Кг'--¿9 ??;

7,30 10цшш ЕзЕ

И,50! 1*1.205

[_0 95 л № 8-1.00.

2006 2007 2008 2011

Рисунок 1. Тенденция роста количества роботов в мире

Количество роботов за период 2008-2011 год возросло в два раза с 8,6 до 18,2 млн. по данным [86]. При этом количество промышленных роботов в период 2008-2011 год снизилось, что обуславливается сложной экономической ситуацией в мире, но при этом мобильных роботов возросло более чем в 2,5 раза. Данный факт обуславливается повсеместным внедрением мобильных роботов для транспортировки деталей на промышленных объектах, вследствие резкого снижения цены и повышения грузоподъемности данного типа устройств. Однако аналитики утверждают, что в ближайшем времени рост спроса на мобильные робототехнические устройства может резко замедлится, так же как и на роботы-манипуляторы.

Расширение сфер применения мобильных роботов в промышленности и быту приводит к необходимости использования групп роботов ввиду неэффективности решения комплексных задач одиночным устройством [3].

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

Группа роботов является сложной системой; эффективность выполнения ею задач характеризуется двумя основными технико-экономическими показателями: скорость выполнения задачи и затраченные на это ресурсы, которые определяются качеством управления группой мобильных роботов [15].

Основные результаты исследований в области группового управления мобильными роботами содержатся в работах российских ученых Юревич Е.И., Каляев И.А., Капустян С.Г., Каляев A.B., Занкевич С.Л., а так же зарубежных ученых Brumitt B.L., Funato D., Conn, N.R., Stenz A., Dias M.B.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практическая ценность работы:

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

- создано программное обеспечение системы управления децентрализованной одноранговой группой мобильных роботов, позволяющая повысить эффективность решения множества взаимосвязанных задач [11];

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты работы обсуждались на Международных научно-технических конференциях: «Математические методы в технике и технологиях» (Саратов, 2010; Харьков, 2012, Нижний Новгород, 2013); «International congress on information technologies-2012» (Саратов, 2012), «Наука вчера, сегодня, завтра» (Новосибирск, 2013).

Исследования поддержаны Фондом содействия развитию малых форм предприятий в научно-технической сфере по программе «СТАРТ» (2012 гг.).

Сконструированные в рамках исследования роботы принимали участие во Всероссийских соревнованиях «Робофест-2011/2012/2013», на которых заняли призовые места и победили в конкурсе «National Instruments».

Публикации. Основные результаты диссертационной работы изложены в 11 публикациях, в том числе 3 статьях в центральных научно-технических журналах, рекомендуемых ВАК РФ, 1 статья в научно-техническом журнале, аккредитованном в системе рецензирования «Scopus», в 5 трудах Международных научных конференций, получено 1 свидетельство об официальной регистрации программы для ЭВМ. Без соавторства опубликовано 2 работы.

Структура и объем работы. Диссертационная работа состоит из введения, 4 глав, выводов и списка литературы. Основная часть работы изложена на 111 страницах, содержит 33 рисунка, 6 таблиц, список литературы, состоящий из 118 наименований публикаций отечественных и зарубежных авторов, и приложения.

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

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

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

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

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

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

ГЛАВА 1. СИСТЕМНЫЙ АНАЛИЗ ПРОЦЕССА УПРАВЛЕНИЯ ГРУППАМИ РОБОТОВ В СТАЦИОНАРНЫХ УСЛОВИЯХ.

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

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

Групповое управление - это глобальная проблема, актуальная для многих