Электронная библиотека Веда
Цели библиотеки
Скачать бесплатно
Доставка литературы
Доставка диссертаций
Размещение литературы
Контактные данные
Я ищу:
Библиотечный каталог российских и украинских диссертаций

Вы находитесь:
Диссертационные работы России
Технические науки
Роботы, мехатроника и робототехнические системы

Диссертационная работа:

Капустян Сергей Григорьевич. Методы и алгоритмы коллективного управления роботами при их групповом применении : диссертация ... доктора технических наук : 05.02.05 / Капустян Сергей Григорьевич; [Место защиты: ГНУ "Южный федеральный университет"]. - Ростов-на-Дону, 2008. - 310 с. : 67 ил.

смотреть содержание
смотреть введение
Содержание к работе:

ВВЕДЕНИЕ 5

1 Метод коллективного управления групповым взаимодействием роботов 20

1.1 Проблема группового управления 20

1.2 Анализ известных подходов к решению проблемы группового управления роботами 22

1.2.1 Управление группами роботов в стационарных условиях 23

1.2.2 Управление группами роботов в сложных нестационарных средах 26

1.2.3 Управление группами роботов в условиях противодействия 33

1.2.4 Управление большими группами роботов 36

1.3 Формальная постановка задачи группового управления роботами 39

1.3.1 Задача управления одиночным роботом 39

1.3.2 Задача управления группой роботов 42

1.3.3 Классификация задач группового управления по уровню сложности 46

1.4 Способы организации систем группового управления роботами 52

1.4.1 Стратегии группового управления 52

1.4.2 Классификация систем группового управления роботами 55

1.4.3 Централизованные системы группового управления роботами 56

1.4.4 Распределенные системы группового управления роботами 58

1.4.5 Иерархическая организация подсистем планирования групповых действий роботов 59

1.5 Метод коллективного управления групповым взаимодействием роботов 64

1.5.1 Принципы коллективного управления группами роботов 64

1.5.2 Формулировка задачи коллективного управления группой роботов 65

1.5.3 Итерационная процедура оптимизации коллективных действий в группе роботов 71

1.6 Исследование итерационной процедуры оптимизации коллективных действий в группах роботов 75

1.6.1 Оценка числа итерационных циклов 75

1.6.2 Условия оптимальности коллективных действий, получаемых с помощью итерационной процедуры 77

1.6.3 Условия устойчивости итерационной процедуры оптимизации коллективных действий группы роботов 81

1.7 Выводы 83

2 Алгоритмическая реализация метода коллективного управления при решении задач распределения заданий (целей) в группах роботов 85

2.1 Постановка задачи коллективного распределения целей 85

2.2 Алгоритмы коллективного улучшения плана 87

2.3 Алгоритмы приближенного решения задач коллективного распределения целей в группах роботов 102

2.4 Сравнительный анализ алгоритмов коллективного распределения целей 112

2.5 Распределение целей в группах боевых роботов 116

2.5.1 Задача нанесения максимального ущерба противнику 116

2.5.2 Задача покрытия площади 120

2.5.3 Программная модель задачи покрытия площади 130

2.6 Алгоритмы распределения заданий в группе складских роботов 134

2.6.1 Задача организации коллективного взаимодействия в группе складских роботов 134

2.6.2 Итерационный алгоритм распределения заданий в группе складских роботов 139

2.6.3 Экспериментальные результаты 143

2.7 Выводы 145

3 Методы и алгоритмы группового управления в условиях противодействия противника 146

3.1 Виртуальный футбол 146

3.1.1 Организация и правила игры 146

3.1.2 Формулировка задачи группового управления роботами при игре в виртуальный футбол 149

3.1.3 Метод и алгоритм выбора и оптимизации коллективных действий при игре роботов в футбол 160

3.1.4 Программная реализация метода коллективного управления при игре в виртуальный футбол 163

3.2 Групповое управление в условиях боевых действий 169

3.2.1 Постановка задачи 169

3.2.2 Организация коллективных действий в условиях боестолкновения 171

