[Перевод] Введение в планировщики иерархических сетей задач (HTN) на примере. Часть 113.02.2024 22:00

Введение 

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

Одна из наиболее распространенных задач, с которой мы сталкиваемся при разработке ИИ, — это выбор поведения. Существует множество решений этой задачи, таких как конечные автоматы, деревья поведения, выбор на основе полезности, нейронные сети и планировщики. Цель этой статьи — изучить нюансы одного из этих решений — планировщика на основе иерархических сетей задач (hierarchical task networks — HTN) на реальных примерах, с которыми можно столкнуться в процессе разработки.

Архитектуры планирования, такие как HTN, принимают на вход задачу и предоставляют на выходе серию шагов, которые ее решают. В терминах иерархических сетей задач серия шагов называется планом. HTN-планировщики отличаются от других планировщиков тем, что позволяют представить поставленную задачу как задание очень высокого уровня, которое в процессе планирования рекурсивно разбивается на более мелкие задания. Когда этот процесс завершается, мы получаем серию атомарных заданий, которые представляют собой план. Разбиение высокоуровневых заданий на более мелкие — это очень естественный способ решения многих реальных задач. В нашем случае все заключается в том, чтобы просто «понять, что делать». Благодаря высокой степени модульности и быстрому выполнению HTN снискали популярность в качестве решения для выбора поведения. Тем из вас, кто знаком с деревьями поведения, эти преимущества могут показаться знакомыми. Однако, в отличие от деревьев поведения, HTN-планировщики могут рассуждать о последствиях возможных действий. Эта способность рассуждать о будущем позволяет HTN-планировщикам быть невероятно выразительными в том, как они описывают поведение. 

Существует множество различных систем, используемых для HTN-планирования [Erol 95]. Система, которую мы будем рассматривать, берет за основу планировщик с прямой линейной декомпозицией (total-order forward decomposition). Эта система использовалась в Transformers: Fall of Cybertron [HighMoon 12], и мы с вами рассмотрим на упрощенном примере некоторые проблемы, с которыми мы столкнулись, и преимущества, которые мы получили в ходе разработки. 

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

Составные элементы HTN 

Прежде чем создавать поведение нашего TrunkThumper«а, нам нужно рассмотреть основные элементы иерархических сетей задач, чтобы мы могли получить представление о том, как все это работает. У NPC, в нашем случае у TrunkThumper, есть планировщик (planner), который использует функциональную область (domain)и состояние мира (world state) для создания последовательности заданий, называемой планом (plan). Этот план будет выполняться исполнителем плана (plan runner)TrunkThumper«а. Состояние мира обновляется сенсорами NPC и успешно завершенными заданиями, которые выполняет планировщик. Схема системы приведена на рисунке 1.

Рисунок 1: Общее представление HTN-системы

Состояние мира

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

enum EHtnWorldStateProperties 
{ 
  WsEnemyRange, 
  WsHealth, 
  WsIsTired, 
  … 
}
enum EEnemyRange 
{ 
  MeleeRange, 
  ViewRange, 
  OutOfRange, 
  … 
} 
vector CurrentWorldState; 
EEnemyRange currentRange = CurrentWorldState[WsEnemyRange];
CurrentWorldState[WsEnemyRange] = MeleeRange;

Как видно из псевдокода, состояние мира может быть просто массивом или вектором, индексируемым перечислением (enum), таким как EhtnWorldStateProperties. Каждая запись в состоянии мира может иметь свой собственный набор значений. В случае WsIsTired байт может представлять логические значения 0 и 1. Для WsEnemyRange используются значения из перечисления EEnemyRange. Важно отметить, что состояние мира должно представлять только то, что необходимо HTN для принятия решений. Именно поэтому WsEnemyRange представлен абстрактными значениями, а не реальным расстоянием. Цель состояния мира не в том, чтобы представлять все возможные состояния всех возможных объектов в игре. Оно должно представлять только пространство предметной области, которое необходимо нашему планировщику для принятия решений. Для нашего примера это, конечно, означает, что оно должно представлять только то, что для принятия решений нужно TrunkThumper«у. 

Сенсоры 

Если вы помните, HTN выводит план или последовательность заданий. Эти задания будут влиять на состояние мира по мере их выполнения. Однако есть и внешние воздействия, такие как игрок или другие NPC, которые также влияют на состояние мира. Например, и враг, и тролль одновременно могут влиять на свойство состояния мира WsEnemyRange. Задания, выполняемые троллем, могут обновить это свойство, если они переместят тролля. Однако в HTN-планировщике нет ничего для обработки изменений, вызванных перемещением врага. 

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

Примитивные задачи 

Как мы уже говорили, иерархическая сеть задач состоит из заданий. Существует два типа заданий, которые используются для построения HTN, называемые составными задачами (compound tasks) и примитивными задачами (primitive tasks). Примитивные задачи представляют собой одно действие, которое может выполнить наш NPC. Для нашего TrunkThumper«а выкорчевывание дерева или удар стволом — это примитивные задачи. Набор примитивных задач — это план, который мы в конечном итоге получаем из HTN. Примитивные задачи состоят из оператора (operator)и наборов эффектов (effects)и условий (conditions). 

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

Эффекты примитивной задачи описывают, как успешное выполнение задачи повлияет на состояние мира NPC. Например, задача DoTrunkSlam заставит троля выполнить атаку стволом дерева в ближнем бою и приводит к тому, что тролль устает. Эффекты DoTrunkSlam — это способ, которым мы описываем этот результат. Это позволяет HTN рассуждать о «будущем», как было сказано ранее. Поскольку эффект «усталости» учтен и описан, наш TrunkThumper может принять лучшее решение о том, что делать после DoTrunkSlam и стоит ли вообще это делать.

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

