397.16 시간 제약 조건의 모델링

1. 시간 제약의 개요

자율 로봇 시스템의 임무 계획에서 시간 제약 조건(temporal constraint)은 작업의 실행 시점, 소요 시간, 시한(deadline), 순서, 동기화 등에 관한 요구사항을 형식적으로 기술하는 수학적 조건이다. 시간 제약은 임무의 실행 가능성(feasibility)과 효율성을 결정짓는 핵심 요소로서, 적절한 수학적 모델링이 없으면 임무 계획의 정확성과 신뢰성을 보장할 수 없다 (Dechter, Meiri, & Pearl, 1991).

시간 제약 조건은 다음의 기본 유형으로 분류된다:

절대 시간 제약(Absolute Temporal Constraint): 작업의 시작 또는 종료 시각이 특정 시간 범위 내에 있어야 하는 조건
상대 시간 제약(Relative Temporal Constraint): 두 작업 간의 시간 간격이 특정 범위 내에 있어야 하는 조건
지속 시간 제약(Duration Constraint): 작업의 수행에 필요한 최소/최대 시간에 관한 조건
시한 제약(Deadline Constraint): 작업이 특정 시각 이전에 완료되어야 하는 조건
주기 제약(Periodicity Constraint): 작업이 일정 주기로 반복 수행되어야 하는 조건

2. 단순 시간 네트워크(STN)

2.1 정의와 구조

단순 시간 네트워크(Simple Temporal Network, STN)는 Dechter, Meiri, 그리고 Pearl(1991)이 제안한 시간 제약 표현 체계로서, 시간 점(time point)들 간의 거리 제약(distance constraint)을 방향 가중 그래프(directed weighted graph)로 모델링한다.

STN은 다음과 같이 정의된다:

$\text{STN} = (\mathcal{T}, \mathcal{C})$

여기서:

$\mathcal{T} = \{t_0, t_1, \ldots, t_n\}$ : 시간 점 변수(time point variable)의 집합
$\mathcal{C}$ : 시간 제약의 집합

각 시간 제약은 두 시간 점 $t_i$ 와 $t_j$ 사이의 거리 한계를 다음과 같이 표현한다:

$l_{ij} \leq t_j - t_i \leq u_{ij}$

여기서 $l_{ij}$ 는 하한(lower bound), $u_{ij}$ 는 상한(upper bound)이며, 이 제약은 $t_i$ 에서 $t_j$ 로의 시간 간격이 $[l_{ij}, u_{ij}]$ 범위 내에 있어야 함을 명세한다.

2.2 그래프 표현

STN의 각 거리 제약 $l_{ij} \leq t_j - t_i \leq u_{ij}$ 는 방향 그래프에서 다음의 두 에지로 표현된다:

$t_i \xrightarrow{u_{ij}} t_j$ : 가중치 $u_{ij}$ 의 에지 (상한 제약)
$t_j \xrightarrow{-l_{ij}} t_i$ : 가중치 $-l_{ij}$ 의 에지 (하한 제약)

이러한 표현에 의하여, STN의 일관성(consistency) 검사, 즉 모든 시간 제약을 동시에 만족하는 시간 점 값의 할당이 존재하는지를 판정하는 문제는, 방향 그래프에서의 음의 사이클(negative cycle) 탐지 문제로 환원된다.

2.3 일관성 검사 알고리즘

STN의 일관성은 벨만-포드 알고리즘(Bellman-Ford algorithm)을 적용하여 다항 시간 내에 검사할 수 있다. 시간 복잡도는 $O(n \cdot e)$ 이며, 여기서 $n = \lvert \mathcal{T} \rvert$ 은 시간 점의 수, $e = \lvert \mathcal{C} \rvert$ 는 제약의 수이다.

대안적으로, 플로이드-워셜 알고리즘(Floyd-Warshall algorithm)을 적용하면 $O(n^3)$ 의 시간 복잡도로 모든 쌍의 최단 거리(all-pairs shortest path)를 계산할 수 있으며, 이를 통하여 각 시간 점의 최초/최후 가능 시각과 임의의 두 시간 점 간의 시간 여유(slack)를 산출할 수 있다:

$\text{EST}(t_i) = -d(t_i, t_0), \quad \text{LST}(t_i) = d(t_0, t_i)$

여기서 $d(t_i, t_j)$ 는 $t_i$ 에서 $t_j$ 로의 최단 거리, $\text{EST}$ 는 최초 시작 시각(Earliest Start Time), $\text{LST}$ 는 최후 시작 시각(Latest Start Time)이다.

3. 불확실 시간 네트워크(STNU)

3.1 정의

실제 로봇 시스템에서는 작업의 수행 시간이 정확히 예측되지 않는 경우가 빈번하다. 이를 반영하기 위하여, Vidal과 Fargier(1999)는 단순 시간 네트워크를 불확실성을 포함하도록 확장한 불확실 시간 네트워크(Simple Temporal Network with Uncertainty, STNU)를 제안하였다.

