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

Содержание

Введение
Глава 1. Коллективы роботов и подходы к их созданию
1.1. Обзор существующих работ по групповой робототехнике
1.2. Формальные модели коллективного поведения
1.3. Многоагентные системы
1.4. Имитационные модели
1.5. Роевые алгоритмы
1.6. Эволюционные методы
1.7. Выбор подхода к созданию коллектива роботов
1.8. Выводы
Глава 2. Создание члена коллектива
2.1. Подсистемы робота
2.2. Анализ существующих инструментариев для создания роботов
2.3. Подведение итогов
2.4. Описание робота
2.5. Выводы
Глава 3. Система позиционирования и ориентирования в пространстве
3.1. Подходы к созданию системы позиционирования и ориентации
3.2. Выбор подхода к созданию системы позиционирования
3.3. Описание системы позиционирования
3.4. Выводы
Глава 4. Система моделирования
4.1. Обзор существующих систем моделирования
4.2. Анализ существующих систем моделирования
4.3. Система моделирования
4.4. Выводы
Глава 5. Алгоритмы выбора и достижения цели
5.1. Анализ получаемых роботом данных
5.2. Базовый выбор первоначальной цели
5.3. Усовершенствованный выбор первоначальной цели
5.4. Учет динамики среды
5.5. Выводы
Заключение
Список использованных источников

Введение

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

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

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

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

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

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

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

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

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

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

Основными элементами научной новизны магистерской диссертации являются:

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

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

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

Апробация работы производилась на тестовом коллективе роботов и показала достаточную адекватность предложенных алгоритмов. Кроме того, ряд положений работы представлялся на международной студенческой конференции «НОВЫЕ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ» в 2012 году[19] и на VII Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте». [20]

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

  1. Алгоритм планирования совместных действий коллектива роботов на основе первоначальных данных.
  2. Архитектура программно-аппаратного комплекса для исследований коллективного поведения роботов.
  3. Система виртуального моделирования роботов.
  4. Система позиционирования роботов.

Глава 1. Коллективы роботов и подходы к их созданию

1.1. Обзор существующих работ по групповой робототехнике

В настоящее время существует ряд систем, реализующих коллективное поведение:

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Заказать диссер

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

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

Задача самоорганизации и самосборки является классической задачей “поиска и спасения” в сложной окружающей среде. Группа до 35 роботов должна транспортировать тяжелый объект от своей начальной локации до места назначения. Есть несколько возможных путей движения до цели, и эти пути могут иметь различные длины и могут потребовать ухода от возникающих препятствий. Вес объекта таков, что его транспортировка требует координационного усилия, по крайней мере нескольких роботов. Полный сценарий может быть расколот на две главных задачи: нахождение объекта или местоположения цели, и совместного транспортирования.

Данный проект нацелен на развитие новой технологии, которая способна поддерживать скоординированные действия 100 роботов (Рис.  3) для таких миссий, как городское наблюдение. Первая команда роботов изучает область, строя ее карту. Затем вторая команда роботов старается найти интересующий предмет, осуществляет наблюдение и передает информацию друг другу. Если один робот терпит неудачу, другой начинает выполнять его задачу.

Главная цель этого проекта состоит в том, чтобы создать дешевый, надежный и способный к самоорганизации микроробот (Рис.  4), который может быть легко воспроизведен даже дома. Этот робот может позволить строить крупномасштабную систему в 100 и более роботов, чтобы исследовать искусственную самоорганизацию, явления на стадии становления, контроль в многочисленных автоматизированных группах и так далее. Данный проект исследует основные принципы обработки информации и знаний, и проектирования и разработки очень ограниченных автономных систем. [7]

Данный проект является преемником проекта SwarmBot и основывается на его результатах.

Главная научная цель этой работы — создание, внедрение и контроль распределенной автоматизированной системы. Данная система составлена из гетерогенных, динамически связанных, маленьких автономных роботов (Рис.  5). Коллективно, формируют коллектив, приблизительно из 60 роботов, которые делятся на три разных типа: роботы-разведчики, роботы-эффекторы и роботы-транспортировщики. Данная система, с помощью коллективных действий роботов, способна найти необходимый предмет, произвести с ним некоторые манипуляции (например, достать с полки) и доставить предмет в необходимое место. [9]

