396.31 임무 간 선행 관계(Precedence) 제약

1. 서론

로봇 임무 관리에서 선행 관계(precedence relation) 제약은 과업(task) 간의 실행 순서를 규정하는 논리적 제약이다. 특정 과업이 다른 과업의 완료를 전제 조건으로 요구하는 경우, 두 과업 사이에는 선행 관계가 성립한다. 예를 들어, 물품의 적재(loading)는 물품의 식별(identification) 이후에만 수행 가능하며, 지뢰 제거(mine clearance)는 지뢰 탐지(mine detection) 이후에만 실시할 수 있다.

선행 관계 제약은 임무의 논리적 일관성(logical consistency)을 보장하고, 물리적·인과적으로 불가능한 실행 순서를 배제하는 역할을 수행한다. 본 절에서는 선행 관계 제약의 수학적 정식화, 다양한 유형의 선행 관계, 그래프 이론적 표현, 선행 관계의 확장 형태, 그리고 선행 관계 하의 스케줄링 문제를 체계적으로 기술한다.

2. 선행 관계의 수학적 정식화

2.1 기본 정의

과업 집합 \mathcal{T} = \{\tau_1, \tau_2, \ldots, \tau_n\}에 대하여, 선행 관계는 이항 관계(binary relation) \prec로 정의된다. \tau_i \prec \tau_j는 과업 \tau_i가 과업 \tau_j보다 선행하여야 함을 의미한다. 즉, \tau_i의 완료가 \tau_j의 시작의 필요 조건이다:

\tau_i \prec \tau_j \implies e_i \leq s_j

여기서 s_i와 e_i는 각각 과업 \tau_i의 시작 시점(start time)과 종료 시점(end time)이다. 이 관계는 종료-시작(Finish-to-Start, FS) 관계의 가장 기본적인 형태이다.

선행 관계 \prec는 다음의 성질을 만족하는 엄격 반순서(strict partial order)를 형성한다:

• 비반사성(irreflexivity): \tau_i \not\prec \tau_i (과업은 자기 자신에 선행할 수 없다)
• 추이성(transitivity): \tau_i \prec \tau_j \wedge \tau_j \prec \tau_k \implies \tau_i \prec \tau_k
• 비대칭성(asymmetry): \tau_i \prec \tau_j \implies \tau_j \not\prec \tau_i (순환 의존이 존재하지 않는다)

2.2 선행 관계 그래프(Precedence Graph)

선행 관계는 방향 비순환 그래프(Directed Acyclic Graph, DAG) G = (\mathcal{T}, \mathcal{P})로 표현된다. 여기서 \mathcal{T}는 노드 집합(과업 집합)이고, \mathcal{P} \subseteq \mathcal{T} \times \mathcal{T}는 간선 집합(선행 관계 집합)이다. 간선 (\tau_i, \tau_j) \in \mathcal{P}는 \tau_i \prec \tau_j를 나타낸다.

DAG의 비순환성(acyclicity)은 선행 관계의 비반사성 및 비대칭성과 동치이며, 순환 의존(cyclic dependency)의 부재를 보장한다. 순환이 존재하면 어떠한 과업도 시작할 수 없는 교착 상태(deadlock)가 발생하므로, 선행 관계의 구성 시 순환 검출(cycle detection)이 필수적이다.

2.3 추이적 축소(Transitive Reduction)

선행 관계 그래프에서 추이적으로 유도되는 간선(redundant edge)을 제거한 추이적 축소(transitive reduction)는 동일한 선행 관계를 최소한의 간선으로 표현한다. 추이적 축소 G^* = (\mathcal{T}, \mathcal{P}^*)는 다음의 조건을 만족한다:

\mathcal{P}^* \subseteq \mathcal{P}, \quad \text{과 } \mathcal{P}^* \text{의 추이적 폐포(transitive closure)} = \mathcal{P} \text{의 추이적 폐포}

추이적 축소는 선행 관계의 저장과 시각화를 효율화하며, 임무 계획 알고리즘의 연산 효율을 향상시킨다.

3. 선행 관계의 유형

3.1 종료-시작(Finish-to-Start, FS) 관계

가장 일반적인 선행 관계 유형으로, 선행 과업의 종료가 후행 과업의 시작 조건이다:

e_i \leq s_j

최소 지연(minimum lag) l_{ij}^{\min}이 지정된 경우:

e_i + l_{ij}^{\min} \leq s_j

이는 선행 과업의 완료 후 최소한 l_{ij}^{\min} 시간 단위만큼 경과한 후에야 후행 과업을 시작할 수 있음을 의미한다. 예를 들어, 접착제 도포 과업 후 경화 시간이 필요한 경우가 이에 해당한다.

최대 지연(maximum lag) l_{ij}^{\max}이 지정된 경우:

s_j \leq e_i + l_{ij}^{\max}

이는 선행 과업의 완료 후 l_{ij}^{\max} 시간 이내에 후행 과업을 시작하여야 함을 의미한다. 시간에 민감한 화학 처리, 식품 운반 등에서 적용된다.

