Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/





Аннотация

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

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

Объем данной работы составляет 98 страниц, включая титульный лист, аннотации и оглавление. Выпускная квалификационная работа содержит 25 иллюстраций, 9 таблиц. В работе было использовано 27 источников информации.

The purpose of this work is to create separate models of imitative behavior and vicarious learning in groups of mobile robots as the basis for organizing collective behavior with the aim of solving group robotics problems. In the course of the course work, a review of models of imitative behavior and vicarious learning in solving group robotics problems was made, a choice and analysis of the solved problem from the field of group robotics were made, methods and algorithms for implementing the selected models were developed.

A program for simulating the mechanism of imitative behavior was developed and implemented using the example of a foraging task in an anthill, an analysis of the results is given.

The volume of this work is 98 pages, including the title page, annotations and table of contents. Interdisciplinary course work contains 25 illustrations, 9 tables that describe the algorithms for the formation of the description of actions and the route and the rules for their interpretation. 27 sources of information were used in the work.



Оглавление

• Введение
• 1. Модели социального поведения
• 1.1 Типы социального поведения
• 1.2 Социальные сообщества
• 2. Обзор моделей подражательного поведения и викарного научения в групповой робототехнике
• 3. Предлагаемая модель подражательного поведения и викарного научения в групповой робототехнике
• 3.1 Эусоциальные насекомые
• 3.2 Задача для моделирования
• 3.3 Ориентация робота в пространстве
• 3.4 Возвращение разведчика домой
• 3.5 Инициация подражательного поведения
• 3.6 Формирование пути преследователя
• 3.7 Инициация поиска пищи
• 4. Результаты экспериментов
• Заключение
• Список литературы
• Приложение 1
• Приложение 2


Введение

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

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

Нетрудно заметить, что изучаются только отдельные задачи, а разработанные методы решений плохо интегрируемы. Причины этого могут лежать в отсутствии методологической основы для построения систем в групповой робототехнике, а также в неоднозначности терминологии [2]. Современная групповая робототехника не располагает единым подходом, который бы определял сложность организации во взаимоотношениях в коллективах роботов. Можно также заметить некоторый пробел между имеющимися моделями взаимодействия в ГРТ, а именно между участниками коллектива. В одном случае они представляются примитивными объектами, которые обладают простой архитектурой, в другом - сложными интеллектуальными агентами. Например, в [3] рассмотрены модели форм поведения, которые начинаются от простейших, постепенно усложняются и заканчиваются человеком. Проблема заключается в том, что поведенческие адаптации простейших форм описываются лишь набором рефлексов и их комбинаций. Отсюда следует, что решаются либо самые простые базовые задачи, либо приводятся попытки решений высокоинтеллектуальных задач, под которыми нет необходимой методологической основы.

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

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

Чтобы достичь поставленной цели необходимо выполнить ряд задач:

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

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

- разработать алгоритмы и методы для реализации выбранных моделей;

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

- проанализировать результаты моделирования.

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

Предметом исследования является применение модели подражательного поведения и викарного научения как основы для организации коллективного поведения в ГРТ.

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

На защиту выносятся следующие основные положения:

1) алгоритм возвращения робота-разведчика домой после нахождения необходимого объекта;

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

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

4) программа по имитационному моделированию для определения эффективности и работоспособности разработанных методов и алгоритмов.



1. Модели социального поведения

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

Определим, что является социальным поведением.

А. Фет [4] определил социальное поведение как взаимодействие двух или более индивидуумов (особей) в популяции одного вида.

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

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

Для такой формы поведения большую роль играют коммуникативные сигналы, с помощью которых происходит взаимодействие особей друг с другом. У муравьев такие сигналы могут быть химической природы (феромоны). Муравьи могут по запаху отличать сородичей от чужаков, живых особей - от мертвых. Химические вещества, выделяемые личинками муравьев, привлекают внимание взрослых особей, чтобы взрослые муравьи их покормили. Муравьи обладают особыми коммуникативными сигналами: характерными позами (ФКД) и передачей информации с помощью постукивания лапками по телу другого муравья [6].

Для жизни в коллективе особое значение имеет согласованность поведения отдельно взятых особей при возникновении угрозы группе. Пчелы и осы, ориентируясь на химические сигналы, при угрозе начинают выделять «вещества тревоги», которые распространяются по воздуху на небольшие расстояния, помогая определить место исходящей опасности. Чем выше опасность, тем больше сила выделяемого сигнала [7]. Муравьи передают сигнал тревоги, используя тревожную позу и ФКД [6].

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