Проект представляет собой группу роботов (Рис.  6), способных координироваться для выполнения некоторых задач. Ожидается, что в перспективе небольшие роботы SwarmBot смогут объединяться в группы численностью до десяти тысяч и выполнять такие задачи, как, например, поиск мин, исследование неизвестных территорий (в том числе на других планетах), обнаружение вредных веществ и пр. Существующий в настоящее время образец SwarmBot имеет форму куба с длиной ребра около 12,5 см и построен на базе 32-разрядного микропроцессора. Для навигации в пространстве и взаимодействия с другими роботами применяются инфракрасные датчики. В качестве программной платформы используется специализированная операционная система SwarmOS. [6]

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Цена магистерской

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

Разработка компании Nissan представляет собой роботизированный автомобиль EPORO или тестовый робот (Рис.  8) с применением технологии, которая позволяет ему двигаться в потоке, имитируя поведенческую модель косяка рыб, огибающей препятствия и избегающей столкновений друг с другом. Обмениваясь информацией об окружающей обстановке с другими участниками движения, несколько EPORO могут безопасно перемещаться вместе, при необходимости изменяя конфигурацию группы. [10]

В настоящий момент одно из самых популярных направлений в спортивной робототехнике, как в России, так и за рубежом, реализующее некоторые принципы группового поведения роботов. [11] Действительно, футбол – это командная игра, что предусматривает некоторые коллективные действия. На данный момент в робофутболе (Рис.  9), существует два подхода к созданию коллективов, но задача согласованного движения в них решается одинаково:

  1. ​Виртуальная имитация. Существует программный агент, позволяющий имитировать согласование действий коллектива.
  2. Реальный коллектив. Агенты получают команды с единого управляющего центра (сервера).

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

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

  1. Непредсказуемая динамика внешней среды вплоть до сознательного противодействия.
  2. Неполнота и противоречивость знаний роботов (агентов) о состоянии внешней среды и о других участниках.
  3. Многообразие вариантов путей достижения цели, структур коллектива, распределения ролей и т.д.
  4. Распределенный и динамический характер планирования действий коллектива.
  5. Проблемы, связанные с тем, что коллектив представляет собой совокупность физических объектов, действующих в реальной сложной среде (проблемы надежной коммуникации, распределенность коллектива в пространстве и т.д.).
  6. Прочие технические проблемы (архитектура сети, протоколы, операционные средства и т.д.).

Как указано в [1], решение данных проблем позволит создать такие системы, которые будут обладать рядом особенностей, например, такими как:

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

Появление систем с такими особенностями позволит решать большой круг задач [1]:

  • Командная работа роботов, совместно выполняющих диагностику труднодоступных объектов,
  • Мониторинг окружающей среды,
  • Коллективное решение задач роботами–спасателями,
  • Разведка и рекогносцировка (для беспилотных летательных аппаратов, роботов военного назначения),
  • Охранные функции, патрулирование,
  • И т.д.

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

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Цена магистерской

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

Очевидно, что существует целый ряд специфических проблем, характерных для коллективной работы роботов. Среди них можно отметить такие, как:

Таблица 1. Проблематика коллективного поведения роботов

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

  1. Формальные модели коллективного поведения.
  2. Технологии многоагентных систем.
  3. Имитационное моделирование.
  4. Роевые, пчелиные и муравьиные алгоритмы.
  5. Эволюционные методы.

Все они подробно рассмотрены в работе [1].

1.2. Формальные модели коллективного поведения

1.2.1 Автоматные модели

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

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

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

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

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

Рассмотрим задачу подробнее:

Дано: Скважина и кольцевой коллектор.

Необходимо: Экономить электроэнергию.

Решение:

  • Кольцо из N автоматов, каждый из которых может находиться в одном из двух состояний – 1 или 0.
  • Плохо, когда 1) не экономится электроэнергия; 2) участки не поливаются;

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

Чем выше ранг рефлексии, тем о большем числе соседей необходимо иметь информацию.

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

