396.35 하양식(Top-Down) 임무 분할 기법

396.35 하양식(Top-Down) 임무 분할 기법

1. 서론

하양식(top-down) 임무 분할 기법은 고수준(high-level)의 추상적 임무를 점진적으로 하위 수준(lower-level)의 구체적 과업(task)으로 분해하는 체계적 방법론이다. 이 접근법은 복잡한 임무를 관리 가능한 단위로 세분화함으로써, 임무 계획의 복잡도를 감소시키고, 계층적 추상화(hierarchical abstraction)를 통한 유연한 임무 관리를 가능하게 한다.

하양식 분할은 소프트웨어 공학의 구조적 분석(structured analysis), 시스템 공학의 기능 분해(functional decomposition), 인공지능의 계층적 계획(hierarchical planning)과 밀접한 관계를 가진다. 본 절에서는 하양식 임무 분할의 기본 원리, 분할 기준, 분해 전략, 형식적 표현, 그리고 로봇 임무에의 적용을 체계적으로 기술한다.

2. 하양식 분할의 기본 원리

2.1 계층적 추상화

하양식 분할은 임무를 추상화 수준(abstraction level)에 따라 계층적으로 구조화한다. 최상위 수준에는 임무의 전체 목적이 위치하고, 하위 수준으로 내려갈수록 구체적인 실행 단위의 과업이 위치한다:

M \xrightarrow{\text{분해}} \{T_1, T_2, \ldots, T_m\} \xrightarrow{\text{분해}} \{\{t_{1,1}, \ldots\}, \{t_{2,1}, \ldots\}, \ldots\}

각 수준에서의 분해는 다음의 원칙을 따른다:

  • 완전성(completeness): 하위 과업의 집합이 상위 임무의 모든 요구사항을 포괄하여야 한다.
  • 분리성(separability): 하위 과업 간의 결합도(coupling)를 최소화하여야 한다.
  • 응집성(cohesion): 각 하위 과업은 의미적으로 일관된 단일 기능을 수행하여야 한다.

2.2 분해 트리(Decomposition Tree)

하양식 분할의 결과는 분해 트리(decomposition tree) \mathcal{D} = (\mathcal{N}, \mathcal{E})로 표현된다. 루트 노드는 원래 임무 M이고, 말단 노드(leaf node)는 더 이상 분해되지 않는 원자적 과업(atomic task 또는 primitive task)이며, 중간 노드는 복합 과업(compound task)이다.

형식적으로, 분해 함수 \delta는 복합 과업을 하위 과업의 서열(ordered set)로 사상한다:

\delta: \mathcal{T}_{\text{compound}} \rightarrow 2^{\mathcal{T}} \times \mathcal{P}

여기서 2^{\mathcal{T}}는 과업 집합의 멱집합(power set), \mathcal{P}는 하위 과업 간의 선행 관계 집합이다.

2.3 분해의 정지 조건

분해는 과업이 다음의 조건 중 하나를 만족할 때 정지한다:

  • 원자성(atomicity): 과업이 로봇의 단일 행동(primitive action)으로 직접 실행 가능한 수준에 도달하였다.
  • 할당 가능성(assignability): 과업이 단일 로봇 또는 단일 실행 모듈에 할당 가능한 수준에 도달하였다.
  • 사전 정의 깊이(predefined depth): 분해 트리의 깊이가 설계 시 지정된 최대 깊이에 도달하였다.
  • 계획 가능성(planability): 과업에 대한 경로 계획이나 행동 계획을 기존 알고리즘으로 직접 수립할 수 있는 수준에 도달하였다.

3. 분할 기준

3.1 기능적 분할(Functional Decomposition)

임무를 수행 기능(function)에 따라 분할하는 방법이다. 각 하위 과업은 고유한 기능적 역할을 담당한다:

  • 감시 임무 → {탐색(search), 식별(identification), 추적(tracking), 보고(reporting)}
  • 배송 임무 → {경로 계획(routing), 물품 적재(loading), 이동(navigation), 물품 하역(unloading)}
  • 구조 임무 → {탐지(detection), 접근(approach), 구출(extraction), 이송(transport)}

3.2 공간적 분할(Spatial Decomposition)

작업 공간을 공간적 영역으로 분할하고, 각 영역에 해당하는 과업을 생성하는 방법이다. 영역 감시, 농업용 로봇의 밭 작업, 탐색 구조 등에서 활용된다.

공간 분할 함수 \sigma는 작업 공간 \mathcal{W}를 N개의 부분 영역으로 분할한다:

