396.4 과업(Task)의 정의와 분류

1. 과업의 형식적 정의

과업(Task)은 임무 관리 계층에서 임무(Mission)와 행동(Action) 사이에 위치하는 중간 수준의 추상화 단위이다. 과업은 명확한 시작 조건(Precondition)과 종료 조건(Postcondition)을 가지며, 단일 또는 복수의 원자적 행동(Atomic Action)의 조합을 통해 수행된다.

형식적으로, 과업 t는 다음과 같은 튜플로 정의된다:

t = \langle \text{id}, \text{pre}(t), \text{post}(t), \text{eff}(t), \mathcal{A}_t, \tau_t, \rho_t \rangle

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

• \text{id}: 과업의 고유 식별자
• \text{pre}(t) \subseteq \mathcal{P}: 전제 조건(Precondition). 과업 실행을 위해 사전에 만족되어야 하는 명제의 집합이다.
• \text{post}(t) \subseteq \mathcal{P}: 종료 조건(Postcondition). 과업 완수 후 성립해야 하는 명제의 집합이다.
• \text{eff}(t): \mathcal{S} \rightarrow \mathcal{S}: 효과 함수(Effect Function). 과업 실행이 환경 상태에 미치는 영향을 기술한다.
• \mathcal{A}_t \subseteq \mathcal{A}: 과업 수행에 필요한 행동의 부분 집합이다.
• \tau_t \in \mathbb{R}^+: 과업의 예상 수행 시간이다.
• \rho_t: \mathcal{R} \rightarrow \mathbb{R}^+: 자원 요구 함수. 과업 수행에 필요한 각 자원의 양을 명시한다.

2. STRIPS 형식에서의 과업 표현

고전적 AI 계획의 STRIPS(Stanford Research Institute Problem Solver) 형식에서 과업(연산자, Operator)은 다음과 같이 표현된다(Fikes and Nilsson, 1971):

\text{Operator}(t) = \langle \text{Pre}(t), \text{Add}(t), \text{Del}(t) \rangle

여기서:

• \text{Pre}(t): 과업 실행을 위한 전제 조건 리터럴(Literal) 집합
• \text{Add}(t): 과업 실행 후 세계 상태에 추가되는 리터럴 집합
• \text{Del}(t): 과업 실행 후 세계 상태에서 제거되는 리터럴 집합

예시: “물체 o를 위치 l_1에서 l_2로 이동” 과업의 STRIPS 표현

\text{Move}(o, l_1, l_2): \begin{cases} \text{Pre} = \{\text{at}(o, l_1), \text{clear}(l_2)\} \\ \text{Add} = \{\text{at}(o, l_2)\} \\ \text{Del} = \{\text{at}(o, l_1)\} \end{cases}

3. PDDL 기반 과업 기술

PDDL(Planning Domain Definition Language)은 STRIPS를 확장한 표준 계획 기술 언어로, 과업(액션, Action)을 다음과 같은 구조로 기술한다(McDermott et al., 1998):

(:action navigate
  :parameters (?robot - robot ?from - location ?to - location)
  :precondition (and (at ?robot ?from) (connected ?from ?to))
  :effect (and (at ?robot ?to) (not (at ?robot ?from)))
)

PDDL2.1에서는 시간적 속성을 지원하여 지속적 행동(Durative Action)을 표현할 수 있다(Fox and Long, 2003):

(:durative-action navigate
  :parameters (?robot - robot ?from - location ?to - location)
  :duration (= ?duration (distance ?from ?to))
  :condition (and (at start (at ?robot ?from))
                  (over all (connected ?from ?to)))
  :effect (and (at start (not (at ?robot ?from)))
               (at end (at ?robot ?to)))
)

4. 과업의 분류 체계

4.1 복잡도 기반 분류

과업은 내부 구조의 복잡도에 따라 다음과 같이 분류된다:

**원자적 과업(Atomic Task)**은 더 이상 분해할 수 없는 최소 단위의 과업이다. 이는 단일 행동에 직접 매핑되거나, 하위 계층의 제어기가 직접 실행할 수 있는 단위이다.

t_{\text{atomic}}: \text{decompose}(t_{\text{atomic}}) = \emptyset

**복합 과업(Compound Task)**은 둘 이상의 하위 과업으로 분해 가능한 과업이다. 계층적 작업 네트워크(HTN)에서 비원시 과업(Non-primitive Task)에 해당한다.

t_{\text{compound}}: \text{decompose}(t_{\text{compound}}) = \{t_{c,1}, t_{c,2}, \ldots, t_{c,p}\}, \quad p \geq 2

4.2 시간적 특성에 따른 분류

4.3 할당 특성에 따른 분류

Gerkey and Matarić(2004)의 다중 로봇 과업 할당(MRTA) 분류 체계에 기반하여, 과업은 다음의 세 차원으로 분류된다:

