Интеллектуальные системы и технологии
УДК 007.5:681.518.2
, студент,
, канд. техн. наук, доц.
Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» Санкт-Петербург
ИССЛЕДОВАНИЕ АЛГОРИТМОВ БАЗОВЫХ ДЕЙСТВИЙ ИНТЕЛЛЕКТУАЛЬНОГО АГЕНТА В ВИРТУАЛЬНОМ ФУТБОЛЕ
Аннотация. Объектом исследования является алгоритмы базовых действий в составе интеллектуального агента реального времени, который действует в среде виртуального футбола. Целью работы является разработка программной среды, реализующей модель базовых действий агента. Рассматривается проблема построения интеллектуальных агентов. Представлен алгоритм перехвата мяча.
Ключевые слова: интеллектуальный агент, модель действий, алгоритм перехвата мяча.
Abstract. The object of research is the basic algorithms of actions as part of a real-time intelligent agent that acts in a virtual environment football. The aim of the work was to create a software environment that implements the model of the agent's actions. Considering the problem of building intelligent agents. Presented algorithm of intercept the ball.
Keywords: intelligent agent, action model, ball interception algorithm.
Многоагентные системы, состоящие из интеллектуальных агентов (автономная, основанная на знаниях система, действующая целенаправленно), являются одной из перспективных областей исследования в искусственном интеллекте [Пузанков и др., 2008; Пантелеев, 2012]. Для исследования вопросов группового поведения агентов применяется среда RoboCup Soccer.
Одной из ключевых ролей в разработке многоагентных систем занимает исследование алгоритмов базовых действий. Существует несколько подходов к разработке модели действий интеллектуального агента, среди которых можно выделить подход, описанный в [Remco de Boer & Jelle Kok, 2002]. В этой работе используется иерархическая структура базовых действий, состоящая из нескольких слоев на разных уровнях абстракции. Действия нижнего уровня могут быть определены в терминах базовых команд, используемых в RoboCup Soccer Server, в то время как умения высокого уровня используют функциональность, определенную уровнем ниже, чтобы сгенерировать желаемое поведение. Структура данной модели представлена на рисунке 1.
Рисунок 1 – Иерархическая модель действий
Целью исследования является сравнение и разработка алгоритма перехвата мяча. В [P. Stone, 1998] описаны два возможных метода перехвата мяча:
1. Аналитический метод, в котором скорость мяча оценивается, используя предыдущее расположение мяча на поле, и в котором будущее перемещение мяча предсказывается на основе его скорости.
2. Эмпирический метод, в котором используется нейронная сеть, чтобы создать основное поведение по перехвату мяча на основе примеров успешных перехватов.
Статистика, представленная в статье «Layered Learning in Multi-Agent Systems», показывает, что эмпирический метод, использующий нейронную сеть дает немного лучшие результаты, чем аналитический метод. Однако, эти результаты были получены в старой версии RoboCup Soccer Server (версия 2), в которой игрок еще не получал информацию об изменении расстояния, изменении направления подвижных объектов, и в которой визуальная информация посылалась игроку через большие интервалы, чем сейчас, этим задача предсказания траектории мяча осложнялась. Таким образом, выше описанные результаты не соответствуют более поздним версиями Soccer Server. Оказалось, что результаты аналитического метода значительно улучшаются, когда визуальная информация получается игроком чаще, и когда используется информация об изменении передвижения движущихся объектов.
Главная цель алгоритма перехвата мяча состоит в определении оптимальной точки перехвата, основанной на текущем расположении и скорости мяча, и в движении к этой точке как можно быстрее, чтобы достичь ее раньше соперника. Это не простая задача в виду того, что к восприятию игрока и к перемещению мяча добавляется шум. Этот шум не позволяет точно определить траекторию мяча и, следовательно, оптимальную точку перехвата. Поэтому оценка точки перехвата должна быть хорошей, т. к. игрок может двигать только вперед или назад по направлению его тела. Если в течение выполнения последовательности команд по перехвату мяча обнаружиться, что точка перехвата определена не точно, то игрок будет вынужден повернуться к заново посчитанной точке перехвата, что значительно замедлит его.
Прежде всего, в алгоритме перехвата мяча следует определить, возможно ли перехватить мяч в течение одного цикла. Для этого предсказывается позиция 
мяча в следующем цикле и вычисляется, возможно ли, исполнив одну команду dash, подбежать на необходимое для перехвата расстояние. Пусть l – линия по направлению тела игрока в следующем цикле 
. Эта линия определяет возможное перемещение игрока в следующем цикле, т. к. перемещение разрешено только по направлению тела игрока. Пусть c – окружность, центр которой находится в предсказанном расположении мяча 
, с радиусом равным сумме радиусов игрока и мяча и некоторого маленького буфера (kickable_margin/6). Игрок определяет, может ли он перехватить мяч, используя число точек пересечения прямой l и окружности c (см. рисунок 2.3). Если у l и c одна точка пересечения, то именно она берется как желаемая точка перехвата. Однако, если точек пересечения прямой и окружности две, то в качестве желаемой точки перехвата берется та, у которой абсолютный угол к мячу меньше. Эта точка соответствует ближайшей точке пересечения, если мяч лежит перед игроком, и дальней, если мяч находится позади игрока. В результате, точка перехвата будет всегда такой, что мяч окажется перед игроком в следующем цикле. Дальше предсказывается позиция игрока после выполнения команды dash. Если оказывается, что расстояние между предсказанной позицией мяча и игрока меньше расстояния необходимого для перехвата, то используется команда dash. На рисунке 2 показан пример, в котором игрок использует команду dash, чтобы подбежать к мячу как можно ближе для перехвата.
Рисунок 2 – Пример перехвата мяча
Однако, если предсказанная позиция игрока не достаточна близка к мячу, то проверяются еще два варианта перехвата. Первый вариант заключается в определении возможности перехвата, используя команду turn с последующим dash. Для этого предсказывается позиция мяча 
и генерируется команда turn, чтобы повернуться к этой точке. Предсказывается позиция игрока 
после выполнения этой команды и затем генерируется команда dash. Если оказывается, что предсказанная позиция игрока 
, после исполнения команды dash, лежит не расстоянии необходимом для перехвата, то используется эта последовательность команд. В противном случае рассматривается второй вариант, в котором определяется возможность перехвата игроком мяча, используя две команды dash. Если оказалось, что нельзя перехватить мяч за два цикла, агент использует итеративную схему для подсчета оптимальной точки перехвата. Для этого выполняется цикл, в котором предсказывается позиция мяча через i циклов 
и количество циклов n необходимых игроку для того, чтобы добежать до этой позиции. Это повторяется для увеличивающегося i, пока n не станет меньше i. В итоге, позиция 
выбирается как точка перехвата, к которой бежит игрок.
Дальнейшее исследование в данной области связаны с доработкой модели действий интеллектуального агента.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Концепция построения интеллектуальных агентов реального времени на основе модели опережающего итеративного планирования// Труды 13-ой Нац. Конф. по ИИ с международным участием КИИ-2012. Т 3. – Белгород: Изд-во БГТУ. – 2012. – С. 25-33. Remco de Boer, Jelle Kok. The Incremental Development of aSynthetic Multi-Agent System: TheUvA Trilearn 2001 Robotic SoccerSimulation Team, 2002. P. Stone. Layered Learning in Multi-Agent Systems. PhD thesis, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, Dec. 1998. Пузанков и др., 2008 , , Интеллектуальные агенты, многоагентные системы и семантический Web: концепции, технологии, приложения. – СПб.: , Изд-во «Технолит», 2008.