\sigma: \mathcal{W} \rightarrow \{\mathcal{W}_1, \mathcal{W}_2, \ldots, \mathcal{W}_N\}

\bigcup_{i=1}^{N} \mathcal{W}_i = \mathcal{W}, \quad \mathcal{W}_i \cap \mathcal{W}_j = \emptyset \; (i \neq j)

분할 기법으로는 보로노이 분할(Voronoi partition), 격자 분할(grid partition), k-평균 군집화(k-means clustering), 사각형 분할(quadtree/octree decomposition) 등이 사용된다.

3.3 시간적 분할(Temporal Decomposition)

임무를 시간적 단계(phase)로 분할하는 방법이다. 각 단계는 순차적으로 수행되며, 단계 간의 전환은 특정 조건이나 이벤트에 의하여 기동된다:

임무 → {준비 단계(preparation phase), 이동 단계(transit phase), 작업 단계(operation phase), 복귀 단계(return phase)}

시간적 분할은 임무 생애 주기(mission life cycle)의 구조와 자연스럽게 대응된다.

3.4 에이전트 기반 분할(Agent-Based Decomposition)

다중 로봇 시스템에서 각 로봇(에이전트)에 할당할 부분 임무를 생성하는 분할이다. 에이전트의 능력(capability), 위치, 자원 상태 등을 고려하여 분할한다:

\delta_{\text{agent}}: M \rightarrow \{M_1, M_2, \ldots, M_N\} \quad \text{s.t.} \quad M_i \subseteq \text{capability}(R_i)

여기서 R_i는 로봇 i, \text{capability}(R_i)는 로봇 i가 수행 가능한 과업의 집합이다.

4. 분해 전략

4.1 순차적 분해(Sequential Decomposition)

임무를 순서가 정해진 과업의 연쇄(sequence)로 분해한다:

M = \tau_1 \rightarrow \tau_2 \rightarrow \ldots \rightarrow \tau_n

이는 과업 간에 엄격한 선행 관계가 존재하는 경우에 적합하다. 조립 공정, 순차적 검사 절차 등이 이에 해당한다.

4.2 병렬 분해(Parallel Decomposition)

임무를 동시에 수행 가능한 독립적 과업의 집합으로 분해한다:

M = \tau_1 \| \tau_2 \| \ldots \| \tau_n

여기서 \|는 병렬 실행을 나타낸다. 다중 로봇 탐색, 분산 감시 등에서 적용된다. 병렬 분해는 임무 소요 시간을 단축시키나, 로봇 간의 자원 경합과 통신 부하를 유발할 수 있다.

4.3 조건부 분해(Conditional Decomposition)

시스템 상태나 환경 조건에 따라 분해 방법이 달라지는 적응적 분해이다:

M = \begin{cases} \tau_A \rightarrow \tau_B & \text{if } \phi_1(\mathbf{s}) \\ \tau_C \rightarrow \tau_D & \text{if } \phi_2(\mathbf{s}) \\ \tau_E & \text{otherwise} \end{cases}

여기서 \phi_i(\mathbf{s})는 시스템 상태 \mathbf{s}에 대한 조건이다. 재난 구조에서 피해 규모에 따른 전략 분기, 기상 조건에 따른 임무 변형 등에 적용된다.

4.4 반복적 분해(Iterative Decomposition)

특정 과업이 반복적으로 수행되는 구조의 분해이다:

M = (\tau_{\text{sense}} \rightarrow \tau_{\text{act}})^* \quad \text{until} \quad \phi_{\text{terminate}}(\mathbf{s})

순찰(patrol), 주기적 감시, 농업용 반복 작업 등에서 사용된다.

5. 하양식 분할의 형식적 표현

5.1 문맥 자유 문법(Context-Free Grammar) 기반 표현

임무의 분해 규칙을 문맥 자유 문법(CFG) G = (V, \Sigma, P, S)로 형식화할 수 있다:

  • V: 비단말 기호(non-terminal symbol)의 집합 (복합 과업)
  • \Sigma: 단말 기호(terminal symbol)의 집합 (원자적 과업)
  • P: 생성 규칙(production rule)의 집합 (분해 규칙)
  • S: 시작 기호 (최상위 임무)

예시:

\text{Mission} \rightarrow \text{Search} \; \text{Identify} \; \text{Engage}

\text{Search} \rightarrow \text{MoveTo}(p_1) \; \text{Scan} \; \text{MoveTo}(p_2) \; \text{Scan}

\text{Identify} \rightarrow \text{Acquire} \; \text{Classify}

