Содержание к диссертации
Введение
Глава 1. Алгоритмы управления роботами-футболистами 19
1.1. Базовые алгоритмы управления мобильнымроботом- футболистом 24
Достижение точки ...24
Перехват мяча с упреждением 27
Достижение точки при заданном направлении приезда 30
1.2. Построение и использование таблиц успевания 33
1.3. Прогнозирование изменения ситуациина игровом поле 41
1.4. Алгоритмы прямой иерархии управления роботом футболистом 45
Недостатки алгоритмов прямой иерархии.управления 51
Глава 2. Алгоритмы планирования действий роботов-футболистов 54
2.1. Граф ситуаций взадаче планирования действий роботами-футболистами 56
2.2: Задача поиска путей и ее обобщение на планирование действий 58
2.3. Стандартные алгоритмы поиска путей, сравнение эффективности 62
Обход препятствий. 62
Поиск пути на.графе 64
Недостатки рассмотренных стандартных алгоритмов 70
2.4. Быстрый поиск путей на больших пространствах поиска 72
Вариация алгоритма Дийкстры, использующая-фиксированную память 72
Иерархические алгоритмы поиска путей 75
Построение укрупненного представления карты 77
Эффективная реализация иерархического поиска 81
2.5. Планирование путем просчета в глубину 83
Сравнение эффективности различных алгоритмов 85
Вариация алгоритма просчета в глубину с лидером 86
2.6. Задача группового передвижения 87
2.7. Алгоритмы обратной иерархии управления. Алгоритм AVST.. 89
Разрешение конфликтов при помощи ключевых точек и избегания коллизий 93
Глава 3. Методы эволюционной оптимизации в задачах виртуального футбола роботов 97
3.1. Использование принципов эволюционной оптимизации при создании алгоритмов-игроков 100
3.2. Сравнение методов эволюционной оптимизации и схемы обратной иерархии управления 111
3.3. Сочетание методов эволюционной оптимизации и схемы, обратной иерархии управления 114
Заключение 127
Приложение. Архитектурные и программные решения в пакете «Виртуальный футбол» 129
Требования к среде моделирования 130
Описание выбранных архитектурных и программных решений 136
Схемы компонент сервера виртуального футбола 150
Литература
- Достижение точки при заданном направлении приезда
- Прогнозирование изменения ситуациина игровом поле
- Стандартные алгоритмы поиска путей, сравнение эффективности
- Сравнение методов эволюционной оптимизации и схемы обратной иерархии управления
Введение к работе
Актуальность темы
Диссертационная работа посвящена разработке алгоритмов группового управления. На их основе и для их исследования и оптимизации создаются программы управления командой виртуальных роботов-футболистов.
В настоящее время задача группового управления роботами признается одной из центральных проблем мехатроники. Поскольку разработки обобщенных алгоритмов и принципов управления в данной задаче пока находятся на ранней стадии, научным сообществом было сформулировано несколько модельных задач, на которых в настоящий момент принято и рекомендуется отрабатывать основные методы решения данной задачи.
Одной из основных модельных задач является так называемый роботизированный футбол. Конечная цель, поставленная научным сообществом- в данной задаче, обычно формулируется так: к 2050 году создать команду человекоподобных роботов, которые смогут на равных играть в футбол на обычном поле по правилам ФИФА с командой-чемпионом мира среди людей. В настоящее время различные соревнования по роботизированному футболу проводятся во многих странах мира, таких как Франция, Корея, Япония.
При этом, однако, возникает ряд существенных проблем. Роботы, принимающие участие в подобных соревнованиях, являются весьма сложными и достаточно дорогостоящими. Создание подобной команды обычно связано с решением множества технических проблем, не имеющих отношения к задаче группового управления.
В связи с вышеизложенным, приобретает большую значимость разработка сред моделирования роботизированного футбола для проведения виртуальных соревнований. Участие в таких соревнованиях позволяет разработчикам алгоритмов, во-первых, избежать расходов на аппаратную часть команды, во-вторых, сконцентрировать усилия на создании алгоритмов.
В 1999 — 2005 годах группой студентов и преподавателей МГУ им. М. 1 В. Ломоносова был создан и поддерживается проект «Виртуальный футбол» [11, 12, 13, 15, 44], включающий в себя виртуальную среду моделирования игры, алгоритмы моделирования поведения роботов - футболистов, средства разработки алгоритмов для сторонних команд и средства проведения и визуализации соревнований таких алгоритмов: В играх принимают участие программы, представляющие собой команду-игрока, и управляющие каждая командой 5 виртуальных «колесных роботов». Первые российские соревнования по виртуальному футболу роботов были организованы в МГУ под эгидой Научно-технических Фестивалей "Мобильные роботы" [10].
Во время Фестиваля "Мобильные роботы - 2000" (декабрь 2000 г.) прошли первые1 показательные соревнования (носившие демонстрационный характер), целью которых являлось ознакомление участников с предлагаемыми схемами разработки игровых программ и подготовка к следующим, официальным, соревнованиям1 по виртуальному футболу роботов. Первые официальные соревнования по виртуальному футболу роботов прошли в пос. Дивноморское на конференции "Искусственный интеллект - 2001", а участие в следующем турнире принимало уже команд. Было проведено несколько региональных турниров, первый из которых прошел в г. Донецке в 2002 году.
За время существования проекта прошло уже более 15 турниров в 6 городах. В проекте принимает участие более 40 команд из 11 городов, между
, которыми идет напряженная борьба за первенство. Обладателями золотых
. медалей турниров становилось восемь различных команд [10].
Результаты, показанные в соревнованиях, проводимых в среде
, моделирования «Виртуальный футбол», позволяют производить отбор
наиболее эффективных методов управления и обобщение этих методов на другие задачи группового управления [8, 19, 22, 24, 26, 44, 49].
Достижение точки при заданном направлении приезда
Для эффективной игры требуется кроме задачи перехвата мяча, решение которой было приведено выше, решить также задачу удара по мячу в заданном направлении. Как правило, она решается при том предположении, что масса мяча мала по сравнению с массой футболиста, и, таким образом, массой мяча можно пренебречь. В этом случае задача удара по мячу сводится к задаче достижения точки упреждения при заданном угле сближения, т.е. к задаче переведения робота из начального состояния \х\ У\ "мах \) в конечное состояние \х2 У2 умах 2)w в начале и конце своего пути робот должен двигаться по минимальным поворотным окружностям (см. рис. 8). Соединяя начальные и конечные пары окружностей общими касательными прямыми, мы получим четыре касательные, хотя бы на одной из которых направление совпадает с направлениями обхода обоих окружностей, по которым она строится. Соединив дуги на начальной и конечной окружности, мы получим искомые траектории, из которых можем выбрать кратчайшую.
Достижение точки при заданном направлении приезда (финальная точка находится на минимальной поворотной окружности).
Недостатком таких траекторий является их неустойчивость. Дело в том, что если целевая точка находится на границе мёртвой зоны робота футболиста (а на финальном участке траектории она находится именно там), то небольшие колебания целевой точки внутрь или наружу мёртвой зоны будут вызывать сильные изменения в траектории движения (пример подобной ситуации приведен на рис. 9)
Одним из решений, позволяющих улучшить ситуацию, является добавление «резервного участка» в конец траектории таким образом, чтобы целевая точка не лежала на границе мёртвой зоны робота во время движения (рис. 10). Длина резервного участка выбирается исходя из типичных для алгоритма колебаний целевой точки со временем.
Устойчивое достижение точки при заданном направлении приезда.
Задача численного построения соответствующего управления упрощается с учетом того, что окружности, общую касательную к которым мы ищем, имеют одинаковый радиус.
Пусть длина финального отрезка траектории выбрана равной /. В этом случае финальный отрезок траектории должен начаться в положении футболиста, задаваемом значениями (х2 -lcosy/2,y2 -lsmy/2,Vmm,ii/2). Две поворотные окружности минимального радиуса, соответствующие данному положению футболиста, имеют центры в точках . , sin 2 , . cosy/-,. (х2 -lcosy/2 + - -, У г -/sin 2 - -) (Х2 -lC0Sl//2 Q » 2 -/Sin 2 + Гі) . Для определенности предположим, что для движения выбрана первая из них, а на первом участке траектории робот движется по правой минимальной поворотной окружности. Робот на первом участке движется с максимальной для себя угловой скоростью до тех пор, пока угол между направлением его движения и осью х не составит величину sin у/7 sin щ, х2 -lcosy/2 + —- i — arctg — —— (здесь и далее предполагается, что , . COSU/-, COS ИЛ функция arctg в плюс и минус бесконечности, т.е. при нулевом знаменателе, доопределена по непрерывности значениями — и — соответственно).
На втором участке траектории робот переходит к прямолинейному движению на расстояние \. , sin и/2 shwl42 ,. cos , cost//, .2 тт J(x2 -lcosy/2 +- - 1 Q ) +te /sin 2 Q " + Q третьем участке робот движется с максимальной угловой скоростью до тех пор, пока его курсовой угол не составит у/2, после чего выходит на финальный прямолинейный участок длины /.
Прогнозирование изменения ситуациина игровом поле
При разработке командных алгоритмов управления роботами-футболистами типично возникновение следующих трудностей. С одной стороны, робот (как виртуальный, так и настоящий) на каждом такте может выполнять только простейшие команды (поворот, ускорение, торможение), а на вход алгоритмов информация об игре поступает только в форме набора координат и скоростей игровых объектов (игроков и мяча). С другой стороны, эффективная командная игра предполагает исполнение сложных правил игровой стратегии, таких, как, например, «если мяч ведет игрок чужой команды, и ситуация может быть опасна для наших ворот, то робот должен попытаться отбить мяч в угол игрового поля, за исключением ситуации, когда другой наш робот уже пытается это сделать». Входящие в подобные правила нечеткие понятия («опасная ситуация», «игрок ведет мяч») и стратегии действия («отбить мяч в угол») являются самоочевидными для человека-наблюдателя или разработчика, однако их эффективная реализация при помощи только простейших команд движения (фактически, только при помощи изменения напряжения на двигателях на протяжении некоторого промежутка времени) - очень непростая задача.
При использовании иерархических ролевых схем принятие решений разбито на два и более уровней. Рассмотрим двухуровневую схему принятия решений. На более высокий уровень вынесены все расчеты, касающиеся командного взаимодействия. Текущая игровая ситуация сравнивается с имеющимися шаблонами, результатом является набор соответствий «номер игрока — роль». Согласно этим соответствиям происходит распределение ролей, то есть постановка промежуточных задач отдельным роботам-футболистам. На более низком уровне происходит формирование собственно команд управления для каждого робота отдельно, при этом используется только информация о роли данного игрока, и местоположении небольшого количества объектов, важных для данной роли (например, игрока, мяча и ближайшего игрока противника). Таким образом, командное взаимодействие полностью вынесено на верхний уровень содержательных решений.
Поскольку в проекте «Виртуальный футбол» игровые правила и физические возможности одинаковы для всех игроков (например, нельзя сказать, что робот А лучше стоит на воротах, а робот Б сильнее бьет по мячу), игровые роли не фиксированы. Со временем игрок может менять свою роль в зависимости от игровой ситуации.
Каждая роль, в свою очередь, характеризуется ролевым алгоритмом. Ролевой алгоритм - это набор правил, определяющих, какие составные действия) (например, «отдать пас игроку номер N») должен в данной ситуации выполнять этот игрок. Когда составные действия определены, вызывается алгоритм-исполнитель, определяющий действия на наиболее низком уровне абстракции, то есть переводящий требуемые действия на язык низкоуровневых команд для данного игрового такта (повернуть, затормозить, ускориться). Разным ролевым алгоритмам может соответствовать один и тот же алгоритм-исполнитель, отличия между ними будут заключаться в том, что исполнителю будут передаваться разные требования.
Ниже приведено описание типичного командного алгоритма для команды, состоящей из трех игроков. Этот алгоритм был использован в одной из версий команды VST.
Распределение ролей. Алгоритм динамически определяет каждому игроку одну из трёх ролей: игрок обороны, игрок поддержки и игрок нападения. Роли не закреплены изначально за игроками и выбираются в соответствии с их текущими позициями: игрок обороны - ближе всех к воротам игрок нападения - ближе всех к мячу игрок поддержки — оставшийся без роли игрок
Эти правила выполняются с приоритетами, расположенными в приведённом выше порядке. Например, игрок обороны, находящийся ближе всех к мячу, остаётся игроком обороны (а не переходит в нападение) до тех пор, пока другой игрок не начнет находиться ближе к воротам.
Оценка текущей ситуации на поле. После распределения ролей алгоритм выясняет, какая из команд контролирует мяч, и какая из команд атакует. Происходит это по следующим правилам. Если мяч находится на половине команды- Б, и при- этом расположен ближе к одному из игроков команды А, нежели к любому из игроков команды Б, считается, что команда А атакует, а команда Б. обороняется. Заметим, что возможна ситуация, в которой ни одна из команд не может быть названа атакующей.
Игрок считается контролирующим мяч, если он может, внося поправки в, его передвижение собственным корпусом, менять его траекторию. Этот процесс внешне схож с ведением мяча в футболе людей, однако производится иначе. Например, чтобы сместить направление движения мяча левее, робот, толкающий его перед собой своим цилиндрическим корпусом, слегка поворачивает направо.
Для того, чтобы определить, контролирует ли1 данный-игрок мяч, и сможет ли он делать это в непосредственном будущем, алгоритм проверяет два условия: расстояние между игроком и мячом, не дoлжнo превышать заданного, и их скорости должны быть близки (как по абсолютной величине, так и по направлению). Конкретные величины допустимых расхождений выбираются в зависимости от параметров физической модели.
Стандартные алгоритмы поиска путей, сравнение эффективности
Хотя методы обхода препятствий, рассмотренные выше, часто проделывают допустимую или даже адекватную работу, в большинстве ситуаций единственно разумным подходом является планирование пути с учетом карты всего пространства поиска.
Из теории графов известно несколько алгоритмов, которые могут быть использованы в задачах поиска путей. В литературе они, как правило, представлены в терминах конечных автоматов или прохода по узлам графа. Применение этих алгоритмов к поиску пути в геометрическом пространстве требует следующей адаптации: состоянием конечного автомата или узлом графа считаетсяt определенная клетка карты пространства поиска, а передвижение в-соседние с ней клетки соответствует изменению состояния автомата (переходу в смежные узлы графа).
Известны следующие алгоритмы поиска путей на графах:
Поиск в ширину. Начиная со стартового узла, при поиске в ширину сначала рассматриваются все непосредственно1 соседние узлы, затем все узлы в двух шагах, затемів трех, и так далее, пока цель не достигнута. Длякаждого узла его непроверенные соседи помещаются в FIFO очередь. Ранее рассмотренный узел второй раз не рассматривается. При рассмотрении узла запоминается тот узел, из которого мы пришли в него (узел-родитель). При достижении целевой точки по информации- о родительских узлах строится искомый путь.
Метод поиска в ширину применим при наличие Ограничения 1 на задачу поиска пути. Метод поиска в ширину редко используется для. задачи поиска путей, т.к. обычно не является оптимальным по скорости. Он хорошо1 работает для пространств поиска, в которых длина минимального пути между точками; как правило, во много раз превышает геометрическое расстояние между ними (например, при поиске пути в сложных лабиринтах). [54]
Модификацией поиска в ширину является двунаправленный поиск в ширину. Этот способ отличается тем, что запускаются два одновременных поиска в ширину - из стартового и конечного узлов. Они останавливаются, когда узел из одного фронта поиска находит соседний узел из другого фронта.
Итеративный поиск в глубину (Алгоритм IDDFS). Поиск в глубину противоположен поиску в ширину. Начиная со стартового узла, посещаются всех наследники, затем - соседи узла. Чтобы гарантировать останов, поиск заканчивается на определенной глубине. Для. каждого узла его непроверенные соседи помещаются в last-in-first-out стек. Каждая ячейка маркируется как "посещенная" при продвижении вглубь. Эта пометка снимается на обратном ходу, чтобы избежать генерации путей, которые дважды посещают одну и ту же ячейку. Для применения этого алгоритма в задачах поиска пути можно сделать два дополнения. Первое будет заключаться в добавлений-метки на каждую ячейку с длиной найденного к ней,кратчайшего пути; алгоритм больше не посетит эту ячейку, пока не будет иметь к ней путь с меньшей стоимостью. Другое дополнение заключается в том, что при выборе порядка обработки соседей первыми обрабатываютсягте, которые находятся ближе к цели. Для того чтобы на задачу не накладывалось» Ограничение 1, требуется делать остановку поиска не по определенной глубине, а по накопленной стоимости пути.
В алгоритме поиска в глубину существует проблема выбора правильной глубины остановки.1 Если она будет слишком- маленькой, то путь не будет найден; если же она выбрана слишком большой, то потенциально можно потратить много времени впустую, исследуя слишком глубоко, или найти путь с очень высокой стоимостью. Эти проблемы решаются введением в алгоритм итеративного углубления. Поиск в глубину выполняется с увеличивающейся глубиной до тех пор, пока путь не будет найден. Поиск начинается с глубины, равной расстоянию по прямой от старта к цели. Этот вид поиска является асимптотически оптимальным среди всех переборных алгоритмов по времени и памяти [54].
Алгоритм IDDFS широко используется в таких приложениях, как автоматическое доказательство теорем [38].
Наиболее эффективно применение алгоритма IDDFS в случае анизотропности свойств пространства поиска, например, при передвижении на небольшие расстояния колесных средств со значительным радиусом разворота. Примером такой ситуации может служить задача автоматической парковки автомобиля.
В пакете «Виртуальный футбол» алгоритм IDDFS был использован в алгоритме команде AVST для выбора оптимального способа ведения мяча корпусом робота. Об этом будет сказано подробнее в 2.7.
Алгоритм Дийкстры Этот метод был разработан Е. Дийкстрой (Е. Dijxtra) [41] для того, чтобы снять присущее алгоритму поиска в ширину Ограничение 1. В реализации этого метода рассматриваемые узлы добавляются не в очередь FIFO, а в очередь с приоритетами, из которой затем извлекаются согласно присвоенным им приоритетам, начиная с наивысшего. В алгоритме Дийкстры значением приоритета является стоимость пути от старта (чем меньше стоимость,,тем выше приоритет).
Сравнение методов эволюционной оптимизации и схемы обратной иерархии управления
Рассматриваемые в предыдущем параграфе методы эволюционной оптимизации и схема обратной иерархии управления имеют между собой много общего.
И в том, и в другом случае алгоритм представляет собой комбинацию некоторых базовых блоков поведения, каждый из которых основан на некоторых теоретических или эмпирических соображениях, и является детерминированным (в том понимании этого термина, которое сформулировано во введении к главе 1). При этом итоговое поведение команды оказывается недетерминированным.
Основное отличие этих двух методов друг от друга заключается в том, в какой момент выбирается используемое сочетание базовых блоков поведения и набора их параметров. В случае методов эволюционной оптимизации оно определяется в процессе создания алгоритма, то есть до начала игры с реальным соперником. В случае схемы обратной иерархии управления, используемые алгоритмы низкого уровня и их настройки определяются непосредственно в ходе игры (вообще говоря, они могут меняться на каждом такте игры).
Перечислим вытекающие из этого отличия преимущества и недостатки этих методов. Эволюционная оптимизация Скорость работы итогового алгоритма — высокая Основные факторы, ограничивающие итоговое качество игры: затраты машинного времени на этапе создания алгоритма; качество используемых базовых блоков; время, затрачиваемое на одну тестовую игру до достижения статистически значимого результата
Нет способа, увеличив затраты машинного времени в ходе реальной игры, сделать ее более эффективной
Настраиваемые параметры базовых блоков определяют стратегию игры (например, размеры и форму зон ответственности игроков, константы, участвующие в выборе ключевых точек; см. 1.4)
Может использоваться для создания как централизованных, так и децентрализованных алгоритмов группового управления, в том числе и таких, в которых отдельные исполнители не обмениваются информацией друг с другом" Схема обратной иерархии управления
Скорость работы итогового алгоритма - низкая (из-за использования перебора вариантов)
Основные факторы, ограничивающие итоговое качество игры: затраты машинного времени в ходе реальной игры; качество функции оценки ситуации; скорость расчета при использовании каждой из тактик, подлежащих перебору
Нет способа, увеличив затраты машинного времени в ходе подготовки алгоритма; автоматически добиться повышения его эффективности
Настраиваемые параметры базовых блоков определяют непосредственные действия в ближайший момент времени (направление удара по мячу,, точку, в которую направляется данный футболист, и т.п.; см. 2.7)
Может использоваться для создания только для централизованных алгоритмов группового управления и для таких децентрализованных алгоритмов, в которых отдельным исполнителям разрешено постоянно обмениваться информацией
В рамках проекта «Виртуальный,футбол роботов» было выявлено, что алгоритмы, построенные по схеме обратной иерархии управления, как правило, играют эффективнее, нежели алгоритмы, полученные эволюционным путем. Это происходит потому, что решение - об использовании того, или иного базового поведения не фиксируется на этапе создания алгоритма, а принимается в зависимости от ситуации на поле при помощи перебора различных вариантов и их оценки. Даже если поведение, настроенное в ходе автоматической оптимизации, является оптимальным среди всех себе подобных, ясно, что выбор наилучшего поведения в каждый момент времени; является более, мощным методом. Единственное, в чем продукты эволюции могут превосходить переборные; алгоритмы — это стратегический уровень организации игры (поскольку варианты стратегического поведения плохо поддаются перебору); однако в контексте проекта; «Виртуальный; футбол роботов» подобное преимущество влияет на результат значительно меньше:
Поведение, получаемое при помощи алгоритмов планирования; с точки зрения . человека-наблюдателя оказывается? менее предсказуемым;! и обеспечивает эффективную "игру даже; в ;такихситуациях, подобные которым не.встречались илиредковстречались выходе тестовых (проводимых на этапе разработки алгоритма) игр:
