396.37 계층적 작업 네트워크(HTN) 기반 임무 분해

396.37 계층적 작업 네트워크(HTN) 기반 임무 분해

1. 서론

계층적 작업 네트워크(Hierarchical Task Network, HTN) 계획은 복합 과업(compound task)을 사전 정의된 분해 방법(decomposition method)에 따라 하위 과업으로 점진적으로 분해하여 실행 가능한 계획을 생성하는 AI 계획 패러다임이다. HTN 계획은 고전적 상태 공간 탐색(state-space search) 기반 계획과 달리, 도메인 전문가의 지식을 분해 방법의 형태로 시스템에 직접 인코딩할 수 있으며, 이를 통하여 계획 공간의 탐색 범위를 대폭 축소한다.

로봇 임무 관리에서 HTN 계획은 복잡한 임무를 체계적으로 분해하고, 제약 조건을 계층 간에 전파하며, 대안적 분해 방법 간의 선택을 도메인 지식에 기반하여 수행하는 효과적 수단을 제공한다. 본 절에서는 HTN 계획의 형식적 정의, 구성 요소, 계획 알고리즘, 로봇 임무 관리에의 적용을 체계적으로 기술한다.

2. HTN 계획의 형식적 정의

2.1 구성 요소

HTN 계획 도메인 \mathcal{D} = (\mathcal{O}, \mathcal{M})은 다음의 구성 요소로 정의된다:

  • 연산자 집합(operator set) \mathcal{O}: 원자적 과업(primitive task)의 실행을 정의하는 연산자의 집합이다. 각 연산자 o \in \mathcal{O}는 다음의 형태를 가진다:

o = \langle \text{name}(o), \text{pre}(o), \text{eff}^+(o), \text{eff}^-(o) \rangle

여기서 \text{pre}(o)는 전제 조건(precondition), \text{eff}^+(o)는 추가 효과(add effects), \text{eff}^-(o)는 삭제 효과(delete effects)이다.

  • 방법 집합(method set) \mathcal{M}: 복합 과업(compound task)의 분해 방법을 정의한다. 각 방법 m \in \mathcal{M}은 다음의 형태를 가진다:

m = \langle \text{name}(m), \text{task}(m), \text{pre}(m), \text{subtasks}(m), \text{constraints}(m) \rangle

여기서 \text{task}(m)은 분해 대상 복합 과업, \text{pre}(m)은 방법의 적용 조건, \text{subtasks}(m)은 하위 과업의 목록, \text{constraints}(m)은 하위 과업 간의 순서 및 변수 제약이다.

2.2 HTN 계획 문제

HTN 계획 문제 \mathcal{P} = (\mathbf{s}_0, \mathcal{T}_0, \mathcal{D})는 다음의 입력으로 정의된다:

  • \mathbf{s}_0: 초기 상태(initial state)
  • \mathcal{T}_0: 초기 작업 네트워크(initial task network), 즉 달성하여야 할 과업의 집합과 제약
  • \mathcal{D}: HTN 계획 도메인

계획의 목표는 초기 작업 네트워크 \mathcal{T}_0를 반복적으로 분해하여, 모든 과업이 원자적 과업(primitive task)으로 분해되고, 이들의 순서가 모든 전제 조건과 제약을 만족하는 계획 \pi = \langle o_1, o_2, \ldots, o_n \rangle을 생성하는 것이다.

2.3 작업 네트워크(Task Network)

작업 네트워크 \mathcal{T} = (\mathcal{U}, \mathcal{C})는 과업 노드의 집합 \mathcal{U}와 제약의 집합 \mathcal{C}로 구성된다. 제약은 다음의 유형을 포함한다:

  • 순서 제약(ordering constraint): u_i \prec u_j (과업 u_i가 u_j보다 선행)
  • 변수 바인딩 제약(variable binding constraint): v_1 = v_2 또는 v_1 \neq v_2
  • 상태 제약(state constraint): 특정 시점에서의 상태 조건

작업 네트워크에서 순서 제약의 유형에 따라 다음의 두 가지 형태가 구분된다:

  • 전순서(totally-ordered) HTN: 모든 과업 쌍에 대하여 순서가 지정된다.
  • 부분순서(partially-ordered) HTN: 일부 과업 쌍만 순서가 지정되며, 나머지는 임의의 순서로 실행 가능하다.