Во всех приведенных примерах информация передается в измененном, символическом виде.

1.1 Типы социального поведения

Социальные механизмы поведения неизбежно проявляются, когда животные держатся вместе, так как без них невозможно эффективное функционирование группы. Одними из важнейших типов социального поведения являются следующие [5, 8, 9,10].

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

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

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

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

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

2. Самцы должны демонстрировать принадлежность к мужскому полу.

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

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

1.2 Социальные сообщества

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

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

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

Отличительные особенности группировок:

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

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

3. связи между особями должны быть прочными;

4. группа должна соблюдать целостность (проявлять агрессию к "чужакам" своего вида)

Согласно Эйзенбергу (Eisenberg, 1965) организованные сообщества должны удовлетворять следующим критериям:

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

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

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

4. Особи, входящие в состав группы, не меняются.

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

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

1.3 Механизмы социального поведения

В Таблица 1 описаны механизмы поведения, соответствующие уже рассмотренным типам поведения [2, 13].

Таблица 1. Механизмы поведения

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

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

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



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

Стоит отметить, что в существующих трудах подражательное поведение в робототехнике вероятнее всего встретить в описании сложных интеллектуальных систем, которые, чаще всего, направлены на имитацию действий человека или обучение [15, 16]. Очевидно, что архитектура и программное обеспечение таких систем достаточно сложные. Привлекательностью групповой робототехники является именно простота строения объекта - члена группы. Агенты по отдельности не вызывают интереса и не обладают сложным оборудованием, но в процессе коллективного взаимодействия они проявляет свои свойства. Данный подход обеспечивает бесперебойность работы, потому как выход из строя агента не повлияет на работу коллектива.

В [17] подчеркнуто, что основной проблемой реализации подражательного поведения является осознание того, чему конкретно следует подражать. Одна из предложенных схем подражательного поведения основана на реализации определенной коммуникативной составляющей в коллективе. Робот издает определенный сигнал при возникновении неких условий: в ответ на некоторое действие или на полученный результат. Таким образом он оповещает соседей о своем состоянии. В работе приведен пример семантической сети, реализующей реакции агентов на опасность. Чтобы определить позитивный/негативный результат определенного действия предложено наделять робота некоторым эмоциональным механизмом, где эмоцией является степень удовлетворения потребностей [19]. Примеры правил, которые управляют поведением агента (робота) с помощью эмоций, представлены ниже:

“ЕСЛИ (голодный), ТО (искать еду)”

“ЕСЛИ (обнаружен противник), ТО (бежать)”

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

Рис. 1. Генерация и восприятие фразы

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



Рис. 2. Схема подражательного поведения

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

Рис. 3. Красным цветом выделены лидеры

В работе [21] описывается механизм взаимодействия учитель-ученик. При инициализации системы агенты получают на вход словарь цветов для изучения, чтобы различать участки и уметь описать их местоположение в соответствующей терминологии (расстояние и ориентация относительно точки изменения состояния). Словарь начинает передаваться от учителя T0, имеющего всю базу лексики с самого начала, к остальным участвующим роботам, которые не знают словарь при инициализации системы. АгентT0 не учится, его словарь не изменяет своего состояния на протяжении всего эксперимента. Если же ученик стал достаточно опытным (то есть провел наблюдения за одними и теми же парами измерений сигнала-датчика достаточное количество раз (Рис. 4)), он становится учителем, но продолжает учиться, даже будучи учителем. Словарный запас передается от учителя к ученику с использованием подражательного поведения. Это происходит благодаря взаимному наблюдению агентов. Агенты используют фототаксис (следящие огни), чтобы следовать друг за другом, а так как следование взаимно, в итоге это приведет к связи между этими агентами. Учитель ждет ученика, если тот идет медленнее, поэтому возможность того, что агенты потеряют друг друга, очень мала.

Рис. 4. Система учитель-ученик.

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

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

Рис. 5. Передатчик виртуальных феромонов

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

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

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

Рассмотренные модели [21, 22] являются централизованными, то есть обладают некоторым абстрактным слоем, в котором происходят вычисления в каждый момент времени (положение соседа, общий феромоновый фон). Достоинством таких моделей является то, что они не привязаны к конкретной территории. Но в то же время, данные решения невозможны для технической реализации из-за невозможности создания роботов с такими характеристиками, которые бы удовлетворяли данным моделям.

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

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



