397.39 HTN의 복합 과업 분해 메커니즘

계층적 작업 네트워크(HTN) 계획에서 **복합 과업 분해(compound task decomposition)**는 추상적인 고수준 과업을 실행 가능한 저수준 원시 과업(primitive task)의 네트워크로 변환하는 핵심 메커니즘이다. 분해 과정의 설계는 HTN 계획의 효율성, 유연성, 그리고 생성되는 계획의 품질에 결정적인 영향을 미치므로, 이 메커니즘의 형식적 구조와 실행 전략에 대한 깊은 이해가 필요하다.

1. 방법(Method)에 의한 과업 분해

1.1 방법의 형식적 구조

복합 과업의 분해는 **방법(method)**이라 불리는 분해 규칙에 의해 수행된다. 방법 $m$ 은 다음과 같은 구조를 지닌다.

$m = (\text{name}(m),\ \text{task}(m),\ \text{pre}(m),\ \text{subtasks}(m),\ \prec_m)$

각 구성 요소의 의미는 다음과 같다.

$\text{name}(m)$ : 방법의 고유 식별자 및 매개변수 목록
$\text{task}(m)$ : 이 방법이 분해 대상으로 하는 복합 과업의 이름
$\text{pre}(m)$ : 방법의 적용 전제 조건으로서, 현재 세계 상태에서 참이어야 하는 명제(proposition)들의 논리적 결합
$\text{subtasks}(m)$ : 분해 결과로 생성되는 하위 과업들의 집합 $\{t_1, t_2, \ldots, t_k\}$
$\prec_m$ : 하위 과업들 간의 순서 제약(ordering constraints)

하나의 복합 과업에 대해 여러 개의 방법이 정의될 수 있으며, 이는 동일한 목표를 달성하기 위한 대안적 분해 전략을 표현한다. 방법의 선택은 전제 조건의 만족 여부와 탐색 전략에 따라 결정된다.

1.2 분해 과정의 수학적 정의

복합 과업 $c$ 의 분해는 다음과 같은 재기록(rewriting) 과정으로 형식화된다. 작업 네트워크 $w = (T, \prec, \alpha)$ 에서 복합 과업 식별자 $t \in T$ 에 대한 분해는 다음 조건을 만족하는 변환이다.