3. HTN 계획 알고리즘

3.1 기본 분해 알고리즘

HTN 계획의 기본 알고리즘은 다음의 재귀적 절차를 따른다:

function HTN-Plan(s, T, D):
    if T가 비어 있으면: return 빈 계획
    t ← T에서 분해되지 않은 과업 선택
    if t가 원자적 과업이면:
        if pre(t)가 s에서 만족되면:
            s' ← apply(t, s)
            plan ← HTN-Plan(s', T - {t}, D)
            if plan ≠ 실패: return t · plan
    if t가 복합 과업이면:
        for each 방법 m ∈ D where task(m) = t:
            if pre(m)이 s에서 만족되면:
                T' ← (T - {t}) ∪ subtasks(m)
                plan ← HTN-Plan(s, T', D)
                if plan ≠ 실패: return plan
    return 실패

3.2 SHOP 및 SHOP2 알고리즘

SHOP(Simple Hierarchical Ordered Planner)(Nau et al., 1999)은 전순서 HTN 계획기로서, 과업을 좌에서 우(left-to-right)로 순차적으로 처리하며, 각 시점의 현재 상태를 유지하면서 계획을 생성한다.

SHOP2(Nau et al., 2003)는 SHOP를 부분순서 HTN으로 확장한 계획기이며, 다음의 추가 기능을 제공한다:

  • 부분순서 작업 네트워크의 처리
  • 외부 함수 호출(external function call)
  • 수치 연산(numerical computation)
  • 조건부 효과(conditional effects)
  • 보호 조건(protected conditions)

SHOP2는 로봇 임무 계획 분야에서 널리 사용되어 왔으며, 국제 계획 대회(International Planning Competition)에서도 우수한 성과를 보인 바 있다.

3.3 비결정적 HTN(Nondeterministic HTN)

실세계의 불확실성을 고려하기 위하여, 비결정적 효과와 센싱(sensing) 행동을 포함하는 HTN 확장이 연구되었다. 비결정적 HTN에서 연산자의 효과는 복수의 가능 결과 중 하나로 비결정적으로 결정된다:

\text{eff}(o) \in \{\text{eff}_1(o), \text{eff}_2(o), \ldots, \text{eff}_k(o)\}

이 경우, 조건부 계획(contingency plan) 또는 정책(policy)의 형태로 계획이 생성된다.

4. HTN 분해의 특성 분석

4.1 표현력(Expressiveness)

HTN 계획은 고전적 STRIPS 계획보다 표현력이 높다(Erol et al., 1994). HTN 도메인이 적절히 설계되면, STRIPS 계획으로 표현 불가능한 과업 관련 제약(예: “이 과업은 반드시 이 방법으로 수행되어야 한다”)을 자연스럽게 인코딩할 수 있다.

이론적으로, 일반적인 HTN 계획 문제는 결정 불가능(undecidable)이나, 실용적 제한(재귀적 방법의 깊이 제한 등)을 적용하면 결정 가능하게 된다.

4.2 도메인 지식의 인코딩

HTN의 핵심적 장점은 도메인 전문가의 절차적 지식(procedural knowledge)을 분해 방법으로 직접 인코딩할 수 있다는 점이다. 이는 다음의 이점을 제공한다:

  • 탐색 공간 축소: 도메인 지식에 의하여 비합리적인 분해 경로를 사전에 배제한다.
  • 계획 품질 보장: 전문가가 검증한 분해 방법을 적용하므로, 생성된 계획의 품질이 일정 수준 이상으로 보장된다.
  • 해석 가능성(interpretability): 계획의 각 단계가 도메인 의미를 가지므로, 인간 운용자가 계획을 이해하고 검토하기 용이하다.

4.3 계산 복잡도

전순서 HTN 계획의 복잡도는 도메인의 구조에 의존한다. 방법의 수와 분해 깊이가 제한되면 다항 시간(polynomial time) 내에 계획을 생성할 수 있으나, 일반적인 경우 NP-난해(NP-hard) 이상의 복잡도를 가진다.

5. 로봇 임무 관리에의 적용

5.1 HTN 도메인 설계 예시

UAV 감시 임무의 HTN 도메인 설계 예시:

복합 과업:

  • \text{SurveillanceMission}(area)
  • \text{SearchArea}(region)
  • \text{InvestigateTarget}(target)

분해 방법:

m_1: \text{SurveillanceMission}(area) \rightarrow \text{Takeoff} \;;\; \text{SearchArea}(area) \;;\; \text{ReturnToBase} \;;\; \text{Land}

m_2: \text{SearchArea}(region) \rightarrow \text{ComputeCoverage}(region) \;;\; \text{FollowCoveragePattern}(region) \;;\; \text{if } \text{TargetFound} \text{ then } \text{InvestigateTarget}(target)

m_3: \text{InvestigateTarget}(target) \rightarrow \text{Approach}(target) \;;\; \text{Classify}(target) \;;\; \text{Report}(target)

원자적 과업(연산자):

  • \text{Takeoff}: 전제 조건 \{\text{on\_ground}\}, 효과 \{+\text{airborne}, -\text{on\_ground}\}
  • \text{Land}: 전제 조건 \{\text{airborne}, \text{at\_base}\}, 효과 \{+\text{on\_ground}, -\text{airborne}\}
  • \text{FollowCoveragePattern}(region): 전제 조건 \{\text{airborne}\}, 효과 \{+\text{covered}(region)\}

5.2 다중 로봇 HTN

다중 로봇 시스템에서는 HTN 분해에 로봇 할당(allocation)이 결합된다. 복합 과업의 분해 시, 각 하위 과업에 적합한 로봇을 할당하는 결정이 포함된다:

m_{\text{multi}}: \text{CooperativeTask} \rightarrow \text{SubTask}_1(\text{robot}=R_1) \;\|\; \text{SubTask}_2(\text{robot}=R_2)

MA-SHOP(Multi-Agent SHOP) 등의 다중 에이전트 HTN 계획기가 이 문제를 다룬다.

5.3 온라인 HTN 재계획

임무 수행 중 환경 변화나 예상치 못한 이벤트가 발생하면, 현재 HTN 계획의 일부를 취소하고 재분해(re-decomposition)하여야 한다. 온라인 HTN 재계획 기법은:

  1. 부분 재계획(partial replanning): 영향을 받는 하위 트리만 재분해한다.
  2. 수리(repair): 기존 계획의 구조를 최대한 유지하면서 실패한 부분만 수정한다.
  3. 점진적 분해(incremental decomposition): 미래 과업의 분해를 실행 시점까지 지연(lazy decomposition)하여, 최신 상태 정보를 반영한다.

점진적 분해는 “최후 결정 순간(latest commitment)” 전략에 해당하며, 동적 환경에서의 적응성을 향상시킨다.

5.4 HTN과 행동 트리의 연계

HTN 계획의 출력을 행동 트리(Behavior Tree) 구조로 변환하여 실행하는 접근법이 연구되고 있다. HTN의 분해 트리는 행동 트리의 서브트리로 자연스럽게 매핑되며, HTN의 분해 방법의 하위 과업 간 순서 제약은 시퀀스(Sequence) 노드로, 대안적 방법 간의 선택은 폴백(Fallback) 노드로 변환된다.

이 접근법은 HTN의 체계적 분해 능력과 행동 트리의 반응적 실행 능력을 결합한다.

6. 참고문헌

  • Erol, K., Hendler, J., and Nau, D. S. (1994). “HTN Planning: Complexity and Expressivity.” Proceedings of the AAAI Conference on Artificial Intelligence, 1994.
  • Nau, D. S., Cao, Y., Lotem, A., and Muñoz-Avila, H. (1999). “SHOP: Simple Hierarchical Ordered Planner.” Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1999.
  • Nau, D. S., Au, T. C., Ilghami, O., Kuter, U., Murdock, J. W., Wu, D., and Yaman, F. (2003). “SHOP2: An HTN Planning System.” Journal of Artificial Intelligence Research, 20, 379–404.
  • Ghallab, M., Nau, D., and Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
  • Georgievski, I. and Aiello, M. (2015). “HTN Planning: Overview, Comparison, and Beyond.” Artificial Intelligence, 222, 124–156.
  • Colledanchise, M. and Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.

본 절은 로봇공학 서적 Volume 9, Part 53, Chapter 396의 일부로 작성되었다. 버전: 2026-03-24 v2.0