3. Предлагаемая модель подражательного поведения и викарного научения в групповой робототехнике

3.1 Эусоциальные насекомые

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

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

1) вместе постоянно живут насекомые двух и более последовательных поколений;

2)в группе существует кооперация между ее членами;

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

Согласно [24] плодовитые и бесплодные особи общественных насекомых издавна относится к разным кастам. Например, «царицами» и «царями» называют насекомых плодовитой касты. Бесплодная касты называется рабочими: насекомые касты выполняют различные работы и вскармливают потомство «царицы», которая занимается откладкой яиц. Размеры бесплодных особей могут отличаться по размерам. Наиболее крупных особей выделяют в отдельную субкасту, называемую "солдаты". Главной задачей солдат является охрана гнезда и выполнение других трудоемких работ. Многообразие форм в колониях общественных насекомых называется социальным полиморфизмом. Разделение функций между членами колонии лежит в основе полиморфизма. Прежде всего это разделение между кастами репродуктивных функций: плодовитые самки приносят потомство, а бесплодные рабочие заботятся о личинках. Среди бесплодной касты существует внутреннее распределение обязанностей. Оно может обуславливаться размерами и строением тела, возрастом или иными критериями. Таким образом в колонии общественных насекомых можно наблюдать довольно рациональное разделение труда. Такое разделение функций между особями называется полиэтизмом. Без него невозможно существование достаточно большого сообщества насекомых. У многих видов число особей в колонии превышает сотни тысяч и даже миллионы.

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

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

3.2 Задача для моделирования

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

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

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

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

Разобьем задачу на этапы:

Разведчик:

· Поиск объекта (случайное блуждание)

· Возвращение в точку отправления после нахождения объекта

· Оповещение агентов, находящихся в точке отправления (у муравейника)

· Повторение пути до объекта

Фуражир:

· Следование за разведчиком

Методы и алгоритмы поиска объекта разведчиком и повторения пути были представлены в работе [25].

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

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

- правила формирования сведений об обратном маршруте робота, по которому он возвращается «домой»;

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

- правила формирования сведений о движении за выбранным роботом.

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

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

3.3 Ориентация робота в пространстве

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

Также, роботы наделены набором базовых действий: движение вперед/назад, повороты направо/налево, остановка, «зрение» в области видимости в 180°, определение расстояние до объектов и определение направления.

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

Пример маршрута, составленный роботом, умеющим различать цвета:

1. Впереди-справа близко красный ориентир

2. Справа ориентир красный, впереди-слева близко синий ориентир

3. Красный ориентир пропал из поля зрения, слева синий ориентир

И т.д.

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

Так как нет четкого понятия направления, приведем шкалу направлений для области видимости 180° (Таблица 2).



Таблица 2. Шкала направлений

Рассмотрим теперь вопрос, как роботы-последователи будут следовать за роботом-разведчиком.

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

Помимо попадания робота-разведчика в поле зрения последователя, робот-последователь должен иметь такое направление , чтобы положение робота-разведчика относительно последователя было как можно больше приближено к значениям переменной «Впереди» в области видимости последователя. Если робот-разведчик пропал из области видимости робота-последователя, то робот-последователь начинает ориентироваться на тех роботов, в поле зрения которых находится разведчик.

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

Для реализации указанных процедур могут использоваться конечные автоматы [27]. Будем использовать автомат Мили для решения данной задачи.

Автомат - это такая система, функция которой может быть описана с помощью использования множества внутренних состояний Q {q} таким образом, что для каждого внутреннего состояния указано, в какое следующее состояние попадет система при получении входного символа x, и какой символ y формируется на выходе. Выделяется начальное состояние системы. В случае конечных множеств X, Y, а, также, Q, автомат называют конечным. Автомат Мили -- конечный автомат, выходная последовательность которого зависит от состояния автомата и входных сигналов. Это является основным преимуществом использования автомата Мили, так как автомат имеет возможность реагировать в течение текущего такта.

В дополнение к автоматам, созданным в работе [25], разработаем автоматы для реализации недостающих процедур.

3.4 Возвращение разведчика домой

В работе [25] был описан способ и алгоритмы создания описания маршрута. Ниже представлено их краткое их изложение.

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



Затем для сопоставления описания маршрута с самим маршрутом меняют форму записи описания, приведя его по точкам (по ориентирам):

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

Описание маршрута роботом-разведчиком происходит по следующему алгоритму:



