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

Институт прикладной математики им. М В Келдыша Российской академии наук

На правах рукописи

Плахов Андрей Григорьевич

ВИРТУАЛЬНЫЙ ФУТБОЛ РОБОТОВ: АЛГОРИТМЫ ИГРОКОВ И СРЕДА МОДЕЛИРОВАНИЯ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

ООЗ 17

Москва, 2008

003171725

Работа выполнена в Институте прикладной математики им М,В Келдыша Российской академии наук

Научный руководитель.

доктор физико-математических наук, профессор Павловский В. Е.

Официальные оппоненты: доктор физико-математических наук

Горбунов-Посадов М. М.

доктор физико-математических наук, профессор Зенкевич С. Л.

Ведущая организация: Научно-исследовательский институт механики

МГУ им М В Ломоносова, г Москва

Защита состоится 24 июня 2008 года в 11 часов 00 минут на заседании диссертационного совета Д 002 024 01 при Институте прикладной математики им М В Келдыша РАН по адресу 125047, Москва, Миусская пл , д 4

С диссертацией можно ознакомиться в библиотеке Института прикладной математики им М В Келдыша РАН

Автореферат разослан 23 мая 2008 года

Ученый секретарь

диссертационного совета Д 002 024 01

доктор физико-математических наук

Полилова Т А

1 Общая характеристика работы

Актуальность темы

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

В настоящее время задача группового управления роботами признается одной из центральных проблем мехатроники На пути се решения научным сообществом было сформулировано несколько модельных задач, среди | которых одной из основных является роботизированный футбол. Конечная I цель, поставленная в данной задаче - к 2050 году создать команду человекоподобных роботов, которые смогут на равных играть в футбол по правилам ФИФА с командой-чемпионом мира среди людей В настоящее время соревнования по роботизированному футболу проводятся во Франции, Кореи, Японии и многих других странах мира

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

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

Наличие подобной среды, созданной в рамках проекта «Виртуальный футбол» [1-11], позволило опробовать различные подходы к построению группового управления в условиях противодействия детерминированный, переборный и эволюционный Сформулированные алгоритмы, а также принципы управления и оптимизации, могут быть использованы в других задачах группового управления в условиях противодействия, в частности в антагонистических играх, характеризуемых большой глубиной дерева игры и наличием большого количества возможных полуходов в каждой игровой позиции

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

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

Научная новизна

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

Практическая значимость работы

Значительная часть разработанных алгоритмов и методик может быть использована в широком классе задач управления, для которых дерево состояний управляемого объекта (или группы объектов) характеризуется большой глубиной и/или большим коэффициентом ветвления При помощи созданных средств моделирования игры в рамках проекта «Виртуальный футбол» проведено более 20 турниров в 6 городах В проекте принимает участие более 40 команд из 11 городов За это время участниками отработано значительное количество различных алгоритмов управления и методик их создания. Команда «АУБТ» [6], в которой были применены излагаемые в диссертации алгоритмы и методы, 6 раз становилась чемпионом этих соревнований

Апробация работы и публикации

Основные результаты работы докладывались и обсуждались на:

трех Международных конференциях "Интеллектуальные и многопроцессорные системы", Россия, Украина

• 4-й международной конференции СЬАЧ¥АЯ-2001, Карлсруэ, Германия

• 12-й научно-технической конференции "Экстремальная робототехника -2001"

международной конференции "Искусственный интеллект - 2000"

• конференции "Мобильные роботы и мсхатронные системы", МГУ, 2000

• международном конкурсе компьютерных программ студентов, аспирантов и молодых специалистов "Программист-2001"

Результаты работы изложены в 11 научных публикациях

Структура и объем работы

1 Диссертация состоит из введения, трех глав, заключения, приложения и

' списка литературы Содержание работы изложено на 157 страницах (включая ( приложение)

2 Содержание работы

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

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

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

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

Положение робота в каждый момент времени задается четверкой чисел (х, у, V, ■ф), где (*,}') - координаты центра футболиста, V - его скорость, и гр -курсовой угол Мяч считается движущимся прямолинейно (т е не сталкивается с игроками и стенками игрового поля), с трением, за счет которого при движении мяча возникает постоянное ускорение, равное а — где Щ -

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

Будем считать, что начальная скорость движения футболиста равна V = vva, где Vo — единичный вектор, направленный по ходу движения, максимальную скорость движения обозначим vmax > v.

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