В качестве примера рассмотрим две задачи: SprintToEnemy и WalkToNextBridge. Обе эти задачи используют оператор MoveTo, но изменяют состояние нашего NPC по-разному. После успешного завершения SprintToEnemy наш NPC окажется у врага и устанет, что определяется эффектами задачи. Эффекты задачи WalkToNextBridge установят местоположение NPC на мосту, и он начнет немного скучать. Как видите, мы можем использовать один и тот же оператор, но описать два разных его применения в нашей сети. Ниже приведена нотация, которую мы будем использовать для описания примитивных задач в дальнейшем, а также задачи SprintToEnemy и WalkToNextBridge в качестве примера:

Primitive Task [TaskName(term1, term2,...)]
  Preconditions [Condition1, Condition2, …]//опционально
  Operator [OperatorName(term1, term2,...)]
    Effects [WorldState op value, WorldState = value, WorldState += value]//опционально
Primitive Task [SprintToEnemy]
  Preconditions [WsHasEnemy == true]
  Operator [NavigateTo(EnemyLoc, Speed_Fast)]
    Effects [WsLocation = EnemyLoc, WsIsTired = true]
Primitive Task [WalkToNextBridge]
  Operator [NavigateTo(BridgeLoc, Speed_Slow)]
     Effects [WsLocation = BridgeLoc, WsBored += 1]

Составные задачи 

Составные задачи — это тот элемент, где HTN проявляет свою «иерархическую» природу. Вы можете представить себе составную задачу как задачу высокого уровня, которая имеет несколько способов выполнения. На примере TrunkThumper«а у него может быть задача AttackEnemy. У нашего TrunkThumper«а могут быть разные способы выполнения этой задачи. Если у него есть доступ к стволу дерева, он может подбежать к цели и использовать его как оружие ближнего боя, чтобы «ударить» своего врага. Если стволы деревьев недоступны, он может достать из земли большой валун и швырнуть его в противника. При удачном стечении обстоятельств он может использовать и множество других приемов. 

Чтобы определить, какой подход мы используем для решения составной задачи, нужно выбрать правильный метод (method). Методы состоят из набора условий и задач. Выбор метода в качестве избранного подхода к выполнению задачи происходит на основе проверки их условий на соответствие состоянию мира. Набор задач, или подзадач (subtasks), представляет собой подход метода (method«s approach). Этот набор подзадач может состоять как из примитивных задач, так и из составных. Возможность помещать составные задачи в методы других составных задач — это то, что придает HTN их иерархический характер. Вот пример нотации, которую мы будем использовать для описания составных задач в дальнейшем:

Compound Task [TaskName(term1, term2,...)]
  Method 0 [Condition1, Condition2,...]
    Subtasks [task1(term1, term2,...). task2(term1, term2,...),...]
  Method 1 [Condition1, Condition2,...]
    Subtasks [task1(term1, term2,...). task2(term1, term2,...),...]

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

Compound Task [AttackEnemy] 
  Method 0 [WsHasTreeTrunk == true] 
    Subtasks [NavigateTo(EnemyLoc). DoTrunkSlam()] 
  Method 1 [WsHasTreeTrunk == false] 
    Subtasks [LiftBoulderFromGround(). ThrowBoulderAt(EnemyLoc)]

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

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

Составление функционально области HTN

Теперь, когда мы разобрались с основными составными элементами HTN, мы можем построить простой функциональную область (domain) для нашего TrunkThumper«а, чтобы проиллюстрировать, как он работает. Функциональную область — это термин, используемый для описания всей иерархии задач. Как мы уже говорили, в зоне ответственности нашего тролля есть определенное множество мостов, которые он активно патрулирует, а также он атакует врагов с помощью большого ствола дерева. Мы начинаем с составной задачи под названием BeTrunkThumper. В этой корневой задаче заключена «главная идея» того, что значит быть TrunkThumper«ом.

Compound Task [BeTrunkThumper] 
  Method [WsCanSeeEnemy == true] 
    Subtasks [NavigateToEnemy(), DoTrunkSlam()] 
  Method [true] 
    Subtasks [ChooseBridgeToCheck(), NavigateToBridge(), CheckBridge()] 

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

Primitive Task [DoTrunkSlam] 
  Operator [AnimatedAttackOperator(TrunkSlamAnimName)] 
Primitive Task [NavigateToEnemy] 
  Operator [NavigateToOperator(EnemyLocRef)] 
    Effects [WsLocation = EnemyLocRef] 
Primitive Task [ChooseBridgeToCheck] 
  Operator [ChooseBridgeToCheckOperator] 
Primitive Task [NavigateToBridge] 
  Operator [NavigateToOperator(NextBridgeLocRef)] 
    Effects [WsLocation = NextBridgeLocRef] 
Primitive Task [CheckBridge] 
  Operator [CheckBridgeOperator(SearchAnimName)] 

Первая задача DoTrunkSlam — это пример того, как примитивная задача может описывать оператор в терминах функциональной области HTN. Здесь задача действительно выполняет оператор анимированной атаки, а имя анимации передается в качестве термина. Следующая задача NavigateToEnemy также является таким примером, но при успешном выполнении этой задачи состояние мира WsLocation устанавливается в EnemyLocRef через эффект примитивной задачи.

В следующей части мы рассмотрим поиск и выполнение плана.

Всех желающих приглашаем на открытый урок по Unity, на котором мы рассмотрим реализацию поведения игровых объектов на GOAP. Разберём алгоритм планирования и элементы, из которых состоит сама GOAP система. Записаться можно на странице онлайн-курса «Unity Game Developer. Professional».

© Habrahabr.ru