А. А. Алимов, О. А. Шабалина - Искусственный интеллект в компьютерных играх. Многоуровневое планирование и реактивное поведение агентов

Ключевые слова

искусственный интеллект, мультиагентные системы, виртуальная реальность.

Аннотация

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

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

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

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

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

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

Основными задачами игрового ИИ являются:

– реализация поведенческих реакций, таких как сбор предметов, нажатие переключателей, выполнение определенных жестов;

– решение задачи навигации в виртуальном мире, в которую входят поиск пути, поиск пути с использованием интерактивного окружения, а также перемещение группами;

– принятие решений, выбор определенной тактики поведения или действия из нескольких возможных.

Поведение аниматов, как правило, имеет многоуровневый характер; разработчики игр обычно выделяют четыре уровня поведения [4]:

– стратегический уровень, на котором персонаж ставит себе те или иные цели;

– тактический уровень, на котором выбираются способы достижения целей;

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

– инстинкт самосохранения (например, персонажи защищаются при нападении и т. д.).

Однако, как показывает практика, подобное деление далеко не всегда является подходящим (в частности, в нем нет места для моделирования эмоций). По словам одного из разработчиков игры SilentStorm, идеальной была бы модель поведения со сколь угодно большим количеством уровней планирования [5].

На сегодняшний день можно выделить следующие существенные проблемы, присущие игровому искусственному интеллекту:

– «зависание», в результате которого подсистема ИИ в некоторых ситуациях никогда не отдает команды «конец хода» (проблема специфичная для пошаговых игр);

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

– применение тактики в неподходящей ситуации (например, строительство верфи на картах, лишенных воды);

– сложность реализации совместных действий c учетом влияния персонажей друг на друга;

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

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

При проектировании систем игрового ИИ различные уровни планирования поведения часто используют принципиально различные интерфейсы, что серьезно затрудняет разработку иерархичных систем. Решение этой проблемы позволит существенно сократить затраты на разработку ИИ и повысить его эффективность. В рамках данной работы были рассмотрены модели и методы реализации поведения аниматов в открытых и коммерческих системах игрового ИИ, таких как FEAR [3], HavokAI [6], ORTS[7], A-Life [8].

В состав HavokAI входят максимально полезные и эффективные для разработчика алгоритмы (преимущественно это алгоритмы нахoждения пути в динамически изменяющемся и динамически подгружаемом виртуальном мире [5]). FEAR позиционируется как проект, использующий преимущественно методы классического ИИ. ORTS – проект с открытым исходным кодом для реализации стратегий в реальном времени. Помимо подсистемы ИИ, ORTS предоставляет также средства визуализации и взаимодействия с пользователем [7].

A-Life – встроенная в X-Ray система управления персонажами.A-Life реализует два режима перемещения персонажей: он- и оффлайн. Для каждого из уровней создается свой навигационный граф, детальный, который используют персонажи для передвижения в онлайне. Для каждого детального графа также создается его менее детализированный аналог, вершины которого можно связать с вершинами графа другого уровня. После объединения всех таких графов воедино получается граф, который объединяет все уровни. Он и используется персонажами для передвижения в оффлайне. Также им пользуются персонажи в онлайне, когда они выполняют свои стратегические цели [8].

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

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

Возможность обучения – одно из главных преимуществ нейронных сетей перед традиционными алгоритмами. Однако, из-за невозможности интерпретации этой модели человеком, нейронные сети редко используют в алгоритмах принятия тактических решений, гораздо лучше они работают в реализации выбора оружия или прицеливания, как например в FEAR [3]. К тому же велика вероятность того, что дообученная или обученная заново нейронная сеть будет работать хуже.

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

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

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

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

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

Рисунок 1 - Cхема поведения агента

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

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

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

Библиографический список

1. Редько, В. Г. От моделей поведения к искусственному интеллекту / В. Г. Редько. – М.: КомКнига, 2010. – 456 с.
2. Крыжановский, А. И. Применение кооперативного обучения и прогнозирования в мультиагентных системах / А. И. Крыжановский, П. С. Пыхтин // Известия Волгоградского государственного технического университета : межвуз. сб. науч. ст. № 6 (66) / ВолгГТУ. – Волгоград, 2010. – (Сер. Актуальные проблемы управления, вычислительной техники и информатики в технических системах. Вып. 8). – С. 44–46.
3. Шампандар, Дж. А. Искуственный интеллект в компьютерных играх / Дж. А. Шампандар. – М.: Вильямс, 2007. – 768 стр.
4. Медноногов, В. А. Интеллект компьютера в стратегиях реального времени [Электронный ресурс] / В. А. Медноногов. – Режим доступа: http://pmg.org.ru/ai/ai_rt.htm.
5. Плахов, А. С. КРИ / А. С. Плахов // Организация разработки AI для стратегических игр. – 2004.
6. Havok AI / Оф. сайт Havok Inc. [Электронный ресурс]. – 2010. – Режим доступа: www.havok.com.
7. Buro Michael ORTS – A Free Software RTS Game Engine. – Games Group University of Alberta. – 2010. – Режим доступа: http://skatgame.net/mburo/orts/.
8. Куляев, А. М. S.T.A.L.K.E.R: Тень Чернобыля. Интервью с руководителем проекта [Электронный ресурс] / А. М. Куляев // CRGP.RU. – 2007. Режим доступа: http:// www.crpg.ru/sections.php?op=viewarticle&artid=2165
9. Бугайченко, Д. Ю. Разработка и реализация методов формально-логической спецификации самонастраивающихся мультиагентных систем с временными ограничениями / Д. Ю. Бугайченко // Сайт математико-механического факультета СпбГУ. – Санкт-Петербургский государственный университет, 2007. – 2010. – Режим доступа : http://www.math.spbu.ru/user/soloviev/Бугайченко_phd_toup load.pdf.