397.59 우선순위 큐 기반 임무 시퀀싱

1. 개요

자율 로봇 시스템이 수행해야 하는 다수의 임무 항목(task item)은 일반적으로 서로 다른 긴급도(urgency), 중요도(importance), 시간 제약(temporal constraint) 등을 가진다. 이러한 이질적 특성을 가진 임무들을 효율적으로 정렬하고 실행 순서를 결정하는 문제를 **임무 시퀀싱(mission sequencing)**이라 한다. 우선순위 큐(priority queue)는 각 원소에 우선순위를 부여하고, 항상 가장 높은 우선순위를 가진 원소를 먼저 추출하는 추상 자료구조로서, 임무 시퀀싱 문제를 체계적으로 해결하는 핵심 메커니즘으로 광범위하게 활용된다.

본 절에서는 우선순위 큐의 자료구조적 기반, 우선순위 산정 기법, 동적 우선순위 갱신 메커니즘, 그리고 로봇 임무 계획에서의 구체적 적용 방법론을 체계적으로 다룬다.

2. 우선순위 큐의 자료구조적 기초

2.1 정의와 기본 연산

우선순위 큐는 다음과 같은 기본 연산을 지원하는 추상 자료형(Abstract Data Type, ADT)이다.

삽입(Insert): 우선순위 $p$ 를 가진 원소 $e$ 를 큐에 추가한다.
최솟값/최댓값 추출(Extract-Min/Extract-Max): 큐에서 가장 높은 우선순위(최소값 또는 최대값)를 가진 원소를 제거하고 반환한다.
피크(Peek): 가장 높은 우선순위를 가진 원소를 제거하지 않고 조회한다.
우선순위 갱신(Decrease-Key/Increase-Key): 특정 원소의 우선순위를 변경한다.

형식적으로, 우선순위 큐 $\mathcal{Q}$ 는 원소-우선순위 쌍의 집합 $\{(e_i, p_i)\}_{i=1}^{n}$ 으로 정의되며, 추출 연산은 다음을 만족한다.

$\text{Extract-Min}(\mathcal{Q}) = \arg\min_{(e_i, p_i) \in \mathcal{Q}} p_i$

2.2 구현 자료구조와 시간 복잡도

우선순위 큐는 다양한 자료구조로 구현할 수 있으며, 각 구현 방식에 따라 연산의 시간 복잡도가 상이하다.

자료구조	Insert	Extract-Min	Decrease-Key	Merge
비정렬 배열	$O(1)$	$O(n)$	$O(1)$	$O(1)$
정렬 배열	$O(n)$	$O(1)$	$O(n)$	$O(n)$
이진 힙(Binary Heap)	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$
이항 힙(Binomial Heap)	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$
피보나치 힙(Fibonacci Heap)	$O(1)^*$	$O(\log n)^*$	$O(1)^*$	$O(1)^*$
페어링 힙(Pairing Heap)	$O(1)^*$	$O(\log n)^*$	$o(\log n)^*$	$O(1)^*$

위 표에서 $^*$ 는 상각 분석(amortized analysis) 기준의 시간 복잡도를 나타낸다.

로봇 임무 시퀀싱에서는 동적으로 새로운 임무가 추가되거나 기존 임무의 우선순위가 빈번하게 변경되므로, Decrease-Key 연산의 효율성이 특히 중요하다. 이러한 요구사항을 고려할 때 피보나치 힙 또는 페어링 힙이 이론적으로 우수한 성능을 제공하며, 실무적으로는 구현의 단순성과 캐시 성능을 고려하여 이진 힙이 널리 채택된다.

3. 임무 우선순위 산정 기법

3.1 단일 기준 우선순위

가장 기본적인 우선순위 산정 방식은 단일 속성을 기준으로 임무의 실행 순서를 결정하는 것이다. 대표적인 단일 기준 정책은 다음과 같다.

마감 시한 기반 우선순위(Deadline-Based Priority): 각 임무 $\tau_i$ 에 마감 시한 $d_i$ 가 부여되며, 마감 시한이 임박한 임무일수록 높은 우선순위를 가진다.

