АНАЛИЗ РЕШЕНИЙ ЗАДАЧИ МОДЕЛИРОВАНИЯ ФУТБОЛЬНОГО МАТЧА НА ОСНОВЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

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

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

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

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

Введение

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

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

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

1. A Reward Function Generation Method Using Genetic Algorithms: A Robot Soccer Study.

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

Рисунок 1. Основа модели поведения игрока

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

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

       (1)

Размер популяции был равен 128, игр каждый игрок сыграл четыре, а число поколений было равно 52. Результатом этого эксперимента стало то, что большинство игроков стали перемещаться по полю хаотично. Лучшей стратегией стала “беги за мячом и ударь в сторону ворот или отдай пас”. Целевая функция достигла приблизительного максимума на двадцатой итерации.

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

 (2)

                                (3)

                                (4)

В одной популяции было 96 особей, было проведено 55 поколений алгоритма, а каждый игрок сыграл две игры. Этот способ дал результат гораздо худший, чем предыдущий. Верной стратегией стала “бежать за мячом и бить в сторону ворот соперника”. Причем такой стратегии следовали все игроки, вне зависимости от амплуа.

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

- изменение ситуации моделирования (у авторов были ограничения по аппаратной части);

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

2. Genetic Algorithm Optimized GravityBased RoboCup Soccer Team.

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

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

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

Рисунок 2. Раскраска поля на области для агента

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

3. Genetic Programming of Multi-agent System in the RoboCup Domain.

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

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

4. Multi Robot Soccer in 3D.

Главным отличием от подобных систем было использование измененной версии PyBioSim – инструмента для симуляции агентов и окружения. Автором он был адаптирован для игры в футбол, введены понятия “границ” и “гола” [5].

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

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

Заключение

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

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

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

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

- не все действия доступны в случайный период времени: невозможно отдать пас, не имея мяча и т.д.;

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

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

Список литературы:

1. Родзин С.И., Курейчик В.В. — Теоретические вопросы и современные проблемы развития когнитивных биоинспирированных алгоритмов оптимизации (обзор) // Кибернетика и программирование. – 2017. – № 3. – С. 51 - 79. DOI: 10.25136/2306-4196.2017.3.18659/
2. Cetin Mericli. A Reward Function Generation Method Using Genetic Algorithms: A Robot Soccer Case Study // The Scientific and Technological Research Council of Turkey. - Bogazici:  The Scientific and Technological Research Council of Turkey, 2005.
3. Tony Harter Genetic Algorithm Optimized Gravity¬Based RoboCup Soccer Team // - LA: 2015. Jonatan Arronson. Genetic Programming of Multi-agent System in the RoboCup Domain [Text].
4. Jonatan Arronson. Jonatan Arronson. Genetic Programming of Multi-agent System in the RoboCup Domain // Lund, Sweden: Lund Institute of Technology, 2003.
5. Multi Robot Soccer in 3d. // Гитхаб URL: http://cjds.github.io/2015/05/03/Multi-Robot-Genetic-Algorithms/ (дата обращения: 12.08.2019).