397.60 위상 정렬(Topological Sort) 기반 임무 순서 결정

1. 개요

자율 로봇 시스템의 임무 계획에서 개별 작업(task) 간에는 선후 관계(precedence relation)가 존재하는 경우가 빈번하다. 특정 작업은 다른 작업이 완료된 후에만 실행 가능하며, 이러한 의존성 구조는 방향 비순환 그래프(Directed Acyclic Graph, DAG)로 자연스럽게 모델링된다. **위상 정렬(topological sort)**은 DAG의 정점들을 모든 간선의 방향이 보존되도록 선형으로 배열하는 알고리즘으로서, 임무 간 선후 관계 제약을 위반하지 않는 유효한 실행 순서를 체계적으로 결정하는 핵심 도구이다.

본 절에서는 위상 정렬의 수학적 기초, 대표 알고리즘, 임무 계획에서의 적용 방법론, 그리고 확장 기법을 상세히 다룬다.

2. 위상 정렬의 수학적 기초

2.1 선후 관계와 방향 비순환 그래프

임무 집합 $T = \{\tau_1, \tau_2, \ldots, \tau_n\}$ 에 대해, 임무 $\tau_i$ 가 임무 $\tau_j$ 보다 먼저 수행되어야 한다는 선후 관계를 $\tau_i \prec \tau_j$ 로 표기한다. 이 관계는 반사적(reflexive)이지 않고 추이적(transitive)이며 반대칭적(antisymmetric)인 **엄격 반순서(strict partial order)**를 형성한다.

선후 관계 집합 $\mathcal{P} = \{(\tau_i, \tau_j) \mid \tau_i \prec \tau_j\}$ 는 방향 비순환 그래프 $G = (V, E)$ 로 표현된다.

$V = T, \quad E = \{(\tau_i, \tau_j) \mid \tau_i \prec \tau_j\}$

DAG의 비순환(acyclic) 조건은 임무 간 순환 의존성이 존재하지 않음을 보장하며, 이는 유효한 임무 실행 순서가 존재하기 위한 필요충분조건이다.

정리 (위상 정렬 존재 조건): 방향 그래프 $G = (V, E)$ 에 대해 위상 정렬이 존재할 필요충분조건은 $G$ 가 비순환(acyclic)인 것이다.

2.2 위상 정렬의 형식적 정의

DAG $G = (V, E)$ 의 위상 정렬(topological ordering)은 정점 집합 $V$ 에 대한 전순서(total order) $\sigma: V \rightarrow \{1, 2, \ldots, |V|\}$ 로서, 다음 조건을 만족하는 단사 함수이다.

$\forall (u, v) \in E: \sigma(u) < \sigma(v)$

즉, 모든 간선 $(u, v)$ 에 대해 시작 정점 $u$ 가 종료 정점 $v$ 보다 앞에 위치하도록 정점을 배열한다. 일반적으로 위상 정렬의 결과는 유일하지 않으며, 선후 관계가 미지정된 작업 쌍의 배치에 따라 다수의 유효한 순서가 존재할 수 있다.

2.3 고유 위상 정렬의 조건

위상 정렬이 고유(unique)하려면, DAG가 **해밀턴 경로(Hamiltonian path)**를 포함해야 한다. 즉, 모든 정점 쌍 사이에 직접적 또는 간접적 선후 관계가 정의되어야 한다. 이 조건은 선후 관계가 엄격 전순서(strict total order)를 형성하는 것과 동치이다.

3. 위상 정렬 알고리즘

3.1 Kahn 알고리즘 (BFS 기반)

Kahn(1962)이 제안한 알고리즘은 진입 차수(in-degree)가 0인 정점을 반복적으로 제거하는 방식으로 위상 정렬을 수행한다.

알고리즘: Kahn’s Topological Sort

입력: DAG G = (V, E)
출력: 위상 정렬된 정점 리스트 L

