Computer Science МФТИ Changes    |    Index    |    Search
::: MIPTRoboTeam :::
Parents: WebHome > AgentProjects
 
  ACM . Agent . MIPTRoboTeam # Edit # Attach # Diffs # Printable # More :::

Main
• Register
• Users
• Site Map

Curriculum

Agent Web
• projects

Algorithms

Web Learn

Image Kit

ProgTech

Publishing

ROBOCUP SOCCERGUYS PROJECT


Интродукция

Robocup - проект, направленный на создание команды искусственных игроков в футбол. Simulation league - это часть проекта Robocup, которая направлена на моделирование игры в наипростейшем, 2D-варианте, без относительно реальных реализаций роботов-футболистов.

Soccerguys - это проект, представляющий реализацию команды игроков для сервера-поля предоставленного проектом Simulation league. Авторы данного проекта считают его далеко не законченным и написанным в далеко не лучшем стиле программирования на C++, и напоминают, что проект распространяется согласно GPL лицензии. Поэтому авторы видят, что польза данного проекта для других создателей может заключаться лишь в просмотре исходных текстов в качестве примера для создания другого, но отнюдь не в качестве использования его в качестве сколько-нибудь готового продукта.

Краткое описание структуры Robocup - Simulation league

  1. Сервер, реализующий футбольное поле – физику происходящих событий – т.е. движение игроков и мяча, передачу информации игрокам – визуальную, звуковую и сенсорную, а также стандартный алгоритм судейства.
  2. Мониторы, подключаемые к серверу, и осуществляющие визуализацию игры и её мануальное судейство.
  3. Игроки, подключаемые к серверу – общение между игроками в обход севера запрещено.
  4. Тренеры, подключаемые к серверу – их основная роль заключается в отладке и настройке программ-игроков.

Структура проекта Soccerguys

1. Клиент

Эта чисто техническая часть программы, являющейся прокладкой между сервером и непосредственно алгоритмической частью программы. Она реализует подключение к серверу, прием событий от сервера (в данном месте клиент производит маскировку стороны поля (левая/правая) для однородности вышележащего алгоритма по отношению к тому, на какой стороне играет команда), передачу действий игрока серверу (процесс обратный маскировке), импорт стандартных констант. Кроме того, каждый клиент создаёт для себя новую нить, для возможности создания одним процессом нескольких (обычно 11) игроков. Реализацией клиента является наследуемый класс Client, и вследствие отсутствия в нём сложных алгоритмов, а также первоочерёдности написания он, видимо, является наиболее стабильно работающей и корректно написанной частью программы.

2. Игрок

Это объединение алгоритмов управления игрока и структур данных для них. Игрок реализуется классом Player, являющимся наследником Client, и представляющий собой финальный класс, создание которого влечёт за собой создание, подключение к серверу и дальнейшую игру полностью работоспособного игрока.

Алгоритмы игрока:

  1. Анализ визуальной информации.
  2. Расшифровка звуковой информации.
  3. Управление бегом.
  4. Управление ударом.
  5. Тактика игрока.

2a. Анализ визуальной информации

Этот алгоритм используется для анализа визуальной информации поступающей от сервера и построения на её основе представления об окружающем мире – координат и скоростей себя, мяча и других игроков. Реализация выполнена в виде классов PhaseState, ObjectPosition, TWorld и переопределения функций Player::SenceBody, Player::SeeStart, Player::SeeEnd, Player::SeeBall, Player::SeePlayer, Player::SeeFlag. В начале визуального такта от Client приходит сообщение Player::SeeStart. Далее визуальная информация поступает в виде сообщений Player::SeeBall, Player::SeePlayer, Player::SeeFlag. Когда визуальный такт оканчивается, приходит сообщение Player::SeeEnd, которое является сигналом для обработки накопленной за данный такт информации. Обработка состоит в следующем:

  1. По положению флагов определяется положение и направление тела игрока
  2. Используя данные о модуле скорости и полученном направлении тела, вычисляется вектор скорости.
  3. Определяется положение и скорость мяча.
  4. Определяются положения и скорости игроков, для которых возможно различить принадлежность их к своей или чужой команде.
