Coordination in Multi-Agent RoboCup Teams Харламов Михаил, 544 гр.

RoboCup Simulation league – игра ведется компьютерными программами. Команда – 11 игроков, каждый игрок – отдельная программа. Игра идет на Soccer Serverе. Такая среда удобна для отработки коллективных стратегий и обучения системы. В этом случае речь идет о MAS (Multi Agent Systems) Middle-size league – игра идет на поле 5 на 9 метров, робот должен умещаться в цилиндр 50 см. в диаметре и 80 см. в высоту. В команде 1 голкипер и 3 игрока. В этих условиях возникает множество дополнительных задач связанных с наличием физических сенсоров, шумов и т.д. В этом случае говорим о MRS (Multi Robot Systems)

Рассматриваемые вопросы Координированное поведение в MAS Архитектуры MAS Коммуникации в MRS Координация в MRS

Координированное поведение в MAS Есть непредсказуемая среда и задачи, которые достаточно сложно достижимы MAS должна быть скоординирована в терминах разделения задач, разделения ресурсов, формирования команд и т.д. Действия в MAS иерархичны, т.е. есть low- level действия, которые являются производными от cooperative действий

Координированное поведение в MAS Role-based decision mechanism Cooperative behaviour through implicit communication A layered approach to learning client behaviours Environment modelling Emergent cooperative behaviours Behaviour-based position selection

Position Selection Behaviors for Coordination Во время игры нужно выбирать позиции, в которые будут двигаться роботы Position Selection Behavior (PSB) Среда (RoboCup simulation League): есть сервер и клиентские программы (игроки), сервер симулирует все движения игроков и мяча. 1 раз в 100мс игрок может передать одну команду серверу (если не передает очередную команду, то стоит на месте, если передает больше одной – выполняется случайная из переданных) 1 раз в 150мс игрок получает данные с сенсоров

Position Selection Behaviors for Coordination Essex Wizards Team

Position Selection Behaviors for Coordination Low-level Basic Behaviors Сервер понимает только команды Kick Turn Dash На самом деле используя память набор действий расширяется Advanced Kick – двигать мяч в несколько этапов до той позиции из которой собираемся делать удар Move – комбинация Turns и Dashes Dribble – ведение мяча Look – смотреть за мячом/искать мяч, если он вне зоны видимости

Position Selection Behaviors for Coordination High-level Basic Behaviors Intercept – предсказать положение мяча через определенное время и двигаться в этом направлении Clear ball – вывести мяч со своей половины поля Send ball – вывести мяч на позицию для поражения ворот соперника Pass ball – анализирует положения игроков команды и считает кому из них лучше всего дать пас, а также вероятность успеха паса Position Selection – определить куда лучше всего двигаться в данный момент

Position Selection Behaviors for Coordination Position Selection Behaviors Нужно учитывать следующие факторы: позиции игроков, позицию мяча, возможности игроков

Position Selection Behaviors for Coordination Fixed & Fixed Relative PSB – фиксированная точка на поле или точка фиксированная относительно положения мяча Tracker PSB – защита, выбирается точка между оппонентом и своими воротами Marker PSB – позиция для перехвата паса оппонента или его удара по воротам Ball Tracker PSB – позиция на линии между мячом и воротами Offside Trap PSB General Purpose PSB – выбираем позицию так чтобы максимизировать расстояние между позицией и другими игроками на поле и минимизировать расстояние между позицией и воротами соперника и позицией и мячом. При этом есть еще 4 ограничения: оставаться рядом с home location, оставаться в границах поля, избегать оффсайд-позиции, находиться в позиции, в которой возможно получение паса

Position Selection Behaviors for Coordination Реализация Есть библиотека PSB Игрок активирует конкретную PSB в зависимости от текущей ситуации Согласованность в действиях нескольких игроков достигается анализом положения игроков на поле и тем, что каждый игрок использует свой identical code, это гарантирует, что все игроки не будут играть одну и ту же роль

Position Selection Behaviors for Coordination External configuration Вместо того чтобы передавать в PSB множество констант, большая часть конфигурации PSB прописана в конфигурационном файле и подгружается в начале игры Это позволяет отделить tactical-details от implementation-details