Vmax

меньше, нежели величина tBCC --, где атах - максимальное допустимое

e-mar

правилами ускорение футболиста

За время t мяч пройдет расстояние, равное ut ——, футболист пройдет расстояние s, где

s = (t-taca)vmax + t^(v^í~) при t > tacc, и

s = + tv при t<tacc

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

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

При этом если у первого из них есть решение, для которого О < £ < "тах то оно представляет собой искомое время достижения, если же

°я;аг

такого решения не оказывается, то искомым временем достижения является минимальное из решении второго уравнения, превосходящее tacc =-.

"шаг

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

В случае, когда решение существует, и получено значение времени упреждения С, вычисляется точка, в которой произойдет встреча Для этого к текущему положеншо мяча прибавляется вектор (иЕ — Щ Соответственно,

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

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

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

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

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

Для того, чтобы представить задачу виртуального футбола как задачу поиска пути в дискретном пространстве состояний, следует ввести дискретизацию для возможных положений футболистов, и ввести квантизацию времени, разбив его на последовательные такты Чтобы получаемая в ходе поиска последовательность действий оказывалась эффективной, шаг этой дискретизации (как временной, так и пространственной и угловой) должен быть достаточно малым В этом случае длина искомой последовательности действий оказывается велика (игровая ситуация сколько-нибудь значительно меняется только за время порядка сотен тактов), а пространство состояний управляемого объекта (команды футболистов) имеет большой коэффициент ветвления (порядка 30 для одного футболиста и порядка 2* 107 для команды из 5 игроков) По этой причине как прямое применение алгоритмов, широко используемых в неантагонистических задачах (таких как А* или Б*), так и минимаксный перебор дерева позиций (часто используемый в антагонистических играх), приводят к огромным вычислительным затратам, исключающим на современном оборудовании возможность построения управления в реальном времени

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

Вкратце изложим предложенную в работе иерархическую реализацию

8

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

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

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

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

9

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

Метод просчета в глубину заключается в том, что вместо задачи планирования в исходном пространстве состояний команды, рассматривается поиск на направленном графе состояний, рекурсивно определенном следующим образом В этот граф входит начальное состояние команды Для каждого вошедшего в граф состояния А строится набор состояний, соответствующих применению каждой стратегии из набора Б в начальном состоянии А в течение некоторого числа 5 шагов (это число может быть как фиксированным, так и выбираться в зависимости от состояния А и используемой стратегии) Полученные таким образом вершины также включаются в граф, и процедура повторяется рекурсивно вплоть до достижения определенной глубины Далее среди терминальных для данной процедуры вершин находится та, которая обеспечивает наилучшую оценку, и в качестве искомой последовательности действий принимается последовательность, ведущая к этому состоянию Отметим, что использование метода просчета в глубину не требует строить описанный граф в явном виде или хранить его в памяти

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

Сравним процедуру поиска по алгоритму Дийкстры с вышеизложенной процедурой стратегического поиска в глубину. На рис 2 слева проиллюстрировано промежуточное состояние в ходе поиска при помощи алгоритма Дийкстры, черным цветом изображена начальная вершина, серым -обработанные на изображаемый момент Справа иллюстрируется промежуточное состояние поиска в этом же пространстве состояний путем просчета в глубину с набором в, состоящим из двух стратегий «идти вправо» и «идти влево по диагонали», применяемым на протяжении фиксированного числа 5=3 шагов Черным цветом изображены вершины укрупненного графа, серым - промежуточные шаги

Рис 2 Сравнение двух методов поиска последовательности действий

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

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

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

оборудовании) Для сравнения различных методов оптимизации в диссертационной работе используется понятие «времени достижения эффективности», которое представляет собой значение t, усредненное для нескольких экспериментальных запусков Предлагается четыре принципа снижения этого показателя минимизация времени одного измерения, раннее отбрасывание неконсистентных наборов параметров, учет внутренней симметрии задачи, и учет априорного влияния параметра на результат Из них наиболее действенным оказывается минимизация времени одного измерения