Возможные направления работы: анализ последствий шума в визуальных данных для уменьшения среднеквадратичного отклонения вычисляемых величин.

2b. Расшифровка звуковой информации

Этот алгоритм используется для анализа услышанной «строки», определение корректности её подписи – своя/чужая команда, получение сообщений и их параметров. Реализация выполнена в виде класса AuralInfoClass а также переопределения функций Player::Hear и Player::AuralSend. При реализации использовался класс MessageDecoder – написанный ранее авторами простейший анализатор строк.

2с. Управление бегом

Этот алгоритм направлен на решение задачи по преследованию движущегося по полю объекта (обычно мяча). При этом производиться численное решение задачи по выбору траектории приближающей игрока на заданное расстояние (обычно расстояние удара) к преследуемому объекту за минимальное время. При этом, из-за того что за один физический такт игрок может либо выполнить команду поворота, либо команду ускорения, то алгоритм проводит решение в пользу той или иной команды. Идейно предполагается, что при преследовании объекта данный алгоритм будет выполняться заново на каждом шаге, что должно исключить накопление ошибок из-за неточного определения координат и скоростей игрока и объекта. Реализация выполнена в виде классов RunToInfoClass, Trajectory, PhaseState а также переопределения функции Player::RunTo.

2d. Управление ударом

Этот алгоритм направлен на решение задачи перемещения мяча в заданную точку пространства-времени. Он реализован в виде переопределения функции void Player::KickTo(float x, float y, float requiredTime).Она рассчитывает параметры удара так, чтобы мяч оказался в точке (х, у) через время requiredTime, и затем вызывает стандартную процедуру kick(power, angle), аргументами которой являются сила удара и его направление относительно ориентации туловища игрока. Расчёт этих параметров выполняется следующим образом: Согласно физической модели сервера, движение мяча описывается формулами:

u(t+1)=v(t)+ a(t)
p(t+1)=p(t)+u(t+1)
v(t+1)=d*u(t+1)
a(t+1)=0   //при условии отсутствия  внешнего воздействия на шаге (t+1)
здесь u,v – скорости (т.е. u – собственно скорость, определяющая изменение координаты, а v – вспомогательная величина для расчёта u), p - координата, d – «затухание», т.е. коэф. трения, a – ускорение.

Если на t-м шаге по мячу наносится удар, то ускорение определяется как

(ax(t+1), ay(t+1)) = power*power_rate* (cos(s(t)), sin s(t))

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

Выполнив суммирование, получаем, что положение мяча через n тактов после удара есть:

p(n)=p(1)+ Si u(i)= p(1)+u(2)* S d^(i-1)= p(1) + u(2) * (1-d^n)/(1-d)

Отсюда выражается желаемая скорость мяча в момент n=2 u(2), после чего можно найти необходимое ускорение как

a(1)=u(2)-u(1)*d

Соответственно, вычислив power_rate и используя ф-лу (1), можно найти силу удара. Выражение для power_rate:

power_rate= 1-0.25*dir_diff/180-0.25* dist_ball/kickable_margin

Здесь dir_diff – угол между направлением от игрока на мяч и ориентацией тела игрока, dist_ball – расстояние от игрока до мяча, а kickable_margin – максимальное расстояние, с которого игрок может ударить по мячу, серверная константа.

Параметр angle процедуры kick равен dir_diff.

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

2e. Тактика игрока

Наиболее загадочный алгоритм программы, полученный эволюционным принципом. Дерево принятия решений:
  1. Мяч достаточно близко чтобы ударить.
    1. Ударить слабо, чтобы далее продолжать ведение мяча. b. Отдать пас. c. Ударить по воротам (как можно сильнее)
  2. Мяч слишком далеко, для того чтобы бить.
    1. Игрок находится в состоянии позиционного движения. b. Игрок находится в состоянии приёма мяча.