$\alpha(t)$ 가 복합 과업이고, 방법 $m$ 의 $\text{task}(m) = \alpha(t)$ 이며, $\text{pre}(m)$ 이 현재 상태 $s$ 에서 성립한다.
$t$ 를 $T$ 에서 제거하고, $\text{subtasks}(m) = \{t_1', t_2', \ldots, t_k'\}$ 를 삽입한다.
$t$ 와 관련된 모든 순서 제약을 적절히 갱신한다. 즉, $t_i \prec t$ 인 모든 제약을 $t_i \prec t_j'\ (j = 1, \ldots, k)$ 로, $t \prec t_i$ 인 모든 제약을 $t_j' \prec t_i\ (j = 1, \ldots, k)$ 로 대체한다.
$\prec_m$ 에 명시된 하위 과업 간 순서 제약을 추가한다.

이 과정을 모든 복합 과업이 원시 과업으로 치환될 때까지 반복하면, 최종적으로 실행 가능한 원시 과업들의 순서가 결정된 계획이 생성된다.

2. 분해 전략의 유형

2.1 전방 분해(Forward Decomposition)

전방 분해는 초기 상태 $s_0$ 에서 출발하여, 과업 네트워크의 첫 번째(또는 선행 제약이 없는) 과업부터 순차적으로 분해하는 전략이다. 분해 시점에 현재 세계 상태를 알 수 있으므로, 상태 의존적 방법 선택이 가능하다는 장점이 있다.

전방 분해의 핵심 특성:

각 분해 단계에서 현재 상태 $s$ 가 명확하게 정의되어 있다.
방법의 전제 조건 $\text{pre}(m)$ 를 현재 상태에 대해 직접 평가할 수 있다.
원시 과업의 효과를 즉시 적용하여 후속 상태를 계산할 수 있다.

전방 분해의 상태 전이 과정은 다음과 같다. 원시 과업 $t_p$ 가 선택되어 상태 $s$ 에서 실행되면:

$s' = (s \setminus \text{eff}^-(t_p)) \cup \text{eff}^+(t_p)$

여기서 $\text{eff}^-(t_p)$ 와 $\text{eff}^+(t_p)$ 는 각각 과업 $t_p$ 의 삭제 효과(delete effect)와 추가 효과(add effect)이다.

SHOP 및 SHOP2 계획기가 이 전략을 채택하고 있으며, 이 전략은 실용적인 효율성 때문에 로봇 임무 계획에서 가장 널리 활용된다.

2.2 후방 분해(Backward Decomposition)

후방 분해는 목표 상태로부터 역방향으로 분해를 진행하는 전략이다. 이 전략에서는 달성해야 할 목표 조건으로부터 출발하여, 해당 조건을 충족시킬 수 있는 과업들을 역추적(regression)을 통해 선택한다.

후방 분해는 목표 지향적 추론에 적합하나, 분해 시점에 현재 상태를 알 수 없으므로 방법의 전제 조건 평가가 제한적이라는 단점이 있다.

2.3 임의 순서 분해(Arbitrary-Order Decomposition)

임의 순서 분해는 작업 네트워크에서 임의의 복합 과업을 선택하여 분해하는 가장 일반적인 전략이다. UMCP(Universal Method Composition Planner)가 이 전략을 채택하며, 부분순서 작업 네트워크에서의 유연한 분해를 지원한다.

3. 분해 심도와 재귀적 분해

3.1 다단계 계층적 분해

실제 로봇 임무에서는 분해가 다수의 계층을 거쳐 진행된다. 최상위 복합 과업 $c_0$ 에서 시작하여 분해 깊이(decomposition depth) $d$ 만큼의 계층을 거치면, 각 단계에서 복합 과업이 하위 과업들로 치환된다.

분해 트리(decomposition tree) $\mathcal{T}$ 의 구조는 다음과 같다.

루트 노드: 초기 복합 과업 $c_0$
내부 노드: 복합 과업과 적용된 방법
리프 노드: 원시 과업

분해 트리의 리프 노드들을 좌에서 우로 읽으면 실행 가능한 계획 $\pi = \langle a_1, a_2, \ldots, a_n \rangle$ 이 얻어진다.

3.2 재귀적 방법(Recursive Methods)

HTN에서는 방법의 하위 과업이 원래 복합 과업과 동일한 유형을 포함할 수 있다. 이를 **재귀적 방법(recursive method)**이라 한다. 재귀적 분해를 통해 반복적인 패턴의 임무를 간결하게 표현할 수 있다.

예를 들어, “구역 순찰(patrol)” 임무에 대한 재귀적 방법은 다음과 같이 정의할 수 있다.

방법: 반복_순찰
  과업: 순찰(구역_리스트)
  전제 조건: 구역_리스트 ≠ ∅
  하위 과업:
    t₁: 해당_구역_점검(첫번째(구역_리스트))
    t₂: 순찰(나머지(구역_리스트))
  순서 제약: t₁ ≺ t₂

방법: 순찰_종료
  과업: 순찰(구역_리스트)
  전제 조건: 구역_리스트 = ∅
  하위 과업: ∅ (작업 없음)

재귀적 방법의 종료 조건(base case)이 반드시 정의되어야 하며, 그렇지 않으면 무한 분해 루프에 빠질 수 있다.

정리 (Erol et al., 1996): 재귀적 방법을 허용하는 HTN 계획은 반결정 가능(semidecidable)하며, 튜링 완전(Turing-complete)한 표현력을 지닌다.

4. 분해 시 제약 조건 처리

4.1 상태 변수 제약(State Variable Constraints)

방법의 전제 조건 외에도, 하위 과업들 사이에 특정 상태 조건이 유지되어야 함을 명시하는 **상태 변수 제약(state variable constraints)**이 존재할 수 있다.

$\text{before}(l, t_i): \text{리터럴 } l \text{이 과업 } t_i \text{ 실행 직전에 참이어야 함}$
$\text{after}(l, t_i): \text{리터럴 } l \text{이 과업 } t_i \text{ 실행 직후에 참이어야 함}$
$\text{between}(l, t_i, t_j): \text{리터럴 } l \text{이 } t_i \text{와 } t_j \text{ 사이의 모든 상태에서 참이어야 함}$

이러한 제약은 안전 제약(safety constraint)이나 불변 조건(invariant)을 분해 과정에 반영하는 데 활용된다. 예를 들어, 로봇의 배터리 잔량이 특정 임계치 이상이어야 한다는 제약을 between 제약으로 표현할 수 있다.

4.2 변수 바인딩 제약(Variable Binding Constraints)

분해 과정에서 하위 과업의 매개변수를 결정하기 위한 변수 바인딩(variable binding)이 필요하다. 바인딩 제약은 다음과 같은 형태를 가진다.

동일 제약(co-designation): $v_1 = v_2$ — 두 변수가 동일한 값에 바인딩되어야 함
비동일 제약(non-co-designation): $v_1 \neq v_2$ — 두 변수가 서로 다른 값에 바인딩되어야 함

이 제약들은 예를 들어, “물품을 집는 로봇과 물품을 내려놓는 로봇이 동일해야 한다“와 같은 조건을 표현한다.

4.3 자원 제약(Resource Constraints)

로봇 임무 계획에서는 에너지, 적재 용량, 통신 대역폭 등의 제한된 자원을 고려해야 한다. HDDL(Hierarchical Domain Definition Language)과 같은 현대적 HTN 언어에서는 자원 제약을 방법 정의에 직접 포함할 수 있다.

$\text{require}(r, q, t_i): \text{과업 } t_i \text{가 자원 } r \text{을 } q \text{만큼 소비함}$

분해 과정에서 누적 자원 소비가 가용 자원을 초과하는 방법은 후보에서 제외된다.

5. 분해 탐색 공간의 관리

5.1 분기 제어(Branching Control)

복합 과업에 여러 방법이 적용 가능할 때, 탐색 공간의 분기(branching)가 발생한다. 분기 계수를 효과적으로 제어하기 위한 전략으로 다음이 활용된다.

방법 우선순위(Method Ordering): 방법에 우선순위를 부여하여, 높은 우선순위의 방법을 먼저 시도한다. SHOP2에서는 방법 목록의 순서가 우선순위를 결정하며, 첫 번째 적용 가능한 방법이 성공하면 이후의 방법은 탐색하지 않는 **결정론적 분해(deterministic decomposition)**를 지원한다.

비용 기반 방법 선택(Cost-Based Method Selection): 각 방법에 예상 비용을 할당하고, 비용이 낮은 방법을 우선적으로 선택하는 전략이다. 이를 통해 최적에 가까운 계획을 효율적으로 생성할 수 있다.

5.2 역추적과 가지치기(Backtracking and Pruning)

선택된 방법이 실패(즉, 하위 과업의 분해가 불가능)할 경우, 계획기는 이전 분기점으로 **역추적(backtracking)**하여 대안적 방법을 시도한다. 효율적인 역추적을 위해 다음 기법들이 활용된다.

의존성 방향 역추적(Dependency-Directed Backtracking): 실패의 원인이 된 분기점으로 직접 역추적하여 불필요한 탐색을 방지한다.
조기 가지치기(Early Pruning): 방법의 전제 조건이 달성 불가능함을 사전에 판별하여 해당 분기를 제거한다.

6. 분해 결과의 해석과 실행

6.1 분해 트리에서 계획으로의 변환

분해 트리의 리프 노드에 위치한 원시 과업들은 순서 제약 $\prec$ 에 따라 위상 정렬(topological sort)되어 선형 계획(linear plan)으로 변환된다. 부분순서 HTN에서는 순서 제약이 없는 과업들에 대해 다수의 유효 정렬(valid linearization)이 존재할 수 있으며, 이들 중 최적의 정렬을 선택하기 위해 추가적인 최적화 기준이 적용될 수 있다.

6.2 계층적 계획의 그래프 표현

분해 결과는 **과업 분해 그래프(Task Decomposition Graph, TDG)**로 표현될 수 있다. TDG는 다음과 같이 정의된다.

$G = (V, E_d, E_o)$

여기서 $V$ 는 과업 노드의 집합, $E_d$ 는 분해 관계(decomposition edge)의 집합, $E_o$ 는 순서 관계(ordering edge)의 집합이다. TDG는 계획의 계층 구조를 명시적으로 보존하므로, 실행 중 일부 과업이 실패할 경우 해당 부분 트리만 재분해하는 **국소적 재계획(local replanning)**을 지원한다.

7. 로봇 임무에서의 분해 설계 원칙

로봇 임무 계획에서 효과적인 복합 과업 분해를 설계하기 위해서는 다음 원칙들을 고려해야 한다.

원칙 1 — 적절한 추상화 수준의 선택: 분해 계층이 너무 깊으면 계획 시간이 증가하고, 너무 얕으면 도메인 지식의 활용이 부족해진다. 일반적으로 3~5단계의 분해 깊이가 실용적이다.

원칙 2 — 모듈성(Modularity): 각 방법은 독립적으로 이해되고 수정될 수 있어야 한다. 방법 간의 강한 결합(tight coupling)은 방법 라이브러리의 유지보수를 어렵게 만든다.

원칙 3 — 실행 환경의 불확실성 반영: 로봇의 실제 운용 환경에서는 센서 노이즈, 동적 장애물, 통신 지연 등의 불확실성이 존재한다. 이를 반영하여 대안적 분해 방법을 충분히 준비해야 한다.

원칙 4 — 안전 제약의 명시적 부호화: 로봇 운용에서의 안전 제약(예: 충돌 회피, 금지 구역, 최소 배터리 잔량)은 방법의 전제 조건 또는 상태 변수 제약으로 명시적으로 부호화되어야 한다.

8. 요약

HTN의 복합 과업 분해 메커니즘은 방법(method)에 의한 체계적 분해, 분해 전략(전방, 후방, 임의 순서)의 선택, 재귀적 분해를 통한 반복 패턴의 표현, 그리고 다양한 제약 조건(상태 변수, 변수 바인딩, 자원)의 처리를 포괄하는 정교한 프레임워크이다. 분해 탐색 공간의 효율적 관리를 위한 방법 우선순위, 역추적, 가지치기 기법과 함께, 분해 결과의 계층적 표현은 로봇 임무의 국소적 재계획을 가능하게 한다. 이러한 메커니즘의 적절한 설계는 자율 로봇 시스템의 임무 계획 성능을 결정하는 핵심 요인이 된다.

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.
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.
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.

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