1.2.2. Оптимизационный подход

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

При этом подходе состояния системы «робот-среда» задаются парами вида:

где R(t) и S(t) – соответственно состояния робота и среды в момент времени t. Далее задаются начальные условия

Общая же постановка задачи определяется следующим образом:

Задача управления роботом R состоит в том, чтобы определить такую последовательность действий (вектор-функцию действий) A(t) на интервале времени [t0, tf], выполнение которых при заданных связях, начальных условиях и ограничениях обеспечивало бы экстремум функционала

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

1.3. Многоагентные системы

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

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

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

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

1.3.1. Теория игр

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

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Подробнее

1.3.2. Теория общих намерений

Основными понятиями теории общих намерений являются:

  1. События – связаны с конкретным агентом или объектом внешнего мира;
  2. Убеждения – утверждения, в истинности которых агент убежден в текущий момент времени;
  3. Цели – некоторые состояния агента, которые он стремится достичь;
  4. Взаимные убеждения – складываются из убеждений группы агентов.

Для описания поведения команды агентов используются как индивидуальные, так и общие обязательства и соглашения.

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

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

Разумеется, для коллективной работы между общими и индивидуальными намерениями агента должна существовать тесная связь.

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

1.3.3. Теория общих планов

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

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

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Цена магистерской

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

1.3.4. Комбинированные модели

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

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

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

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

1.3.5. Пример системы

В [Городецкий, 2010] описана командная работа подводных роботов при охране припортовой зоны подводного пространства.

Подводное пространство припортовой зоны патрулируется несколькими автономными подводными роботами (АПР). Каждому из них назначена траектория патрулирования. АПР могут связываться между собой, а также с центром управления (ЦУ).

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

Таким образом, технологии МАС применительно к задаче коллективного управления роботами, дают основания сделать следующие выводы:

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Подробнее

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

1.4. Имитационные модели

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

Однако проблема состоит в том, что насекомые – очень непростой объект для исследований. Например, нервные клетки муравьев и пчел – любимых объектов для подражания – малы по размеру и трудны для изучения. Если центральная нервная система такого простого объекта, как виноградная улитка, содержит около 10 тыс. нейронов, то у муравьев общее количество нейронов – порядка 1 млн. При этом изучение той же улитки также сопряжено с большими сложностями. В основном опыты проводятся на командных нейронах.

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

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

Муравей – это один из основных предметов исследований коллективного поведения. Но в то же время это одни из наименее удачных примеров для изучения коллективных форм, так как он слишком сложен.

1.5. Роевые алгоритмы

Роевые алгоритмы и методы зачастую относят к методам роевого интеллекта. Термин «роевой интеллект» (Swarm intelligence) был введен Х. Бени и В.Цзином в 1989 г. в контексте предложенной ими системы клеточных роботов. Задачей роевого интеллекта (РИ) является изучение и описание коллективного поведения децентрализованной самоорганизующейся системы [3], при этом методы РИ рассматривается прежде всего, как некие специфические механизмы поисковой оптимизации. Большинство алгоритмов РИ относятся к классу метаэвристик.

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

Ниже представлен перечень некоторых алгоритмов РИ, названия которых хорошо отражают суть подхода к решению задач:

  • Муравьиный алгоритм (Ant colony optimization).
  • Метод роя частиц (Particle swarm optimization).
  • Пчелиный алгоритм (Bees algorithm).
  • Оптимизация передвижением бактерий (Bacterial foraging optimization).
  • Стохастический диффузионный поиск (Stochastic diffusion search).
  • Алгоритм гравитационного поиска (Gravitational search algorithm).
  • Алгоритм капель воды (Intelligent Water Drops algorithm).
  • Светляковый алгоритм (Firefly algorithm).

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

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Заказать диссер

1.5.1. Рой, стая коллектив

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

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

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

1.5.2. Общие механизмы роения

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

1.5.3. Задача подражательного движения

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