$p_i = -d_i \quad \text{(최소 힙 기준)}$

이 정책은 Earliest Deadline First(EDF) 스케줄링과 동일한 원리를 따르며, 단일 프로세서 환경에서 마감 시한 충족 가능성이 존재하는 경우 최적의 스케줄을 보장한다(Liu & Layland, 1973).

긴급도 기반 우선순위(Urgency-Based Priority): 임무의 여유 시간(slack time) $s_i = d_i - t_{\text{current}} - C_i$ 를 기반으로 산정된다. 여기서 $C_i$ 는 임무 $\tau_i$ 의 예상 실행 시간이다.

$p_i = \frac{1}{s_i + \epsilon}$

$\epsilon$ 은 영분모(division-by-zero)를 방지하기 위한 미소 상수이다.

가치 기반 우선순위(Value-Based Priority): 각 임무의 달성이 전체 임무 목표에 기여하는 가치 $v_i$ 에 따라 우선순위를 부여한다.

$p_i = v_i$

3.2 다중 기준 우선순위 통합

실제 로봇 임무 환경에서는 단일 기준만으로 적절한 임무 순서를 결정하기 어려운 경우가 빈번하다. 다중 기준 우선순위 통합에서는 복수의 속성을 종합적으로 고려하여 최종 우선순위를 산출한다.

가중 합 방식(Weighted Sum Method): $k$ 개의 기준 속성 $\{a_1, a_2, \ldots, a_k\}$ 에 대해 가중치 $\{w_1, w_2, \ldots, w_k\}$ 를 부여하고, 최종 우선순위를 다음과 같이 계산한다.

$p_i = \sum_{j=1}^{k} w_j \cdot \hat{a}_{ij}$

여기서 $\hat{a}_{ij}$ 는 기준 $j$ 에 대한 임무 $i$ 의 정규화된 속성값이다. 정규화는 각 속성의 스케일 차이를 제거하기 위해 수행된다.

$\hat{a}_{ij} = \frac{a_{ij} - a_j^{\min}}{a_j^{\max} - a_j^{\min}}$

사전식 순서(Lexicographic Ordering): 기준 속성 간에 절대적인 우선 관계가 존재할 때 사용한다. 기준 $a_1$ 이 $a_2$ 보다 절대적으로 우선하는 경우, $a_1$ 이 동일한 임무들에 대해서만 $a_2$ 를 비교한다.

$\tau_i \succ \tau_j \iff \exists m \leq k : \left( \forall l < m,\, a_{il} = a_{jl} \right) \land \left( a_{im} > a_{jm} \right)$

분석적 계층 과정(Analytic Hierarchy Process, AHP): 기준 간의 쌍대 비교(pairwise comparison)를 통해 상대적 가중치를 도출하는 체계적 방법론이다. 쌍대 비교 행렬 $\mathbf{A} = [a_{ij}]_{k \times k}$ 에서 고유벡터를 추출하여 가중치 벡터 $\mathbf{w}$ 를 산출한다.

$\mathbf{A} \mathbf{w} = \lambda_{\max} \mathbf{w}$

AHP는 일관성 비율(Consistency Ratio, CR)을 통해 비교 판단의 논리적 일관성을 검증하며, 일반적으로 $\text{CR} < 0.1$ 을 만족해야 신뢰할 수 있는 가중치로 간주한다(Saaty, 1980).

4. 동적 우선순위 갱신 메커니즘

4.1 시간 의존적 우선순위 감쇄

정적으로 부여된 우선순위는 시간이 경과함에 따라 임무의 실질적 중요도를 적절히 반영하지 못하는 한계가 있다. 동적 우선순위 갱신은 시간 경과, 환경 변동, 로봇 상태 변화 등에 따라 우선순위를 실시간으로 재조정하는 메커니즘이다.

에이징(Aging) 기법: 오래 대기한 임무의 우선순위를 점진적으로 상승시켜 기아(starvation) 현상을 방지한다. 시간 $t$ 에서의 임무 $\tau_i$ 의 동적 우선순위는 다음과 같이 갱신된다.