1.  각 정점 v ∈ V의 진입 차수 in[v] 계산
2.  큐 Q ← {v ∈ V | in[v] = 0}
3.  L ← []
4.  while Q ≠ ∅ do:
      u ← Q.Dequeue()
      L.append(u)
      각 간선 (u, w) ∈ E에 대해:
          in[w] ← in[w] - 1
          if in[w] = 0 then:
              Q.Enqueue(w)
5.  if |L| ≠ |V| then:
      순환 의존성 존재 → 오류 보고
6.  return L

시간 복잡도: $O(|V| + |E|)$

공간 복잡도: $O(|V|)$

Kahn 알고리즘은 순환 의존성 검출 기능을 내장하고 있어, 알고리즘 종료 시점에 $|L| < |V|$ 이면 그래프에 순환이 존재함을 즉시 판별할 수 있다.

3.2 DFS 기반 위상 정렬

깊이 우선 탐색(Depth-First Search, DFS)을 활용한 위상 정렬은 각 정점의 완료 시점(finish time)을 기록하고, 완료 시점의 역순으로 정점을 배열하는 방식이다.

알고리즘: DFS-based Topological Sort

입력: DAG G = (V, E)
출력: 위상 정렬된 정점 리스트 L

1.  visited ← ∅, L ← [], in_progress ← ∅
2.  각 정점 v ∈ V에 대해:
      if v ∉ visited then:
          DFS-Visit(v)
3.  L.Reverse()
4.  return L

DFS-Visit(v):
    in_progress ← in_progress ∪ {v}
    각 인접 정점 w ∈ adj(v)에 대해:
        if w ∈ in_progress then:
            순환 의존성 존재 → 오류 보고
        if w ∉ visited then:
            DFS-Visit(w)
    in_progress ← in_progress \ {v}
    visited ← visited ∪ {v}
    L.append(v)

시간 복잡도: $O(|V| + |E|)$

공간 복잡도: $O(|V|)$ (재귀 호출 스택 포함)

DFS 기반 방식은 재귀적 구조로 인해 구현이 직관적이지만, 깊은 의존성 체인이 존재하는 경우 스택 오버플로의 위험이 있으므로, 반복적(iterative) 구현이나 명시적 스택 사용을 고려해야 한다.

3.3 두 알고리즘의 비교

특성	Kahn 알고리즘	DFS 기반 알고리즘
탐색 전략	BFS (너비 우선)	DFS (깊이 우선)
순환 검출	내장	추가 구현 필요 (`in_progress` 집합)
병렬화 적합성	높음 (진입 차수 0인 정점 동시 처리)	낮음 (순차적 재귀)
스택 오버플로 위험	없음	있음 (깊은 그래프)
구현 복잡도	낮음	중간
결정론적 순서	큐 정책에 의존	탐색 순서에 의존

4. 임무 계획에서의 위상 정렬 적용

4.1 임무 의존성 그래프 구성

로봇 임무 계획에서 위상 정렬을 적용하기 위해서는 먼저 임무 간 의존성을 정확히 식별하고 그래프로 구성해야 한다. 의존성의 유형은 다음과 같이 분류된다.

완료-시작 의존성(Finish-to-Start, FS): 가장 일반적인 의존성으로, 선행 임무가 완료된 후에 후속 임무가 시작될 수 있다.

$\text{start}(\tau_j) \geq \text{finish}(\tau_i), \quad (\tau_i, \tau_j) \in E$

완료-완료 의존성(Finish-to-Finish, FF): 선행 임무의 완료 전에 후속 임무가 완료될 수 없다.

$\text{finish}(\tau_j) \geq \text{finish}(\tau_i), \quad (\tau_i, \tau_j) \in E$

시작-시작 의존성(Start-to-Start, SS): 선행 임무의 시작 전에 후속 임무가 시작될 수 없다.

$\text{start}(\tau_j) \geq \text{start}(\tau_i), \quad (\tau_i, \tau_j) \in E$

