WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

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

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

Данная процедура выполняется только один раз, это происходит до начала собственно игры.

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

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

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

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

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

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

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

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

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

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

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

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

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

Будем считать, что промежутки игры между двумя последовательными голами независимы, и что гол на каждом таком промежутке забивается правой и левой командами с вероятностью соответственно и, где, причем эти вероятности нам заранее неизвестны, и мы хотим найти их приближенное значение в ходе тестовой игры. Рассмотрим величины, где, если гол на N-том промежутке забит правой командой, и, если гол забит левой. Обозначим общий счет игры, где – число голов, забитых правой, – левой командой. Согласно закону больших чисел, Для вычисления приближенного значения следует использовать это равенство со снятым (то есть при фиксированном N). Найдем дисперсию этой величины. Имеем:

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

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

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

Поэтому интерес представляют гибридные подходы.

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

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

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

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

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

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

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

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

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

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

Издательство МГУ, 2001, с.192 - 203.

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

Моделирование игры роботов-футболистов и базовые алгоритмы управления ими. // Искусственный интеллект, N 3, 2000, с. 534-540.

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

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

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

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

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

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»