397.38 계층적 작업 네트워크(HTN) 계획의 원리

자율 로봇 시스템의 임무 계획에서는 복잡한 고수준 목표를 실행 가능한 저수준 행동의 시퀀스로 변환하는 과정이 필수적이다. 계층적 작업 네트워크(Hierarchical Task Network, HTN) 계획은 이러한 계층적 분해(hierarchical decomposition) 과정을 체계적으로 형식화한 계획 패러다임으로서, 인간 전문가의 문제 해결 방식과 유사한 하향식(top-down) 문제 분해 전략을 구현한다.

1. HTN 계획의 기본 개념

HTN 계획은 고전적 계획(classical planning)과 근본적으로 다른 접근 방식을 취한다. 고전적 계획이 초기 상태에서 목표 상태까지의 행동 시퀀스를 직접 탐색하는 반면, HTN 계획은 추상적인 **복합 과업(compound task)**을 점진적으로 분해하여 **원시 과업(primitive task)**의 네트워크로 변환하는 과정을 통해 계획을 수립한다.

1.1 과업의 분류

HTN에서 과업은 두 가지 유형으로 구분된다.

원시 과업(Primitive Task): 로봇이 직접 실행할 수 있는 기본 행동에 해당한다. 원시 과업 $t_p$ 는 고전적 계획의 연산자(operator)와 동일하게 전제 조건(precondition)과 효과(effect)를 가진다. 예를 들어, 이동(위치A, 위치B), 물체_집기(물체1), 센서_스캔(영역3) 등이 원시 과업에 해당한다.

복합 과업(Compound Task): 직접 실행할 수 없으며, 하나 이상의 **방법(method)**을 통해 더 작은 과업들의 네트워크로 분해되어야 하는 추상적 과업이다. 예를 들어, 물품_배달(물품1, 목적지B)는 경로_계획, 물품_적재, 이동, 물품_하역 등의 하위 과업으로 분해될 수 있다.

2. HTN 계획의 형식적 정의

HTN 계획 문제는 다음과 같은 튜플로 정의된다.

$\mathcal{P} = (s_0, w_0, D)$

여기서 각 구성 요소는 다음과 같다.

$s_0$ : 초기 상태로서, 세계의 현재 상태를 기술하는 명제(proposition)들의 집합이다.
$w_0$ : 초기 작업 네트워크(initial task network)로서, 달성해야 할 과업들과 그 순서 제약을 포함한다.
$D$ : 계획 도메인으로서, 연산자(operator) 집합과 방법(method) 집합으로 구성된다.

2.1 계획 도메인의 구조

계획 도메인 $D = (O, M)$ 은 다음 두 요소로 구성된다.

연산자(Operator) $o = (\text{name}(o), \text{pre}(o), \text{eff}(o))$ 는 다음을 포함한다.

$\text{name}(o)$ : 연산자의 이름과 매개변수
$\text{pre}(o)$ : 전제 조건(precondition), 즉 연산자가 적용되기 위해 현재 상태에서 참이어야 하는 명제들의 집합
$\text{eff}(o)$ : 효과(effect), 즉 연산자 적용 후 상태에 추가되거나 제거되는 명제들

방법(Method) $m = (\text{name}(m), \text{task}(m), \text{pre}(m), \text{subtasks}(m), \text{constr}(m))$ 는 다음을 포함한다.

$\text{name}(m)$ : 방법의 이름과 매개변수
$\text{task}(m)$ : 이 방법이 분해하는 복합 과업
$\text{pre}(m)$ : 이 방법이 적용되기 위한 전제 조건
$\text{subtasks}(m)$ : 분해 결과로 생성되는 하위 과업들의 집합
$\text{constr}(m)$ : 하위 과업들 간의 순서 제약(ordering constraints)

2.2 작업 네트워크(Task Network)

작업 네트워크는 과업들의 집합과 그들 사이의 순서 제약으로 구성되는 방향 비순환 그래프(Directed Acyclic Graph, DAG)이다.

$w = (T, \prec, \alpha)$