로봇 요구 차원:

• 단일 로봇 과업(Single-Robot Task, SR): 한 대의 로봇이 독립적으로 수행할 수 있는 과업이다.
• 다중 로봇 과업(Multi-Robot Task, MR): 둘 이상의 로봇이 협력하여 수행해야 하는 과업이다.

로봇 능력 차원:

• 단일 과업 로봇(Single-Task Robot, ST): 동시에 하나의 과업만 수행 가능한 로봇이다.
• 다중 과업 로봇(Multi-Task Robot, MT): 동시에 여러 과업을 수행할 수 있는 로봇이다.

할당 시점 차원:

• 즉시 할당(Instantaneous Assignment, IA): 현재 시점의 정보만으로 할당을 결정한다.
• 시간 확장 할당(Time-Extended Assignment, TA): 미래의 과업과 상태를 고려하여 할당을 결정한다.

이 분류의 조합으로 2^3 = 8개의 과업-로봇 할당 유형이 정의된다:

4.4 환경 의존성에 따른 분류

결정론적 과업(Deterministic Task): 동일한 조건에서 항상 동일한 결과를 산출하는 과업이다. 수행 결과가 예측 가능하며, 결정론적 전이 함수로 모델링된다.

s' = f(s, a) \quad \text{(확정적 전이)}

비결정론적 과업(Non-deterministic Task): 동일한 조건에서도 여러 결과가 발생할 수 있는 과업이다. 환경의 불확실성이나 행동의 비결정성에 의해 발생한다.

s' \in F(s, a) \subseteq \mathcal{S} \quad \text{(비결정적 전이)}

확률적 과업(Stochastic Task): 결과의 확률 분포가 알려진 비결정론적 과업이다. 확률적 전이 함수로 모델링된다.

P(s' | s, a) = T(s, a, s') \quad \text{(확률적 전이)}

4.5 기능 영역에 따른 분류

로봇공학에서 흔히 마주하는 과업 유형을 기능 영역별로 분류하면 다음과 같다:

이동 과업(Locomotion Task):

• 지점 간 이동(Point-to-Point Navigation)
• 경로 추종(Path Following)
• 형상 유지 이동(Formation Navigation)

인식 과업(Perception Task):

• 환경 매핑(Environment Mapping)
• 물체 인식(Object Recognition)
• 상황 인식(Situation Awareness)

조작 과업(Manipulation Task):

• 물체 파지(Object Grasping)
• 물체 배치(Object Placement)
• 조립(Assembly)

통신 과업(Communication Task):

• 데이터 전송(Data Transmission)
• 상태 보고(Status Reporting)
• 릴레이 통신(Relay Communication)

감시 과업(Surveillance Task):

• 영역 순찰(Area Patrol)
• 목표 추적(Target Tracking)
• 경계 감시(Perimeter Monitoring)

5. 과업 간 의존 관계

과업 간에는 다양한 의존 관계(Dependency Relation)가 존재하며, 이를 정확히 모델링하는 것이 임무 계획의 정확성을 보장하는 데 핵심적이다.

5.1 선행 관계 (Precedence Relation)

t_i \prec t_j \iff \text{post}(t_i) \supseteq \text{pre}(t_j) \setminus \text{pre}_{\text{initial}}

과업 t_i가 과업 t_j에 선행한다는 것은 t_j의 전제 조건 중 일부가 t_i의 효과에 의해 성립됨을 의미한다.

5.2 상호 배타 관계 (Mutual Exclusion)

t_i \perp t_j \iff \rho_{t_i}(r) + \rho_{t_j}(r) > R_{\max}(r), \quad \exists r \in \mathcal{R}

두 과업이 동시에 수행될 수 없는 경우, 이는 자원 제약에 의한 상호 배타 관계에 해당한다.

5.3 동기화 관계 (Synchronization)

\text{sync}(t_i, t_j) \iff t_i\text{.start} = t_j\text{.start} \vee t_i\text{.end} = t_j\text{.end}

특정 시점에서 두 과업이 동시에 시작하거나 종료해야 하는 동기화 제약이다.

6. 참고 문헌

• Fikes, R. E., and Nilsson, N. J. (1971). “STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving.” Artificial Intelligence, 2(3-4), 189-208.
• Fox, M., and Long, D. (2003). “PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains.” Journal of Artificial Intelligence Research, 20, 61-124.
• Gerkey, B. P., and Matarić, M. J. (2004). “A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems.” The International Journal of Robotics Research, 23(9), 939-954.
• McDermott, D., Ghallab, M., Howe, A., et al. (1998). “PDDL—The Planning Domain Definition Language.” Technical Report CVC TR-98-003, Yale Center for Computational Vision and Control.
• Nau, D., 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.

Version: v1.0 (2026-03-23)