단순 위상 정렬은 FS 의존성에 직접 적용 가능하며, FF 및 SS 의존성은 적절한 그래프 변환을 통해 FS 형태로 환원할 수 있다.

4.2 다중 유효 순서에서의 최적 순서 선택

위상 정렬의 결과가 유일하지 않은 경우, 다수의 유효한 순서 중에서 추가적인 최적화 기준에 따라 최선의 순서를 선택할 수 있다. 이를 위해 Kahn 알고리즘의 큐를 우선순위 큐로 대체하는 방법이 널리 사용된다.

동일한 위상 레벨(동일 진입 차수 시점)에 있는 임무들 사이에서 우선순위 함수 $f(\tau)$ 에 따라 선택함으로써, 선후 관계를 준수하면서도 부가적 최적화 목표를 달성할 수 있다. 예를 들어, 다음과 같은 최적화 기준이 적용 가능하다.

총 이동 거리 최소화: 현재 로봇 위치로부터 각 후보 임무 위치까지의 거리를 기준으로 우선순위를 부여한다.
마감 시한 우선: 마감 시한이 임박한 임무에 높은 우선순위를 부여한다.
자원 효율 최대화: 현재 가용 자원에 가장 적합한 임무를 우선적으로 선택한다.

4.3 임계 경로 분석과의 결합

위상 정렬은 **임계 경로 방법(Critical Path Method, CPM)**과 결합하여 임무 완료에 필요한 최소 시간을 산출하는 데 활용된다. 각 임무 $\tau_i$ 에 실행 시간 $c_i$ 가 부여된 경우, 위상 정렬 순서에 따라 다음을 계산한다.

최조 시작 시간(Earliest Start Time, EST):

$\text{EST}(\tau_i) = \max_{(\tau_j, \tau_i) \in E} \left[ \text{EST}(\tau_j) + c_j \right]$

진입 간선이 없는 임무(소스 정점)의 경우 $\text{EST}(\tau_i) = 0$ 이다.

최조 완료 시간(Earliest Finish Time, EFT):

$\text{EFT}(\tau_i) = \text{EST}(\tau_i) + c_i$

임계 경로(Critical Path): 전체 프로젝트 완료 시간 $\text{makespan} = \max_{\tau_i \in T} \text{EFT}(\tau_i)$ 을 결정하는 경로로, 이 경로 상의 모든 임무는 여유 시간(slack)이 0이다.

최지 시작 시간(Latest Start Time, LST):

$\text{LST}(\tau_i) = \min_{(\tau_i, \tau_j) \in E} \left[ \text{LST}(\tau_j) \right] - c_i$

여유 시간(Total Float):

$\text{TF}(\tau_i) = \text{LST}(\tau_i) - \text{EST}(\tau_i)$

여유 시간이 0인 임무들의 집합이 임계 경로를 형성하며, 이 임무들의 지연은 전체 임무 완료 시간을 직접적으로 증가시킨다.

5. 순환 의존성의 검출과 해결

5.1 순환 의존성 검출

임무 의존성 그래프에 순환이 존재하는 경우 위상 정렬이 불가능하며, 이는 논리적 모순을 의미한다. 순환 검출은 다음 방법으로 수행한다.

Kahn 알고리즘 기반: 알고리즘 종료 후 처리되지 않은 정점이 남아 있으면 순환이 존재한다.
DFS 기반: 탐색 과정에서 현재 경로 상의 정점으로 되돌아가는 **역방향 간선(back edge)**이 발견되면 순환이 존재한다.
강연결 요소(Strongly Connected Components, SCC) 분석: Tarjan 알고리즘이나 Kosaraju 알고리즘을 사용하여 크기가 2 이상인 SCC를 식별함으로써 순환 구조를 정확히 파악한다.

5.2 순환 의존성 해결 전략

임무 계획 과정에서 순환 의존성이 감지된 경우, 다음 전략을 통해 해결할 수 있다.