여기서 $T$ 는 과업 식별자의 집합, $\prec$ 는 $T$ 위의 부분 순서(partial order), $\alpha: T \rightarrow \text{TaskNames}$ 는 각 식별자를 과업 이름에 대응시키는 함수이다.

순서 제약 $t_i \prec t_j$ 는 “과업 $t_i$ 가 과업 $t_j$ 보다 먼저 실행되어야 한다“는 의미를 나타낸다. HTN에서는 전순서(total-order) 방법과 부분순서(partial-order) 방법의 두 가지 변형이 존재한다.

전순서 HTN(Totally-Ordered HTN): 모든 하위 과업 쌍에 대해 순서가 정의되어 있다. 즉, 임의의 두 과업 $t_i, t_j \in T$ 에 대해 $t_i \prec t_j$ 또는 $t_j \prec t_i$ 가 성립한다.
부분순서 HTN(Partially-Ordered HTN): 일부 과업 쌍에 대해서만 순서가 정의되어 있으며, 순서가 정의되지 않은 과업 쌍은 병렬 실행이 가능하다.

3. HTN 계획 알고리즘

HTN 계획의 표준 알고리즘은 작업 네트워크 $w$ 에서 복합 과업을 반복적으로 분해하여 모든 과업이 원시 과업으로 변환된 계획을 생성하는 과정으로 진행된다.

3.1 전순서 분해 알고리즘

전순서 HTN 계획의 기본 알고리즘은 다음과 같다.

알고리즘: Total-Order HTN Planning
입력: 현재 상태 s, 작업 리스트 w = [t₁, t₂, ..., tₙ]
출력: 행동 시퀀스 π 또는 실패(failure)