Дело в том, что для реализации подражания неизбежно возникают следующие задачи:

  • Распознавание «своих», т.е. объектов для подражания.
  • Определение действий «своих», которым следует подражать. Иными словами, робот должен знать, что делает его окружение, т.е. распознать их действия.
  • Выполнение такого же действия. Здесь речь идет даже не столько о реализации действия, сколько о реализации поведенческого акта.

Таким образом, принцип «делай, как остальные» превращается в принцип «веди себя так же». Например, идти в том же направлении, что и прочие, отработать защитное поведение, поиск пищи и т.п.

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

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

1.5.4. Формальные методы

Говоря о моделях движения объектов, выделяются следующие базовые алгоритмы, которым должны следовать эти объекты:

  1. Движение в направлении цели;
  2. Движение в направлении центра масс своих соседей;
  3. Поддержка минимально допустимого расстояния друг между другом и препятствиями.

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

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

Тем не менее, на практике эти модели вполне применимы для решения частных технических задач.

1.6. Эволюционные методы

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

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

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

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

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

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Заказать диссер

1.7. Выбор подхода к созданию коллектива роботов

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

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

Условно, все это можно свести в таблицу, и сравнить подходы по критериям полноты информации и сложности агентов:

Таблица 2. Распределение методов создания коллектива

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

1.8. Выводы

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

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

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

Глава 2. Создание члена коллектива

2.1. Подсистемы робота

При создании робота обычно используют следующие пять групп робототехнических устройств [12; 13]:

  1. Системы восприятия информации о внешнем мире
  2. Системы воздействия на объекты внешнего мира
  3. Системы для перемещение робота
  4. Системы целеполагания и планирования действий робота
  5. Системы, обеспечивающие коммуникацию робота с человеком-оператором и/или другими роботами

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

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Цена магистерской

  1. Систему восприятия информации о внешнем мире. Сюда же всходит и система локализации робота в пространстве.
  2. Систему перемещения робота в пространстве.
  3. Систему целеполагания и планирования действий.
  4. Систему коммуникации с другими роботами. (По беспроводному каналу)

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

2.2. Анализ существующих инструментариев для создания роботов

2.2.1. Робот на базе Аrduino

Arduino — аппаратная вычислительная платформа, основными компонентами которой являются простая плата ввода/вывода и среда разработки на языке Processing/Wiring [14]. Arduino может использоваться как для создания автономных интерактивных объектов, так и подключаться к программному обеспечению, выполняемому на компьютере. Плата Arduino состоит из микроконтроллера Atmel AVR (ATmega328P и ATmega168 в новых версиях и ATmega8 в старых), а также элементов обвязки для программирования и интеграции с другими схемами. На многих платах присутствует линейный стабилизатор напряжения +5В или +3,3В. Тактирование осуществляется на частоте 16 или 8 МГц кварцевым или керамическим резонатором. В микроконтроллер предварительно прошивается загрузчик BootLoader, поэтому внешний программатор не нужен.

На концептуальном уровне все платы программируются через RS-232 (последовательное соединение), но реализация этого способа отличается от версии к версии. Плата Serial Arduino содержит простую инвертирующую схему для конвертирования уровней сигналов RS-232 в уровни ТТЛ, и наоборот. Текущие рассылаемые платы, например, Diecimila, программируются через USB, что осуществляется благодаря микросхеме конвертера USB-to-Serial FTDI FT232R. В версии платформы Arduino Uno в качестве конвертера используется микроконтроллер Atmega8 в SMD-корпусе. Данное решение позволяет программировать конвертер так, чтобы платформа сразу определялась как мышь, джойстик или иное устройство по усмотрению разработчика со всеми необходимыми дополнительными сигналами управления. В некоторых вариантах, таких как Arduino Mini или неофициальной Boarduino, для программирования требуется подключение отдельной платы USB-to-Serial или кабеля. Кроме того, существует конструктор Arduino Robot, включающий в себя управляющую и моторную платы, которые легко соединяются друг с другом, что позволяет достаточно быстро собрать готового робота.

Достоинства: Возможность быстро собрать робота, удобный дизайн, возможность передачи данных по беспроводному интерфейсу.

Недостатки: Цена (275 USD), необходимость докупать дополнительные модули (связь, датчики) отдельно.