의존성 완화(Dependency Relaxation): 순환에 관여하는 간선 중 가장 약한 의존성을 제거하여 순환을 해소한다. 간선 제거의 비용 함수 $w(e)$ 를 정의하고, 최소 비용으로 순환을 해소하는 최소 피드백 간선 집합(Minimum Feedback Arc Set)을 구한다.

$\min_{S \subseteq E} \sum_{e \in S} w(e) \quad \text{s.t.} \quad G' = (V, E \setminus S) \text{ is acyclic}$

이 문제는 NP-난해(NP-hard)이지만, 탐욕적 근사 알고리즘이나 정수 선형 계획법(Integer Linear Programming, ILP)으로 실용적인 해를 구할 수 있다.

임무 병합(Task Merging): 상호 의존적인 임무들을 하나의 복합 임무로 병합하여 순환을 제거한다.

조건부 순서(Conditional Ordering): 런타임 조건에 따라 실행 순서를 동적으로 결정하도록 설계하여, 정적 순환 의존성을 회피한다.

6. 동적 위상 정렬

6.1 증분 위상 정렬 알고리즘

자율 로봇 시스템에서는 런타임에 새로운 임무가 추가되거나 기존 의존성이 변경되는 경우가 빈번하다. 이러한 상황에서 전체 그래프를 대상으로 위상 정렬을 재수행하는 것은 비효율적이므로, 증분 위상 정렬(incremental topological sort) 알고리즘이 요구된다.

Marchetti-Spaccamela et al.(1996)이 제안한 알고리즘은 간선 삽입 시 영향 받는 정점만을 대상으로 부분적 재정렬을 수행한다.

간선 삽입 $(u, v)$ 처리:

현재 위상 순서에서 $\sigma(u) < \sigma(v)$ 이면 순서 변경이 불필요하다.
$\sigma(u) > \sigma(v)$ 이면, $v$ 에서 $u$ 까지의 경로가 존재하는지 검사한다.

경로가 존재하면 순환이 발생하므로 간선 삽입을 거부한다.
경로가 존재하지 않으면, 영향 받는 정점들의 순서를 갱신한다.

Pearce & Kelly(2007)는 $O(\min(m^{1/2}, \delta_d) \cdot \delta_a)$ 의 상각 시간 복잡도를 달성하는 알고리즘을 제안하였다. 여기서 $\delta_d$ 와 $\delta_a$ 는 각각 영향 받는 정점의 수와 간선의 수이다.

6.2 온라인 임무 시퀀싱에의 적용

온라인 환경에서의 임무 시퀀싱은 다음 절차를 따른다.

초기 임무 집합에 대해 정적 위상 정렬을 수행한다.
새로운 임무 $\tau_{\text{new}}$ 가 도착하면:

$\tau_{\text{new}}$ 와 기존 임무 간의 의존 관계를 파악한다.
증분 위상 정렬을 통해 $\tau_{\text{new}}$ 를 기존 순서에 삽입한다.

임무 완료 또는 취소 시:

해당 임무와 관련된 간선을 제거한다.
후속 임무의 진입 차수를 갱신한다.

7. 병렬 임무 실행을 위한 위상 정렬

7.1 위상 레벨과 병렬 실행

DAG의 위상 레벨(topological level)은 동시에 실행 가능한 임무 집합을 식별하는 데 활용된다. 정점 $v$ 의 위상 레벨 $\ell(v)$ 는 소스 정점으로부터 $v$ 까지의 최장 경로 길이로 정의된다.

$\ell(v) = \begin{cases} 0 & \text{if } v \text{ has no predecessors} \\ \max_{(u,v) \in E} \left[ \ell(u) + 1 \right] & \text{otherwise} \end{cases}$

동일 위상 레벨의 임무들은 상호 의존 관계가 없으므로 병렬로 실행 가능하다. 다중 로봇 시스템에서는 각 레벨의 임무들을 가용 로봇에 분배하여 동시 수행함으로써 전체 완료 시간을 단축할 수 있다.

