Введение в планировщики иерархических сетей задач (HTN) на примере. Часть 2

Поиск плана 

В прошлой части мы остановились на том, что сформировали из составных и примитивных задач функциональную область (domain), которая представляет всю иерархию задач нашего NPC. Объединив ее с состоянием мира (world state), мы можем перейти к рабочей лошадке нашей HTN — планировщику (planner). Есть три условия, которые заставляют планировщик искать новый план: NPC завершает или проваливает текущий план, у NPC нет плана, или какой-нибудь сенсор меняет состояние мира NPC. Если произойдет любая из этих ситуаций, планировщик попытается сгенерировать план. Для этого планировщик начинает с корневой составной задачи, представляющей область задач, для которой мы пытаемся составить план. В нашем предыдущем примере такой корневой задачей будет задача BeTrunkThumper. Эта корневая задача помещается в стек TasksToProcess. Далее планировщик создает копию состояния мира и будет изменять это рабочее состояние мира (working world state), чтобы "смоделировать" то, что произойдет при выполнении задач.

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

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

WorkingWS = CurrentWorldState 
TasksToProcess.Push(RootTask) 
while TasksToProcess.NotEmpty 
{ 
  CurrentTask = TasksToProcess.Pop() 
  if CurrentTask.Type == CompoundTask 
  { 
    SatisfiedMethod = CurrentTask.FindSatisfiedMethod(WorkingWS) 
    if SatisfiedMethod != null 
    { 
      RecordDecompositionOfTask(CurrentTask, FinalPlan, DecompHistory)
      TasksToProcess.InsertTop(SatisfiedMethod.SubTasks) 
    } 
  else 
    { 
      RestoreToLastDecomposedTask() 
    } 
    }
else// Примитивная задача
  { 
    if PrimitiveConditionMet(CurrentTask) 
      { 
        WorkingWS.ApplyEffects(CurrentTask.Effects)
        FinalPlan.PushBack(CurrentTask) 
      } 
    else 
      { 
        RestoreToLastDecomposedTask() 
      } 
  } 
} 

В функциях RecordDepositionOfTask и RestoreToLastDecomposedTask происходит некоторая магия, которую мы рассмотрим поподробнее. Функция RecordDepositionOfTask записывает состояние планировщика в стек DecompHistory. Сюда входят контейнеры TasksToProcess и FinalPlan, а также метод, выбранный для декомпозиции, и составная задача которой он принадлежит. Когда составная задача не может быть декомпозирована или когда условия примитива не выполняются, планировщик может вернуться назад с помощью функция RestoreToLastDecomposedTask.

Как вы уже поняли, чтобы найти правильный план, планировщик использует поиск в глубину. Это означает, что вам, возможно, придется исследовать всю функциональную область, чтобы найти корректный план. Однако важно помнить, что вы обходите иерархию задач. Эта иерархия позволяет планировщику отбрасывать большие участки сети благодаря методам составных задач. Поскольку мы не используем эвристику или стоимость, как в случае с алгоритмами поиска A* и Дейкстры, мы можем полностью пренебречь сортировкой. Эти возможности позволили HTN-планировщику в Transformers: Fall of Cybertron быть значительно быстрее, чем наша GOAP-система (целеориентированный планировщик), использованная в Transformers: War for Cybertron [HighMoon 10].

Теперь, когда мы разобрались с планировщиком, мы можем немного расширить наш пример и посмотреть, как будет разворачиваться модифицированная версия функциональной области TrunkThumper (рис. 2). Корневой задачей этого домена по-прежнему является BeTrunkThumper, но DoTrunkSlam теперь является составной задачей. У DoTrunkSlam есть два метода, каждый из которых выполняет свою версию удара стволом. Условия метода для обеих составных задач были опущены, чтобы сделать пример немного проще. Под функциональной областью вы можете увидеть итерации планировщика, идущие сверху вниз. На каждой итерации обрабатывается самая левая задача в стеке TasksToProcess.  

Выполнение плана  

В выполнении HTN-плана нет ничего сложного. Исполнитель плана (plan runner) NPC попытается последовательно выполнить операторы каждой примитивной задачи. По мере успешного выполнения каждой задачи планировщик применяет эффекты задачи к состоянию мира. Если задача не выполняется по какой-то причине, связанной с выполняемым оператором, план также терпит неудачу и требует перепланирования. 

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

Использование рекурсии для большей выразительности 

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

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

Compound Task [BeTrunkThumper] 
  Method [ WsCanSeeEnemy == true] 
    Subtasks [AttackEnemy()]// используем новую составную задачу 
  Method [true] 
    Subtasks [ChooseBridgeToCheck(), NavigateToBridge(), CheckBridge()] 
Compound Task [AttackEnemy]// новая составная задача 
  Method [WsTrunkHealth > 0] 
    Subtasks [NavigateToEnemy(), DoTrunkSlam()] 
  Method [true] 
    Subtasks [FindTrunk(), NavigateToTrunk(), UprootTrunk(), AttackEnemy()] 