Таким образом, набор имеет достаточно большое количество деталей, для создания достаточно сложных роботов, но имеет высокую стоимость. (Около 375 USD за каждого робота).

2.2.2. Робот на базе Lego

LEGO Mindstorms — это набор сопрягаемых деталей и электронных блоков для создания программируемого робота [15]. Наборы LEGO Mindstorms комплектуются набором стандартных деталей LEGO и набором, состоящим из сенсоров, двигателей и программируемого блока. Наборы делятся на базовый и ресурсный.

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

Достоинства: Возможность быстро собрать робота, простота.

Недостатки: Малое число портов ввода/вывода, сложность их перепрограммирования под свои задачи, высокая цена (около 10тыс. Руб), сложность реализации беспроводной передачи данных.

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

2.2.3. Другие конструкторы роботов

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

2.2.4. Создание робота собственной конструкции

Как уже упоминалось, подходящий робот-агент, должен иметь 4 подсистемы:

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Цена магистерской

  1. Система восприятия информации о внешнем мире. Сюда же всходит и система локализации робота в пространстве.
  2. Систему перемещения робота в пространстве.
  3. Систему целеполагания и планирования действий.
  4. Систему коммуникации с другими роботами. (По беспроводному каналу)

Рассмотрим создание каждой подсистемы подробнее.

Система восприятия информации о внешнем мире.

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

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

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

Система перемещения робота в пространстве.

Система перемещения в пространстве может быть основана на нескольких вариантах:

Таблица 3. Варианты шасси

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

Система целеполагания и планирования действий.

Создание этой системы является целью данной работы.

Система коммуникации с другими роботами.

Коммуникация между членами коллектива — одна из важнейших задач при создании коллектива роботов. Наиболее удобным вариантом, будет система, основанная на протоколах ZigBee, так как купленные модули практически сразу готовы к работе. Передача данных будет осуществятся через RS-232 интерфейс посредством готовых модулей Xbee Pro Series 2.

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Цена магистерской

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

2.2.5. Анализ стоимости предложенных решений

Посчитаем стоимость одного робота, если его собирать вручную:

Таблица 3. Стоимость сборки робота вручную (руб.)

Общая стоимость одного робота ручной сборки составляет 3226 руб.

Сравним три варианта стоимости одного робота (Arduino, Lego, сборка самостоятельно):

Таблица 4. Сравнение стоимости

2.3. Подведение итогов

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

Таким образом, было принято решения создать робота-агента своими силами.

2.4. Описание робота

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

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

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Заказать диссер

2.5. Выводы

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

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

Глава 3. Система позиционирования и ориентирования в пространстве

3.1. Подходы к созданию системы позиционирования и ориентации

Существует четыре основных подхода к созданию системы позиционирования и ориентации в пространстве (СПОП):

  1. Локально-автономная система.
  2. Глобальная система.
  3. Ориентация по маякам.
  4. Смешанные системы.

Рассмотрим каждую из них подробнее.

3.1.1. Локально-автономная система

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

Достоинства: Высокая автономность. Как правило, высокая точность работы таких систем.

Недостатки: Высокая стоимость и энергоемкость. Занимает место на борту робота.

3.1.2. Глобальная система

Системы глобального позиционирования позволяют не имея развитой системы   рецепторов, определять роботу свое местоположение, полагаясь на внешнюю систему ориентации. Например: GPS, ГЛОНАСС, общая камера и др. Одним из примеров такой системы является общая камера в робофутболе, определяющая местоположение каждого робота-футболиста по цветовым маркерам на его крыше (Рис.  9). Глобальные системы позволяют перенести всю тяжесть задач по локализации и ориентации робота в пространстве перенести на специальную систему позиционирования, которая передает им их координаты.

Достоинства: Такая система гораздо дешевле и несколько проще организуется, по сравнению с локально-автономным подходом. Позволяет создавать более компактных и дешевых роботов.

Недостатки: Привязка к глобальной системе сильно ограничивает область возможного действия роботов (в случае с камерой) или не дает достаточно точных данных (в случае с GPS или ГЛОНАСС и достаточно маленькими — 10см объектами).