3.2.3 Программная модель организации коллективного взаимодействия в условиях боестолкновения , 176

3.3 Стайные принципы управления группой роботов 179

3.3.1 Постановка задачи стайного управления группой роботов 181

3.3.2 Алгоритм оптимизации действий робота в составе стаи 182

3.3.3 Программная реализация модельной задачи стайного управления группой роботов 184

3.4 Выводы 191

4 Методы и алгоритмы коллективного управления в больших группах роботов 193

4.1 Проблема управляемости в больших группах роботов 193

4.2 Методы кластеризации больших групп роботов 197

4.2.1 Метод иерархической кластеризации больших групп роботов 198

4.2.2 Разбиение больших групп роботов на непересекающиеся кластеры постоянного состава 198

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

4.2.4 Метод динамической кластеризации 200

4.2.5 Метод разбиения больших групп роботов на пересекающиеся кластеры постоянной численности и переменного состава 200

4.3 Иерархическая кластеризация 201

4.4 Последовательная кластеризация 210

4.5 Безрезервная последовательная кластеризация 217

4.6 Динамическая кластеризация 221

4.7 Метод пересекающихся кластеров 228

4.8 Выводы 238 5 Методы и алгоритмы управления отдельным роботом группы при реализации коллективных действий 240

5.1 Комплекс задач, решаемых системой управления отдельного мобильного робота в группе 240

5.2 Графовое представление пространства состояний мобильного робота 242

5.3 Метод управления мобильным роботом на основе однородной нейроподобной структуры 254

5.4 Иерархическая реализация метода управления мобильным роботом 258

5.5 Экспериментальные исследования систем управления мобильных роботов на основе однородных нейроподобных структур 278

5.6 Выводы 283

ЗАКЛЮЧЕНИЕ 285

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 288

ПРИЛОЖЕНИЕ А. Модельные примеры решения задачи коллективного распределения целей в группах роботов 306

ПРИЛОЖЕНИЕ Б. Примеры решения задач кластеризации больших групп роботов 342

ПРИЛОЖЕНИЕ В. Имитационные программные модели функционирования интеллектуальных роботов в виртуальной среде 350

ПРИЛОЖЕНИЕ Г. Акты внедрения и использования результатов диссер тационной работы 362 

Введение к работе:

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

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

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

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

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

Основные исследования в области управления группами роботов ведутся во многих индустриально развитых странах мира, прежде всего в интересах обороны. Наиболее интенсивный характер этих работ применительно к направлению военной робототехники наблюдается в США по линии Управления перспективных исследова-

ний Министерства обороны США ДАРПА (DARPA - Defense Advanced Research Projects Agency). Здесь следует выделить программу "Распределенные робототехниче-ские системы", которая финансировалась этим агентством и выполнялась рядом ведущих университетов и научно-исследовательских организаций США .

В настоящее время разработке методов организации взаимодействия в группах роботов на основе децентрализованного способа управления посвящены исследования, проводимые под патронажем управления DARPA в рамках программ "Программное обеспечение для распределенных робототехнических систем" (Software for Distributed Robotics (SDR)), "Программное обеспечение автономных мобильных роботов" (Mobile Autonomous Robot Software (MARS)) и MARS-2020.

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

Решением проблемы группового управления занимались многие известные ученые, в нашей стране - И.М. Макаров, Д.Е. Охоцимский, Е.П. Попов, Е.И. Юревич, И.А. Каляев, В.Е. Павловский, А.В. Тимофеев и др., за рубежом - Т. Фукуда, Т. Балч, Р. Аркин, М. Матарик, М. Диас, М. Велосо и др.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Научная новизна полученных результатов заключается в следующем:

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

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

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

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

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

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

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

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

Наиболее существенные новые научные положения и результаты, выдвигаемые для защиты:

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

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

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

алгоритмическая реализация метода коллективного управления при решении задач распределения заданий (целей) в группах роботов;

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

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

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

Достоверность и обоснованность полученных в диссертационной работе ре-

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

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

