Содержание к диссертации
Введение
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
Список использованных источников
- Управление группами роботов в стационарных условиях
- Алгоритмы приближенного решения задач коллективного распределения целей в группах роботов
- Программная реализация метода коллективного управления при игре в виртуальный футбол
- Разбиение больших групп роботов на непересекающиеся кластеры постоянного состава
Введение к работе
Актуальность. Роботы используются во многих областях науки, техники и промышленности, в первую очередь там, где жизнедеятельность "человека либо затруднена, либо вообще невозможна, например, в зонах радиоактивного или химического загрязнения, в условиях боевых действий, при проведении подводных или космических исследований и т.п. Проблеме создания роботов различного назначения посвящено достаточно большое число исследований, проводимых как у нас в стране, так и за рубежом, начиная с середины 60-х годов прошлого века [1 - 16]. В результате этих исследований достаточно хорошо проработаны основные проблемы, с которыми приходится сталкиваться разработчикам при создании роботов, такие как распознавание объектов и сцен, формирование моделей окружающей среды, планирование маршрутов движения и последовательностей действий для достижения цели, управление движением с учетом динамики роботов и т.д.
В то же время стало понятно, что одиночный робот, каким бы интеллектуальным он ни был, может использоваться только для решения некоторых частных задач, либо выполнения довольно простых операций, поскольку он, как правило, обладает сравнительно малыми возможностями для выполнения поставленной задачи (небольшой радиус действия, ограниченный бортовым энергоресурсом; небольшое число выполняемых функций, ограниченное набором исполнительных устройств, невысокая вероятность выполнения поставленной задачи при функционировании в экстремальных ситуациях, поскольку выход из строя одиночного робота ведет к невыполнимости его миссии и т.п.).
Очевидным решением указанных выше проблем является применение при решении сложных задач сразу нескольких роботов, то есть групп роботов.
Преимущества группового применения роботов очевидны. Это и больший радиус действия, достигаемый за счет рассредоточения роботов по всей рабочей зоне; и расширенный набор выполняемых функций, достигаемый за счет установки на каждый робот индивидуальных исполнительных устройств; и, наконец, более высокая вероятность выполнения задания, достигаемая за счет возможности перераспределения целей между роботами группы в случае выхода из строя некоторых из них. Поэтому такие сложные задачи как, например, масштабное исследование и зондирование поверхности других планет, сборка сложных конструкций в космосе и под водой, участие в боевых и обеспечивающих операциях, разминирование территорий и т.п., могут быть эффективно решены роботами только при их групповом взаимодействии. При этом возникают новые проблемы группового управления и коммуникации, связанные с организацией группового взаимодействия роботов.
Особую важность проблема группового взаимодействия роботов прини мает в такой перспективной области современной робототехники, каковой является микроробототехника. Действительно, микророботы, как правило, обладают крайне ограниченными возможностями, и только их групповое или даже массовое (до нескольких десятков тысяч) применение может привести к эффективному решению поставленной перед ними задачи. Примером группового применения микророботов может служить так называемая "интеллектуальная пыль" [17], когда с самолета сбрасывается "туча" микророботов, каждый из которых должен выполнять некоторые простейшие функции, например, сбора информации о покрываемой территории или поражения объектов противника. При этом микророботы должны таким образом координировать свои действия, чтобы собрать информацию о как можно большей территории или нанести как можно больший урон противнику.
Основные исследования в области управления группами роботов ведутся во многих индустриально развитых странах мира, прежде всего в интересах обороны. Наиболее интенсивный характер этих работ применительно к направлению военной робототехники наблюдается в США по линии Управления перспективных исследований Министерства обороны США ДАРПА (DARPA - Defense Advanced Research Projects Agency). Здесь следует выделить программу "Распределенные робототехнические системы", которая финансировалась этим агентством и выполнялась рядом ведущих университетов и научно-исследовательских организаций США [18].
В настоящее время разработке методов организации взаимодействия в группах роботов на основе децентрализованного способа управления посвящены исследования, проводимые под патронажем управления DARPA в рамках программ "Программное обеспечение для распределенных робототехнических систем" (Software for Distributed Robotics (SDR)), "Программное обеспечение автономных мобильных роботов" (Mobile Autonomous Robot Software (MARS)) и MARS-2020.
При групповом применении роботов, решающих единую крупную целевую задачу, роботы должны определенным образом взаимодействовать друг с другом с тем, чтобы как можно более эффективно решить поставленную задачу в условиях сложной среды, когда ситуация может изменяться непредсказуемым образом. При этом понятно, что методы и алгоритмы планирования и управления групповыми действиями роботов должны изначально разрабатываться с учетом необходимости их реализации в реальном времени на основе бортовых вычислительных устройств. Чтобы достичь поставленной цели, группа роботов должна действовать как нечто единое целое, и действия каждого отдельного робота должны быть направлены на получение наибольшего группового эффекта. В работах, посвященных проблеме группового управления, такие действия часто называются командными, а по отношению к группам роботов, спо собных к такому взаимодействию, применяется термин "команда роботов" [19 — 38]. Ученые однозначно приходят к выводу, что командное взаимодействие может быть эффективно реализовано только с использованием методов децентрализованного (распределенного) управления [19 - 42].
Таким образом, актуальной является научная проблема группового управления интеллектуальными роботами, функционирующими автономно в условиях сложной, недетерминированной, динамической среды. Решение данной проблемы позволит, во-первых, значительно расширить области применения роботов, во-вторых, вплотную приблизиться к решению проблемы массового применения микророботов в составе больших групп, насчитывающих тысячи и десятки тысяч микророботов. Применение групп роботов, способных выполнять сложные работы, например, при ликвидации последствий природных или техногенных катастроф, рост числа которых наблюдается в последнее время, в свою очередь, позволит снизить риск для людей в условиях вредных или даже опасных сред, сократить затраты, связанные с обеспечением безопасности, увеличить производительность предприятий и т.п.
Решением проблемы группового управления занимались многие известные ученые, в нашей стране - И.М. Макаров, Д.Е. Охоцимский, Е.П. Попов, Е.И. Юревич, И.А. Каляев, В.Е. Павловский, А.В. Тимофеев и др., за рубежом -Т. Фукуда, Т. Балч, Р. Аркин, М. Матарик, М. Диас, М. Велосо и др.
Анализируя результаты исследований, можно сделать вывод об отсутствии в настоящее время какого-либо общего подхода к проблеме группового управления роботами. Каждая исследовательская группа пытается разработать свой способ решения стоящей перед ней частной задачи, который, как правило, не может быть применен при решении других задач подобного типа. Кроме того, большинство упомянутых выше проектов предполагает функционирование группы роботов в идеализированной (искусственно созданной) среде, в которой отсутствуют внешние, заранее неизвестные силы, способные влиять на ситуацию.
Отсутствие общей методологии решения задач, возникающих при групповом управлении роботами в заранее неизвестной и динамически изменяющейся среде, существенно ограничивает их реальное применение.
Настоящая диссертационная работа посвящена разработке новых подходов, которые могли бы быть использованы при решении широкого класса задач управления роботами, в том числе интеллектуальными, при их групповом применении в реальных средах.
В качестве основы может быть предложен подход, присущий социальным образованиям людей - коллективам, решающим одну коллективную задачу без командира или начальника, определяющего действия отдельных членов коллектива, и основанный на принципах коллективного управления. В таком кол лективе его члены самостоятельно определяют свои действия, направленные на достижение коллективной цели наилучшим в текущей ситуации образом. Реализация данных принципов требует разработки новых эффективных методов и алгоритмов группового управления роботами, ориентированных на использование распределенных систем управления.
Целью диссертационного исследования является расширение функциональных возможностей и областей использования, а также повышение эффективности применения роботов за счет их группового взаимодействия при решении сложных задач в условиях сложных недетерминированных динамических сред.
Научная проблема, решение которой содержится в диссертации, -разработка методов и алгоритмов распределенного (децентрализованного) управления коллективным взаимодействием роботов при их групповом применении в условиях сложных, заранее неизвестных динамически изменяющихся ситуаций.
В соответствии с поставленной целью для решения сформулированной научной проблемы определены задачи диссертации:
- провести анализ существующих подходов к проблеме группового управления роботами;
- разработать метод коллективного управления роботами при их групповом взаимодействии и провести анализ его эффективности;
- разработать принципы организации распределенных систем управления группами роботов, реализующих метод коллективного управления;
- на основе метода коллективного управления разработать алгоритмы распределения заданий (целей) в группах роботов, решающих общую групповую задачу;
- разработать методы и алгоритмы коллективного управления роботами в условиях противодействия со стороны противника;
- разработать методы и алгоритмы управления большими группами роботов, насчитывающими сотни и тысячи единиц;
- разработать методы и алгоритмы управления отдельным роботом при отработке им коллективных действий в составе группы;
- провести экспериментальные исследования и анализ эффективности разработанных методов и алгоритмов;
- разработать технические решения по реализации предложенных методов и алгоритмов при решении прикладных задач группового управления роботами.
Методы исследований. При проведении исследований были использованы: методы современной теории автоматического управления, методы оптимального управления, методы линейного программирования, элементы теории множеств и теории дискретных систем, методы вычислительного эксперимента, методы имитационного моделирования. Теоретические исследования подтверждены реализацией в реальных системах группового управления роботами и другими объектами.
Научная новизна полученных результатов заключается в следующем:
- предложен новый подход к решению проблемы управления группами роботов, отличающийся от известных тем, что он основан на принципах коллективного взаимодействия;
- разработан новый метод коллективного распределенного управления группой роботов, обеспечивающий по сравнению с известными централизованными методами снижение вычислительной сложности задачи группового управления не менее чем в Л раз (N— число роботов в группе);
- предложена оригинальная итерационная процедура оптимизации коллективных действий, отличающаяся тем, что ее использование позволяет за число итерационных циклов, не превышающее число роботов в группе, найти для каждого робота группы такое действие, которое бы являлось оптимальным или близким к нему в смысле достижения общей групповой цели;
- разработаны алгоритмы коллективного распределения заданий (целей) в группах роботов, реализующие метод коллективного управления и обеспечивающие возможность решения данной задачи в реальном времени, во-первых, за счет снижения вычислительной сложности по сравнению с известными алгоритмами, а, во-вторых, за счет их децентрализованной реализации;
- разработаны методы и алгоритмы коллективного выбора действий в группах роботов, функционирующих в условиях организованного противодействия, отличающиеся тем, что они обеспечивают возможность принятия решений о коллективных действиях роботов в условиях дефицита времени;
- предложены методы и алгоритмы управления большими группами роботов, насчитывающими сотни и тысячи единиц, обеспечивающие их управляемость в условиях динамически изменяющихся ситуаций;
- разработаны метод и алгоритмы управления отдельным роботом группы при отработке им коллективных действий, основанные на использовании однородных нейроподобных структур (ОНС) и отличающиеся возможностью выработки управляющих воздействий в реальном времени изменения ситуации в среде.
Наиболее существенные новые научные положения и результаты, выдвигаемые для защиты:
- новый подход к проблеме управления группами роботов, основанный на принципах коллективного взаимодействия;
- метод коллективного распределенного управления, позволяющий не менее чем в N (N - число роботов в группе) раз снизить вычислительную слож ность задачи группового управления роботами по сравнению с централизованными методами;
- итерационная процедура оптимизации коллективных действий, которая позволяет за число итерационных циклов, не превышающее числа роботов в группе, находить для каждого робота группы оптимальное или близкое к оптимальному действие для достижения общей групповой цели;
- алгоритмическая реализация метода коллективного управления при решении задач распределения заданий (целей) в группах роботов;
- метод и алгоритмы коллективного управления группами роботов при наличии противодействия со стороны противника;
- методы кластеризации больших групп роботов, обеспечивающие их управляемость при коллективном взаимодействии в условиях динамических, недетерминированных изменений ситуации;
- методы и алгоритмы решения задачи управления отдельным роботом группы при реализации им коллективных действий на основе ОНС.
Достоверность и обоснованность полученных в диссертационной работе результатов подтверждается полнотой и корректностью исходных посылок, теоретическим обоснованием, непротиворечивостью математических выкладок. Теоретические исследования подтверждены вычислительными экспериментами с использованием программных моделей, а также реализацией полученных научных результатов при создании систем группового управления различного назначения, в частности, систем группового управления складскими роботами, а также бортовых систем управления интеллектуальными мобильными роботами, способными функционировать в составе группы.
Научная значимость работы заключается в том, что разработаны и развиты теоретические основы коллективного управления роботами при их групповом взаимодействии в условиях динамических, недетерминированных ситуаций.
Практическая ценность работы. Практическое использование научных результатов позволяет:
- расширить функциональные возможности и области применения роботов за счет их группового применения;
- создать предпосылки к массовому применению микророботов за счет использования методов коллективного управления большими группами, а также снижения требований к массогабаритным характеристикам бортовых устройств управления микророботов и возможности их миниатюрного исполнения;
- повысить производительность автоматизированных складов, обслуживаемых группами роботов-штабелеров, на 20-30% за счет применения предложенных методов и алгоритмов, повысить безопасность складских операций, а также обеспечить сохранность грузов за счет исключения человека-оператора;
- повысить живучесть распределенных мультиплексных систем управления (МСУ) роботизированных транспортных средств (РТС) за счет обеспечения возможности перераспределения функций между исправными элементами системы в случае отказов, а также повысить уровень унификации программно-технических средств базовых элементов МСУ и, соответственно, снизить затраты при монтаже системы не менее, чем в 2-2,5 раза;
- обеспечить режим автономного функционирования в условиях пересеченной местности дистанционно-управляемых наземных робототехнических комплексов специального назначения.
Разработанные в рамках диссертации системы управления автоматизированным складом демонстрировались:
- на Первой специализированной выставке "Робототехника", г. Москва, ВВЦ, февраль 2004 г. (диплом и золотая медаль ВВЦ);
- на Второй специализированной выставке "Робототехника", г. Москва, ВВЦ, ноябрь 2004 г.
Реализация и внедрение результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении госбюджетных и хоздоговорных НИОКР в НИИ МВС ТРТУ (НИИ МВС ЮФУ), научным руководителем, ответственным исполнителем и непосредственным участником которых являлся автор диссертации.
Наиболее важными из них являются:
- "Разработка, исследование и макетирование нейроноподобной управляющей структуры, предназначенной для управления движением автономного робота в реальной среде", 1984- 1985 г.г., №ГР 01.83.0033262;
- "Разработка системы управления адаптивного автономного транспортного робота", 1987 - 1988 г.г., №ГР 01.86. 0064833;
- "Разработка аппаратных средств и алгоритмического обеспечения систем планирования поведения и адаптивного управления интеллектуальных роботов в сложных средах", 1991 - 1995 г.г., №ГР 01.9.30005780;
- "Разработка теоретических и практических основ построения интеллектуальных распределенных систем управления целенаправленным поведением коллективов микророботов", 1997 -1999 г.г., № ГР 01.9.70008000;
- "Поисковые исследования и разработка прототипов интеллектуальных систем автономного и группового управления боевыми и обеспечивающими роботами", 1999-2001 г.г., № ГР 01.20.0008196;
- "Разработка научно-технических основ построения систем управления коллективным взаимодействием массово применяемых микро- и биороботов", 2000 г., № ГР 01.2.00100685;
- "Разработка научно-технических основ построения систем управления коллективным взаимодействием массово применяемых микро- и биороботов", 2001-2003 г.г., № ГР 01.2.00104213;
- "Поисковые исследования и разработка научно-технических основ построения адаптивных систем управления взаимодействием микросистем и микророботов военного назначения", 2000-2004 г.г., № ГР 1601809;
- "Многопроцессорные ЭВМ с параллельной структурой в бортовых системах принятия решений и управления автономными объектами", МНТП "Многопроцессорные ЭВМ с параллельной структурой и системы виртуальной реальности", 1998-1999 г.г., № ГР 01.9.90002062;
- "Разработка принципов построения и макетирование базовых элементов микро- и миниробототехники военного назначения на основе микроэлектронных вычислительных, сенсорных и микроэлектронных устройств", 1999-2001 г.г.,№ГР 01.20.0008195;
- "Исследование технических путей создания танковых автономных интеллектуальных робототехнических комплексов", 1999 - 2002 г.г., №ГР 01.20.0008194;
- "Разработка теоретических и практических основ построения интеллектуальных распределенных систем управления целенаправленным поведением коллективов микророботов", 1997-2000 г.г., № ГР 01.9.70008000;
- "Разработка интеллектуальной системы управления коллективным взаимодействием роботов", 2001-2003 г.г., № ГР 01.2.00105590;
- "Разработка интеллектуальной распределенной системы управления группой складских роботов", 2003-2004 г.г., № ГР 01.20.0307749;
- "Разработка научно-технических основ построения самоорганизующихся распределенных систем управления коллективным поведением роботов на базе биомиметических принципов", 2004 - 2008 г.г., № ГР 120.0404537;
- "Разработка бортового многопроцессорного вычислительного устройства на базе микропроцессорной техники для решения задач обработки информации и управления подвижными объектами", 2002 - 2004 г.г., №ГР 01.20.0307748;
- "Разработка технологии организации отказоустойчивых распределенных вычислений в системах реального времени на основе мультиагентного взаимодействия", 2007 г., № ГР 01.2.007 06420;
- ОКР "Разработка и создание системы управления оборудованием автоматизированных складов" по договору №513201 между НИИ МВС ТРТУ и ОАО "СКБ "Точрадиомаш", 2001-2002 г.г.
- ОКР "Разработка и изготовление системы управления автоматизированным складом, включая автоматизированный учёт", по договору №553227 между НИИ МВС ТРТУ и ОАО "СКБ "Точрадиомаш", 2005 - 2007 г.г.
Результаты диссертационной работы внедрены в НИИ МВС ЮФУ (г. Таганрог), НИИ специального машиностроения МГТУ им. Н.Э. Баумана (г. Моек ва), ОАО "ВНИИ ТРАНСМАШ" (г. Санкт-Петербург), ОАО "СКБ "Точрадио-маш" (г. Майкоп), Секции прикладных проблем при Президиуме РАН, ГОУ ВПО "Московский государственный институт электронной техники (технический университет)", войсковой части 93603 (г. Москва).
Внедрение результатов диссертации позволило расширить функциональные возможности робототехнических комплексов и систем, расширить области их применения, уменьшить или даже исключить непосредственное участие людей в выполнении опасных и тяжелых работ, повысить эффективность автоматизированных технологических процессов на базе мультиробототехнических систем.
Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях:
- VII научно-технической конференции "Экстремальная робототехника", С.-Петербург, 1996 г.;
- 14h Workshop on Distributed Control Systems. - Seoul, Korea, July 1997;
- VIII научно-технической конференции "Экстремальная робототехника", С.-Петербург, 1997 г.;
- Всероссийской научно-технической конференции "Новые технологии управления робототехническими и автотранспортными объектами", г. Ставрополь, 1998 г.;
- The 4h ECPD Inter. Conference on Advanced Robotics Intelligent Automation and Active System Proceedings, Moscow, Russia, 1998;
- IX научно-техническая конференция "Экстремальная робототехника", С.-Петербург, 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", пос. Дивноморское, Геленджик, 2003 г.;
-Научной молодежной школе "Экстремальная робототехника - 2003", пос. Дивноморское, Геленджик, 2003 г.;
- Первой Всероссийской конференции с международным участием "Ме-хатроника, автоматизация, управление", г. Владимир, 2004 г.;
- Международной научной конференции "Искусственный интеллект. Интеллектуальные и многопроцессорные системы-2004", п. Кацивели, Крым, Украина, 2004 г.;
- Международной научной молодежной школе "Микросистемная техника", п. Кацивели, Крым, Украина, 2004 г.;
- IX Международной конференции "Устойчивость, управление и динамика твердого тела", г. Донецк, Украина, 2005 г.;
- Международной научной конференции "Интеллектуальные и многопроцессорные системы-2005", пос. Дивноморское, Геленджик, 2005 г.;
- Седьмой международной научно-технической конференции "Искусственный интеллект. Интеллектуальные и многопроцессорные системы-2006", пос. Кацивели, Крым, Украина, 2006 г.;
- Международной научно-технической выставке-конгрессе "Мехатроника и робототехника (МиР-2007)", г. Санкт- Петербург, 2007 г.;
- Международной научно-технической конференции "Мехатроника, автоматизация и управление - 2007 (МАУ-2007)", пос. Дивноморское, Геленджик, 2007 г.
Личный вклад автора. Все научные результаты, полученные при решении крупной научной проблемы разработки теоретических и практических основ организации, функционирования и построения распределенных систем коллективного управления роботами при их групповом применении в условиях сложных, заранее неизвестных динамических сред, получены автором лично.
Публикации. По теме диссертации опубликовано 80 печатных работ, в том числе: 2 монографии, 18 статей в центральной печати, из них 12 - в изданиях, входящих в "Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации" ВАК.
Наиболее важными из публикаций являются.
Каляев И.А., Гайдук А.Р., Капустян С.Г. Распределенные системы планирования действий коллективов роботов. -М.: Янус-К, 2002. - 292 с.
Каляев И.А., Капустян С.Г., Усачев Л.Ж. Основы построения распределенных систем управления коллективами роботов // Информационные технологии.-1998.-№ 5.-С.13-18.
Капустян С.Г., Усачев Л.Ж., Стоянов СВ. Метод оптимального распределения целей в коллективе роботов // Информационные технологии.- 1998.- №4.-С.29-34.
Капустин С.Г., Вьюшин А.А. Распределенная система управления группой роботов-штабелеров //Мехатроника, Автоматизация, Управление.- 2003.-№3.- С. 22-28.
Капустян С.Г. Многоуровневая организация коллективного взаимодействия в группах интеллектуальных роботов //Известия ТРТУ.- 2004.- №9.- С. 149-158.
Капустян С.Г., Бондарев Ю.П. Методы организации локальной координации действий в больших группах микророботов //Известия ТРТУ.- 2004.- №9.-С. 158-167.
Капустян С.Г. Децентрализованный метод коллективного распределения целей в группе роботов // Известия высших учебных заведений. Электроника.-2006.-№2,-С. 84-91.
Каляев И.А., Капустян С.Г. Однородные структуры для решения вариационных задач оптимизации и планирования.- Львов: НТЦ "Интеграл", 1991.- 88 с.
Каляев И.А., Капустян С.Г., Усачев Л.Ж., Луконин О.А. Программно-аппаратный комплекс для моделирования систем управления движением мобильных роботов в виртуальной среде // Информационные технологии.- 1998.-№ 6.- С. 9-13.
Каляев И.А., Капустян С.Г., Усачев Л.Ж., Стоянов СВ. Системы управления интеллектуальных мобильных роботов для исследовательских и промышленных работ // Наука производству.- 1999.- № 11.- С.28-32.
Каляев И.А., Капустян С.Г., Усачев Л.Ж. Системы технического зрения на базе сканирующих лазерных дальномеров // Наука производству.- 1999.-№11.-С. 45-47.
Капустян С.Г., Усачев Л.Ж. Моделирование функционирования мобильных роботов в виртуальной среде на ПЭВМ // Известия ТРТУ.- 2002.- №1 (24).-С. 52-53.
Капустян С.Г. Интеллектуальная система автоматического вождения безэкипажного транспортного средства // Известия ТРТУ.- 2002.- №1 (24).- С.53-54.
Гандурин В.А., Капустян С.Г., Мельник Э.В. Алгоритм коллективного улучшения плана в задачах распределения ресурсов многопроцессорных информационно-управляющих систем //Вестник компьютерных и информационных технологий.- 2007.-№12.- С. 40-50.
Каляев И.А., Капустян С.Г., Усачев Л.Ж., Стоянов СВ. Creation bases of distributed control system of robot collective II The 4h ECPD Inter. Conference on Advanced Robotics Intelligent Automation and Active System Proceedings. Moscow, Russia, 1998.pp.l79-182.
I.A. Kaliaev., S.G.Kapustian, S.V. Stojanov, L.Zh. Usachov Development of Robots Collective Distributed Control System Bases II Proc. of the 44 Inter. Wissen-schaftliches Kolloquium , Ilmenau, Germany, Sept. 1999.
Kaliaev L, Kapustjan S., Stojanov S., Usachov L. The Distributed Cjntrol Sys tem of Micro Robots Collectiv II IARP Int. Workshop on Micro Robots, Micro Mashines and Systems. Moscow, Russia, nov. 24-25, 1999, pp. 163-166.
Капустин С.Г. Метод организации мультиагентного взаимодействия в распределенных системах управления группой роботов при решении задачи покрытия площади //Искусственный интеллект, 2004.- №3,- Донецк (Украина): "Нука і освіта".- С. 715-727.
Каляев И.А., Гайдук А.Р., Капустян С. Г. Управление коллективом интеллектуальных объектов на основе стайных принципов //Вестник ЮНЦ РАН, 2005.- Т. 1.- Вып. 2.- С. 20-27.
Каляев И.А., Капустян С.Г., Усачев Л.Ж. Концептуальные аспекты организации распределенных систем управления коллективами роботов // IX На-учн.-техн. конф. "Экстремальная робототехника": мат-лы конф.- С.-Петербург: изд-во СПбГТУ, 1998.- С. 36-43.
Каляев И.А., Капустян С.Г., Усачев Л.Ж., Стоянов СВ. Метод оптимального распределения целей в коллективе роботов // IX НТК "Экстремальная робототехника": мат-лы конф. С.-Петербург: изд-во СПбГТУ, 1998.- С. 331-338.
Каляев И.А., Капустян С.Г., Усачев Л.Ж. Способ динамического целерас-пределения в задаче группового применения мобильных роботов специального назначения // Интеллектуальные многопроцессорные системы ИМС-99: труды междунар. конф.- Таганрог: Изд-во ТРТУ, 1999.- С.70-72.
Каляев И.А., Гайдук А.Р., Капустян С.Г., Чистяков В.М. Принципы организации больших коллективов роботов //Интеллектуальные робототехнические системы - 2001: Материалы молодежной научн. школы, 1-6 октября, 2001, пос. Дивноморское, Геленджик. Таганрог: Изд-во ТРТУ, 2001- С. 178-181.
Каляев И.А., Капустян С.Г., Усачев Л.Ж. Способ динамического распределения целей в задаче группового применения мобильных роботов // Интеллектуальные робототехнические системы — 2001: мат-лы молодеж. научн. школы.- Таганрог: Изд-во ТРТУ, 2001.- С. 181-184.
Капустян С.Г. Децентрализованное планирование действий коллектива интеллектуальных роботов // Интеллектуальные робототехнические системы - 2001: мат-лы молодеж. научн. школы.- Таганрог: Изд-во ТРТУ, 2001.- С. 184-187.
Каляев И.А., Капустян С.Г., Усачев Л.Ж., Стоянов СВ. Способы организации многопроцессорных вычислительных структур для решения задачи планирования действий группы мобильных роботов // СуперЭВМ и многопроцессорные вычислительные системы (МВС 2002): мат-лы Междунар. науч.-техн. конф.- Таганрог: Изд-во ТРТУ, 2002.- С. 324-329.
Каляев И.А., Капустян С.Г., Усачев Л.Ж., Стоянов СВ. Программная модель системы динамического распределения целей в задаче группового применения мобильных роботов // СуперЭВМ и многопроцессорные вычислительные системы (МВС 2002): мат-лы Междунар. науч.-техн. конф.- Таганрог: Изд-во ТРТУ, 2002.- С. 329-333.
Капустян С.Г. Распределенная интеллектуальная система управления коллективным взаимодействием роботов // СуперЭВМ и многопроцессорные вычислительные системы (МВС 2002): мат-лы Междунар. науч.-техн. конф.-Таганрог: Изд-во ТРТУ, - С.333-337.
Гайдук А.Р., Вершинин Ю.А., Капустян С.Г. Распределенная система управления коллективом роботов // Интеллектуальные и многопроцессорные системы - 2003, т. 2: мат-лы Междунар. науч.-техн. конф,- Таганрог: Изд-во ТРТУ, 2003.-С. 182-185.
Капустян С.Г. Распределенная система управления группой складских ро-ботов-штабелеров // Интеллектуальные и многопроцессорные системы - 2003, т. 2: мат-лы Междунар. науч.-техн. конф. Таганрог: Изд-во ТРТУ, 2003.- С- 185-194.
Капустян С.Г., Усачев Л.Ж. Способ и программная модель динамического распределения целей в задаче группового применения мобильных роботов // Интеллектуальные и многопроцессорные системы - 2003, т. 2: мат-лы Междунар. науч.-техн. конф.- Таганрог: Изд-во ТРТУ, 2003.- С. 203-205.
Капустян С.Г., Усачев Л.Ж., Стоянов СВ. Применение многопроцессорных вычислительных структур для решения задачи планирования действий группы мобильных роботов // Интеллектуальные и многопроцессорные системы - 2003, т. 2: мат-лы Междунар. науч.-техн. конф.- Таганрог: Изд-во ТРТУ, 2003.-С. 206-210.
Каляев И.А., Гайдук А.Р., Капустян С.Г., Кулиничев P.PL, Плаксиенко Е.А. Исследование метода кластеризации больших коллективов микророботов // Экстремальная робототехника - 2003: мат-лы науч. молодеж. школы.- Таганрог: Изд-во ТРТУ, 2003.- С. 213-216.
Каляев И.А., Капустян С.Г. Распределенная система управления коллективом складских роботов //Мехатроника, автоматизация, управление: труды Первой Всеросс. конф. с междунар. участием.- М.: Новые технологии, 2004.- С. 428-432.
Капустян С.Г. Многоуровневая архитектура организации взаимодействия в группах интеллектуальных роботов //Искусственный интеллект. Интеллектуальные и многопроцессорные системы — 2004, т. 2.: мат-лы Междунар. науч. конф.- Таганрог: Изд-во ТРТУ, 2004.- С. 386-390.
Капустян С.Г., Бондарев Ю.П. Алгоритмы и имитационная модель локальной координации действий в больших группах микророботов //Искусственный интеллект. Интеллектуальные и многопроцессорные системы - 2004, т. 2.: мат-лы Междунар. науч. конф.- Таганрог: Изд-во ТРТУ, 2004.- С. 391-395.
Капустян С.Г., Кулиничев Р.Н. Алгоритм и имитационная модель решения задачи оптимального покрытия поверхности группой роботов //Искусственный интеллект. Интеллектуальные и многопроцессорные системы — 2004, т. 2.: мат-лы Междунар. науч. конф.- Таганрог: Изд-во ТРТУ, 2004.- С. 396-400.
Каляев И.А., Гайдук А.Р., Капустин С.Г. Стайное управление группой объектов // Устойчивость, управление и динамика твердого тела: тез. докладов IX Междунар. конф.- Донецк: Ин-т прикл. математики и механики НАНУ, 2005.- С.6-7.
Капустин С.Г. Ускоренный децентрализованный метод коллективного распределения целей в группе роботов // Интеллектуальные и многопроцессорные системы — 2005, т. 3: мат-лы Междунар. научн. конф.- Таганрог: Изд-во ТРТУ, 2005.-С. 45-51.
Структура диссертации. Диссертация состоит из введения, пяти глав, заключения и библиографического списка из 229 наименований.
Во введении обоснована актуальность работы, дана ее общая характеристика, сформулированы цель и задачи исследования.
В первой главе сформулирована проблема группового управления, проведен аналитический обзор систем и методов группового управления. Дана формальная постановка задачи управления группой роботов. Проведена классификация задач группового управления роботами по уровню сложности в зависимости от условий функционирования. Рассмотрены принципы организации систем группового управления роботами. Сформулированы принципы коллективного управления группами роботами. Дана формулировка задачи коллективного управления группой роботов в дискретном виде. Предложена итерационная процедура оптимизация коллективного управления в группах роботов, реализующая принципы коллективного управления. Рассмотрены вопросы сходимости, конечности, устойчивости и оптимальности итерационной процедуры оптимизации коллективного управления в группах роботов.
Во второй главе.
Дана постановка задачи распределения заданий (целей) в группе роботов и описано применение метода коллективного управления для ее решения.
Описаны алгоритмы коллективного улучшения плана, позволяющие получить точное (оптимальное), то есть дающее экстремум целевого функционала на ближайшее будущее, решение задачи распределения целей в группах роботов при различных соотношениях числа роботов в группах и числа целей. Рассмотрены условия оптимальности решения.
Приведены алгоритмы приближенного решения задачи коллективного распределения целей в группах роботов, минимизирующие временные затраты. Обоснована сходимость этих алгоритмов. Работоспособность и эффективность алгоритмов коллективного распределения целей в группах роботов показана на модельных примерах, приведенных в Приложении А.
Проведен сравнительный анализ вычислительной сложности предложенных в диссертационной работе алгоритмов коллективного распределения целей в группах роботов с известными алгоритмами централизованного решения этой задачи.
Рассмотрено применение методов и алгоритмов коллективного управления для решения прикладных задач. Описан алгоритм решения задачи целерас-пределения в группе боевых роботов, ориентированный на реализацию в распределенной системе группового управления роботами.
Показано применение метода коллективного управления при решении задачи покрытия площади группой роботов, а также при решении задачи управления группой складских роботов, обслуживающих автоматизированный склад.
В третьей главе рассмотрены вопросы организации управления группами роботов в условиях динамической быстро изменяющейся ситуации при организованном противодействии со стороны другой группы роботов на примере игры роботов в футбол и при ведении группой роботов боевых действий. Предложен метод стайного управления группой роботов в условиях противодействия. Приведены результаты экспериментальных исследований с использованием имитационных моделей.
Четвертая глава посвящена решению проблемы управления большими группами роботов. Предложен подход, основанный на разбиении больших групп роботов на подгруппы, численность которых удовлетворяет условиям управляемости, и организации кластеров роботов.
Рассмотрены принципы и методы кластеризации, основанные на методах и алгоритмах коллективного управления.
Исследованы методы и алгоритмы кластеризации. Показана эффективность управления большими группами роботов на основе предложенных методов кластеризации, в том числе и на модельных примерах, приведенных в Приложении Б.
В пятой главе.
Анализируется комплекс задач, решаемых отдельным роботом группы при достижении поставленной перед ним цели. Рассматриваются методы и алгоритмы управления движением отдельных роботов группы при отработке коллективных действий, основанные на использовании однородных нейроподоб-ных структур. Описание имитационных программных моделей функционирования роботов в виртуальной среде с использованием разработанных методов и алгоритмов приведено в Приложении В.
Таким образом, в диссертации сформулирована и решена крупная и актуальная научная проблема, имеющая важное народно-хозяйственное значение.
Внедрение полученных в диссертационной работе результатов вносит значительный вклад в развитие экономики и обороноспособности страны, что подтверждается актами внедрения и использования основных результатов диссертации, приведенных в Приложении Г.
Управление группами роботов в стационарных условиях
Проблема группового управления роботами возникла практически сразу, как только первые роботы появились на производственных предприятиях. Действительно, применение роботов эффективно только в том случае, если их много, и они выполняют, по крайней мере, большинство технологических операций. При этом они должны работать согласовано друг с другом и с другим технологическим оборудованием.
Впервые эта проблема в нашей стране была поднята в начале 80-х годов прошлого века учеными Поповым Е.П., Юревичем Е.И. [1, 58]. Решению проблемы группового управления роботами-манипуляторами были посвящены работы Макарова И.М., например [59], транспортными роботами - работы Каляева И. А. [60-63].
В настоящее время проблема группового управления роботами принимает все более актуальное значение, что подтверждается большим числом исследований, проводимых в странах Западной Европы, США, Японии и России.
В России активные исследования в данной области ведутся научными коллективами в Институте прикладной математики им. М.В. Келдыша под ру ководством академика РАН [Охоцимского Д.Е.] и профессора Павловского В.Е [64-71], в НИИ многопроцессорных вычислительных систем Таганрогского государственного радиотехнического университета (ныне НИИ многопроцессорных вычислительных систем Южного федерального университета) под руководством члена-корреспондента РАН Каляева И.А. [72-80], на кафедре системного анализа и управления Санкт-Петербургского государственного технического университета под руководством профессора Куприянова В.Е. [81-85] и в ГНЦ РФ ЦНИИ РТК под руководством д.т.н., профессора Юревича Е.И. [50-52], в Московском институте радиотехники, электроники и автоматики (МИРЭА) под руководством академика РАН Макарова И.М. [86, 87]. Проблеме группового управления уделяется значительное внимание в работах ученых МГТУ им. Н.Э. Баумана [88, 89], Санкт-Петербургского государственного университета аэрокосмического приборостроения [39, 90-92], а также ряда других научных организаций [93-96].
За рубежом исследования в области группового управления роботами проводятся, как правило, в рамках закрытых программ по созданию новейших образцов вооружений, финансируемых министерствами обороны соответствующих государств [18, 97 - 98]. Однако существует тенденция возрастающей потребности использования групп роботов и в мирных целях.
Одной из самых ранних известных разработок мобильной мультиробото-технической системы является проект СЕВОТ (Cellular robotic system ) [99, 100]. Эта система предполагает стыковку отдельных малых роботов для создания одного большого робота и иллюстрирует механизмы, которые могут быть использованы для координации группового поведения.
Рассмотрим существующие в настоящее время системы группового управления роботами различного назначения, а также современные разработки, выполняемые проекты и научные исследования по данному направлению.
Примером исследований в области группового управления роботами, функционирующими в условиях стационарных сред, может служить проект "MARTHA", который выполнялся в лаборатории Анализа Системных Архитектур Франции [101]. Целью данного проекта являлась разработка методов организации группового взаимодействия роботов (от 10 до 100 шт.), предназначенных для транспортировки грузов в складских терминалах.
Концепция проекта "MARTHA" заключается в следующем.
Система управления группой роботов состоит из двух основных частей: центральной станции (ЦС) и бортовых вычислителей (БВ) с контроллером свя зи (КС). Центральная станция устанавливается стационарно в командном центре и решает задачу планирования действий всей группы роботов. Кроме того, ЦС обеспечивает связь человека-оператора с каждым роботом группы в случае непредвиденных ситуаций, а также используется для постановки целевой задачи. На борту каждого робота устанавливается БВ, который предназначен для решения задачи маршрутизации его движения к указанной цели. Контроллер связи служит для обеспечения связи робота с центральной станцией и с другими роботами группы.
Структура организации системы управления проекта "MARTHA" представлена на рисунке 1.1. Робот №2 Робот №3 ЦС - центральная станция; КС - контроллер связи; БВ - бортовой вычислитель; _ - связь "ЦС - робот"; - связь "робот-робот" Рисунок 1.1- Структура системы управления проекта "MARTHA"
Описанные выше группы роботов предназначены для использования в стационарных, заранее подготовленных средах, что позволяет использовать стационарные достаточно мощные центральные вычислительные устройства, решающие централизованно задачу управления роботами группы [50 - 52, 102].
Другим примером использования централизованного управления группой роботов или, что чаще встречается в литературе, мультиробототехн и ческой системой, является проект, выполнявшийся в Центре распределенных робото-технических систем Университета Миннесоты (США) при поддержке управления DARPA (Defense Advanced Research Projects Agency) Министерства обороны США. Проект был связан с разработкой программного обеспечения и аппаратных средств системы управления группой миниатюрных роботов-разведчиков ("Scout") (рисунок 1.2), предназначенных для решения задач охраны, разведки и наблюдения за обстановкой в различных помещениях [103 -106]. Здесь упор делается на разработку программного обеспечения, имеющего иерархическую распределенную организацию, представленную на рисунке 1.3,
Алгоритмы приближенного решения задач коллективного распределения целей в группах роботов
В основе данного алгоритма, как и описанных выше, лежит итерационная процедура оптимизации коллективных действий, в рамках которой роботы делают попытки выбора целей в соответствии с принципами коллективного управления. Но при этом роботы группы при выборе целей в рамках итерационной процедуры должны руководствоваться следующими правилами:
1) роботы делают попытку выбора целей в определенной последовательности, например, в порядке возрастания номеров;
2) каждый робот может выбирать не более чем одну цель, что соответствует ограничению (2.42), после чего он не участвует в выборе целей в данной реализации итерационной процедуры;
3) цель, для которой выполняется условие І ,-/ "Г% 1ФМ1 пГ =1,2,3,.-, (2.44) то есть необеспеченная цель выбирается роботом, еще не выбравшим какую-либо цель в данной реализации итерационной процедуры и для которого оценка эффективности djj этой цели имеет наибольшее значение по сравнению с другими роботами, выбравшими эту же цель;
4) если на момент выбора цели у -м роботом группы имеется несколько необеспеченных целей, имеющих для данного робота одинаковые значения оценки эффективности, то робот осуществляет выбор только одной цели в со ответствии с заранее определенным правилом, одинаковым для всех роботов данной группы, например, может выбираться цель с наименьшим номером.
Другими словами, если dj,h=dJh= =dJA l\ h - h (2.45) и выполняется условие (2.44), тоу -м роботом выбирается цель с номером і, =Г{; 5) если несколько роботов имеют одинаковые значения оценки эффек тивности для 1-й цели (/є[1,М]) при условии, что она не обеспечена, то выбор этой цели осуществляется только одним роботом по заранее определенному правилу, одинаковому для всех роботов данной группы, например, цель может быть выбрана роботом с наименьшим номером, то есть если dJbi=dj2,i=-=djk,i Л Л - Л (2-46) и выполняется условие (2.44), то юу- /=1 (_/je[l,JV],/G[l,M]). С учетом приведенных правил алгоритм 2.7 коллективного распределения целей в группе роботов заключается в следующем.
Каждый робот группы R Vl (j l,N) в момент времени t0=t формирует список целей в соответствии с правилами, одинаковыми для всех роботов данной группы, а затем для каждой из целей вычисляет оценку эффективности, то есть формирует массив оценок эффективности Dj=[djl,dj2,...,dJ. l,...,djM], который затем передается всем остальным роботам группы. В результате каждый робот имеет двумерную матрицу D оценок эффективности размером NxM, строки которой соответствуют роботам группы, столбцы - целям, а элементами матрицы являются оценки эффективности соответствующих целей реализации итерационной процедуры; 3) цель, для которой выполняется условие лУі/ иР\ /є[1,М], пГ =1,2,3,..., (2.44) ./=1 то есть необеспеченная цель выбирается роботом, еще не выбравшим какую-либо цель в данной реализации итерационной процедуры и для которого оценка эффективности djj этой цели имеет наибольшее значение по сравнению с другими роботами, выбравшими эту же цель; 4) если на момент выбора цели у -м роботом группы имеется несколько необеспеченных целей, имеющих для данного робота одинаковые значения оценки эффективности, то робот осуществляет выбор только одной цели в со ответствии с заранее определенным правилом, одинаковым для всех роботов данной группы, например, может выбираться цель с наименьшим номером.
Другими словами, если dJA=dJh= =dJJit h h - h С2-45) и выполняется условие (2.44), то у -м роботом выбирается цель с номером і. =Г{; 5) если несколько роботов имеют одинаковые значения оценки эффек тивности для 1-й цели (/є[1,М]) при условии, что она не обеспечена, то выбор этой цели осуществляется только одним роботом по заранее определенному правилу, одинаковому для всех роботов данной группы, например, цель может быть выбрана роботом с наименьшим номером, то есть если dM=dhJ= "=dJkJ У і Л - Л (2-46) и выполняется условие (2.44), то и,- /=1 (j\e[\,N],l Е[\,М)).
С учетом приведенных правил алгоритм 2.7 коллективного распределения целей в группе роботов заключается в следующем. Каждый робот группы RjZffl (y =l,7V) в момент времени tQ=i формирует список целей в соответствии с правилами, одинаковыми для всех роботов данной группы, а затем для каждой из целей вычисляет оценку эффективности, то есть формирует массив оценок эффективности Dj=[djUdjt2,--;djj,...,dJM], который затем передается всем остальным роботам группы. В результате каждый робот имеет двумерную матрицу D оценок эффективности размером NxM, строки которой соответствуют роботам группы, столбцы - целям, а элементами матрицы являются оценки эффективности соответствующих целей для тех или иных роботов группы, (2.47)
Кроме того, в момент времени tQ=i каждый робот группы имеет информацию о максимальном числе роботов, необходимом для обеспечения той или иной цели, в виде одномерного массива Nmax =[п ,п2 ,...,пт . nf]. Далее, каждый робот в порядке возрастания номеров выполняет следующие действия.
Сначала робот Rx єі# в строке, соответствующей его номеру, отыскивает элемент, имеющий максимальное положительное значение, и фиксирует номер соответствующего столбца, например, іх. Этот номер определяет цель, достижение которой наиболее эффективно для данного робота. Если таких значений несколько, то выбирается одно из них в соответствии с правилом 4). Затем максимальный элемент отыскивается в столбце с номером /(. Если индекс строки;/ этого элемента совпадает с номером робота, то есть в данном случае это у—1, то данная цель с номером іх выбирается роботом Яг, о чем он сообщает всем остальным роботам группы, передавая им номер выбранной цели. Все роботы группы при этом, в том числе и робот R}, во-первых, обнуляют (или присваивают отрицательное значение) все элементы строки, соответствующей роботу, сделавшему выбор цели. Это означает, что данный робот больше не участвует в выборе целей до конца процедуры распределения целей в соответствии с правилом 2), во-вторых, элемент я(тах массива Nmax, то есть п eNmax, уменьшается на единицу. При этом, если п3 = 0, а это означает, что данная цель обеспечена, все роботы группы обнуляют (или присваивают отрицательные значения) элементы матрицы D в столбце z,, соответствующем обеспеченной цели в результате ее выбора роботом Rl . Это означает, что данная цель больше не рассматривается в данной реализации процедуры распределения целей.
Программная реализация метода коллективного управления при игре в виртуальный футбол
С целью экспериментальных исследований предложенных методов и алгоритмов коллективного управления действиями роботов при игре в футбол, предложенных в настоящей главе, была разработана и создана программная модель, имитирующая игру двух команд роботов в футбол. Данная программная модель была реализована в инструментальной системе программирования Delphi версии 5.0 и предназначена для работы под ОС Windows 95/98 и более поздних.
Основная идея построения программной модели заключается в использовании многопотокового механизма (multi thread mechanism). В общем виде игру можно представить как некоторое количество потоков, взаимодействующих между собой. В программе используются два типа потоков: асимметричные — это модель мяча и модель арбитра и симметричные - это модели роботов-игроков (их количество устанавливается в процессе конфигурирования команд). В каждом потоке модели игрока реализованы модуль планирования действия и модуль маршрутизатора, а в потоке модели мяча - только модуль маршрутизатора. Все потоки соединены с каналом сообщений. Потоки моделей игроков имеют входные и выходные сообщения, тогда как поток модели арбитра - только выходные, а мяча - входные. Выходными сообщениями модели арбитра являются команды перемещения игроков и мяча в заданные участки поля в зависимости от текущей ситуации, например, розыгрыш мяча командой "В". Эти же команды, соответственно, являются входными сообщениями и для потоков моделей игроков каждой из команд и мяча. Кроме того, входными сообщениями для потоков моделей игроков являются координаты целевых участков поля при передаче паса. Для потока мяча входным сообщением являются направление удара и скорость перемещения. Каждый поток в определенные моменты времени использует общую для всех информацию о положении игроков на поле. Структура программной модели показана на рисунке 3.9.
Общий вид графического экрана программы показан на рисунке 3.10.
Здесь для простоты отображения роботы-игроки обеих команд и мяч изображаются в виде одинаковых кружков разного цвета, причем текущее направление движения каждого робота-игрока обозначается стрелкой внутри соответствующего кружка. В целом графический экран программы состоит из следующих основных частей: панели меню, панели инструментов, футбольного
Меню "Параметры" состоит из трех подменю: "Поле", "Команды" и "Общие". В подменю "Поле" можно задавать размер поля, причем при изменении длины одной из сторон автоматически пропорционально меняется длина другой стороны.
С помощью подменю "Команды" можно отдельно задавать параметры каждой команде, используя соответствующие вложенные подменю "Команда В" или "Команда С", либо сделать равные настроечные параметры для обеих команд, переписав их из конфигурации одной команды в другую, используя для этого соответствующее подменю "Установки В— С" или "Установки С— В" (см. рисунок 3.11). В подменю "Команда В" или "Команда С" можно выполнить следующие операции: задать цвет игроков для четкого распознавания принадлежности к той или иной команде, используя пункт "Цвет"; загрузить индивидуальный модуль планирования действий команды в виде dil-файла через подменю "Загружаемый модуль"; изменить характер поведения игроков команды, меняя значения коэффициентов для каждой функции эффективности, активизировав для этого подменю "Основные параметры".
Рассмотрим более подробно возможность изменения характера поведения игроков команды за счет задания различных значений тактических коэффициентов К] - К9. При активизации подменю "Основные параметры" соответствующей команды на экране появляется окно "Установка параметров команды", представленное на рисунке 3.13. +1 до +999. Значения коэффициентов определяют приоритеты тех или иных функций эффективности в различных ситуациях, а знак - их положительное или отрицательное влияние. Заданием значений констант осуществляется более тонкая настройка приоритетов функций. Поэтому для каждого состояния системы "игроки - мяч" необходимо определить основные действия, которые в данном случае считаются наиболее эффективными, установить наибольшие приоритеты для соответствующих функций и определить их влияние. Так, например, при состоянии "мяч свободен" первоочередным действием является организация захвата мяча. Для этого, если в зоне целевых положений одного из игроков присутствует мяч, то игрок должен переместиться к нему с целью захвата, остальные же роботы-игроки команды должны равномерно рассредоточиться по полю. Если же таких игроков нет, то вся команда рассредоточивается по полю, таким образом, чтобы накрыть наибольшую площадь (см. задачу покрытия площади), увеличивая тем самым вероятность перехвата мяча, поэтому наибольшие значения должны быть у коэффициентов соответствующих функциям "цель - мяч" и "цель - игрок команды" (например, на рисунке 3.13 - =50, KF=4G).
Помимо коэффициентов и констант в окне "Установка параметров команды" можно задавать количество игроков каждого типа (нападающий, защитник, вратарь), поведение которых будет зависеть от установленных им тактических коэффициентов К\ — Кб Для определения размерности зон целевых положений игрока и мяча (радиус действия) в подменю "Общие" задается значение длины максимального перемещения игрока ff , на которое он может переместиться за время выполнения решения 7ВР, и величина 1$ максимального перемещения мяча при ударе по нему.
С помощью подменю "Сетка" и "Разметка", входящих в состав меню "Вид", можно включать или отключать соответственно координатную сетку и разметку координат, накладываемые на поле (см. рисунок 3.14).
С помощью подменю "Коэффициенты по одному роботу", также входящего в состав меню "Вид", можно отображать значения функций эффективности в процессе игры для одного (по выбору) робота-игрока. Для этого в окне "Выбор объекта" из списка игроков выбирается нужный и активизируется кнопка "Коэф.". В результате открывается окно "Монитор состояния игрока", отображающее значения функций эффективности для выбранного игрока, рассчитанных для текущей ситуации. Вид окна представлен на рисунке 3.15. Кроме значений функций эффективности в данном окне отображается текущее состояние системы "игроки - мяч", что позволяет легко проверить соответствие между состоянием системы и принимаемыми решениями.
Разбиение больших групп роботов на непересекающиеся кластеры постоянного состава
Как показано выше, непосредственное применение предложенных в главе 2 алгоритмов для больших групп роботов может привести к нарушению условия управляемости (4.2). В то же время кластеризация группы позволяет применить эти алгоритмы к небольшой подгруппе роботов, в отношении которой выполняется условие управляемости. Поэтому кластеризация является необходимым условием решения задачи управления большими группами роботов в реальном времени.
При организации процедуры кластеризации, прежде всего, возникает вопрос, на каких принципах должны создаваться кластеры и как они должны взаимодействовать между собой?
Образование кластеров, т.е. кластеризация группы роботов может осуществляться различными способами. Группа роботов может быть, например, разбита на кластеры принудительно до начала функционирования. При этом принадлежность каждого робота к тому или иному кластеру заносится в память его бортовой системы управления.
Но наибольший интерес представляет процесс образования кластеров на принципах самоорганизации.
В процедурах кластеризации на принципах самоорганизации можно выделить следующие этапы: - инициализация кластера; - рост кластера.
Инициализация кластера - это способ образования начальной устойчивой неоднородности в группе роботов.
Рост кластера - это процесс изменения числа роботов, входящих в его состав, для достижения некоторой заданной численности. При этом процесс роста кластеров в большой группе роботов должен быть организован таким образом, чтобы, во-первых, выполнялось условие управляемости (4.2), а во-вторых, чтобы численность каждого из образующихся кластеров соответствовала той целевой задаче, на выполнение которой ориентируются роботы данного кластера.
В зависимости от того, какие цели стоят перед большой группой роботов и какими функциональными возможностями они обладают, можно использовать различные методы кластеризации. Кратко рассмотрим некоторые из них.
Структура большой группы роботов, разбитой на кластеры по иерархическому принципу, подобна структуре таких четко организованных групп людей, как трудовой коллектив крупного предприятия или воинское соединение, например, дивизия, которые разбиваются на структурные подразделения различного уровня, и во главе которых стоит руководитель. Например, дивизия разбивается на полки, полки - на батальоны, батальоны — на роты и т.д. вплоть до отделений, являющихся подразделениями самого низкого уровня. Такая организация обеспечивает достаточно хорошую управляемость коллектива при решении определенного класса целевых задач.
В этом случае при проведении кластеризации в каждый кластер (рисунок 4.1) включаются роботы, которые имеют постоянную связь между собой и число которых не превышает NmaK - максимального числа роботов в кластере, при котором еще выполняется условие управляемости (4.2). Планирование действий для каждого робота, в этом случае, осуществляется с учетом текущих действий роботов только данного кластера, и кластеры между собой никак не взаимодействуют.
Для гомогенных групп роботов разбиение на кластеры может осуществляться по пространственному принципу, т.е. в кластер объединяются роботы, размещенные в какой-то области пространства (см. рисунок 4.1 а). Разбиение на кластеры неоднородных или гетерогенных групп роботов может осуществляться по функциональному признаку, то есть в кластер объединяются роботы, предназначенные для выполнения одного типа операций или решения однотипных целевых задач (см. рисунок 4.1 б), а может осуществляться как по функциональному, так и по пространственному признаку. Например, большая группа роботов предназначена для перемещения грузов, то есть перед группой роботов поставлена групповая цель - переместить разнообразные грузы из одних точек пространства в другие. Причем одни роботы группы способны перемещать, например, сыпучие грузы, другие - жидкие, третьи - сборные конструкции и т.д., то есть решать свойственные им целевые задачи. В этом случае большая гетерогенная группа роботов сначала разбивается на кластеры по функциональному признаку, а затем, если численность кластеров превышает значение Nmax, априори определенное для того или иного типа роботов, то эти кластеры могут быть разбиты на подкластеры, численность которых удовлетворяет условию (4.2), по пространственному признаку.
Разбиение большой группы роботов на непересекающиеся кластеры
Очевидно, что при таком разбиении больших групп роботов на кластеры действия каждого робота могут быть далеки от оптимальных с точки зрения достижения общей групповой цели. Фактически в этом случае мы будем иметь некоторое число небольших самостоятельных групп, каждая из которых решает свою целевую задачу.
Метод разбиения больших групп роботов на непересекающиеся кластеры переменного состава (последовательная кластеризация)
В этом случае кластеры формируются в соответствии с указанными выше условиями управляемости и обеспечения соответствующих целевых задач. По аналогии с понятием обеспеченной цели / -ю целевую задачу некоторого уровня будем называть обеспеченной, если ее выбрало необходимое п число роботов.
При данном способе кластеризации возможны переходы роботов из кластера в кластер при изменении ситуации, когда по мере функционирования группы число роботов, требуемое для обеспечения той или иной целевой задачи, может изменяться. Если число роботов в группе превышает число, требуемое для обеспечения общей групповой цели, то могут образовываться так называемые резервные кластеры. Роботы, входящие в эти кластеры, могут участвовать в решении целевых задач основных кластеров, и если их действия более эффективны с точки зрения достижения групповой цели, то эти роботы заменяют роботов в основном кластере, эффективность действий которых ниже. Последние переходят в резервный кластер.
Метод динамической кластеризации
При использовании данного метода процесс образования кластеров совмещается с процессом их роста. При этом роботы также могут переходить из кластера в кластер, и численность кластеров может изменяться.
Метод разбиения больших групп роботов на пересекающиеся кластеры постоянной численности и переменного состава Этот метод заключается в следующем. Сначала образуется первый кластер численностью TVj NmaK, роботы которого определяют свои действия с помощью одного из приведенных в главе 2 алгоритмов, реализующих итерационную процедуру оптимизации коллективных действий. После завершения этой процедуры некоторое число роботов TVQ, действия которых наиболее эффективны, приступают к их отработке, а оставшиеся Nl -N0 роботов служат основой для второго кластера. К ним присоединяются NQ новых роботов, еще не вошедших ни в один из кластеров, и процесс определения действий осуществляется уже для нового кластера той же численности и т. д., как представлено на рисунке 4.2.
В результате получаем некий "плавающий" кластер, в состав которого входят роботы, уже принимавшие ранее участие в процедуре оптимизации коллективных действий, а также новые роботы, не принимавшие участия в этой процедуре.
Следует отметить, что такой принцип кластеризации позволяет распараллелить процедуру оптимизации коллективных действий. Так, например, в ситуации, показанной на рисунке 4.2, эта процедура может одновременно осуществляться, например, в кластерах №1 и №4, далее №2 и №5, затем в кластерах №3 и №6 и т.д.