3.1.3. Ориентация по маякам

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

Достоинства: Система достаточно проста и дешева.

Недостатки: Низкая точность позиционирования.

3.1.4. Смешанные системы

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

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Цена магистерской

3.2. Выбор подхода к созданию системы позиционирования

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

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

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

3.3. Описание системы позиционирования

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

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

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

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

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

Данная процедура происходит однократно перед выполнением основного тела программы.

Затем выполняется тело программы, куда входят следующие этапы обработки изображения:

  • Получение кадра.
  • Фильтрация.
  • Поиск точек, удовлетворяющих значениям коэффициентов HSV для каждого из трех цветов.
  • Для каждого найденного красного маркера ищутся три других маркера.
  • Вычисляется угол поворота (направление движения) робота с помощью всех 4 маркеров.

Формируется командная строка, передающаяся каждому роботу

1. Первая позиция – команда робота

2. Вторая позиция – ID робота

3. Третья позиция – координаты робота по Х

4. Четвертая позиция – координаты робота по Y

5. Пятая позиция – направление (1- Север, 2 Северо-Запад,…,8-Северо-Восток)

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Подробнее

  • Передача строки роботам.
  • Вывод данных.

Идентифицирующие маркеры робота делятся на три типа:

  • Первый тип красного цвета(1) обозначает то, что в некоторой области вокруг него могут быть маркеры других типов. Кроме того, вместе с другими маркерами, он показывает куда направлены передние дальномеры робота. Этот тип маркера распознается первым.
  • Второй тип маркеров(2) может быть либо зеленым, либо синим и кодирует команду, за которую выступает робот. Кроме того, он играет вспомогательную роль для определения местоположения робота.
  • Маркеров третьего типа (3 и 4) на роботе два, они также могут быть либо зелеными, либо синими и кодируют самого робота. Играют вспомогательную роль для определения местоположения робота и определения его угла поворота.

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

Маркеры расположены таким образом, чтобы их расстояние между центрами маркеров отличалось друг от друга как можно больше. (т.е. расстояние между центрами 1 и 2 маркеров равно 4см, а расстояние между 2 и 3, и 2 и 4 равно 5,7 см).

В ходе испытаний было выявлено, что распознавание и передача происходит успешно.

3.4. Выводы

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

Глава 4. Система моделирования

4.1. Обзор существующих систем моделирования

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

На данный момент существует достаточно большое количество систем виртуального моделирования роботов, такие как MRDS, Webots, player/stage, GameLogo и др.. Рассмотрим некоторые из них.

4.1.1. Система моделирования MRDS

Microsoft Robotics Developer Studio — Windows-ориентированная среда для управления роботами и их симуляции [16]. MRDS основана на библиотеке CCR (Concurrency and Coordination Runtime), .NET-реализации библиотеки для работы с параллельными и асинхронными потоками данных, используя обмен сообщениями, и DSS (Decentralized Software Services) — облегченное средство создания распределенных приложений на основе сервисов, которое предусматривает управление множеством сервисов для корректировки поведения в целом. Особенности:

  • Язык визуального программирования Microsoft Visual Programming Language для создания и отладки программных приложений для роботов.
  • Веб-ориентированные и windows-ориентированные интерфейсы
  • Симуляция 3D (включая аппаратное ускорение)
  • Упрощенный доступ к датчикам и исполнительным механизмам робота
  • Осуществляет поддержку нескольких языков, включая C#, Visual Basic .NET, JScript и IronPython.

Microsoft Robotics Developer Studio поддерживает модульность для добавления новых сервисов в комплект. В настоящее время доступны:

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Заказать диссер

  • Soccer Simulation (Симуляция футбола)
  • Sumo Competition (Соревнование по сумо) от Microsoft
  • Maze Simulator (Симулятор лабиринта) — программа для создания миров и стен, которые могут исследовать при помощи виртуального робота.

Инструменты, позволяющие разрабатывать MRDS-приложения, включают в себя графическую среду (Microsoft Visual Programming Language : VPL); утилиты командной строки, позволяющие взаимодействовать с проектами Visual Studio на языках C#, C++ или VB.NET; поддержку скриптовых языков, как например, IronPython; и инструменты симуляции 3D. Таким образом, MRDS достаточно развитая система виртуального моделирования, поддерживающая множество различных функций и утилит, позволяющих проводить достаточно сложные моделирования.

