Utility AI: Поведенческие деревья уходят в прошлое?

Введение

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

Как поведенческие деревья стали править миром игровых ИИ (и почему перестают им править)

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

Способность к переходу из любого состояния в любое другое посредством определения соответствующих условий позволяет без лишних сложностей настраивать конечный автомат для поведения ИИ. Однако, в этом и недостаток такого подхода. В комплексных играх конечный автомат может вмещать сотни состояний, и при таких масштабах отладка становится чрезвычайно сложной. В 2005 году Дэмиен Айла (Damian Isla) в своей речи на GDC в подробностях рассказал об этом на примере Halo 2.

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

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

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

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

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

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

Каковы современные требования к передовому искусственному интеллекту?

Всё это возвращает нас к тому, чего ждут от ИИ в наши дни.

Современный игровой ИИ требует технологий, способных поддерживать комплексные игровые миры с глубоким погружением. В таких играх, как Hitman, Witcher и Assassin’s Creed количество неигровых персонажей всё возрастает, и люди ждут от них всё более естественного и своеобразного поведения. А, к примеру, в Call of Duty и The Division очень много противников, вместе с чем растёт спрос на разнообразие их поведения и на способность к тактическим действиям. Статичный гейм-дизайн со скриптами уже никого не впечатляет, нынешним игрокам, да и самим гейм-дизайнерам хочется динамичных и постоянно меняющихся ситуаций.

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

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

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

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

Новая парадигма искусственного интеллекта

Killzone 2 в своё время хвалили за один из лучших ИИ. Для динамического принятия тактических решений искусственными оппонентами Guerilla Games использовали систему подсчёта очков на основе выгодности действий, и в подробностях описали, как она позволяет ИИ совершать обдуманные тактические манёвры без досконального знания игрового мира. Подобные системы ИИ использовались в F.E.A.R и Civilization, схожим образом работают и знаменитые боты из Quake.

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

• Простота проектирования – Искусственный интеллект на основе Utility AI зачастую может описываться на обыкновенном языке, что упрощает коммуникацию между программистом и дизайнером. Нет необходимости затрагивать такие мистические понятия, как условия, состояния, последовательности и декораторы. Вместо этого можно объяснить планируемое поведение как «если персонаж под огнём, главная его задача – поиск укрытия». Обратите внимание, какие размытые, но естественные для обычного общения термины («главная задача») могут при этом использоваться.
• Упрощённая расширяемость – Правила, часто называемые маркерами, можно свободно добавлять поверх существующей системы ИИ. В отличие от того же конечного автомата, здесь не порвутся никакие важные связи. Новые начислители просто добавляются к уже работающим, что расширяет функциональность и правдоподобность искусственного интеллекта.
• Повышенное качество – Вышеуказанные пункты значительно сокращают количество ошибок и увеличивают продуктивность. Это, в свою очередь, оставляет простор для совершенствования ИИ в пределах прежних сроков и бюджета, что повышает его итоговое качество.

Однако, внутри у Utility AI есть особая магия, делающая его в целом более качественным методом принятия решений. Дэйв Марк (Dave Mark) из Intrinsic Algorithm объясняет, как можно использовать кривые для начисления очков различным действиям, доступным ИИ:

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

Кривые позволяют Utility AI принимать решения на основе широкого спектра входных данных, и качество системы выходит на уровень нечёткой логики. На практике это означает, что Utility AI может принимать неплохие решения даже в ситуациях, не предусмотренных программистом ИИ. Такое в изобилии встречается в Killzone 2, и это часть внутренней магии искусственного интеллекта.

Простота использования Utility AI распространяется и на те области, с которыми обычно возникают проблемы у поведенческих деревьев. Сравнение и сортировка по приоритету сотен тактических позиций, как это делает ИИ Killzone 2, было бы сложной задачей для деревьев, поскольку новые ветви нельзя добавлять динамически. Некоторые поведенческие деревья, например, как в Blueprint, решают эту проблему подключением специального модуля Environmental Query System. Это система, опрашивающая окружение на предмет позиций и определяющая их важность согласно установленным правилам – как в линейном программировании. Однако, правила Utility AI могут начислять очки любой отдельно взятой группе объектов, будь то тактическая позиция, планета, поставленная задача или выбор оружия. Таким образом методология принятия решений становится очень гибкой.

Различия между поведенческими деревьями и Utility AI

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

Им доступно четыре действия: движение к врагу, огонь по врагу, движение к укрытию и перезарядка. Решения о текущем действии принимается на основании четырёх входящих значений.

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

Таблица ниже сопоставляет входные данные и выполняемые действия:

Сначала мы попробуем реализовать такой ИИ с помощью поведенческого дерева, а потом с помощью Utility AI.

Поведенческое дерево

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

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

На этом этапе у дерева уже немало ветвей, хотя действий и входящих параметров всего по четыре. Можно и не говорить, что поведенческие деревья разрастаются очень быстро. Если добавить пять или более параметров и нам понадобится менять порядок их проверки, придётся переделывать дерево с нуля. И даже если гейм-дизайнер решит изменить какое-нибудь из действующих правил, может потребоваться переработка внушительной части дерева.

Utility AI

Рисунок ниже демонстрирует возможную реализацию ИИ на основе выгодности решений. Каждое действие оценивается по отдельности и выбирается то, что наберёт больше очков. Движение к врагу основано на расстоянии до него в условных единицах, пусть это будут метры. Если оружие не заряжено, 100 очков вычитается, чтобы действие в таком случае не набирало очков. Огонь по врагу получает 75 очков, когда боец стоит не далее 50 метров от врага. Если укрытие слишком далеко – дальше, чем враг, к примеру – начисляется ещё 50 очков. Если оружие не заряжено, отнимается 125 очков, таким образом действие точно не будет выполняться. Движение к укрытию получает 50 очков, если боец не в укрытии и ещё 50, когда ближайшее укрытие в пределах 50 метров. Перезарядка получает 75 очков, когда оружие не заряжено и 50, когда боец в укрытии. Если оружие заряжено, 125 очков вычитается.

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

Utility AI не требует реализации иерархических или древовидных структур для описанного ИИ. Однако, при необходимости ими можно воспользоваться. Таким образом, действиям не обязательно быть непосредственными действиями, вроде движения или перезарядки, они могут выступать активаторами последующих оценок. На самом деле, Utility AI можно использовать как поведенческое дерево и реализовать в нём первоначально представленную структуру – если возникнет желание.

В каких областях Utility AI будет полезнее всего?

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

По своему опыту могу сказать, что технология Utility AI особенно хороша, когда дело касается современных требований к искусственному интеллекту. Полный список очень длинный, но вот несколько областей, в которых Utility AI превосходно проявляет себя:

• Комплексное поведение
• Определение приоритета действия
• Обдумывание тактики
• Поведение на основе поставленных целей
• Стратегическое планирование
• Групповое поведение
• Динамические, контекстно-зависимые диалоги
• Определение первостепенной цели для атаки
• Желания
• Эмоции
• Симуляция человеческого поведения

Каковы ограничения Utility AI?

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

Заключение

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

Автор Якоб Расмуссен(Jakob Rasmussen) руководитель Apex Game Tools – Are Behavior Trees a Thing of the Past?