5.2 AND/OR 그래프 표현

분해 트리의 각 노드는 AND 분해 또는 OR 분해를 나타낸다:

  • AND 노드: 모든 자식 과업의 수행이 필요하다.
  • OR 노드: 자식 과업 중 하나의 수행으로 충분하다 (대안적 분해).

AND/OR 그래프는 계획 공간의 탐색에 활용되며, AO* 알고리즘에 의하여 최적 분해 전략을 탐색할 수 있다(Nilsson, 1980).

5.3 STRIPS 표현과의 연계

고전적 AI 계획에서 STRIPS(Stanford Research Institute Problem Solver) 표현을 사용하여 각 분해 단계의 전제 조건(precondition)과 효과(effect)를 명시할 수 있다. 이를 통하여 분해의 타당성(validity)을 자동으로 검증한다:

\tau: \langle \text{pre}(\tau), \text{add}(\tau), \text{del}(\tau) \rangle

여기서 \text{pre}(\tau)는 과업의 전제 조건, \text{add}(\tau)는 과업 수행 후 추가되는 상태, \text{del}(\tau)는 제거되는 상태이다.

6. 분해의 품질 평가

6.1 분해 깊이와 복잡도

분해 트리의 깊이 D와 가지 수(branching factor) B는 임무 관리의 복잡도에 직접적으로 영향을 미친다. 분해 트리의 말단 노드 수(원자적 과업의 수)는 최대 O(B^D)이므로, 과도한 분해는 관리 부하를 증가시킨다.

적절한 분해 수준의 결정 기준:

  • 각 원자적 과업의 소요 시간이 시스템의 반응 시간(response time) 요구를 만족하는가
  • 각 원자적 과업이 단일 모듈의 능력 범위 내에 있는가
  • 과업 간의 통신·동기화 오버헤드가 수용 가능한가

6.2 결합도와 응집도

분해의 품질은 모듈 설계에서의 결합도(coupling)와 응집도(cohesion)의 관점에서 평가된다:

  • 낮은 결합도: 과업 간의 자원 공유, 데이터 교환, 시간적 동기화가 최소화되어야 한다.

\text{coupling}(T_i, T_j) = \frac{|\text{shared\_resources}(T_i, T_j)| + |\text{data\_exchange}(T_i, T_j)|}{|\text{resources}(T_i)| + |\text{resources}(T_j)|}

  • 높은 응집도: 과업 내부의 행동들이 단일 목적에 밀접하게 관련되어야 한다.

6.3 확장성(Scalability)

분해 기법은 임무의 규모(과업 수, 로봇 수, 공간 범위)가 증가하여도 합리적인 시간 내에 분해를 수행할 수 있어야 한다. 분해 알고리즘의 시간 복잡도와 공간 복잡도가 확장성의 주요 지표이다.

7. 로봇 임무에의 적용 사례

7.1 UAV 감시 임무의 하양식 분할

UAV 감시 임무의 하양식 분할 예시:

  1. 임무 수준: 지정 구역 감시
  2. 단계 수준: 이륙 → 이동 → 감시 → 복귀 → 착륙
  3. 감시 단계 분할: 구역 1 감시 \| 구역 2 감시 \| 구역 3 감시 (공간적 분할)
  4. 구역 감시 분할: 경로 추종 → 영상 촬영 → 이상 탐지 → 보고 (기능적 분할)
  5. 원자적 과업: 경유점 이동, 카메라 활성화, 영상 전송 등

7.2 물류 로봇 배송 임무의 하양식 분할

물류 배송 임무의 하양식 분할 예시:

  1. 임무 수준: 다중 주문 배송
  2. 주문별 분할: 주문 1 처리 → 주문 2 처리 → … (시간적 분할)
  3. 주문 처리 분할: 물품 위치 확인 → 이동 → 물품 파지 → 이동 → 물품 하역 (기능적 분할)
  4. 원자적 과업: 경유점 이동, 그리퍼 개폐, 바코드 스캔 등

8. 참고문헌

  • Ghallab, M., Nau, D., and Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
  • Nilsson, N. J. (1980). Principles of Artificial Intelligence. Springer.
  • 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.
  • Erol, K., Hendler, J., and Nau, D. S. (1994). “HTN Planning: Complexity and Expressivity.” Proceedings of the AAAI Conference on Artificial Intelligence, 1994.
  • Korsah, G. A., Stentz, A., and Dias, M. B. (2013). “A Comprehensive Taxonomy for Multi-Robot Task Allocation.” The International Journal of Robotics Research, 32(12), 1495–1512.

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