4.1.2. Система моделирования Webots

Система моделирования Webots является профессиональным симулятором роботов [17]. Webots использует ODE для обнаружения столкновений и моделирования динамики твердого тела. Библиотека ODE позволяет точно имитировать физические свойства объектов, таких как скорость, инерции и трения.

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

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

Программы управления роботом можно записать в C, C + +, Java, Python и MATLAB, AIBO, Nao.

Данная система по своим возможностям не уступает MRDS, но в отличие от нее, является платной.

4.1.3. Система моделирования player/stage

Среда ориентирована как на *NIX системы, так и на NT [18]. Состоит из непосредственно среды описания — Player и системы 2D эмуляции Stage, который является сервером, ожидающим запросы от клиентов и изменяющем положение и состояние объектов, которые загружены в данной эмуляции. Проект Player содержит клиентские библиотеки для работы с сервером Stage на трех языках: C, C++, Python. Также существуют неофициальные клиенты на других языках, например Java. Клиент-серверный подход позволяет легко использовать библиотеки для взаимодействия и моделировать робота совершенно не занимаясь написанием эмулятора, тратя минимум усилий на создание и описание объектов, которые в нем находятся.  Для моделирования в 3D создана среда Gazebo.

Данная среда моделирования уступает по своим возможностям MRDS и Webots, но также является достаточно мощным инструментом для моделирования.

4.2. Анализ существующих систем моделирования

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

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Подробнее

Таблица 5. Сравнение и анализ рассмотренных систем моделирования

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

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

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

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

4.3. Система моделирования

Система моделирования состоит из:

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

Система вывода результатов

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

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

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Подробнее

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

4.4. Выводы

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

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

Глава 5. Алгоритмы выбора и достижения цели

5.1. Анализ получаемых роботом данных

Как уже было сказано, робот имеет 3 источника получения данных:

  1. Данные с общей камеры.
  2. Данные с ИК-дальномера.
  3. Данные с датчика полосы.

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

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

Таким образом, остаются данные с камеры, с помощью которых робот оценивает внешнюю обстановку. Камера дает информацию о:

  1. Координатах всех роботов.
  2. Направлении всех роботов.

Эти данные обрабатываются каждым роботом, и, после обработки, он принимает какое-либо решение.

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

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Цена магистерской

5.2. Базовый выбор первоначальной цели

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

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

Матрица выбора представляет собой квадратную матрицу, размером NxN, где N – общее количество роботов, Xmn время достижения роботом m робота n. При этом Xmn:

где, Smn -расстояние от робота m до робота n, ANGmn — угол между направлением робота m и роботом n, Sbn — расстояние до края полигона робота n, V — скорость роботов, VA — скорость поворота.

Каждый робот m находит минимальное значение Xmn min и считает его наиболее оптимальным.

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

Роботы не могут дальше продолжать движение, так как им мешают роботы-союзники. Если роботы будут стараться объезжать препятствие, ориентируясь на ИК-дальномер, время Xmn — перестанет отражать реальное время достижения цели, и, как следствие, его вычисление в таком случае не требуется, что ставит под сомнение идею планирования.

Чтобы избежать такой ситуации, необходимо:

  1. Ограничить число роботов, которые атакуют одну и ту же цель приемлемым числом (например 1), чтобы избежать сильной концентрации роботов на малой площади.
  2. Учитывать время ожидания/объезда препятствия, находящегося на траектории движения.
  3. Учитывать время ожидания/объезда препятствия, которое может появится на траектории движения.
  4. Использовать возможность переоценивать приоритетность цели через каждый определенный момент t. (Учитывать динамику среды)