Алгоритм создания описания маршрута

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

Алгоритм следования по маршруту



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

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

Рис. 6. Маршрут движения робота: а) поиск пищи; б) возврат робота домой

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

Таблица 3. Преобразование маршрута

Самой трудной задачей здесь является начало движения в обратном направлении к дому. Разведчик дошел до объекта и ему необходимо развернуться. Нет гарантии, что робот сможет повернуться на 180°. Возникает вопрос: как это можно реализовать?

Рассмотрим рисунок ниже (Рис. 7):



Рис. 7. Начальное положение робота для движения к дому

Допустим, что последние несколько точек маршрута описаны таким образом:

1) объект 3 слева-впереди, объект 2 справа-впереди;

2) объект 3 слева, объект 2 справа-впереди;

3) объект 2 справа, объект 1 слева-впереди;

4) объект 1 справа-впереди.

На последнем 4 шаге разведчик дошел до еды и готов к возвращению в муравейник. Чтобы начать двигаться к дому, робот должен встать в исходную позицию для следующего движения по маршруту. Для этого нужно выявить ориентиры, которые должны быть в поле зрения робота. Мы не берем точки маршрута, описывающие объекты, до которых разведчик не дошел. Иными словами, мы не будем рассматривать объекты, на последних шагах имеющие одно из направлений: впереди-впереди/слева-впереди/справа.

Применяя преобразования из Таблица 3 к описанным выше точкам маршрута, мы получаем описание обратного маршрута для разведчика :

1) объект 1 не рассматривается (на последних шагах имел направление справа-впереди);

2) объект 2 впереди-слева, объект 1 не рассматривается;

3) объект 3 впереди-справа, объект 2 слева;

4) объект 3 справа, объект 2 слева.

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

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

В Таблица 4 сформулированы общие правила для выбора действий в зависимости от направления на ориентир:



Таблица 4. Правила выбора действий в зависимости от направления на ориентир

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

Рис. 8. Схема автомата начала движения к дому

На Рис. 8, Рис. 10,Рис. 11, используются следующие обозначения:

S, T - начальное и конечное состояния автомата;

N - количество тактов, в течение которых выполняется действие;

RandomTurn -случайный выбор поворота направо или налево;

L(X), FL(X), F(X), FR(X), R(X) - функции определения направления на объект Х;

D(Х) - функция, определяющая расстояние до объекта Х;

Active- функция, которая возвращает «истину», если разведчик нашел еду;

Leader - функция, которая возвращает «истину», если в области видимости робота-фуражира находится разведчик;

Home- функция, которая возвращает «истину», если разведчик добрался до дома;

LeaderF - функция, которая возвращает «истину», если в области видимости робота-фуражира находятся роботы-фуражиры с выбранными целями для преследования;

ChangeLeadC- функция изменения цвета робота-разведчика при нахождении еды и прибытии к «дому»;

Search- функция, которая возвращает «истину», если в области видимости робота-разведчика находятся точки маршрута, которые удовлетворяют условиям, описанным в 3.4;

ChangeFollowC- функция изменения цвета робота-последователя при попадании в область видимости объекта преследования (в приоритете разведчика, иначе иного фуражира);

CountF- функция подсчета доступных для преследования роботов, которые находятся в поле зрения;

IsLFF,IsRFF- функции, которые возвращает «истину», если робот левым или правым датчиком видит робота определенного цвета;

gofwd, goleft, goright, goback, stop - действия робота (вперед, налево, направо, назад и стоп соответственно).

3.5 Инициация подражательного поведения

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

Рис. 9. Привлечение внимания фуражиров

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

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

Рис. 10. Схема автомата, который управляет роботом-разведчиком: привлечение внимания (Attention)

Роботы-фуражиры, которые находятся около «дома», должны среагировать на сигнал робота-разведчика (Рис. 11).

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

3.6 Формирование пути преследователя

Рассмотрим далее поведение преследователей (фуражиров), идущих за выбранной целью.

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

Основные:

1. Следование за разведчиком.

2. Обход препятствий.

Побочная:

1. Следование за другим фуражиром

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

1. Преследователь не видит разведчика, но видит других преследователей.

2. Преследователь не видит разведчика, не видит других преследователей.

3. Преследователь не нашел цель для преследования после обхода препятствия.

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

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

Сформированный набор правил поведения для робота-последователя представлен в Таблица 5).

Таблица 5.Правила поведения робота-последователя

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

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

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

1) фуражир видит «ведущего» и следует за ним (зеленый);