1. if w = [] then return []  // 모든 과업 처리 완료
2. t₁ ← w의 첫 번째 과업
3. if t₁이 원시 과업이면:
4.     if pre(t₁) ⊆ s then
5.         s' ← γ(s, t₁)  // 상태 전이
6.         π' ← TotalOrderHTN(s', [t₂, ..., tₙ])
7.         if π' ≠ failure then return [t₁] ∘ π'
8.     end if
9.     return failure
10. if t₁이 복합 과업이면:
11.     for each 적용 가능한 방법 m (task(m) = t₁ 이고 pre(m) ⊆ s) do
12.         w' ← subtasks(m) ∘ [t₂, ..., tₙ]
13.         π ← TotalOrderHTN(s, w')
14.         if π ≠ failure then return π
15.     end for
16.     return failure

여기서 $\gamma(s, t_1)$ 은 상태 $s$ 에서 과업 $t_1$ 을 실행한 후의 결과 상태를 나타내며, $\circ$ 는 리스트 연결(concatenation) 연산이다.

3.2 부분순서 분해 알고리즘

부분순서 HTN 계획에서는 순서 제약이 없는 과업들 중에서 하나를 비결정론적으로 선택하여 처리한다. 이 접근 방식은 더 넓은 해 공간을 탐색할 수 있으나, 탐색 공간 또한 확대되는 trade-off가 존재한다.

4. HTN 계획의 표현력과 계산 복잡도

4.1 고전적 계획과의 표현력 비교

HTN 계획과 고전적 계획의 표현력 관계는 다음과 같이 정리된다.

정리 (Erol et al., 1996): 부분순서 HTN 계획은 PSPACE-완전(PSPACE-complete)이며, 적절한 제한 하에서 고전적 계획과 동일한 표현력을 지닌다. 그러나 재귀적 방법(recursive methods)을 허용하는 일반적인 HTN 계획은 반결정 가능(semidecidable)하며, 고전적 계획보다 엄밀하게 더 높은 표현력을 가진다.

이는 HTN 계획이 단순히 효율적인 탐색 기법이 아니라, 고전적 계획으로 해결할 수 없는 문제 클래스도 표현할 수 있음을 의미한다.

4.2 도메인 지식에 의한 탐색 공간 축소

고전적 계획은 상태 공간에서의 맹목적 탐색(blind search)에 의존하는 반면, HTN 계획에서는 방법(method)을 통해 도메인 전문가의 지식이 계획 과정에 직접 부호화(encoded)된다. 이로 인해 실질적인 탐색 공간이 대폭 축소되며, 대규모 계획 문제에서도 효율적인 계획 생성이 가능해진다.

상태 공간 $|S|$ 와 행동 공간 $|A|$ 가 주어졌을 때, 고전적 계획의 탐색 공간은 최악의 경우 $O(|A|^n)$ ( $n$ 은 계획 길이)으로 증가하지만, HTN 계획에서는 방법의 분기 계수(branching factor) $b_m$ 에 의해 탐색 공간이 $O(b_m^d)$ ( $d$ 는 분해 깊이)로 제한된다. 일반적으로 $b_m \ll |A|$ 이므로 탐색 효율이 크게 향상된다.

5. 주요 HTN 계획기(Planner)

5.1 SHOP 및 SHOP2

**SHOP(Simple Hierarchical Ordered Planner)**와 그 후속 시스템인 SHOP2는 전순서 HTN 계획기의 대표적인 구현체이다. SHOP의 핵심 특징은 전방 분해(forward decomposition) 방식을 채택하여, 과업 분해 시점에 현재 상태 정보를 활용할 수 있다는 점이다. 이를 통해 분해 과정에서 상태 의존적(state-dependent) 방법 선택이 가능하며, 이는 계획의 품질 향상에 기여한다.

SHOP2는 다음과 같은 주요 기능을 제공한다.

기능	설명
수치 계산	전제 조건에서 산술 연산 지원
축 기반 변수 바인딩	상태로부터 변수를 바인딩하는 축(axiom) 지원
외부 함수 호출	Lisp 함수를 전제 조건과 효과에서 호출
분기 제거	정렬된 방법 목록을 통한 결정론적 분해
다중 해 생성	모든 가능한 계획을 열거하는 기능

5.2 UMCP (Universal Method Composition Planner)

UMCP는 부분순서 HTN 계획을 지원하는 계획기로서, 보다 일반적인 HTN 형식론을 다룰 수 있다. UMCP에서는 과업 간의 순서 제약이 부분 순서로 주어지며, 상호 배타적 과업(interleaving tasks)의 스케줄링이 가능하다.

5.3 PANDA (Planning and Acting in a Network Decomposition Architecture)

PANDA 프레임워크는 HTN 계획의 형식적 기반을 강화하고, 계획 검증(plan verification)과 계획 인식(plan recognition)까지 포괄하는 종합적인 HTN 계획 생태계를 제공한다. PANDA에서는 HTN 문제의 결정 가능성(decidability)과 복잡도 분류를 체계적으로 분석하여, 효율적인 계획 알고리즘의 설계에 이론적 기반을 제공한다.

6. 로봇 임무 계획에서의 HTN 적용

6.1 서비스 로봇의 가사 임무 분해

서비스 로봇이 “거실을 청소하라“는 고수준 임무를 수행할 때, HTN 기반 분해는 다음과 같이 진행된다.

거실_청소(거실)
  → 방법: 체계적_청소
    ├── 장애물_수거(거실)
    │     ├── 물체_탐지(거실)
    │     ├── 물체_집기(물체1)
    │     └── 물체_정리(물체1, 수납함)
    ├── 바닥_청소(거실)
    │     ├── 진공_청소(거실_영역1)
    │     ├── 진공_청소(거실_영역2)
    │     └── 걸레질(거실)
    └── 완료_보고(거실)

이 과정에서 각 방법의 전제 조건은 현재 환경 상태(예: 장애물 존재 여부, 바닥 재질)에 따라 평가되며, 적합한 분해 방법이 선택된다.

6.2 물류 로봇의 복합 임무 계획

물류 환경에서는 “입고된 물품을 지정 위치에 배치하라“와 같은 복합 임무를 다수의 로봇이 협력하여 수행해야 한다. HTN 기반 계획에서는 이러한 복합 임무를 개별 로봇의 원시 행동으로 분해하면서, 동시에 자원 제약(예: 통로 용량, 충전 스테이션 가용성)과 시간 제약을 반영할 수 있다.

6.3 군사 로봇의 다단계 작전 계획

군사 작전 환경에서는 “목표 지역 정찰“이라는 고수준 임무가 “경로 선정 → 은폐 이동 → 관측 지점 확보 → 감시 수행 → 정보 전송 → 복귀“와 같은 다단계 과업 네트워크로 분해된다. HTN의 방법을 통해 지형 조건, 위협 수준, 통신 가용성 등의 상황에 따른 대안적 분해 전략을 사전에 정의할 수 있다.

7. HTN 계획의 장점과 한계

7.1 장점

도메인 지식의 체계적 활용: 방법(method)을 통해 전문가 지식이 계획 과정에 직접 반영되므로, 탐색 효율이 높고 생성되는 계획의 품질이 우수하다.
자연스러운 계층 구조: 로봇 임무의 계층적 특성과 자연스럽게 부합하며, 다양한 추상화 수준에서의 추론이 가능하다.
확장성: 도메인 지식에 의한 탐색 공간 축소로 인해, 대규모 계획 문제에서도 효율적으로 동작한다.
재사용성: 한번 정의된 방법은 다양한 맥락에서 재사용될 수 있어, 도메인 모델링의 효율성이 높다.

7.2 한계

방법 정의의 부담: 효과적인 HTN 계획을 위해서는 도메인 전문가가 방법을 사전에 정의해야 하며, 이 과정에 상당한 노력이 소요된다.
완전성(completeness) 미보장: 방법이 불충분하게 정의된 경우, 해가 존재하더라도 계획기가 이를 발견하지 못할 수 있다.
동적 환경 대응의 어려움: 사전 정의된 방법이 예상치 못한 환경 변화에 대응하지 못할 경우, 재계획(replanning) 메커니즘이 필요하다.
최적성 미보장: HTN 계획은 일반적으로 실행 가능한(feasible) 계획을 생성하지만, 그 계획이 최적(optimal)임을 보장하지는 않는다.

8. 요약

계층적 작업 네트워크(HTN) 계획은 복합 과업을 방법(method)을 통해 계층적으로 분해함으로써 임무 계획을 수립하는 강력한 패러다임이다. 고전적 계획의 맹목적 탐색과 달리, 도메인 전문가의 지식을 방법으로 부호화하여 탐색 공간을 대폭 축소한다. SHOP2, PANDA 등의 계획기가 대표적인 구현체이며, 서비스 로봇, 물류 로봇, 군사 로봇 등 다양한 영역에서 복잡한 임무의 계층적 분해와 실행에 활용되고 있다. HTN 계획의 표현력은 재귀적 방법 허용 시 고전적 계획을 엄밀하게 초과하며, 이는 로봇 임무 계획의 표현적 유연성을 보장하는 핵심 기반이 된다.

9. 참고 문헌

Erol, K., Hendler, J., & Nau, D. S. (1996). “Complexity results for HTN planning.” Annals of Mathematics and Artificial Intelligence, 18(1), pp. 69–93.
Nau, D. S., Au, T. C., Ilghami, O., Kuter, U., Murdock, J. W., Wu, D., & Yaman, F. (2003). “SHOP2: An HTN planning system.” Journal of Artificial Intelligence Research, 20, pp. 379–404.
Bercher, P., Alford, R., & Höller, D. (2019). “A survey on hierarchical planning – One abstract idea, many concrete realizations.” Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 6267–6275.
Georgievski, I., & Aiello, M. (2015). “HTN planning: Overview, comparison, and beyond.” Artificial Intelligence, 222, pp. 124–156.
Höller, D., Behnke, G., Bercher, P., Biundo, S., Fiorino, H., Pellier, D., & Alford, R. (2020). “HDDL: An extension to PDDL for expressing Hierarchical Planning Problems.” Proceedings of the AAAI Conference on Artificial Intelligence, 34(06), pp. 9883–9891.

v1.0 | 로봇공학 서적 – Volume 9, Part 53, Chapter 397, Section 38