3.2 시작-시작(Start-to-Start, SS) 관계

선행 과업의 시작이 후행 과업의 시작 조건이다:

s_i + l_{ij}^{\min} \leq s_j

두 과업이 동시에 또는 일정 간격을 두고 시작되어야 하는 경우에 적용된다. 예를 들어, 센서 보정(calibration) 과업의 시작 후 일정 시간이 경과한 뒤 데이터 수집 과업을 시작하는 경우가 이에 해당한다.

3.3 종료-종료(Finish-to-Finish, FF) 관계

선행 과업의 종료가 후행 과업의 종료 조건이다:

e_i + l_{ij}^{\min} \leq e_j

두 과업이 동시에 또는 일정 간격을 두고 종료되어야 하는 경우에 적용된다.

3.4 시작-종료(Start-to-Finish, SF) 관계

선행 과업의 시작이 후행 과업의 종료 조건이다:

s_i + l_{ij}^{\min} \leq e_j

이는 비교적 드문 관계 유형이나, 교대 작업(shift work)에서 다음 교대조의 시작이 현재 교대조의 종료 조건이 되는 경우 등에 적용된다.

3.5 일반화된 시간적 제약(Generalized Temporal Constraints)

위의 네 가지 기본 관계 유형은 모두 다음의 일반화된 형태로 통합된다. Allen의 시간 간격 대수학(Allen’s Interval Algebra)에서는 두 시간 구간의 관계를 13가지 기본 관계로 분류하며, 이는 선행 관계의 더욱 정밀한 표현을 가능하게 한다. 두 과업 \tau_i = [s_i, e_i]와 \tau_j = [s_j, e_j] 사이의 시간적 관계는 다음의 간격 관계들로 표현된다:

이들 관계와 그 역관계를 포함하면 총 13가지 기본 관계가 구성된다.

4. 선행 관계의 확장

4.1 조건부 선행 관계(Conditional Precedence)

기본 선행 관계는 무조건적(unconditional)이나, 실제 임무에서는 특정 조건이 충족될 때에만 선행 관계가 성립하는 조건부 선행 관계가 필요하다:

\phi(\mathbf{x}) \implies (\tau_i \prec \tau_j)

여기서 \phi(\mathbf{x})는 시스템 상태 \mathbf{x}에 대한 논리적 술어(predicate)이다. 예를 들어, 특정 센서가 이상 징후를 감지한 경우에만 추가 검사 과업이 선행 과업으로 삽입되는 경우가 이에 해당한다.

4.2 선택적 선행 관계(Alternative Precedence)

복수의 선행 과업 중 하나만 완료되면 후행 과업을 시작할 수 있는 경우:

\bigvee_{i \in \mathcal{S}} (\tau_i \prec \tau_j) \quad \text{(OR 관계)}

모든 선행 과업이 완료되어야 후행 과업을 시작할 수 있는 경우:

\bigwedge_{i \in \mathcal{S}} (\tau_i \prec \tau_j) \quad \text{(AND 관계)}

AND 관계는 동기화 지점(synchronization point)을 형성하며, 다중 로봇 시스템에서 여러 로봇의 부분 과업이 완료된 후 합류(rendezvous)하는 경우에 적용된다.

4.3 소프트 선행 관계(Soft Precedence)

경성 선행 관계(hard precedence)를 위반할 수 없는 반면, 소프트 선행 관계는 위반 시 페널티가 부여되나 실현 가능성이 유지되는 관계이다:

\min \left[ C_{\max} + \sum_{(\tau_i, \tau_j) \in \mathcal{P}_{\text{soft}}} \lambda_{ij} \cdot \max(0, s_j - e_i) \right]

이는 과잉 제약 상황에서 유연한 스케줄링을 가능하게 한다.

5. 선행 관계의 분석

5.1 위상 정렬(Topological Sorting)

선행 관계 DAG에 대한 위상 정렬은 모든 선행 관계를 만족하는 과업의 선형 순서(linear order)를 생성한다. 위상 정렬의 결과는 일반적으로 유일하지 않으며, 가능한 위상 정렬의 수는 DAG의 구조에 의존한다. 위상 정렬은 O(|\mathcal{T}| + |\mathcal{P}|)의 시간 복잡도로 계산 가능하다.

5.2 임계 경로(Critical Path) 분석

임계 경로법(Critical Path Method, CPM)은 선행 관계 제약 하에서 전체 임무의 최소 완료 시간(makespan)을 결정하는 방법이다. 임계 경로는 DAG 상의 최장 경로(longest path)에 해당하며, 임계 경로 상의 과업은 지연이 즉시 전체 임무의 지연으로 전파되므로 가장 높은 시간적 민감도를 가진다.

과업 \tau_i의 최조 시작 시점(earliest start time) \text{ES}_i와 최만 시작 시점(latest start time) \text{LS}_i는 다음의 전진 패스(forward pass)와 후진 패스(backward pass)를 통하여 계산된다:

전진 패스(Forward Pass):