2) фуражир ищет робота для преследования (синий).

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

Если в области видимости есть несколько роботов, претендующих на роль ведущих, выбирается тот, кто находится ближе к направлению «впереди». Если таких роботов несколько - случайный выбор.

Рассмотрим ситуацию, когда агент a1 следует не за ведущим фуражиром, а за «преследователем» - агентом a2. Если «преследователь» а2 потерял разведчика, то он начинает искать другой ориентир. Агент a1 наблюдает за поведением «преследователя» и видит, что a2 поменял цвет, следовательно, ищет цель для преследования. Это является сигналом для агента a1, что необходимо также начать поиск нового ориентира для преследования. Данный механизм основан на принципах викарного научения, в которых научение происходит через наблюдения за другой особью и группой особей.

Автомат, который реализует процедуру выбора нового лидера при потере объекта для преследования, приведен на рисунке Рис. 12.

Рис. 12. Схема автомата, который управляет роботом-фуражиром при потере объекта для преследования



Алгоритм следования за разведчиком

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

3.7 Инициация поиска пищи

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

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

Потребности и эмоции агента

Чтобы использовать описанный выше процесс в созданной модели, необходимо наделить каждого агента определенным набором потребностей. Этот подход базируется на потребностно-информационной теории эмоций П.В. Симонова [18]. В данном случае эмоция - это оценка текущей потребности агента [19]. Обмен пищей будет представлен как обмен сигналами, содержащими некоторые значения. Для описания эмоции агента будем использовать следующую формулу [19]:

E=N (I_has - I_need ),

где E - эмоция, ее величина, качество и знак (в данном случае эмоция - потребность в пище); N - текущая сила необходимости конкретного агента; I_has - информация о количестве ресурсов у агента в настоящий момент; I_need - информация о текущих потребностях агента. Разность между I_has и I_need, то есть между возможностью удовлетворить потребности и самими потребностями, определяет эмоцию текущей ситуации. Если робот может удовлетворить потребности имеющимися возможностями, то полученная эмоция будет положительной.

Определим два типа агентов:

1. Сытые. Сытые агенты обладают достаточным количеством еды и готовы ею поделиться. Сытый агент не инициирует обмен пищей (сигналами), но отвечает на сигналы «голодных» агентов. Параметр N сытых агентов будет увеличиваться после обмена с голодными N+0,5, параметр I_has будет уменьшаться I_has -1.

2. Голодные. Голодные агенты забирают часть «еды» у сытых. То есть параметр N таких роботов уменьшается за счет переданных сытым агентом сигналов N-0,5, параметр I_has становится равен минимальному порогу сытости.

На текущее состояние сытости N также влияет затраченная агентом энергия. Следовательно, с каждым следующим обменом сигналами потребность N для каждого агента будет увеличиваться, имитируя появление чувства голода: N=N+0,1. Если параметр N достигает предельного значения N=x, то параметр E становится отрицательным, а агент переходит в состояние «голодный».

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

“ЕСЛИ (голодный), ТО (искать еду)"

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

Уровни сытости

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

Уровень сытости в данной модели - это значения начального количества ресурсов агента I_has и значения параметра потребности в пище N.

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

Уровни активности

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

Согласно исследованию [28], в муравейнике все время активно трудятся только 3% процента муравьев, 72% не заняты минимум половину времени, а 25% вовсе не удалось застать за работой. Применяя данное распределение к нашей задаче получаем, что только 3% агентов будут являться активными и при наступлении чувства голода пойдут искать пищу. Так как для решения задачи нам всегда необходим хотя бы один активный агент, то при моделировании менее 16 агентов количество активных агентов будет равняться 1. В остальных случаях количество активных высчитывается согласно правилам округления.

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

4. Результаты экспериментов

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

Моделирование проводилось с использованием системы моделирования Kvorum, которая работает под управлением фреймворка ROS (Robot Operating System). Инструкцию по установке системы можно найти в Приложении 1. Программа написана на языке Python 2.7. Полный текст программы приведен в Приложении 2.

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

Система описана скриптом Hunger.py. В ней осуществляется моделирование группы роботов, которые блуждают по территории и обмениваются сигналами (пищей) друг с другом; отправляются на поиск пищи при наступлении чувства голода; инициируют подражательное поведение (привлекают к себе внимание); повторяют путь до объекта (или идут за выбранным ориентиром). На Рис. 13 представлена схема системы «Hunger».

...