$p_i(t) = p_i^{(0)} + \alpha \cdot (t - t_i^{\text{enqueue}})$

여기서 $p_i^{(0)}$ 는 초기 우선순위, $t_i^{\text{enqueue}}$ 는 큐에 삽입된 시점, $\alpha > 0$ 는 에이징 계수이다.

마감 시한 접근에 따른 긴급도 증가: 마감 시한 $d_i$ 에 가까워질수록 우선순위를 비선형적으로 증가시킨다.

$p_i(t) = p_i^{(0)} \cdot \exp\left(\frac{\beta}{d_i - t}\right), \quad t < d_i$

$\beta > 0$ 는 긴급도 스케일링 파라미터이다. 이 함수는 마감 시한에 근접할수록 급격히 증가하는 특성을 가진다.

4.2 이벤트 구동 우선순위 재산정

시간 의존적 갱신 외에도, 외부 이벤트 발생 시 우선순위를 재산정하는 메커니즘이 필요하다.

환경 변동 이벤트: 장애물 출현, 기상 조건 변화, 적대적 위협 감지 등의 환경 변동이 발생하면, 관련 임무의 우선순위를 즉시 재산정한다. 환경 상태 $\mathbf{e}(t)$ 에 대한 우선순위 함수는 다음과 같이 정의할 수 있다.

$p_i(t) = f\bigl(p_i^{(0)},\, \mathbf{e}(t),\, \mathbf{s}_{\text{robot}}(t)\bigr)$

여기서 $\mathbf{s}_{\text{robot}}(t)$ 는 로봇의 현재 상태 벡터(위치, 잔여 에너지, 탑재 장비 상태 등)이다.

임무 의존성 기반 연쇄 갱신: 임무 간 의존 관계가 존재하는 경우, 특정 임무의 완료 또는 실패가 후속 임무의 우선순위에 영향을 미친다. 임무 의존성 그래프 $G = (V, E)$ 에서 임무 $\tau_j$ 가 완료되면, 모든 후속 임무 $\tau_k \in \text{succ}(\tau_j)$ 에 대해 우선순위를 재산정한다.

$p_k \leftarrow p_k + \Delta p_k(\tau_j), \quad \forall \tau_k \in \text{succ}(\tau_j)$

5. 우선순위 큐 기반 임무 시퀀싱 알고리즘

5.1 기본 시퀀싱 알고리즘

우선순위 큐를 활용한 기본 임무 시퀀싱 절차는 다음과 같다.

알고리즘: PriorityQueueMissionSequencing

입력: 임무 집합 T = {τ₁, τ₂, ..., τₙ}, 우선순위 함수 f(·)
출력: 임무 실행 순서 σ

1.  초기화: 우선순위 큐 Q ← ∅, 실행 순서 σ ← []
2.  각 임무 τᵢ ∈ T에 대해:
      pᵢ ← f(τᵢ)
      Q.Insert(τᵢ, pᵢ)
3.  while Q ≠ ∅ do:
      τ* ← Q.Extract-Min()
      if Feasible(τ*) then:
          σ.append(τ*)
          Execute(τ*)
          UpdateDependencies(τ*, Q)
      else:
          Defer(τ*, Q)  // 실행 불가 시 우선순위 재산정 후 재삽입
4.  return σ

이 알고리즘의 시간 복잡도는 이진 힙 기반 구현 시 $O(n \log n)$ 이다.

5.2 선후 관계 제약을 포함한 시퀀싱

임무 간 선후 관계(precedence constraint)가 주어진 경우, 우선순위 큐 기반 시퀀싱은 위상 정렬과 결합되어야 한다. 선행 임무가 모두 완료된 임무만 우선순위 큐에 삽입 가능하도록 제어하는 방식을 채택한다.

알고리즘: PrecedenceConstrainedSequencing

입력: 임무 집합 T, 선후 관계 그래프 G = (T, E), 우선순위 함수 f(·)
출력: 유효한 임무 실행 순서 σ

1.  각 임무 τᵢ의 진입 차수(in-degree) dᵢ 계산
2.  Q ← ∅
3.  dᵢ = 0인 모든 τᵢ에 대해:
      Q.Insert(τᵢ, f(τᵢ))