5.3. Усовершенствованный выбор первоначальной цели

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

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

  • Сравнивается время T1, необходимое на поворот первого робота и время T2, необходимое на поворот робота, который ему мешает.
  • Если Т1 > T2 предполагается, что мешающий робот успеет уйти с линии движения первого робота, следовательно, он ему не помешает.
  • Иначе, учитывается время T3, необходимое первому роботу, для достижения робота-препятствия.
  • Если T3 > T2, то мешающий робот успеет уйти с линии движения первого робота.
  • Иначе вычисляется время T4 = T3-T2, оно прибавляется к времени t1, которое необходимо для достижения цели.

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

  • Найти пересечения траекторий выбранного робота, с траекториями других роботов.
  • Вычислить время Т1, необходимое для достижения первого робота точки пересечения.
  • Вычислить время Т2, необходимое для достижения второго робота точки пересечения.
  • Если они равны, то роботы встретятся, и необходимо учесть время Т3, необходимое для объезда/ожидания того робота, чья цель дальше.

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

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

5.4. Учет динамики среды

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

5.5. Выводы

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

Заключение

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

Нужна помощь в написании магистерской?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Подробнее

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

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

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

  1. Проанализированы текущие работы в области групповой робототехники и методы создания коллективов роботов. На основании данного анализа был выбран наиболее подходящий метод.
  2. На основании анализа существующих инструментариев роботов было принято решение о создании робота собственной конструкции. Создан коллектив таких роботов.
  3. Создана система позиционирования и ориентации роботов в пространстве.
  4. Создана система виртуального моделирования коллектива роботов для отработки алгоритмов на модели.
  5. Написан ряд алгоритмов, способных работать в условиях ограниченных когнитивных способностях робота, которые в целом дают базовое планирование действий всего коллектива.

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

Список использованных источников

1. Карпов В.Э. Коллективное поведение. Желаемое и действительное.//Современная мехатроника. Сб. научн. трудов Всероссийской научной школы-Орехово-Зуево,2011.C.35-51.
2. Alex Kushleyev, Daniel Mellinger, Vijay Kumar. Towards A Swarm of Agile Micro Quadrotors. 2012. URL: http://www.roboticsproceedings.org/rss08/p28.pdf
3. Миллер, П. Роевой интеллект: Муравьи, пчелы и птицы способны многому нас научить.// National Geographic Россия. — 2007г. — № 8. — С. 88-107.
4. Официальный сайт проекта I-Swarm URL: http://i-swarm.org/MainPage/Project/P_Overview1.htm
5. Swarm-bots: Swarm iof self-assembling artifacts URL: http://www.swarm-bots.org/
6. Official site of project IRobotSwarm URL: http://www.irobot.com/governmentindustrial/
7. Open source micro-robotic project SwarmRobot http://swarmrobot.org
8. Centibots: The 100 robots project URL: http://www.ai.sri.com/centibots/
9. Swarmanoid: Towards humanoid robotic swarm URL: http://www.swarmanoid.org/
10. The Official Global Website of Nissan Motor Company URL: http://www.nissan-global.com/
11. Футбол роботов: виртуальная лига URL: http://www.keldysh.ru/pages/robosoccer/
12. Представление знаний в человеко-машинных и робототехнических системах. Том D. Фундаментальные и прикладные исследования в области робототехнических систем. – М.: ВЦ АН СССР – ВИНИТИ, 1984.
13. Накано Э. Введение в робототехнику: Пер. с япон. – М.: Мир, 1988.
14. Описание платформы Arduino URL: http://ru.wikipedia.org/wiki/Arduino
15. Описание платформы Lego URL:http://ru.wikipedia.org/wiki/LEGO_Mindstorms
16. Описание Microsoft Robotics Developer Studio URL: http://ru.wikipedia.org/wiki/Microsoft_Robotics_Developer_Studio
17. Описание системы моделирования Webots URL: http://en.wikipedia.org/wiki/Webots
18. Описание системы моделирования Player URL: http://playerstage.sourceforge.net/
19. Воробьев В.В. Групповая борьба роботов // Материалы международной студенческой конференции «НОВЫЕ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ» — С. 194
20. Воробьев В.В. Алгоритм поиска и планирования пути для задач групповой робототехники // Материалы VII Международной научно-практической конференции “Интегрированные модели и мягкие вычисления в искусственном интеллекте” – С.793-798