УДК 004.652

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

М.В. Быстряков

СФ МЭИ (филиал НИУ МЭИ в г. Смоленске)

Статья посвящена освещению проблем поиска пути возникающим при игровом моделировании. Целью работы является анализ и оптимизация существующих алгоритмов под задачи игрового моделирования.

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

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

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

Рассмотрим типовой алгоритм A*.

Алгоритм A* по сути является расширением алгоритма Дейкстры. Этот алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).

A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. От жадного алгоритма (который тоже является алгоритмом поиска по первому лучшему совпадению) его отличает то, что при выборе вершины он учитывает, помимо прочего, весь пройденный до неё путь (составляющая g(x) — это стоимость пути от начальной вершины, а не от предыдущей, как в жадном алгоритме). В начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению

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

Чем меньше эвристика h(x), тем больше приоритет (поэтому для реализации очереди можно использовать сортирующие деревья). [1]

На рисунке 1 представлен процесс нахождения пути от начальной точки на относительно простом и небольшом участке карты.

Рисунок 1 – Реализация поиска пути алгоритмом A*

Принято считать что алгоритм A* для нахождения пути является наилучшим для применения в игровых моделях причём реального времени. Тем не менее остаётся ряд проблем:

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

Рассмотрим пути решения перечисленных проблем.

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

Алгоритм выбора вейпойнтов:

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

Алгоритм поиска пути:

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

Преимущества такого подхода:

• сильно увеличивается скорость нахождения пути относительно алгоритма A*;
• уменьшается объемы используемой памяти;
• простота реализации;
• возможность обрабатывать динамически изменяемую карту.

Недостатки алгоритма:

• чрезмерная абстракция может как упростить, так и усложнить задачу поиска пути. Необходимо найти золотую середину.

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

Литература

1. Нильсон Н. Искусственный интеллект: методы поиска решений = Problem-solving Methods in Artificial Intelligence / Пер. с англ. В.Л. Стефанюка; под ред. С.В. Фомина. – М.: Мир, 1973. – С. 70–80.
2. БЫСТРЯКОВ Михаил Владимирович – магистрант СФ МЭИ (филиал НИУ МЭИ в г. Смоленске).