Primitive Task [DoTrunkSlam] 
  Operator [DoTrunkSlamOperator] 
    Effects [WsTrunkHealth += -1] 
Primitive Task [UprootTrunk] 
  Operator [UprootTrunkOperator] 
    Effects [WsTrunkHealth = 3] 
Primitive Task [NavigateToTrunk] 
  Operator [NavigateToOperator(FoundTrunk)] 
    Effects [WsLocation = FoundTrunk] 

Когда наш тролль видит врага, он атакует, как и раньше, только теперь это поведение обернуто в новую составную задачу под названием AttackEnemy. Высокоприоритетный метод этой задачи выполняет перемещение и удар, как и в оригинальном домене, но теперь с условием, что у ствола есть шкала здоровья. Изменение задачи DoTrunkSlam будет уменьшать здоровье ствола при каждой успешной атаке. Это позволит планировщику перейти к методу с более низким приоритетом, если ему нужно будет учесть сломанный ствол дерева. 

Второй метод AttackEnemy предназначен для добывания нового ствола дерева. Сначала он выбирает новое дерево, перемещается к нему и выкорчевывает его, после чего может атаковать противника (AttackEnemy). Вот тут-то и возникает рекурсия. Когда планировщик снова приступает к декомпозиции задачи AttackEnemy, он может снова рассмотреть все методы. Если бы здоровье ствола дерева по-прежнему было нулевым, это привело бы к бесконечному циклу в планировщике. Но эффект новой задачи UprootTrunk устанавливает WsTrunkHealth обратно в три, что позволяет нам сформировать план FindTrunk → NavigateToTrunk → UprootTrunk → NavigateToEnemy → DoTrunkSlam. Эта новая функциональная область позволяет нам повторно использовать методы, уже имеющиеся в ней, чтобы вернуть тролля к атаке. 

Планирование с учетом изменений состояния мира, не вызванных задачами NPC

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

Compound Task [BeTrunkThumper] 
  Method [ WsCanSeeEnemy == true] 
    Subtasks [AttackEnemy()] 
  Method [ WsHasSeenEnemyRecently == true]//New method 
    Subtasks [NavToLastEnemyLoc(), RegainLOSRoar()] 
  Method [true] 
    Subtasks [ChooseBridgeToCheck(), NavigateToBridge(), CheckBridge()] 
Primitive Task [NavToLastEnemyLoc] 
  Operator [NavigateToOperator(LastEnemyLocation)] 
    Effects [WsLocation = LastEnemyLocation] 
Primitive Task [RegainLOSRoar] 
  Preconditions[WsCanSeeEnemy == true] 
  Operator [RegainLOSRoar()]

Если TrunkThumper не видит врага, то планировщик переходит к новому методу, основанному на свойстве состояния мира WsHasSeenEnemyRecently. Задачи этого метода будут перемещаться к последнему месту, где был замечен враг, и делать большой анимированный "рев", если он снова увидит врага. Проблема здесь в том, что задача RegainLOSRoar имеет предварительное условие, чтобы WsCanSeeEnemy было истинным. Это состояние мира обрабатывается датчиком зрения тролля. Когда планировщик поместит задачу RegainLOSRoar в финальный список задач, он провалит проверку предварительного условия, потому что в функциональной области нет ничего, что представляло бы ожидаемое состояние мира по завершении навигации. 

Чтобы решить эту проблему, мы должны ввести понятие ожидаемых эффектов (expected effects). Ожидаемые эффекты — это эффекты, которые применяются к состоянию мира только во время планирования и проверки плана. Идея заключается в том, что вы можете выразить изменения в состоянии мира, которые должны произойти на основе выполняемых задач. Это позволяет планировщику продолжать планирование на более отдаленную перспективу, основываясь на том, что, по его мнению, будет выполнено на этом пути. Помните, что ключевое преимущество планировщиков в принятии решений заключается в том, что они могут рассуждать о будущем, что помогает им принимать лучшие решения о том, что делать дальше. Чтобы учесть это, мы можем изменить NavToLastEnemyLoc на: 

Primitive Task [NavToLastEnemyLoc] 
  Operator [NavigateToOperator(LastEnemyLocation)] 
    Effects [WsLocation = LastEnemyLocation] 
    ExpectedEffects [WsCanSeeEnemy = true] 

Теперь, когда эта задача будет вычеркнута из списка декомпозиции, состояние рабочего мира обновится с ожидаемым эффектом, и задача RegainLOSRoar сможет продолжить добавление задач в цепочку. Это поведение можно было бы реализовать и по-другому, но ожидаемые эффекты хорошо зарекомендовали себя во время разработки Transformers: Fall of Cybertron. Это простой способ добавить еще немного выразительности в HTN-систему.

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

Всем актуальным GameDev инструментам и практикам можно научиться на онлайн-курсах OTUS под руководством экспертов сферы.