Position Selection Behaviors for Coordination Failsafe operation Конкретная PSB не всегда может выдать позицию (мешает положение мяча или игроков на поле) В этом случае она выдает home position Или же может быть реализован стэк PSB, так что если первая PSB не может выдать ответ, управление переходит к следующей

Архитектуры MAS Простейший вариант: каждый агент действует if stimulus then reaction Belief-Desire-Intention Architecture (BDI) обычно 2 основных процесса: поставить перед собой задачи, решить, как эти задачи будут выполнены. Гибридные архитектуры Кроме того задача может быть разбита на несколько подзадач, что влечет за собой появление иерархических слоев архитектуры

Архитектуры MAS Control flow в слоистых архитектурах Horizontally layered Каждый слой ведет себя как агент (имеет доступ к входным данным и может совершать действия) Vertically layered Есть слои занимающиеся обработкой входных данных, промежуточные и совершающие действия

Holonic architecture for coordination and control Holonic Manufacturing System HMS based on the concept of holon defined as autonomous and cooperative building block of a manufacturing system for transforming, transporting, storing and/or validating information and physical objects In the HMS framework soccer can be viewed as a multilevel real-time system, requiring a multi-agent approach and exhibiting an enterprise-like structure suitable for applying a manufacturing paradigm

Holonic architecture for coordination and control Holarchy – иерархия саморегулирующихся управляющих блоков (holons) которые действуют как 1.Автономные целые, управляющие своими частями 2.Зависимые части, подчиненные блокам высшего уровня 3.Блоки, действующие в координации с их локальной средой Holarchy позволяет создавать очень сложные системы, которые эффективно используют ресурсы и очень устойчивы к возмущениям среды, а также способны адаптироваться к изменяющейся среде

Holonic architecture for coordination and control Одно из самых важный свойств holarchy – это возможность модифицировать себя, т.е. создавать временные иерархии Поэтому holarchy позволяет соблюдать баланс между моделями принятия решений hierarchical control (fixed, static, preestablished) и heterarchical control (autonomous, decentralized, flexible)

Holonic architecture for coordination and control PROSA – Product-Resource-Order-Staff-Architecture The resource holon contains a physical part namely a production resource of the manufacturing system and an information processing part that controls the resource The product holon holds the process and production knowledge to assure the correct product manufacturing with adequate quality The order holon represents a task in the manufacturing system It is responsible for performing the assigned work correctly and on time The staff holon is implemented to assist the other three holons in performing their work

Holonic architecture for coordination and control

Holarchy level – содержит механизмы для разработки общих планов с другими holons/agents Deliberative layer – нужен для создания локальных планов и постановки локальных целей Reactive layer – содержит факты отражающие модель мира holon/agent

Holonic architecture for coordination and control Holarchy level состоит из трех подуровней: 1.Integration - вертикальное взаимодействие (игрок-команда, команда-тренер, …) 2.Cooperation – горизонтальное взаимодействие 3.Monitoring – нужен для модифицирования holarchy

Коммуникации в MRS The problem of action recognition Каждый робот в MRS должен хотя бы в общих чертах понимать какие задачи решают другие роботы в системе 2 типа MRS систем Implicit communication Нет прямого общения, выводы делаются на основе информации с сенсоров Explicit communication Есть обмен сообщениями между агентами

ETHNOS IV Expert Tribe in a Hybrid Network Operating System ETHNOS IV – распределенная операционная система реального времени, поддерживающая различные представления, коммуникации и требования исполнения Строится на ядре Posix compliant Linux RT kernel Включает в себя специальный протокол для коммуникаций с учетом шумов Объектно-ориентированный API Набор дополнительных средств для разработки (robot simulator, etc)

ETHNOS IV Expert – центральное понятие в ETHNOS IV Expert - a concurrent agent responsible for a specific deliberative or reactive behaviour Эксперты могут быть организованы в группы, однако эти группы не иерархичны

Inter-Expert and Inter-Robot Communication EIEP Expert Information Exchange Protocol The EIEP is essentially an efficient implementation of a network distributed blackboard based on a publish/subscribe protocol Эксперт может подписаться на получение сообщений определенного типа. Когда некий другой эксперт передает сообщение данного типа, подписавшийся его получает. При этом получивший сообщение не знает о том кто его отправил и кто еще его получил

