Актуальность темы
.
Диссертационная работа посвящена разработке алгоритмов группового управления. На их основе и для их исследования и оптимизации создаются программы управления командой виртуальных роботов-футболистов.
В настоящее время задача группового управления роботами признается одной из центральных проблем мехатроники. Поскольку разработки обобщенных алгоритмов и принципов управления в данной задаче пока находятся на ранней стадии, научным сообществом* было сформулировано несколько модельных задач, на которых в настоящий момент принято и рекомендуется отрабатывать основные методы решения данной задачи.
Одной из основных модельных задач является так называемый роботизированный футбол. Конечная цель, поставленная научным сообществомв данной задаче, обычно формулируется так: к 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, точками показаны стартовые позиции роботов обеих команд, для игры 5×5. Случайное положение мяча при вбрасывании необходимо для того, чтобы, каждый сеанс игры после вбрасывания отличался от другого, и игра не зацикливалась. При этом для достижения симметричности правил игры последовательные вбрасывания зеркально отличаются друг от друга, за исключением небольшого случайного слагаемого. ¦ Система коорринат на и грозам псле «.
— А. ч"о) (0.0) (-^&bdquo-о).
Рис. 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.