Данный алгоритм реализуется классом TacticalInfoClass а также переопределением функции Player::SimulationStep. При этом основой для принятия решений являются две потенциальные функции, зависящие от координат игрока, мяча и других игроков. Первая – выгодность положения игрока в данной точке поля, вторая – выгодность положения мяча в данной точке поля. Рассмотрим процесс принятия решения подробнее.
  1. Близость мяча определяется в результате сравнения расстояния до мяча, вычисленного в соответствии с текущими представлениями о мире, с максимальным расстоянием на котором возможно провести удар, которое является заранее известным свойством игрока.
  2. Решение касательно удара принимается на основе максимизации минимума функции выгодности положения мяча на возможных его траекториях, среди которых есть траектория ведения мяча, траектории ударов в различные точки ворот, и траектории пасов союзникам.
  3. Решение касательно приёма мяча/позиционного движения принимается на основе того, является ли игрок ближайшим из своей команды к мячу, был ли дан ему или им пас (о приёме паса ему “кричит” дающий пас игрок).
  4. Позиционное движение выполнено с использованием функции выгодности положения игрока в данной точке поля (игрок бежит по градиенту этой функции с ускорением пропорциональным его модулю), которая учитывает положения чужих(для возможности их покрытия) и своих(для того чтобы свои игроки не сбивались в кучу) игроков, мяча, коробки поля(для того чтобы игрок не убегал за поле), а также положения своих и чужих ворот.
  5. Приём мяча заключается в выполнении алгоритма преследования мяча с помощью функции Player::RunTo.

3. О потенциалах

Потенциал есть линейная суперпозиция (с “эмпирически найденными коэффициентами”, которые различны для потенциалов игрока и мяча (и вратаря)) простейших потенциалов отдельных объектов. Используемые простейшие потенциалы:

float OurPlayerPotentialFirst (float X, float Y, float PlayerX, float PlayerY)

Потенциал вида (L-1)*exp(-L^2) где L-расстояние до игрока своей команды. Он нужен для того, чтобы удерживать своих игроков на определённых расстояниях друг от друга.

float OurPlayerPotentialSecond (float X, float Y, float PlayerX, float PlayerY)

Потенциал вида exp(-L^2) где L-расстояние до игрока своей команды. Он нужен для того, чтобы свои игроки “притягивали” к себе мяч.

float TheirPlayerPotential (float X, float Y, float PlayerX, float PlayerY)

Потенциал вида -exp(-L^2) где L-расстояние до игрока чужой команды. Он нужен для того, чтобы чужие игроки “отталкивали” от себя мяч.

float GoalPotential (float X, float Y)

Потенциал вида -X-exp(-L1^2)+exp(-L2^2), где X-координата на поле, L1 и L2– расстояния до своих и чужих ворот.

float FieldPotential (float X, float Y)

Потенциал вида -L^2, где L расстояние игрока до поля, если игрок в поле то L=0. Он нужен для удержания игроков в поле.

float HomePotential (float X, float Y)

Потенциал вида exp(-L^2), где L – расстояние до заранее выбранной точки – домашней позиции игрока.

float BallPotential (float X, float Y)

Потенциал вида exp(-L^2), где L – расстояние до мяча. Он нужен для того, чтобы “притягивать” игрока к мячу.

float PenaltyPotential (float X, float Y)

Потенциал вида -L^2, где L – расстояние до своей штрафной площадки, если игрок в ней находиться, то L=0. Он нужен для удержания вратаря в штрафной.

float LinearBallPotential (float X, float Y)

Потенциал вида -L^2, где L – расстояние до прямой, соединяющей центр своих ворот и мяч. Он нужен для того, чтобы вратарь стремился находиться между воротами и мячом.

Архитектура и основные концепции.

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

  • ov.gif:
    ov.gif

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

  • goals.gif:
    goals.gif

Из этой диаграммы можно сделать два вывода:

1) для полноценного функционирования агента-футболиста, он должен обладать средствами

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