Inter-Expert and Inter-Robot Communication ETHNOS также поддерживает механизм коммуникаций между роботами При такой коммуникации все происходит почти также, только полезно знать кто именно передает сообщение, а также различать внутренние (внутри одного робота) и внешние сообщения, чтобы не создавать лишний трафик Кроме того можно создавать communication clubs к которым могут присоединяться игроки. Например communication club из робота, ведущего мяч и помогающего ему

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

Inter-Expert and Inter-Robot Communication Поскольку обычно коммуникации между роботами происходят посредством беспроводных сетей, то возникают трудности с использованием стандартных протоколов – TCP/IP, UDP TCP/IP крайне неэффективен в таких условиях UDP не гарантирует доставки сообщения

Inter-Expert and Inter-Robot Communication Поэтому был разработан специальный протокол EEUDP Ethnos Extended UDP У каждого сообщения есть приоритет Сообщения с низшим приоритетом идут как UDP, т.е. без гарантии их доставки Сообщения с высшим идут как TCP/IP, однако не гарантируется сохранения правильного порядка сообщений Сообщения со средними приоритетами повторяются каждый n мс. пока не придет подтверждение их получения

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

Distributed Coordination in Heterogeneous Robotic Teams Предположения: Communication-based coordination Т.е. есть возможность коммуникации между роботами Autonomy in coordination Т.е. роботы способны выполнять свои задачи (возможно менее эффективно) даже в случае отсутствия коммуникаций Heterogeneity in the multi agent system Т.е. игроки гетерогенны как с точки зрения software, так и с точки зрения hardware

Distributed Coordination in Heterogeneous Robotic Teams Кроме того координация поддерживает роли (атакующий, защитник и т.д.) и стратегии (нападение, защита) Стратегия выбирается из вне тренером Роли же могут динамически изменяться во время игры в зависимости от положения игроков на поле

Distributed Coordination in Heterogeneous Robotic Teams Некоторые наблюдения: Если более чем один робот из одной команды пытается выполнить одно действие (бежать к мячу) они скорее всего помешают друг другу, ухудшая эффективность команды Для победы необходимо контролировать разные части поля Например не все роботы должны атаковать, некоторые должны оставаться в защите, иначе будет пропущено множество голов

Distributed Coordination in Heterogeneous Robotic Teams Исходя из этих наблюдений, базовая formation команды требует чтобы один робот бежал к мячу, второй поддерживал его, а третий находился в защите Однако могут приниматься и другие формации в зависимости от стратегии и необходимости обрабатывать специальные ситуации (например, некорректная работа голкипера) Каждый робот обрабатывает coordination messages и выбирает формацию и свою роль в ней

Distributed Coordination in Heterogeneous Robotic Teams Шаг 1 Formation selection Роботы знают некоторый набор предопределенных формаций и используют правила для выбора формации на основе состояния среды Если возникают разногласия роботов о формации, выбирается формация с максимальным количеством голосов

Distributed Coordination in Heterogeneous Robotic Teams Шаг 2 Role assignment Пусть есть n {R 1,…,R n } роботов и m {r 1,…,r m } ролей (в нашем случае считаем, что m>n) Роли отсортированы по значимости, т.е. назначить роль r 1 в текущей формации важнее чем r 2 F j (i) – utility function считаемая роботом R i для роли r j A(i) = j означает, что i-му роботу назначена j-я роль

Distributed Coordination in Heterogeneous Robotic Teams Каждый робот R p делает следующее: Считает и рассылает всем F j (p) для каждой роли r j Получает аналогичную информацию от всех остальных роботов L = empty (Очищаем лист с ролями роботов) Для каждой r j – h = робот R i такой, что R i не в L и F j (i) максимальна – Если h = p тогда A(p) = j (нашли свою роль) – Добавить h в L

Distributed Coordination in Heterogeneous Robotic Teams Для того чтобы избежать частых переключений ролей у робота, который в данный момент выполняет функцию r j F j (i) будет больше Если робот понимает, что не может эффективно выполнять свою роль (его заблокировали, перед ним препятствие), его utility functions должны сразу резко уменьшиться Если коммуникации надежные то все роботы гарантированно будут выбирать согласованные роли. Если же коммуникации ненадежны, то возможно присвоение одной роли нескольким игрокам, однако, если считать, что сбои длятся всего доли секунды, то это не является проблемой