4.  while Q ≠ ∅ do:
      τ* ← Q.Extract-Min()
      σ.append(τ*)
      각 후속 임무 τⱼ ∈ succ(τ*) 에 대해:
          dⱼ ← dⱼ - 1
          if dⱼ = 0 then:
              Q.Insert(τⱼ, f(τⱼ))
5.  if |σ| < |T| then:
      순환 의존성 존재 → 오류 보고
6.  return σ

이 알고리즘은 위상 정렬의 Kahn 알고리즘에 우선순위 큐를 도입한 변형으로, 동일한 위상 레벨 내에서 우선순위 기반 정렬을 수행한다. 시간 복잡도는 $O((n + m) \log n)$ 이며, 여기서 $m = |E|$ 는 선후 관계 간선의 수이다.

5.3 자원 제약 하의 시퀀싱

로봇 시스템의 자원(에너지, 통신 대역폭, 탑재 용량 등)이 제한적인 경우, 단순한 우선순위 기반 추출만으로는 실행 가능한 시퀀스를 보장할 수 없다. 이 경우 우선순위 큐에서 추출된 임무가 현재 가용 자원으로 실행 가능한지 검증하는 적합성 검사(feasibility check)를 추가한다.

자원 벡터 $\mathbf{r}(t) = [r_1(t), r_2(t), \ldots, r_l(t)]^T$ 가 현재 가용 자원을 나타내고, 임무 $\tau_i$ 의 자원 요구량이 $\mathbf{c}_i = [c_{i1}, c_{i2}, \ldots, c_{il}]^T$ 일 때, 적합성 조건은 다음과 같다.

$\text{Feasible}(\tau_i, t) \iff \mathbf{c}_i \leq \mathbf{r}(t) \quad \text{(원소별 비교)}$

자원 제약 하에서의 시퀀싱 알고리즘은 추출된 임무가 적합성 조건을 만족하지 않을 경우, 해당 임무를 보류(defer)하고 차순위 임무를 추출하는 방식으로 동작한다. 이 과정에서 보류된 임무는 자원 회복 후 재삽입되며, 보류 횟수에 비례하여 우선순위를 조정할 수 있다.

6. 다중 큐 아키텍처

6.1 다중 우선순위 수준 큐

단일 우선순위 큐로는 임무의 긴급도 수준 간 차별적 서비스를 보장하기 어렵다. 다중 큐 아키텍처는 $L$ 개의 우선순위 수준에 대응하는 $L$ 개의 독립 큐를 운용하며, 높은 수준의 큐에 있는 임무가 항상 먼저 서비스된다.

$\mathcal{Q} = \{\mathcal{Q}_1, \mathcal{Q}_2, \ldots, \mathcal{Q}_L\}, \quad \text{priority}(\mathcal{Q}_1) > \text{priority}(\mathcal{Q}_2) > \cdots > \text{priority}(\mathcal{Q}_L)$

각 수준 내에서는 개별 우선순위 큐 정책(예: FIFO, 우선순위 큐)이 독립적으로 적용된다. 이 구조는 실시간 운영체제(RTOS)의 다중 수준 피드백 큐(Multilevel Feedback Queue, MLFQ)와 유사한 원리를 따른다.

6.2 임무 유형별 분리 큐

로봇 임무의 유형(감시, 탐색, 운반, 정비 등)에 따라 별도의 큐를 운용하는 방식도 효과적이다. 각 유형별 큐에는 해당 유형의 특성에 최적화된 우선순위 정책이 적용된다.

$\mathcal{Q}_{\text{type}} = \{\mathcal{Q}_{\text{surveillance}}, \mathcal{Q}_{\text{transport}}, \mathcal{Q}_{\text{maintenance}}, \ldots\}$

큐 간 스케줄링은 라운드 로빈(Round Robin), 가중 공정 큐잉(Weighted Fair Queuing), 또는 엄격 우선순위(Strict Priority) 방식으로 수행된다. 특히 가중 공정 큐잉은 각 임무 유형에 배정된 대역폭 비율에 따라 공정한 서비스를 보장한다.