\text{ES}_i = \max_{\tau_k \prec \tau_i} \left( \text{ES}_k + d_k \right)

후진 패스(Backward Pass):

\text{LS}_i = \min_{\tau_i \prec \tau_k} \left( \text{LS}_k \right) - d_i

여기서 d_i는 과업 \tau_i의 소요 시간(duration)이다. 과업 \tau_i의 여유 시간(slack 또는 float)은:

\text{Slack}_i = \text{LS}_i - \text{ES}_i

여유 시간이 0인 과업들이 임계 경로를 구성한다.

5.3 PERT 기반 확률적 분석

과업 소요 시간이 확률적인 경우, PERT(Program Evaluation and Review Technique)를 적용하여 임계 경로의 확률적 분포를 추정할 수 있다. 과업 \tau_i의 소요 시간이 베타 분포(beta distribution)를 따를 때, 기대값과 분산은:

\mu_i = \frac{a_i + 4m_i + b_i}{6}, \quad \sigma_i^2 = \left(\frac{b_i - a_i}{6}\right)^2

여기서 a_i는 낙관적(optimistic) 추정, m_i는 최빈(most likely) 추정, b_i는 비관적(pessimistic) 추정이다. 중심 극한 정리에 의하여, 임계 경로 상의 과업 소요 시간의 합은 근사적으로 정규 분포를 따른다.

6. 다중 로봇 임무에서의 선행 관계

6.1 로봇 간 동기화 제약

다중 로봇 시스템에서는 로봇 간의 과업 수행 순서에 대한 선행 관계가 필요하다. 로봇 R_a의 과업 \tau_i^{(a)}가 로봇 R_b의 과업 \tau_j^{(b)}에 선행하는 경우:

e_i^{(a)} \leq s_j^{(b)}

이러한 로봇 간 선행 관계는 과업의 산출물(output)을 다른 로봇에 전달하는 핸드오프(handoff) 시나리오, 협력 조립(cooperative assembly), 탐색-개입(search-and-engage) 작전 등에서 발생한다.

6.2 합류 제약(Rendezvous Constraint)

복수의 로봇이 특정 시점과 장소에서 합류하여야 하는 제약은 다중 AND 선행 관계와 시공간 제약의 결합이다:

\forall a \in \mathcal{A}_{\text{rdv}}: \quad e_{\text{approach}}^{(a)} \leq t_{\text{rdv}} \wedge \mathbf{q}^{(a)}(t_{\text{rdv}}) = \mathbf{q}_{\text{rdv}}

여기서 \mathcal{A}_{\text{rdv}}는 합류에 참여하는 로봇의 집합, t_{\text{rdv}}는 합류 시점, \mathbf{q}_{\text{rdv}}는 합류 위치이다.

7. 선행 관계 제약의 표현과 구현

7.1 인접 행렬(Adjacency Matrix) 표현

선행 관계 DAG는 인접 행렬 \mathbf{A} \in \{0, 1\}^{n \times n}로 표현할 수 있다:

A_{ij} = \begin{cases} 1 & \text{if } \tau_i \prec \tau_j \\ 0 & \text{otherwise} \end{cases}

추이적 폐포(transitive closure) 행렬 \mathbf{A}^*는 도달 가능성(reachability)을 나타내며, 워셜-플로이드(Warshall-Floyd) 알고리즘으로 O(n^3)에 계산된다.

7.2 인접 리스트(Adjacency List) 표현

과업 수에 비하여 선행 관계의 수가 적은 희소(sparse) 그래프에서는 인접 리스트가 메모리 효율적이다. 각 과업 \tau_i에 대하여 후행 과업의 리스트 \text{succ}(\tau_i)와 선행 과업의 리스트 \text{pred}(\tau_i)를 유지한다.

7.3 순환 검출(Cycle Detection)

선행 관계의 추가 시 순환(cycle)의 발생을 검출하여야 한다. 깊이 우선 탐색(Depth-First Search, DFS) 기반의 순환 검출은 O(|\mathcal{T}| + |\mathcal{P}|)의 시간 복잡도를 가진다. 순환이 검출되면 해당 선행 관계의 추가를 거부하거나, 순환에 포함된 과업들을 단일 복합 과업(compound task)으로 통합하는 방법이 적용된다.

8. 참고문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms. 3rd Edition, MIT Press.
• Kelley, J. E. and Walker, M. R. (1959). “Critical-Path Planning and Scheduling.” Proceedings of the Eastern Joint IRE-AIMS-ACM Computer Conference, 160–173.
• Allen, J. F. (1983). “Maintaining Knowledge about Temporal Intervals.” Communications of the ACM, 26(11), 832–843.
• Dechter, R., Meiri, I., and Pearl, J. (1991). “Temporal Constraint Networks.” Artificial Intelligence, 49(1–3), 61–95.
• Brucker, P., Drexl, A., Möhring, R., Neumann, K., and Pesch, E. (1999). “Resource-Constrained Project Scheduling: Notation, Classification, Models, and Methods.” European Journal of Operational Research, 112(1), 3–41.
• 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