STNU에서는 시간 점을 다음의 두 유형으로 구분한다:

제어 가능 시간 점(Controllable Time Point): 계획기가 직접 결정할 수 있는 시간 점 (예: 작업 시작 시각)
제어 불가능 시간 점(Uncontrollable Time Point): 환경이나 외부 요인에 의하여 결정되는 시간 점 (예: 작업 종료 시각)

제어 불가능 시간 점은 관측 가능하나 제어 불가능한 불확실 지속 시간(contingent duration)에 의하여 결정된다:

$l_{ij} \leq t_j - t_i \leq u_{ij}, \quad t_j \text{는 제어 불가능}$

3.2 동적 제어 가능성

STNU의 핵심 개념은 동적 제어 가능성(Dynamic Controllability, DC)이다. STNU가 동적으로 제어 가능하다 함은, 과거에 관측된 불확실 사건들의 결과에 기반하여, 미래의 제어 가능 시간 점을 실시간으로 결정하는 전략(strategy)이 존재하여, 모든 가능한 불확실 결과에 대하여 모든 제약을 만족시킬 수 있음을 의미한다 (Morris, Muscettola, & Vidal, 2001).

동적 제어 가능성의 검사는 다항 시간 알고리즘으로 수행 가능하며, Morris(2006)는 $O(n^4)$ 의 시간 복잡도를 가지는 효율적 알고리즘을 제안하였다.

4. 유연 시간 제약 모델

4.1 시간 창(Time Window)

시간 창(time window) 모델은 각 작업 $\tau_i$ 에 대하여, 실행이 허용되는 시간 구간을 다음과 같이 지정한다:

$\tau_i \in [r_i, d_i]$

여기서 $r_i$ 는 해제 시각(release time), $d_i$ 는 시한(deadline)이다. 작업의 시작 시각 $s_i$ 는 $r_i \leq s_i$ 조건을 만족해야 하며, 종료 시각 $c_i = s_i + p_i$ 는 $c_i \leq d_i$ 조건을 만족해야 한다. 여기서 $p_i$ 는 작업의 처리 시간(processing time)이다.

4.2 시간 간격 제약

두 작업 $\tau_i$ 와 $\tau_j$ 사이의 시간 간격에 대한 제약은 다음과 같이 표현된다:

$\delta_{\min} \leq s_j - c_i \leq \delta_{\max}$

여기서 $\delta_{\min}$ 은 최소 간격, $\delta_{\max}$ 는 최대 간격이다. $\delta_{\min} = 0$ 인 경우 작업의 즉시 연속 수행을 허용하며, $\delta_{\min} > 0$ 인 경우 최소 대기 시간을 부과한다.

5. 임계 경로 분석

5.1 정의와 알고리즘

임계 경로법(Critical Path Method, CPM)은 작업 네트워크에서 전체 임무 완료 시간을 결정하는 최장 경로(longest path)를 산출하는 기법이다 (Kelley & Walker, 1959). 임계 경로 상의 작업들은 시간 여유(slack)가 0이므로, 이 작업들의 지연이 전체 임무 완료 시간의 지연으로 직접 이어진다.

작업 $\tau_i$ 의 시간 여유는 다음과 같이 계산된다:

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

임계 경로는 $\text{Slack}(\tau_i) = 0$ 인 작업들의 연속으로 구성된다.

5.2 전진 패스와 후진 패스

CPM은 두 번의 순회(pass)를 통하여 실행된다:

전진 패스(Forward Pass): 위상 정렬 순서로 각 작업의 최초 시작 시각과 최초 종료 시각을 계산한다:

$\text{EST}(\tau_j) = \max_{(\tau_i, \tau_j) \in \mathcal{E}} \left( \text{EST}(\tau_i) + p_i \right)$

후진 패스(Backward Pass): 역위상 정렬 순서로 각 작업의 최후 시작 시각과 최후 종료 시각을 계산한다:

$\text{LST}(\tau_i) = \min_{(\tau_i, \tau_j) \in \mathcal{E}} \left( \text{LST}(\tau_j) - p_i \right)$

전진 및 후진 패스의 시간 복잡도는 모두 $O(\lvert \mathcal{V} \rvert + \lvert \mathcal{E} \rvert)$ 이다.

6. 확률적 시간 제약 모델링

6.1 PERT 모델

PERT(Program Evaluation and Review Technique)는 작업의 수행 시간을 확률 변수로 모델링하여 임무 완료 시간의 불확실성을 분석하는 기법이다 (Malcolm et al., 1959). 각 작업 $\tau_i$ 의 수행 시간 $P_i$ 는 베타 분포(Beta distribution)로 근사되며, 낙관치( $a_i$ ), 최빈치( $m_i$ ), 비관치( $b_i$ )로부터 기대값과 분산을 산출한다:

