HTN 분해 규칙과 메서드 (HTN Decomposition Rules and Methods)

1. 개요

HTN 플래닝의 핵심은 복합 태스크를 하위 태스크로 분해하는 메서드(method)이다. 메서드는 도메인 전문가의 지식을 인코딩하여 “이 태스크를 이런 방식으로 수행한다“는 분해 전략을 정의한다.

2. 메서드의 형식적 정의

메서드 m은 다음으로 구성된다.

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

메서드 예시

배달 임무의 메서드

method deliver_near(robot, obj, dest):
  task: deliver(robot, obj, dest)
  precondition: near(robot, obj_location)
  subtasks:
    1. pick(robot, obj, obj_location)
    2. move(robot, obj_location, dest)
    3. place(robot, obj, dest)

method deliver_far(robot, obj, dest):
  task: deliver(robot, obj, dest)
  precondition: not near(robot, obj_location)
  subtasks:
    1. move(robot, current_location, obj_location)
    2. pick(robot, obj, obj_location)
    3. move(robot, obj_location, dest)
    4. place(robot, obj, dest)

대안 메서드

동일한 복합 태스크에 대해 복수의 메서드가 정의될 수 있다. 계획기는 전제 조건이 충족되는 메서드를 선택한다.

분해 규칙의 유형

순차 분해 (Sequential Decomposition)

하위 태스크가 순서대로 실행된다.

\text{subtasks} = [t_1, t_2, t_3] \quad \text{(t_1 before t_2 before t_3)}

2.1 부분 순서 분해 (Partial-Order Decomposition)

하위 태스크 간의 순서가 부분적으로만 지정된다.

\text{subtasks} = \{t_1, t_2, t_3\}, \quad \text{ordering} = \{t_1 \prec t_3\}

t_2는 t_1이나 t_3와 순서 관계가 없으므로 자유롭게 배치 가능하다.

조건부 분해 (Conditional Decomposition)

현재 상태에 따라 다른 분해 방식을 선택한다.

method clean_room(robot, room):
  if dirty(room):
    subtasks: [sweep(robot, room), mop(robot, room)]
  if very_dirty(room):
    subtasks: [deep_clean(robot, room), sweep(robot, room), mop(robot, room)]

재귀적 분해

복합 태스크의 하위 태스크가 다시 복합 태스크일 수 있으며, 이 경우 재귀적 분해가 발생한다.

serve_customer(robot, customer)
├── take_order(robot, customer)  ← 복합 태스크
│   ├── approach(robot, customer)
│   └── listen(robot, customer)
├── prepare_order(robot, order)  ← 복합 태스크
│   ├── get_ingredients(robot, order)
│   └── make_food(robot, order)
└── deliver_order(robot, customer, order)  ← 복합 태스크

메서드 설계 원칙

참고 문헌

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