최대 병렬도(maximum parallelism)는 최대 위상 레벨 폭(width)으로 결정된다.

$\text{max\_parallelism} = \max_{l} |\{v \in V \mid \ell(v) = l\}|$

7.2 다중 로봇 임무 할당과의 결합

위상 레벨별 병렬 실행 가능 임무 집합이 식별되면, 각 레벨 내에서 다중 로봇 간의 임무 할당 문제를 해결해야 한다. 이는 일반적으로 다음과 같이 정식화된다.

$\min \max_{r \in R} \sum_{\tau_i \in T_r} c_i$

여기서 $R$ 은 로봇 집합, $T_r$ 은 로봇 $r$ 에 할당된 임무 집합, $c_i$ 는 임무 $\tau_i$ 의 실행 시간이다. 이 문제는 최소 메이크스팬 스케줄링(minimum makespan scheduling) 문제와 동치이며, NP-난해이다. 그러나 목록 스케줄링(list scheduling)과 같은 탐욕적 근사 알고리즘은 $(2 - 1/m)$ -근사 비율을 보장한다(Graham, 1969). 여기서 $m$ 은 로봇의 수이다.

8. 실용적 고려사항

8.1 대규모 임무 그래프의 효율적 처리

수천 개 이상의 임무로 구성된 대규모 의존성 그래프에서는 메모리 효율성과 처리 속도가 중요하다. 다음 최적화 기법이 적용 가능하다.

인접 리스트(Adjacency List) 표현: 희소 그래프에 적합하며, 공간 복잡도 $O(|V| + |E|)$ 를 보장한다.
정점 축소(Vertex Contraction): 직렬 연쇄(serial chain) 구조의 정점들을 하나의 슈퍼 정점으로 축약하여 그래프의 크기를 줄인다.
분할 정복(Divide and Conquer): 그래프를 독립적인 부분 그래프로 분할하고, 각 부분 그래프에 대해 독립적으로 위상 정렬을 수행한 후 결과를 병합한다.

8.2 의존성 명세의 완전성 검증

위상 정렬의 정확성은 의존성 그래프의 완전성에 의존한다. 누락된 의존성은 임무 실행 시 충돌이나 오류를 유발할 수 있으므로, 다음 검증 절차를 수행한다.

자원 충돌 분석: 동일 자원을 사용하는 독립 임무들 사이에 암묵적 의존성이 존재하는지 확인한다.
시간 제약 일관성 검증: 의존성 그래프에서 도출된 최소 실행 시간이 마감 시한 제약과 양립 가능한지 검증한다.
전이적 축소(Transitive Reduction): 중복 간선을 제거하여 의존성 그래프를 최소 형태로 정리하면, 그래프의 가독성과 유지보수성이 향상된다.

전이적 축소는 그래프 $G$ 에서 전이적으로 도달 가능한 간선 중 불필요한 직접 간선을 제거하는 연산이다.

$G^* = (V, E^*), \quad E^* = E \setminus \{(u, v) \in E \mid \exists \text{ path } u \rightarrow \cdots \rightarrow v \text{ in } (V, E \setminus \{(u,v)\})\}$

전이적 축소의 시간 복잡도는 $O(|V| \cdot |E|)$ 이며, 일반적으로 전처리 단계에서 수행된다.

9. 참고 문헌

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Graham, R. L. (1969). “Bounds on Multiprocessing Timing Anomalies.” SIAM Journal on Applied Mathematics, 17(2), 416–429.
Kahn, A. B. (1962). “Topological Sorting of Large Networks.” Communications of the ACM, 5(11), 558–562.
Marchetti-Spaccamela, A., Nanni, U., & Rohnert, H. (1996). “Maintaining a Topological Order under Edge Insertions.” Information Processing Letters, 59(1), 53–58.
Pearce, D. J., & Kelly, P. H. J. (2007). “A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs.” Journal of Experimental Algorithmics, 11, Article 1.7.