Для иллюстрации важности этого принципа рассмотрим вопрос об определении необходимой длительности тестовой игры, если в качестве критерия оптимизации используется только счет игры (число забитых голов). Будем считать, что промежутки игры между двумя последовательными голами независимы, и что гол на каждом таком промежутке забивается правой и левой командами с вероятностью соответственно р и q, где р + q = 1, причем эти вероятности нам заранее неизвестны, и мы хотим найти их приближенное значение в ходе тестовой игры Рассмотрим величины а„ i = l N, где at = 1, если гол на N-том промежутке забит правой командой, и at — —1, если гол забит левой Обозначим общий счет игры А:В, где А— число голов, забитых правой, В - левой командой Согласно закону больших чисел,

1 + Р~<? 1 . А-В 1 £1=1

Р =---= — + lim -——— = - + lim ——-—

и 2 2 л-«°2(Л + В) 2 л-*« 2 N

Для вычисления приближенного значения р следует использовать это

равенство со снятым lim (то есть при фиксированном N) Найдем дисперсию

этой величины Имеем

, Ег=1л-аД ХылОСад D(a0) p(l-p + (7)2 + (r(-l-p + q)2

2 2 N } 4 N2 4 N 4 N pq2 + qp2 _ pq

N N

Таким образом, среднеквадратичное отклонение при заданном N

РЧ 1

составляет а — I— <

причем максимум, как и следовало ожидать,

1

достигается при р = ц = -. Отсюда следует, что, если следовать правилу трех

сигм, то для определения р с точностью до ±£ следует вести тестовую игру

9

вплоть до достижения суммарного счета как минимум N = А + В = —. Как правило, при небольшой подстройке алгоритма р отличается от ^ на величины

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

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

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

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

В заключении подведены итоги работы и сформулированы ее основные результаты

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

3 Основные результаты

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

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

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

• Предложена принципиальная схема алгоритма планирования групповых действий путем перебора стратегий в глубину Данная схема позволяет использовать гетерогенный набор стратегий для построения систем, сочетающих в себе сильные стороны каждой из них На ее основе создана программа управления виртуальными роботами-футболистами АУБТ, использующая в своей работе обратную иерархию управления

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

Список публикаций по теме диссертации

1 Д Е Охоцимский, В Е Павловский, А.Г Плахов, А Н.Туганов Система моделирования игры роботов-футболистов // Тр Конференции "Мобильные роботы и мехатронные системы", МГУ, 5-6 декабря 2000 -Под ред д ф -м н А М Формальского и к.ф.-м н В.М Буданова М Издательство МГУ, 2001, с 192 - 203

2. Д Е Охоцимский, В Е. Павловский, А Г Плахов, А Н Туганов Моделирование игры роботов-футболистов и базовые алгоритмы управления ими // Искусственный интеллект, N 3, 2000, с 534-540

3 Д Е Охоцимский, В Е Павловский, А.Г Плахов, А.Н.Туганов Моделирование игры роботов-футболистов и базовые алгоритмы управления ими Тр (тезисы докладов) Международной конференции "Искусственный интеллект - 2000", Кацивели, Крым, 11-16 сентября 2000 г., с. 123-125 (Зстр)

4 Д.Е Охоцимский, В Е. Павловский, А К Платонов, А.Г Плахов, АНТуганов Моделирование алгоритмов управления игрой роботов-футболистов Тр 12 научно-технической конференции "Экстремальная робототехника - 2001", С -Петербург, 2001

5 Д Е Охоцимский, В Е Павловский, А Г Плахов, А Н Туганов Моделирование игры роботов-футболистов в пакете "Виртуальный футбол" Тр Международной конференции "Интеллектуальные и многопроцессорные системы" (ИМС-2001), Дивноморское, Россия, 1-6 октября 2001, с 167-170 (4 стр) Тр научной школы "Интеллектуальные робототехнические системы" (ИРС-2001), Дивноморское, Россия, 1-6 октября 2001, с 165-167 (3 стр)

6. Д Е Охоцимский, В Е. Павловский, А Г.Плахов, А Н Туганов, В В Павловский Моделирование игры роботов-футболистов в пакете "Виртуальный футбол". // Мехатроника, 2002, №1, с 2-5

7 Д Е Охоцимский, В Е Павловский, А Г.Плахов, А.Н Туганов, В В Павловский Виртуальный футбол алгоритмы и моделирование игры роботов-футболистов //Сб. "Новые методы управления сложными системами", - М.:Наука, 2004, с.289

8 В Е Павловский, А Г Плахов, А Н Туганов, В.В Павловский Проект "Виртуальный футбол"- расширение серверов и программ-игроков // Искусственный интеллект, 2003, №4, с 153-157.

9. В Е Павловский, А Г Плахов, А Н Туганов, В.В Павловский Программный пакет "Виртуальный футбол". Тр Международного конкурса компьютерных программ студентов, аспирантов и молодых специалистов "Программист-2001" Владивосток, ИАПУ ДВО РАН, с 4749. (3 стр)

10.D.E Okhotsimsky, V.E Pavlovsky, A G Plakhov, A N.Touganov. Towards the CLAWAR robots soccer playing - simulation of robotic soccer. Proc of 4-th Int Conf on Climbmg and Walking Robots CLAWAR'2001 Karlsruhe, Germany, 24-26 September 2001, pp 451-456 (6 pages)

11 D.E.Okhotsimsky, V.E Pavlovsky, A G Plakhov, A N Touganov,

VV Pavlovsky, S.S.Stepanov, A Yu Zaslavsky. Robosoccer-RU Open Simulation League Principles and Algorithms. //Proc RoboCup 2002: Robot Soccer World Cup VI Intal Symposium, pp, 271-278, Springer 2003

Подписано в печать 22 05 2008 г Печать на ризографе Тираж 100 экз Заказ № 1082. Объем 1,3 п л Отпечатано в типографии ООО "Алфавит 2000", ИНН 7718532212, г Москва, ул Маросейка, д 6/8, стр 1, т 623-08-10, www alfavit2000 ru

Содержание.

Введение.

Глава 1. Алгоритмы управления роботами-футболистами.

§1.1. Базовые алгоритмы управления мобильнымфоботомфутболистом.

Достижение точки.

Перехват* мяча с;упреждением.

Достижение точки при заданном направлении приезда.

§1.2. Построение и использование таблиц успевания.

§1.3. Прогнозирование изменения ситуации-на игровом поле.

§1.4. Алгоритмы прямой иерархии управления роботом футболистом.

Недостатки алгоритмов прямой иерархии.управления.

Глава 2. Алгоритмы планирования действий роботов-футболистов

§2.1. Граф ситуаций в задаче планирования действий роботамифутболистами

§2.2: Задача поиска путей и ее обобщение на планирование действий.

§2.3. Стандартные алгоритмы поиска путей,' сравнение эффективности.

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

Поиск пути на. графе.

Недостатки рассмотренных стандартных алгоритмов.

§2.4. Быстрый поиск путей на больших пространствах поиска.

Вариация алгоритма Дийкстры, использующая,фиксированную память.

Иерархические алгоритмы поиска путей.

Построение укрупненного представления карты.

Эффективная реализация иерархического поиска.

§2.5. Планирование путем просчета в глубину.

Сравнение эффективности различных алгоритмов.

Вариация алгоритма просчета в глубину с лидером.

§2.6. Задача группового передвижения.

§2.7. Алгоритмы обратной иерархии управления. Алгоритм AVST. 89 Разрешение конфликтов при помощи ключевых точек и избегания коллизий.

Глава 3. Методы эволюционной оптимизации в задачах виртуального футбола роботов.

§3.1. Использование принципов эволюционной оптимизации при создании алгоритмов-игроков.

§3.2. Сравнение методов эволюционной оптимизации и схемы обратной иерархии управления.

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

Актуальность темы

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

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

Одной из основных модельных задач является так называемый роботизированный футбол. Конечная цель, поставленная научным сообществом- в данной задаче, обычно формулируется так: к 2050 году создать команду человекоподобных роботов, которые смогут на равных играть в футбол на обычном поле по правилам ФИФА с командой-чемпионом мира среди людей. В настоящее время различные соревнования по роботизированному футболу проводятся во многих странах мира, таких как Франция, Корея, Япония.

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

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

В 1999 — 2005 годах группой студентов и преподавателей МГУ им. М. В. Ломоносова был создан и поддерживается проект «Виртуальный футбол» [11, 12, 13, 15, 44], включающий в себя виртуальную среду моделирования игры, алгоритмы моделирования поведения роботов — футболистов, средства разработки алгоритмов для сторонних команд и средства проведения и визуализации соревнований таких алгоритмов: В играх принимают участие программы, представляющие собой команду-игрока, и управляющие каждая командой! 5 виртуальных «колесных роботов». Первые российские соревнования по виртуальному футболу роботов были организованы в МГУ под эгидой Научно-технических Фестивалей "Мобильные роботы" [10].

Во время Фестиваля "Мобильные роботы - 2000" (декабрь 2000 г.) прошли первые показательные соревнования (носившие демонстрационный характер), целью которых являлось ознакомление участников с предлагаемыми схемами разработки игровых программ и подготовка к следующим, официальным, соревнованиям' по виртуальному футболу роботов. Первые официальные соревнования по виртуальному футболу роботов прошли в пос. Дивноморское на конференции "Искусственный интеллект - 2001", а участие в следующем турнире принимало уже 10 команд. Было проведено несколько региональных турниров, первый из которых прошел в г. Донецке в 2002 году.

За время существования проекта прошло уже более 15 турниров в 6 городах. В проекте принимает участие более 40 команд из 11 городов, между которыми идет напряженная борьба за первенство. Обладателями золотых медалей турниров становилось восемь различных команд [10].

Результаты, показанные в соревнованиях, проводимых в среде моделирования «Виртуальный футбол», позволяют производить отбор наиболее эффективных методов управления и обобщение этих методов на другие задачи группового управления [8, 19, 22, 24, 26, 44, 49].

Обзор аналогичных пакетов и систем

Аналогами проекта «Виртуальный футбол» являются следующие международные соревнования:

1. RoboCup Simulation League (Лиги Моделирования инициативы RoboCup) [34, 35, 49, 58, 61, 62, 65]. Соревнования в рамках данной инициативы проводятся японскими организаторами с 1997 года. В отличие от проекта «Виртуальный футбол», проект RoboCup моделирует игры команд, состоящих из 11 человекоподобных роботов (или 11 человек) по футбольным правилам ФИФА. Проект «Виртуальный футбол» также отличается от своего восточного аналога другими принципами взаимодействия команд-игроков и программы моделирования, что приводит к упрощению и ускорению разработки команд-игроков.

2. Федерация FIRA [24]. В рамках данных проводятся как соревнования материальных роботов с определенными ограничениями, на конструкцию^ (фиксированы размеры роботов, число колес, устройства контроля мяча и т.п.), так и симуляция соревнований. В отличие от проекта «Виртуальный футбол», в симуляционных программах жестко заданы размеры команд, параметры поля, продолжительность матча. Кроме того, в серверной, программе симуляции FIRA используется существенно более медленная схема динамического моделирования, нежели в пакете «Виртуальный футбол», что приводит к "невозможности batch-тестирования алгоритмов в ускоренном режиме симуляции.

3. Роботы-футболисты на Фестивале Наук и Технологий (Франция) [26].

4. RoboCup SmallSize, Medium Size, 4-Legged, Humanoid [49]. Соревнования в рамках данных инициатив проводятся между командами, состоящими из материальных роботов с различными ограничениями на конструкцию

5. RoboCup Rescue Simulation [49]: Соревнования в рамках данной инициативы проводятся между виртуальными роботами, имитирующими действия по устранению последствий техногенных и природных катастроф, работу в агрессивной внешней среде и т.п. Соревнования-проводятся с 2002 года.

Подробный обзор развития, футбола роботов в России и за рубежом приведен в работах [21, 27]^

Правила игры в проекте «Виртуальный футбол»

Игра проходит между двумя командами роботов-футболистов на прямоугольном поле с бордюрами (ограничивающими поле стенками). 11ри моделировании; игры роботов в футбол в предлагаемой схеме не делается-предположений о специфических особенностях их двигательной активности, и такие предположения не закладываются в систему. Однако считается, что роботы должны иметь способность управляться по ускорению и по! повороту. Эти предположения основаны на некоторой: конкретной модели - модели колесных роботов с минимально достаточной; системой? управления. Считается также, что; роботы имеют такие средства восприятия информации о текущей игровой ситуации на поле, что игра проходит с полной информацией.

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

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

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

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

Игра моделируется на 20-поле и считается, что все объекты на поле и их движения также двумерны. Соответственно, считается, что мяч движется только по плоскости игрового поля.

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

Puc.J. Общий вид игрового поля.

В начале игры, а также после забитых голов и остановок производится вбрасывание мяча. При вбрасывании, мяч случайным образом располагается в небольшом квадрате в центре поля, а роботы занимают фиксированные позиции на своих половинах. На рис.2, точками показаны стартовые позиции роботов обеих команд, для игры 5x5. Случайное положение мяча при вбрасывании необходимо для того, чтобы, каждый сеанс игры после вбрасывания отличался от другого, и игра не зацикливалась. При этом для достижения симметричности правил игры последовательные вбрасывания зеркально отличаются друг от друга, за исключением небольшого случайного слагаемого. ♦ Система коорринат на и грозам псле «

-А\.ч„о) (0.0) (-^„о)