$\text{BW}_{\text{type}} = \frac{w_{\text{type}}}{\sum_{\text{all types}} w_{\text{type}}}$

7. 실시간 제약 하의 우선순위 큐 운용

7.1 하드 실시간 임무와 소프트 실시간 임무의 분리

실시간 로봇 시스템에서는 임무를 마감 시한의 엄격성에 따라 하드 실시간(hard real-time) 임무와 소프트 실시간(soft real-time) 임무로 구분한다.

하드 실시간 임무: 마감 시한을 반드시 준수해야 하며, 위반 시 시스템 안전에 치명적인 결과를 초래한다. 예를 들어, 충돌 회피 기동이나 비상 착륙 절차가 이에 해당한다.
소프트 실시간 임무: 마감 시한 위반이 허용 가능하지만, 임무 가치의 점진적 감소를 수반한다. 정찰 영역 순회나 데이터 전송 등이 해당한다.

이 두 유형의 임무는 별도의 큐에서 관리되며, 하드 실시간 큐의 임무가 항상 절대적 우선권을 가진다.

7.2 스포래딕 임무의 수용

자율 로봇 시스템은 사전에 계획되지 않은 스포래딕(sporadic) 임무가 런타임(runtime)에 발생할 수 있다. 긴급 구조 요청, 위협 탐지 등의 스포래딕 임무는 즉시 우선순위 큐에 삽입되며, 기존 임무 시퀀스에 대한 재정렬을 유발한다.

스포래딕 임무 $\tau_s$ 의 삽입에 따른 큐 재조정 절차는 다음과 같다.

$\tau_s$ 의 우선순위 $p_s$ 를 산정한다.
$p_s$ 가 현재 실행 중인 임무 $\tau_{\text{current}}$ 의 우선순위보다 높으면 **선점(preemption)**을 수행한다.
선점이 불가능한 경우(비선점 임무), $\tau_s$ 를 큐에 삽입하고 현재 임무 완료 후 즉시 실행되도록 한다.

선점 결정의 비용-편익 분석은 다음과 같이 수행된다.

$\text{Preempt} \iff v_s - C_{\text{preempt}} > v_{\text{current}} \cdot \frac{t_{\text{remaining}}}{C_{\text{current}}}$

여기서 $C_{\text{preempt}}$ 는 선점에 따른 전환 비용(컨텍스트 스위칭, 이동 비용 등), $t_{\text{remaining}}$ 은 현재 임무의 잔여 실행 시간이다.

8. 분산 로봇 환경에서의 우선순위 큐

8.1 분산 우선순위 큐 구성

다중 로봇 시스템에서는 각 로봇이 독립적인 로컬 우선순위 큐를 유지하면서, 글로벌 임무 할당기(global task allocator)와 동기화하는 분산 우선순위 큐(distributed priority queue) 구조가 필요하다.

분산 환경에서의 핵심 과제는 다음과 같다.

일관성(Consistency): 모든 로봇이 동일한 글로벌 임무 상태를 공유해야 한다.
가용성(Availability): 통신 단절 상황에서도 각 로봇이 독립적으로 임무를 수행할 수 있어야 한다.
분할 내성(Partition Tolerance): 네트워크 분할 시에도 시스템이 정상 동작해야 한다.

CAP 정리(Brewer의 CAP theorem)에 따르면, 분산 시스템에서 이 세 가지 속성을 동시에 완전히 만족시키는 것은 불가능하다. 따라서 로봇 임무 시스템은 운용 환경에 따라 적절한 트레이드오프를 선택한다.

8.2 합의 기반 분산 시퀀싱

다중 로봇 간의 임무 순서 합의를 위해 합의 기반 번들 알고리즘(Consensus-Based Bundle Algorithm, CBBA)을 우선순위 큐와 결합할 수 있다(Choi et al., 2009). 각 로봇 $r_j$ 는 로컬 우선순위 큐 $\mathcal{Q}_j$ 를 유지하며, 다음 절차를 통해 글로벌 합의에 도달한다.