Практическая ценность работы. Практическое использование научных результатов позволяет:

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

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

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

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

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

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

Реализация и внедрение результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении госбюджетных и хоздоговорных НИОКР в НИИ МВС ТРТУ (НИИ МВС ЮФУ), научным руководителем, ответственным исполнителем и непосредственным участником которых являлся

автор диссертации. Результаты диссертационной работы внедрены в НИИ МВС ЮФУ (г. Таганрог), НИИ специального машиностроения МГТУ им. Н.Э. Баумана (г. Москва), ОАО "ВНИИ ТРАНСМАШ" (г. Санкт-Петербург), ОАО "СКБ "Точрадиомаш" (г. Майкоп), Секции прикладных проблем при Президиуме РАН, ГОУ ВПО "Московский государственный институт электронной техники (технический университет)", войсковой части 93603 (г. Москва).

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на ряде научно-технических конференций, в том числе: на 14-и международных конференциях и с международным участием, на 7-й всесоюзных, всероссийских конференциях и молодежных научных школах, среди них: 14-th Workshop on Distributed Control Systems. - Seoul, Korea, July 1997; VII, VIII и IX научно-технических конференциях "Экстремальная робототехника", С.-Петербург, 1996, 1997 и 1998 г.г.; Всероссийской научно-технической конференции "Новые технологии управления робо-тотехническими и автотранспортными объектами", г. Ставрополь, 1998 г.; The 4-th ECPD Inter. Conference on Advanced Robotics Intelligent Automation and Active System Proceedings, Moscow, Russia, 1998; Международной конференцией "Интеллектуальные многопроцессорные системы (ИМС'99)", Таганрог, 1999 г.; IARP Int. Workshop on Micro Robots, Micro Mashines and Systems. Moscow, Russia, nov. 24-25, 1999; Молодежной научной школе "Интеллектуальные робототехнические системы", пос. Див-номорское, Геленджик, 2001 г.; Международной научно-технической конференции "СуперЭВМ и многопроцессорные вычислительные системы" (МВС'2002), г. Таганрог, 2002г.; Первой научной молодежной школе "Интеллектуальные роботы" (ИР-2002), п. Кацивели, Крым, Украина, 2002г.; Юбилейной Международной конференции по нейрокибернетике "Проблемы нейрокибернетики", посвященной 90-летию со дня рождения профессора А.Б. Когана, г. Ростов-на-Дону, 2002 г.; Международных конференциях "Интеллектуальные и многопроцессорные системы", пос. Дивномор-ское, Геленджик, 2003 г. и 2005 г.; Научной молодежной школе "Экстремальная робототехника - 2003", пос. Дивноморское, Геленджик, 2003 г.; Первой Всероссийской конференцим с международным участием "Мехатроника, автоматизация, управление", г. Владимир, 2004 г.; Международных научных конференциях "Искусственный интеллект. Интеллектуальные и многопроцессорные системы" (ИМС-2004 и ИМС-2006), п. Кацивели, Крым, Украина, 2004 г., 2006 г; Международной научной молодежной школе "Микросистемная техника", п. Кацивели, Крым, Украина, 2004 г.; IX

Международной конференции "Устойчивость, управление и динамика твердого тела", г. Донецк, Украина, 2005 г.; Международной научно-технической выставке-конгрессе "Мехатроника и робототехника (МиР-2007)", г. Санкт- Петербург, 2007 г.; Международной научно-технической конференции "Мехатроника, автоматизация и управление - 2007 (МАУ-2007)", пос. Дивноморское, Геленджик, 2007 г.

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

Публикации. По теме диссертации опубликовано 80 печатных работ, в том числе 2 монографии, 18 статей в центральной печати, из них 12 - в изданиях, входящих в "Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации", утвержденный ВАК.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и библиографического списка из 229 наименований. Диссертация содержит 376 страниц текста, 2 таблицы, 92 рисунка, 71 страницу приложений.

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

© Научная электронная библиотека «Веда», 2003-2013.
info@lib.ua-ru.net