Рис.2. Модель игрового поля, система координат.

С каждым объектом на поле связан ряд параметров 3-х типов, а именно: (1) постоянные параметры, к ним относятся масса объекта т, радиус г, максимальная скорость Vmax и т. д.; (2) переменные параметры: координаты (ус,у), скорость V и ее направление; (3) управляющие параметры для роботов: линейное ускорение и, угловая скорость со (считается, что она ортогональна плоскости'управляемого объекта).

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

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

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

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

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

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

Такие возможности настройки сделаны для повышения гибкости создаваемых средств моделирования, и для обеспечения моделирования большого числа разных вариантов. Описываемый подход может быть использован для моделирования и разработки средств управления для команд таких роботов, как роботы, определенные условиями Лиг инициативы RoboCup, роботы федерации F1RA [24], роботы-футболисты Фестиваля Наук и Технологий (Франция) [26], и других аналогичных.

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

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

- II

Рис.3. Область разрешенного удара. область, внутри которой данному, игроку разрешается наносить удар. Она представляет собой сектор круга, характеризуемый постоянным углом а и максимальным расстоянием удара Rmax. Значения этих констант может быть получено программой-игроком через соответствующие функции серверной программы. Удар характеризуется одной величиной — силой-, влияющей на то^ какой дополнительный импульс получает мяч, если он находится в зоне удара. При этом между двумя последовательными1 ударами, наносимыми данным игроком, должно пройти определенное время, зависящее от силы последнего удара.

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

Тактика игры> отличия от футбола ФИФА

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

Прежде всего, робот, даже находящийся рядом с мячом, не может осуществить на него какое-либо другое воздействие, кроме удара по нему своим корпусом, имеющим форму диска (или подталкивания, если в этот момент его скорость относительно мяча невелика). Это намного меньше того,, что может сделать с мячом человек-футболист. Например, робот не сможет «обработать» мяч, движущийся навстречу ему с большой скоростью - он сможет лишь отбить его в ту или иную сторону, либо пропустить его, уехав с линии движения мяча. В версии 2.0 было введено дополнительное средство контроля мяча - удар.

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

В отличие от людей, роботы, одинаковы по своим физическим возможностям. Кроме того, в правилах не описаны ни> амплуа вратаря, ни какие-либо дополнительные возможности, которые былиг бы для него доступны. Отметим, в частности, что»робот, играющий в данный момент роль вратаря, не может «поймать» мяч, а может только отбить его, как и любой другой игрок. Это означает, что в виртуальном футболе роботов деление игроков согласно их амплуа (например, «вратарь - защитник — полузащитник - нападающий») носит весьма условный характер. В данной диссертации во избежание путаницы и ложных ассоциаций мы будем пользоваться нейтральными обозначениями, например, «игрок обороны», «игрок нападения» и «игрок поддержки». I

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

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

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

Цель работы и методы выполнения исследований

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

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

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

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

Наиболее существенные результаты и научная новизна

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

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

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

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

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

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

Структура диссертации

Диссертация состоит из введения, 3 глав, заключения, приложения и списка литературы.

Заключение

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

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

Основное внимание уделено разработке и оптимизации алгоритмов игры роботов-футболистов.' Вместе с тем разработаны средства поддержки игры, такие как серверная программа, включающая 2d и* 3d визуализационные блоки, блоки механического5моделирования, а»также SDK для разработки команд игроков.

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

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

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

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

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

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

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

1. А. Александреску. Современное проектирование на С++: Обобщенное программирование и прикладные шаблоны проектирования: Перевод с английского. -М., Вильяме, 2004

2. Э. Аллен. Типичные ошибки проектирования. С.-Пб., Питер, 2003

3. К. Бек. Экстремальное программирование. С.-Пб., Питер, 2002

4. Г. Буч. Объектно ориентированный анализ и проектирование с примерами приложений на С++. - М., Бином-Пресс, 1999

5. Воленко Е.В., Квичанский А.В., TepexoBi С.А., Щукин Н.В. Генетическая оптимизация сложных иерархических систем. Тезисы IV Всероссийского рабочего семинара "Нейроинформатика* и ее приложения". Красноярск, 5-7 октября, 1996 г. С.75

6. Воленко Е.В., Терехов С.А., Щукин Н.В. Оптимизация функций многих переменных алгоритмами генетического поиска. Препринт ВНИИТФ 82, Снежинск, 1995

7. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно ориентированного проектирования. Паттерны проектирования. С.-Пб., Питер, 2004

8. А.В. Малолетов, Р.В. Лещенко, К.Ю.Лепетухин, Е.В.Ветошкина "Моделирование стратегии управления группой роботехнических объектов" II Искусственный интеллект, N 4, 2002, с. 574-579

9. Неймарк Ю.И. Динамические системы и управляемые процессы, М., Наука, 1978

10. Официальные материалы проекта «Виртуальный футбол». http://www.keldysh.ru/pages/robosoccer/

11. Д.Е.Охоцимский, В.Е. Павловский, А.Г.Плахов, А.Н.Туганов. Моделирование игры роботов-футболистов и базовые алгоритмы управления ими. // Искусственный интеллект, N 3, 2000, с. 534-540.

12. Д.Е.Охоцимский, В.Е. Павловский, А.К.Платонов, А.Г.Плахов,

13. A.Н.Туганов. Моделирование алгоритмов управления игрой роботов-футболистов. Тр. 12 научно-технической конференции "Экстремальная робототехника 2001", С.-Петербург, 2001

14. Д.Е.Охоцимский, В.Е. Павловский, А.Г.Плахов, А.Н.Туганов,

15. B.В.Павловский. Моделирование игры роботов-футболистов в пакете "Виртуальный футбол". // Мехатроника, 2002, №1, с.2-5.

16. Д.Е.Охоцимский, В.Е.Павловский, А.Г.Плахов, А.Н.Туганов, В.В.Павловский. Виртуальный футбол: алгоритмы и моделирование игры роботов-футболистов. //Сб. "Новые методы управления сложными системами", М.:Наука, 2004, с.289

17. В.Е.Павловский, А.Г.Плахов, А.Н.Туганов, В.В.Павловский. Проект "Виртуальный футбол": расширение серверов и программ-игроков. // Искусственный интеллект, 2003, №4, с. 153-157.

18. Растригин J1.A. Адаптация сложных систем. Рига, "Зинатне", 1981, 376 стр.

19. А.А. Станкевич, В.Э. Шмаков. Развитие футбола роботов за рубежом и в России//Х1 научно техническая конференция «Экстремальная робототехника»/Изд-во СПБГУ, С.Пб. 2001. С.45-51

20. С. Степанов. Алгоритм команды n-th.com («Днепр»), http://www.n-th.com/soccer/Dnepr.htm

21. Shu-Heng Chen, Tzu-Wen Kuo. Overfitting or Poor Learning: A Critique of Current Financial Applications of GP. Genetic Programming, Proceedings of EuroGP'2003, LNCS, Vol. 2610, Springer-Verlag, 14-16 April'2003, pp. 34-46.

22. FIRA official materials, http:// www. fira.net.

23. M. Fowler. Patterns of Enterprise Application Architecture. Addison Wesley, 2004

24. France Robotic Festival: http://www.robotik.org.

25. F. C. A. Groen, M. T. J. Spaan, N. Vlassis, "Robot soccer: Game or science?". Proceedings CNR-2002. http://citeseer.ist.psu.edu/groen02robot.html

26. P. Haroun. The Automated Theorem Proving System CARINE. http ://www.atpcarine .com/index2 .html

27. С. Hofner, G. Schmidt. Path planning and guidance techniques for antautonomous mobile cleaning robot. Robotics and Autonomous Systems, 14:199-212, 1995

28. J.H.Holland. Adaptation in Natural and Artifical Systems. MIT Press, 1975

29. J. Kok, R. de Boer, N. Vlassis. Towards an optimal scoring policy for simulated soccer agents. In Proc. 7th Int. Conf. on Intelligent Autonomous Systems, Marina del Rey, California, 2002, p. 195-198

30. J. R. Kok, R. de Boer, N. Vlassis, F.C.A. Groen. UvA Trilearn 2002 team description. In RoboCup 2002: Robot Soccer World Cup VI, Fukuoka, Japan, 2002.

31. G. Kuhlmann, P. Stone, J. Lallinger. The Champion UT Austin Villa 2003 Simulator Online Coach Team. RoboCup-2003: Robot Soccer World Cup VII, Springer Verlag, Berlin, 2004.

32. K. G. Kvikekval. Adaptive Graph Library. http://www.cs.ucsb.edu/~kris/Research/agl/agl.html

33. Ik Soo Lim, D. Thalmann. How Not to Be a Black-Box: Evolution and Genetic-Engineering of High-Level Behaviours. Proceedings of the Genetic and Evolutionary Computation Conference, Vol. 2, pp. 1329-1335, Morgan Kaufmann, 13-17 July 1999.

34. G. Luger. Artificial Intelligence: Structures and Strategies for Complex Problem Solving. Addison Wesley, 2005

35. H. H. Lund. Robot Soccer in Education. http://Iegolab.daimi.au.dk/Publications/pdfSocEdu.pdf

36. D. Mawhinney. Preventing early convergence in' genetic programming by replacing similar programs. Honours Thesis, 2000;

37. J.Morris. Dijkstra's Algorithm. http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html42. ; A. Kandel, G. Langholz. Fuzzy Control Systems. CRC Press, 1994

38. M. Nowostawski. Hierarchical; Code Generators. ALife VIII Workshop proceedings, 2002, pp. 63-71.

39. O. Omidvar, D. L. Elliott. Neural Systems For Control. Academic Press, 1997

40. Path Engine: Intelligent agent movement. Downloads. http://www.pathengine.com/downloads.php

41. M. Pinter. Toward More Realistic pathfinding. http://www.gamasutra.com/features/20010314/pinter 01 .htm

42. P. Robinson, P. Hall, J. Wolf, R. Phillips, C. Peck, P. Culverhouse, R. Bray, A. J. Simpson. The Technology and Challenges of Mirosot Robot'Football. http://www.tech.plym.ac.uk/robofoot/publications/paulrobihson/Warwick%2 0paper%202004.pdf

43. RoboCup Federation. Official materials, http://www.robocup.org

44. Robot F ootbal 1 at Plymouth. http://www. tec h. ply т. ac. uk/robofoot/

45. J. P. Rosea. An Analysis of Hierarchical Genetic Programming. Technical Report Number 566, University of Rochester, NY, USA, 1995.

46. S. Russell P. Norvig Artificial Intelligence: A Modern Approach.,- Prentice Hall, 1995

47. C. Ryan. Automatic Re-engineering of Software Using. Genetic Programming. Springer, 2000.

48. R;. Ryolo, B. Worzel. Genetic Programming Theory and Practice. Springer, 2004.

49. R. Salustowicz, J. Schmidhuber Evolving Structured Programs with Hierarchical Instructions and Skip Nodes. Proceedings of the Fifteenth International Conference on Machine Learning; ICML'98, Morgan Kaufmann, 1998, pp. 488-496 .

50. SoccerServer Manual. // RoboCup Federation electronic documentation and , links on the Internet, http://www.robocup.org/resource .

51. P. Smith. , Polygon Soup for the Programmer's Soul:: 3D pathfinding. . http://www.gamasutra.com/features/20020405/smith01 .htm

52. A.Stentz, The Focussed D* Algorithm for Real-Time Replanning. Proceedings of the International Joint Conference on Artificial Intelligence, 1995

53. P; Stone, M. M. Veloso, P. Riley. The CMUnited-98: Champion: Simulator Team. RoboCup-98: Robot Soccer World Cup II. Lecture Notes in Computer Science 1604 Springer 1999. pi 61-76

54. Wang, С.; Chen, X.; Zhao, X.; Ju, S. Design and Implementation of a General Decision-making Model in RoboCup Simulation. International Journal of Advanced Robotic Systems, Volume 1, Number 3, 2004, pp. 207 -212

55. T. Yu. Hierachical Processing for Evolving Recursive and Modular Programs Using Higher Order Functions and Lambda Abstractions. -Genetic Programming and Evolvable Machines, 2(4), December 2001, pp. 345-380