계층적 태스크 네트워크 플래닝 (Hierarchical Task Network Planning)

1. 개요

계층적 태스크 네트워크(Hierarchical Task Network, HTN) 플래닝은 추상적 태스크를 구체적 행동으로 단계적으로 분해(decomposition)하는 계층적 계획 방식이다. 도메인 전문가의 분해 지식을 활용하여 탐색 공간을 효과적으로 축소하며, 로봇 공학에서 특히 유용한 계획 패러다임이다.

2. HTN의 형식적 정의

2.1 태스크의 유형

2.2 메서드 (Method)

메서드 m은 복합 태스크 t를 하위 태스크의 시퀀스로 분해하는 규칙이다.

m = \langle t, \text{pre}(m), \text{subtasks}(m) \rangle

• t: 분해 대상 복합 태스크
• \text{pre}(m): 메서드 적용의 전제 조건
• \text{subtasks}(m): 하위 태스크의 순서 있는 집합

HTN 계획 문제

\mathcal{P}_{\text{HTN}} = \langle D, s_0, T_0 \rangle

• D: HTN 도메인 (행동 + 메서드)
• s_0: 초기 상태
• T_0: 초기 태스크 네트워크 (달성할 최상위 태스크)

3. 분해 과정

deliver(robot, box, room_C)          ← 복합 태스크
├── fetch(robot, box)                ← 복합 태스크
│   ├── move(robot, dock, room_B)    ← 원시 태스크
│   └── pick(robot, box, room_B)     ← 원시 태스크
└── transport(robot, box, room_C)    ← 복합 태스크
    ├── move(robot, room_B, room_C)  ← 원시 태스크
    └── place(robot, box, room_C)    ← 원시 태스크

4. HTN 알고리즘

4.1 SHOP (Simple Hierarchical Ordered Planner)

현재 상태를 유지하면서 태스크를 순차적으로 분해하는 전방 분해(forward decomposition) 알고리즘이다.

function HTN-Plan(s, T):
    if T is empty: return []
    t = first(T)
    if t is primitive:
        if pre(t) ⊆ s:
            s' = γ(s, t)
            plan = HTN-Plan(s', rest(T))
            return [t] + plan
    if t is compound:
        for each method m applicable to t:
            plan = HTN-Plan(s, subtasks(m) + rest(T))
            if plan ≠ FAILURE:
                return plan
    return FAILURE

4.2 SHOP2

SHOP의 확장으로, 부분 순서 태스크, 조건부 분기, 외부 호출 등을 지원한다.

5. 고전적 플래닝과의 비교

6. 로봇 공학에서의 HTN

HTN은 로봇 행동의 계층적 구조를 자연스럽게 표현한다. “배달 임무“를 “이동+집기+이동+놓기“로 분해하는 것은 로봇 엔지니어의 사고방식과 일치한다. 행동 트리의 서브트리 구조와도 유사하여, HTN 계획을 행동 트리로 변환하는 것이 자연스럽다.

7. 참고 문헌

• Nau, D., et al. (2003). “SHOP2: An HTN Planning System.” JAIR, 20, 379-404.
• Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.