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

Краткое описание

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное агентство по образованию РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
’ ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ”
На правах рукописи
Ю5.20 0.8 009 68 -
КАПУ СТЯН Сергей Григорьевич
’’МЕТОДЫ И АЛГОРИТМЫ КОЛЛЕКТИВНОГО УПРАВЛЕНИЯ
РОБОТАМИ ПРИ ИХ ГРУППОВОМ ПРИМЕНЕНИИ”
Специальность: 05.02.05 - Роботы, мехатроника и
робототехнические системы
Диссертация на соискание ученой степени доктора технических наук
Научный консультант:
член-корреспондент РАН, доктор технических наук, профессор Каляев И.А.
Таганрог - 2008

2
СОДЕРЖАНИЕ
стр.
ВВЕДЕНИЕ 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

85
87
102
112
116
116
120
130
134
134
139
143
145
146
146
146
149
160
163
169
169
171
176
179
181
182
184
191
193
З
Постановка задачи коллективного распределения целей
Алгоритмы коллективного улучшения плана
Алгоритмы приближенного решения задач коллективного
распределения целей в группах роботов
Сравнительный анализ алгоритмов коллективного распределения
целей
Распределение целей в группах боевых роботов
Задача нанесения максимального ущерба противнику
Задача покрытия площади
Программная модель задачи покрытия площади
Алгоритмы распределения заданий в группе складских роботов
Задача организации коллективного взаимодействия в группе
складских роботов
Итерационный алгоритм распределения заданий в группе складских роботов Экспериментальные результаты Выводы
Методы и алгоритмы группового управления в условиях противодействия противника Виртуальный футбол Организация и правила игры
Формулировка задачи группового управления роботами при игре в виртуальный футбол
Метод и алгоритм выбора и оптимизации коллективных действий при игре роботов в футбол
Программная реализация метода коллективного управления при игре в виртуальный футбол
Групповое управление в условиях боевых действий Постановка задачи
Организация коллективных действий в условиях боестолкновения Программная модель организации коллективного взаимодействия в условиях боестолкновения ,
Стайные принципы управления группой роботов Постановка задачи стайного управления группой роботов Алгоритм оптимизации действий робота в составе стаи Программная реализация модельной задачи стайного управления группой роботов Выводы
Методы и алгоритмы коллективного управления в больших группах роботов

4
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

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

ЗАКЛЮЧЕНИЕ
В диссертации решена актуальная научная проблема разработки методов и алгоритмов коллективного управления при групповом взаимодействии роботов. Данная проблема имеет важное народнохозяйственное значение, поскольку ее решение позволяет значительно расширить функциональные возможности и области применения робототехнических систем, сократить временные и финансовые затраты на создание систем группового управления роботами, заменить людей при выполнении опасных работ, например, в зонах техногенных и экологических катастроф, в боевых условиях, повысить производительность технологических процессов.
В процессе достижения основного научного результата диссертации были решены следующие задачи:
- проведен анализ существующих подходов к проблеме группового управления роботами, сделан вывод об отсутствии общей методологии решения данной проблемы;
- для решения указанной проблемы разработан метод коллективного управления роботами при их групповом взаимодействии и проведен анализ его эффективности;
- разработаны принципы организации распределенных систем управления группами роботов, реализующих метод коллективного управления;
- на основе метода коллективного управления разработаны алгоритмы распределения заданий (целей) в группах роботов, решающих общую групповую задачу;
- разработаны методы и алгоритмы управления большими группами роботов;
- разработаны методы и алгоритмы коллективного управления роботами в условиях противодействия со стороны противника;
- проведены экспериментальные исследования и анализ разработанных методов и алгоритмов;
- разработаны технические решения по реализации предложенных методов и алгоритмов, в том числе для автоматизированного склада;
- разработаны методы и алгоритмы управления отдельным роботом при отработке им коллективных действий в составе группы;
- проведены экспериментальные исследования разработанных методов и алгоритмов управления отдельным роботом.
Научная новизна диссертации заключается в том, что:
- впервые предложен подход к проблеме управления группами роботов,

