HTN ( Hierarchy Task Network )

"HTN" 은 Hierarchy Task Network 의 약어로 "HTN Planner" 는 현재 상황에서 가장 적절한 Decision 을 하기 위한 계획을 수립합니다. HTN 은 수 많은 TASK 로 구성되어 있으며 "HTN Planner" 는 복수 개의 Task 에서 가장 적절한 Task 들을 선택하여 계획 ( plan ) 을 세웁니다.

 

이는 Planning 방식으로 많이 알려진 G.O.A.P 과 비슷하지만 차이점이 있습니다.

용어

HTN 은 아래와 같은 추상화 된 개념을 가지고 있습니다.

• Plan : Task 들의 집합으로 목적을 달성하기 위한 작은 작업들의 집합입니다
• Domain : 복수 개의 선언된 Task 들의 집합입니다. Plan 은 Domain 의 Task 로 구성됩니다
• WorldState : World ( Game ) 의 관심 있는 상태를 추상화 합니다. Game 에서 접근하는 State 를 직접 가져올 수 없고 중간의 추상화 과정을 거쳐 상태를 확인할 수 있습니다. 이는 복잡한 Game World 를 쉽게 풀어내기 위한 트릭 입니다. 모든 World State 는 기록될 필요가 없습니다. Plan ( Task ) 가 관심 있는 요소만 관리합니다. 그리고 World State 는 Game 의 상태를 반영해야 합니다. 추상화 된 상태를 업데이트 하는 수단으로 Task 의 결과와 Sensor ( 관찰자 ) 를 통하여 달성 가능합니다
• Task : 가장 작은 단위의 목적을 달성하는 수단 입니다. 성질에 따라 Primitive, Compound 로 나뉩니다.
  • Primitive Task : 단일 결과를 생성하는 Task
    • Operator : World 에 영향을 주는 작업 ( job ) 을 의미합니다. 예로 애니메이션을 재생, 액터의 이동을 수행하는 단위로 HTN 이 World 에 영향을 줄 수 있는 유일한 수단 입니다
    • Effects ( 선택 ) : World State 를 변경합니다. Operator 로 인한 World 의 변경은 World State 에 반영될 수 있지만 Planning 은 simulation 을 하는 과정이므로 직접적인 World 를 변경하지 못합니다. 이를 대체하기 위해 가상의 World ( world state ) 를 두고 이를 업데이트 하여 Planing 에 영향을 전파합니다
    • Conditions ( 선택 ) : Task 가 수행되기 위한 조건을 의미합니다. 주로 World State 값을 검사합니다.
  • Compound Task :  if-else 와 같은 선택적인 결과를 생성하는 Task
    • Method : Tasks ( SubTask ) 를 수행하기 위한 조건을 의미합니다
    • Tasks : Method ( 조건 ) 을 만족하는 경우 수행할 Task 들의 집합 입니다

개념적으로 HTN 이 되기 위해서는 SubTask 를 포함해야 합니다. 

 

기능

• Search  ( Planning ) : DFS ( depth first search ) 를 사용합니다. Tree cull ( 가지치기 ) 을 통해 탐색 순회 비용을 줄이는 것이 핵심 입니다. GOAP 은 cost 를 사용하여 최적의 plan 을 수립하지만, HTN 에서는 ordering 를 통해 plang 을 수립하고 있습니다. Compound Task 의 Method Cost ( utility ) 를 사용하지 않아 예상하지 못한 동작을 방지하고 의도한 결과를 달성하기 쉽습니다.
• Decomposion : Method 를 사용하여 가장 적합한 task 들의 조합을 선택할 수 있습니다
• Record & Restore : Current Task 가 유효하지 않은 경우 back ( restore ) 과정이 필요합니다. Planning 과정에서 접근하는 정보는 World State 로 제한됩니다. 이러한 특성 덕에 World State 의 사본을 두어 손쉽게 Simulation 을 반복할 수 있습니다
• World State Update & Re-Plan : World State 가 변경되는 경우는 두 가지가 있습니다.
  Planning 과정에서 Effect 에 의한 변경과 Planing 이후 Task 수행 과정에서 변경된 World State 로 인한 예측이 실패할 수 있습니다 ( 먼 거리의 이동 과정에서 World 상태가 변경될 수 있습니다 )
  변경된 World State 를 반영하여 새로운 Planning 이 가능해야 합니다 ( 즉각적인 변화에 반응 )

Planning 은 PrimitiveTask 의 조합을 찾는 과정이다

Reference

• https://www.gameaipro.com/GameAIPro/GameAIPro_Chapter12_Exploring_HTN_Planners_through_Example.pdf