번들 구축 단계(Bundle Construction Phase): 각 로봇이 자신의 능력과 상태를 기반으로 임무에 입찰하고, 로컬 우선순위 큐에 임무를 할당한다.
합의 단계(Consensus Phase): 로봇 간 입찰 정보를 교환하고, 충돌하는 할당을 해결한다. 낙찰된 임무만 최종적으로 각 로봇의 큐에 유지된다.

합의 수렴 후, 각 로봇의 로컬 큐는 글로벌 최적 할당에 근사하는 임무 시퀀스를 포함한다.

9. 성능 분석과 최적성

9.1 최적성 보장 조건

우선순위 큐 기반 시퀀싱이 최적 순서를 보장하는 조건은 우선순위 함수의 성질에 의존한다.

정리: 임무 간 선후 관계가 없고, 실행 시간이 균일하며, 우선순위 함수가 임무의 고유 가치와 일치하는 경우, 우선순위 큐 기반 탐욕적(greedy) 시퀀싱은 총 가치를 최대화하는 최적 순서를 산출한다.

그러나 임무 간 의존성, 이질적 실행 시간, 자원 제약 등이 존재하는 일반적인 경우, 탐욕적 시퀀싱은 최적 해를 보장하지 않는다. 이 경우의 최적성 갭(optimality gap)은 문제의 구조에 의존하며, 서브모듈러(submodular) 목적 함수에 대해서는 $(1 - 1/e)$ 근사 비율을 달성할 수 있다(Nemhauser et al., 1978).

9.2 계산 복잡도 분석

우선순위 큐 기반 시퀀싱의 전체 계산 복잡도는 다음 요소에 의해 결정된다.

큐 연산: $O(n \log n)$ (이진 힙 기준)
동적 우선순위 갱신: 갱신 빈도 $u$ 에 대해 $O(u \log n)$
적합성 검사: 자원 차원 $l$ 에 대해 $O(n \cdot l)$

총 시간 복잡도는 $O((n + u) \log n + n \cdot l)$ 이며, 대부분의 실시간 로봇 시스템에서 이는 충분히 효율적인 수준이다.

10. 산업 응용 사례

10.1 물류 로봇의 주문 시퀀싱

물류 창고에서 다수의 픽업 주문을 처리하는 자율 이동 로봇(Autonomous Mobile Robot, AMR)은 우선순위 큐를 활용하여 주문의 긴급도, 위치 근접성, 적재 효율성 등을 종합적으로 고려한 시퀀싱을 수행한다. 각 주문은 다중 기준 우선순위를 부여받으며, 동적 주문 추가에 따른 실시간 우선순위 재산정이 필수적이다.

10.2 드론 감시 정찰 임무

복수의 감시 지점을 순회하는 감시 정찰 드론은 각 지점의 감시 긴급도, 마지막 방문 이후 경과 시간, 잔여 배터리 등을 기반으로 우선순위 큐를 구성한다. 에이징 기법을 적용하여 장시간 미방문 지점의 우선순위를 자동 상승시킴으로써 공간적 커버리지의 균등성을 확보한다.

10.3 수색 구조 로봇의 탐색 우선순위

수색 및 구조(SAR) 환경에서는 생존자 발견 확률, 접근 위험도, 구조 소요 시간 등을 종합하여 탐색 구역의 우선순위를 산정한다. 실시간으로 유입되는 센서 데이터(열화상, 음향 탐지 등)에 기반한 이벤트 구동 우선순위 갱신이 인명 구조 효율을 결정하는 핵심 요소이다.

11. 참고 문헌

Choi, H. L., Brunet, L., & How, J. P. (2009). “Consensus-Based Decentralized Auctions for Robust Task Allocation.” IEEE Transactions on Robotics, 25(4), 912–926.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Liu, C. L., & Layland, J. W. (1973). “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment.” Journal of the ACM, 20(1), 46–61.
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978). “An Analysis of Approximations for Maximizing Submodular Set Functions.” Mathematical Programming, 14(1), 265–294.
Saaty, T. L. (1980). The Analytic Hierarchy Process. McGraw-Hill.