Согласно концепции агентно-ориентированного проектирования, агент отличается от объекта наличием внутренней мотивации, цели (Goal). В нашем случае такой целью являются глобально – победа команды, а локально – выполнение действия, наиболее полезного в данный момент. Переходя от knowledge-level к design-level, сформулируем цель как максимизацию функции полезности. Эта функция будет вычисляться для ситуаций, порождаемых различными действиями игрока из текущей ситуации на поле (такими действиями в случае, когда игрок владеет мячом, могут быть пас, удар по воротам либо ведение мяча, а для игрока без мяча – изменение позиции). Функция строится на основе потенциалов и её вид зависит от состояния игрока, т.е. играемой роли. Переключателем между ролями служит расстояние от игрока до мяча: если игрок считает себя ближайшим к мячу, он переходит в состояние WithBall, при этом целевая функция изменяется с функции, оптимизрующей положение игрока на поле, на функцию, оптимизирующую положение мяча. Задачей же игрока становится приведение мяча в оптимальное состояние. После отдачи паса либо удара по воротам игрок возвращается в состояние WithoutBall, но при этом в течении какого-то времени он остаётся ближайшим к мячу. Для того, чтобы он не «брослся» за мячом в этих случаях, а также для того, чтобы не «бросал» мяч при ведении или захвате, вводится инертность состояний: однажды изменив состояние, игрок остаётся в нём не менее, чем на заданное число тактов. Таким образом, нам необходима память о состояниях в предыдущие моменты времени. Для реализации всевозможных действий футболиста необходимы две «атомарные» операции – удар по мячу, переводящий его в заданную точку через заданное время, и бег, так же в заданную точку через заданное время. «Картина Мира» описывается фазовыми состояниями (координаты+скорость) футболистов и мяча. Кроме того, для каждой записи хранится дата последнего обновления, что позволяет выбирать из нескольких источников информации (сервер, другие игроки) наиболее свежий. Если запись не обновлялась давно, то содержащаяся в ней информация считается устаревшей и не учитывается при рассчёте функции полезности. Так как получаемая информация, как правило, запаздывает (это вызвано тем, что такт «видения» - интервал, с которым сервер посылает данные о том, что игрок видит, длиннее физического такта – периода обновления информации о физическом состоянии игрока и «единицы времени» моделируемого мира), то на основании построенной по сообщениям «Картины Мира» предсказывается ситуация на текущий такт, и именно это предсказание используется при выборе действия.

agent.gif

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

task.gif (для просмотра картинки в 100% масштабе, см. список картинок в таблице аттачментов)

Направления дальнейшего развития

  • Анализ последствий шума в визуальных данных для уменьшения среднеквадратичного отклонения вычисляемых величин
  • Текущая реализация процедуры удара не учитывает физическое состояние игрока, наносящего удар, и шумы, вносимые сервером
  • Улучшить зрение игрока
  • Дописать обработку стандартных положения, таких как FreeKick, Offside, GoalKick

Установка проекта

  1. Поставить CBuilder 6, ознакомившись с документацией по его установки
  2. Собрать проект Soccerguys, используя Soccerguys.bpg файл
  3. Запустить rcssserver. Для запуска его под Windows потребуется установить CYGWIN
  4. Настроить конфигурационный файл сервера .rcssserver-server.conf (он обычно в /home/#username#):
    • say_msg_size 512
    • use_offside off
    • free_kick_faults off
    • back_passes off
  5. Запустить понравившийся монитор (можно найти на официального сайта Robocup) и подключить его к серверу
  6. Запустить собранный Soccerguys.exe
  7. С помощью монитора, в котором уже должны появиться фигурки игроков, откинувшись на спинку стула, запустить игру и наслаждаться.

Ссылки


Attachment sort Action Size Date Who Comment
agent.gif manage 22.4 K 27 Apr 2004 - 02:55 AndreySalnikov?  
goals.gif manage 13.8 K 27 Apr 2004 - 02:52 AndreySalnikov?  
ov.gif manage 15.5 K 27 Apr 2004 - 02:52 AndreySalnikov?  
task.gif manage 20.1 K 27 Apr 2004 - 02:52 AndreySalnikov?  
SoccerGuys-Archive.exe manage 86.2 K 18 May 2004 - 18:06 AndreySalnikov? Исходники проэкта
SoccerGuys.zip manage 56.7 K 25 May 2004 - 06:58 AndreySalnikov? Исходники проэкта
PotentialMethodRobot.pdf manage 156.3 K 16 Jun 2004 - 21:28 AndreyUstyuzhanin Potential Field Methods for Robot Navigation

Rambler's Top100 Rambler's Top100


# Edit menu  

Topic revision r1.9 - 14 May 2005 - 13:30 GMT - AndreyUstyuzhanin
Topic parents: WebHome > AgentProjects
Copyright © 2003-2017 by the contributing authors.