286
основанный на принципах коллективного взаимодействия;
-разработан новый метод коллективного распределенного управления группой роботов, обеспечивающий по сравнению с известными централизованными методами снижение вычислительной сложности задачи группового управления не менее, чем в //раз (N — число роботов в группе);
- предложена оригинальная итерационная процедура оптимизации коллективных действий, позволяющая за число итерационных циклов, не превышающее числа роботов в группе, найти для каждого робота группы такое действие, которое бы являлось оптимальным или близким к нему в смысле достижения общей групповой цели;
- разработаны новые алгоритмы коллективного распределения заданий (целей) в группах роботов, реализующие метод коллективного управления и обеспечивающие возможность решения данной задачи в реальном времени, во-первых, за счет снижения вычислительной сложности, по сравнению с известными алгоритмами, а во-вторых, за счет их децентрализованной реализации;
- разработаны методы и алгоритмы коллективного выбора действий в группах роботов, функционирующих в условиях организованного противодействия, отличающиеся тем, что они обеспечивают возможность принятия решений о коллективных действиях роботов в условиях дефицита времени;
- предложены новые методы и алгоритмы управления большими группами роботов, обеспечивающие их управляемость в реальном времени в условиях динамически изменяющихся сред;
- разработаны метод и алгоритмы управления отдельным роботом группы при отработке им коллективных действий, основанные на использовании однородных нейроподобных структур (ОНС) и отличающиеся возможностью выработки управляющих воздействий в реальном времени изменения ситуации в среде.
Практическая значимость полученных в диссертации научных результатов заключается в расширении функциональных возможностей и областей применения робототехнических систем за счет реализации методов и алгоритмов группового управления в режиме реального времени, а также сокращении сроков создания и финансовых затрат при создании систем управления группами роботов за счет снижения требований к программно-техническим средствам таких систем, повышения их надежности и живучести.
Практическое использование научных результатов позволило:
1) Повысить эффективность мобильных роботов специального назначения за счет группового применения и организации их коллективного

287
взаимодействия.
2) Решить проблему управляемости массово применяемых микророботов и микросистем военного назначения.
3) Снизить уровень риска для людей при ликвидации последствий техногенных катастроф и аварий, при проведении антитеррористических операций и т. п. за счет замены людей группами роботов.
4) Создать эффективную систему управления группой складских роботов, обеспечивающую повышение производительности автоматизированных складов промышленных предприятий на 20-30% за счет коллективной оптимизации распределения между складскими роботами технологических заданий и снижение требований к обслуживающему персоналу.
5) Повысить живучесть распределенных мультиплексных систем управления (МСУ) роботизированных транспортных средств (РТС) за счет обеспечения возможности перераспределения функций между исправными элементами системы в случае отказов с использованием разработанных алгоритмов коллективного распределения заданий (целей), а также повысить уровень унификации программно-технических средств базовых элементов МСУ и, соответственно, снизить затраты при монтаже системы не менее, чем 2-2,5 раза.
6) Обеспечить режим автономного функционирования в условиях пересеченной местности дистанционно-управляемых наземных робототехнических комплексов специального назначения.
7) Реализация технических решений, предложенных в диссертации, позволила в 2-2,5 раза сократить массогабаритные характеристики бортовых систем управления мобильных роботов.
Основные научные результаты диссертации опубликованы в работах [53— 56, 102, 164-168,170-176,182,183,185-197,204,209-216, 219, 220,222-229].
Предложенные в диссертационной работе новые решения строго аргументированы и критически оценены по сравнению с другими известными результатами. В диссертации приведены рекомендации по использованию полученных научных выводов. Полученные научные результаты практически используются на различных предприятиях и в организациях РФ, что подтверждается соответствующими актами о реализации.
Все научные результаты проведенных в диссертационной работе исследований, направленных на решение крупной научной проблемы разработки и создания методов коллективного управления в реальном времени группами роботов, функционирующими в сложных динамических средах, в том числе и большими, получены автором лично.