$\mathbb{E}[P_i] = \frac{a_i + 4m_i + b_i}{6}, \quad \text{Var}[P_i] = \left(\frac{b_i - a_i}{6}\right)^2$

임계 경로 상의 작업 수행 시간들이 독립이라는 가정 하에, 전체 임무 완료 시간 $T$ 의 기대값과 분산은 다음과 같이 계산된다:

$\mathbb{E}[T] = \sum_{i \in \text{CP}} \mathbb{E}[P_i], \quad \text{Var}[T] = \sum_{i \in \text{CP}} \text{Var}[P_i]$

중심 극한 정리(Central Limit Theorem)에 의하여, $T$ 는 근사적으로 정규 분포를 따르므로, 특정 시한 $D$ 이내에 임무를 완료할 확률은 다음과 같이 산출된다:

$P(T \leq D) = \Phi\left(\frac{D - \mathbb{E}[T]}{\sqrt{\text{Var}[T]}}\right)$

여기서 $\Phi$ 는 표준 정규 분포의 누적 분포 함수이다.

6.2 확률적 시간 제약 전파

확률적 시간 제약의 전파(propagation)를 위하여, 몬테카를로 시뮬레이션(Monte Carlo simulation) 기법이 활용된다. 각 작업의 수행 시간을 확률 분포로부터 반복 샘플링하고, 전진 패스를 수행하여 임무 완료 시간의 분포를 추정한다. 이 접근법은 작업 간의 복잡한 의존성과 비선형 제약을 고려할 수 있으며, 베타 분포 외의 임의 분포에도 적용 가능하다.

7. 자율 로봇 시스템에서의 시간 제약 모델링 사례

7.1 드론 배송 임무

드론 배송 임무에서의 시간 제약은 다음과 같이 모델링된다:

이륙 시각: $s_{\text{takeoff}} \geq t_{\text{ready}}$
배송 시한: $c_{\text{delivery}} \leq d_{\text{delivery}}$
비행 지속 시간: $c_{\text{delivery}} - s_{\text{takeoff}} \leq T_{\text{max\_flight}}$
귀환 시한: $c_{\text{return}} \leq d_{\text{return}}$

이러한 제약들은 STN으로 통합되어, 실행 가능한 시간 할당의 존재 여부를 다항 시간 내에 검사할 수 있다.

7.2 순찰 임무의 주기 모델링

순찰 임무에서 각 구역의 방문 주기 제약은 다음과 같이 모델링된다:

$t_{\text{visit}}^{(k+1)}(i) - t_{\text{visit}}^{(k)}(i) \leq P_i, \quad \forall k, \; \forall i$

여기서 $t_{\text{visit}}^{(k)}(i)$ 는 구역 $i$ 의 $k$ 번째 방문 시각, $P_i$ 는 최대 허용 주기이다. 이 제약은 각 구역이 규정된 주기 이내에 반복 방문됨을 보장한다.

7.3 다중 로봇 임무 동기화

다중 로봇이 특정 시점에 동시에 행동을 수행해야 하는 동기화 제약은 다음과 같이 모델링된다:

$\lvert t_{\text{arrive}}^{(i)} - t_{\text{arrive}}^{(j)} \rvert \leq \epsilon_{\text{sync}}, \quad \forall (i, j) \in \mathcal{S}$

여기서 $t_{\text{arrive}}^{(i)}$ 는 로봇 $i$ 의 도착 시각, $\epsilon_{\text{sync}}$ 는 동기화 허용 오차, $\mathcal{S}$ 는 동기화가 필요한 로봇 쌍의 집합이다.

8. 참고문헌

Dechter, R., Meiri, I., & Pearl, J. (1991). “Temporal Constraint Networks.” Artificial Intelligence, 49(1–3), 61–95.
Kelley, J. E., & Walker, M. R. (1959). “Critical-Path Planning and Scheduling.” In Proceedings of the Eastern Joint IRE-AIEE-ACM Computer Conference, 160–173.
Malcolm, D. G., Roseboom, J. H., Clark, C. E., & Fazar, W. (1959). “Application of a Technique for Research and Development Program Evaluation.” Operations Research, 7(5), 646–669.
Morris, P. (2006). “A Structural Characterization of Temporal Dynamic Controllability.” In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), LNCS 4204, Springer, 375–389.
Morris, P., Muscettola, N., & Vidal, T. (2001). “Dynamic Control of Plans with Temporal Uncertainty.” In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI), 494–499.
Vidal, T., & Fargier, H. (1999). “Handling Contingency in Temporal Constraint Networks: From Consistency to Controllabilities.” Journal of Experimental and Theoretical Artificial Intelligence, 11(1), 23–45.