396.28 시간 제약 조건의 정식화

1. 서론

로봇 임무 관리에서 시간 제약 조건(temporal constraint)은 임무의 실행 가능성과 적시성(timeliness)을 결정하는 핵심 요소이다. 시간 제약은 과업의 시작 시점, 종료 시한, 수행 기간, 과업 간 시간적 관계 등을 규정하며, 이러한 제약의 정확한 정식화(formalization)는 임무 계획 알고리즘의 정확성과 효율성에 직접적으로 영향을 미친다.

시간 제약 조건의 정식화는 로봇 임무 관리를 넘어, 스케줄링 이론(scheduling theory), 실시간 시스템(real-time system), 시간 논리(temporal logic) 등 다양한 분야의 이론적 기반 위에 구축된다. 본 절에서는 로봇 임무에 적용되는 시간 제약의 유형별 수학적 정식화 방법론과 이를 처리하기 위한 계산적 프레임워크를 상세히 기술한다.

2. 시간 변수의 기본 정의

임무를 구성하는 과업 집합 \mathcal{T} = \{\tau_1, \tau_2, \ldots, \tau_n\}에 대하여, 각 과업 \tau_i의 시간적 속성은 다음과 같은 변수로 정의된다:

• s_i: 과업 \tau_i의 시작 시각(start time)
• e_i: 과업 \tau_i의 종료 시각(end time)
• d_i = e_i - s_i: 과업 \tau_i의 수행 기간(duration)
• r_i: 과업 \tau_i의 최조 가용 시각(release time), 즉 s_i \geq r_i
• D_i: 과업 \tau_i의 절대 시한(absolute deadline), 즉 e_i \leq D_i

이들 변수 사이의 기본 관계는 다음과 같다:

e_i = s_i + d_i, \quad r_i \leq s_i, \quad e_i \leq D_i

3. 시간 제약의 유형별 정식화

3.1 절대 시간 제약(Absolute Temporal Constraints)

절대 시간 제약은 과업의 시작이나 종료 시각이 절대적인 시간 범위 내에 있어야 함을 규정한다.

시작 시간 윈도우(start time window):

s_i^{\min} \leq s_i \leq s_i^{\max}

종료 시한(deadline):

e_i \leq D_i

시간 윈도우(time window): 과업 \tau_i가 시간 구간 [a_i, b_i] 내에서만 실행 가능하다:

s_i \geq a_i, \quad e_i \leq b_i

시간 윈도우 제약이 있는 임무는 시간 윈도우가 있는 차량 경로 문제(Vehicle Routing Problem with Time Windows, VRPTW)로 정식화되며, 이는 NP-난해(NP-hard) 문제에 해당한다.

3.2 상대 시간 제약(Relative Temporal Constraints)

상대 시간 제약은 두 과업 사이의 시간적 관계를 규정한다.

선행 제약(precedence constraint): 과업 \tau_i가 \tau_j보다 먼저 완료되어야 한다:

e_i \leq s_j

최소 간격 제약(minimum separation): 과업 \tau_i와 \tau_j 사이에 최소 \delta_{\min}의 시간 간격이 보장되어야 한다:

s_j - e_i \geq \delta_{\min}

최대 간격 제약(maximum separation): 과업 \tau_i와 \tau_j 사이의 시간 간격이 \delta_{\max}를 초과하지 않아야 한다:

s_j - e_i \leq \delta_{\max}

일반화된 차분 제약(generalized difference constraint): 두 시간 변수 t_i와 t_j 사이의 관계를 범위로 표현한다:

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

이 형태는 단순 시간 네트워크(Simple Temporal Network, STN)의 기본 제약 단위이다.

3.3 수행 기간 제약(Duration Constraints)

과업의 수행 기간에 대한 제약이다.

고정 수행 기간(fixed duration): 과업 \tau_i의 수행 기간이 상수 d_i^{\text{fixed}}로 결정된다:

e_i - s_i = d_i^{\text{fixed}}

가변 수행 기간(variable duration): 과업의 수행 기간이 범위 내에서 변동할 수 있다:

d_i^{\min} \leq e_i - s_i \leq d_i^{\max}

확률적 수행 기간(stochastic duration): 과업의 수행 기간이 확률 분포를 따른다:

d_i \sim F_i(\cdot)

여기서 F_i는 과업 \tau_i의 수행 기간에 대한 누적 분포 함수(cumulative distribution function)이다. 로봇 임무에서 수행 기간은 흔히 로그정규 분포(log-normal distribution)나 감마 분포(gamma distribution)로 모델링된다.

3.4 주기적 시간 제약(Periodic Temporal Constraints)

반복 실행 임무에서 과업이 일정한 주기로 수행되어야 하는 제약이다:

s_i^{(k+1)} = s_i^{(k)} + T_i, \quad k = 0, 1, 2, \ldots

여기서 T_i는 과업 \tau_i의 주기(period)이며, s_i^{(k)}는 k번째 실행의 시작 시각이다. 주기적 과업의 스케줄 가능성(schedulability)은 다음의 이용률(utilization) 조건으로 필요 조건이 판별된다:

U = \sum_{i=1}^{n} \frac{d_i}{T_i} \leq 1

4. 시간 네트워크 기반 정식화

4.1 단순 시간 네트워크(Simple Temporal Network, STN)

STN은 시간 제약의 정식화와 일관성 검사를 위한 대표적 프레임워크이다. STN은 방향 가중 그래프 \mathcal{G} = (\mathcal{V}, \mathcal{E})로 표현된다:

• \mathcal{V} = \{v_0, v_1, \ldots, v_n\}: 시간 점(time point)의 집합. v_0은 기준 시점(reference time)이다.
• \mathcal{E}: 간선 집합으로, 각 간선 (v_i, v_j)에 가중치 w_{ij}가 부여되어 t_j - t_i \leq w_{ij}를 나타낸다.

범위 제약 l_{ij} \leq t_j - t_i \leq u_{ij}는 두 개의 방향 간선으로 분해된다:

(v_i, v_j, u_{ij}) \quad \text{및} \quad (v_j, v_i, -l_{ij})

STN의 일관성은 그래프에 음수 순환(negative cycle)이 존재하지 않는 것과 동치이며, 벨만-포드(Bellman-Ford) 알고리즘을 통하여 O(\vert \mathcal{V} \vert \cdot \vert \mathcal{E} \vert) 시간에 검사할 수 있다. 플로이드-워셜(Floyd-Warshall) 알고리즘을 적용하면 O(\vert \mathcal{V} \vert^3) 시간에 모든 시간 점 쌍 사이의 최단 경로를 계산하여, 각 시간 변수의 허용 범위를 도출할 수 있다.

4.2 불확실성이 있는 단순 시간 네트워크(STNU)

로봇 임무에서 과업의 수행 기간이 불확실한 경우, STNU(Simple Temporal Network with Uncertainty)가 적용된다. STNU는 제어 가능 시간 점(controllable time point)과 제어 불가능 시간 점(uncontrollable time point)을 구분한다.

우발 링크(contingent link) \langle v_i, v_j, [l, u] \rangle는 시간 점 v_i에서 v_j까지의 기간이 [l, u] 범위 내에서 환경에 의하여 결정됨을 나타낸다. 즉, 로봇이 이 기간을 제어할 수 없다.

STNU의 핵심 개념은 **동적 제어 가능성(dynamic controllability)**이다. 동적으로 제어 가능한 STNU는, 과거의 관측에 기반하여 미래의 제어 가능 시간 점을 실시간으로 결정하는 전략(execution strategy)이 존재함을 보장한다. Morris et al. (2001)은 STNU의 동적 제어 가능성을 O(n^3) 시간에 검사하는 알고리즘을 제안하였다.

4.3 확률적 시간 네트워크(Probabilistic STN)

수행 기간이 확률 분포를 따르는 경우, 확률적 시간 네트워크(Probabilistic Simple Temporal Network, PSTN)가 사용된다. PSTN에서 각 우발 링크의 기간은 확률 분포 f(d)를 따르며, 스케줄의 실행 가능 확률(probability of feasibility)이 분석 대상이 된다:

P(\text{feasible}) = P\left(\bigwedge_{(i,j) \in \mathcal{E}} t_j - t_i \leq w_{ij}\right)

이 확률을 특정 임계값 \alpha 이상으로 보장하는 스케줄을 구하는 것이 확률적 시간 제약 하의 임무 계획 문제이다.

5. 시간 논리 기반 정식화

5.1 선형 시간 논리(Linear Temporal Logic, LTL)

LTL은 시간적 순서와 반복에 관한 제약을 형식적으로 명세하는 데 활용된다. LTL의 주요 시간 연산자는 다음과 같다:

시간 제약의 LTL 표현 예시:

• 과업 A를 반드시 수행하라: \diamondsuit \text{task}_A
• 과업 A 이후에 과업 B를 수행하라: \square(\text{done}_A \rightarrow \diamondsuit \text{task}_B)
• 과업 B를 수행하기 전에 항상 과업 A가 선행되어야 한다: (\neg \text{task}_B) \; \mathcal{U} \; \text{task}_A
• 항상 안전 조건을 유지하라: \square \text{safe}

5.2 메트릭 시간 논리(Metric Temporal Logic, MTL)

LTL은 정성적(qualitative) 시간 관계를 표현하나, 정량적(quantitative) 시간 제약을 직접 명세할 수 없다. 메트릭 시간 논리(MTL)는 시간 연산자에 시간 구간을 부여하여 정량적 제약을 표현한다:

\diamondsuit_{[0, T]} \varphi \quad \text{(시간 $T$ 이내에 $\varphi$가 성립한다)}

\square_{[a, b]} \varphi \quad \text{(시간 구간 $[a, b]$ 동안 $\varphi$가 항상 성립한다)}

로봇 임무에서의 적용 예시:

• 10초 이내에 목표 지점에 도달하라: \diamondsuit_{[0, 10]} \text{at\_goal}
• 30초에서 60초 사이에 정찰을 수행하라: \diamondsuit_{[30, 60]} \text{patrol}
• 항상 장애물과의 거리를 유지하라: \square_{[0, \infty)} (\text{distance} \geq d_{\text{safe}})

5.3 신호 시간 논리(Signal Temporal Logic, STL)

STL은 실수 값 신호(real-valued signal)에 대한 시간 제약을 명세하며, 로봇의 연속 상태 변수(위치, 속도, 센서 값 등)에 직접 적용할 수 있다. STL의 특징은 **강건도(robustness degree)**를 정량적으로 계산할 수 있다는 점이다.

속성 \varphi에 대한 신호 \mathbf{x}(t)의 강건도 \rho(\varphi, \mathbf{x}, t)는 다음과 같이 재귀적으로 정의된다:

\rho(\mu, \mathbf{x}, t) = f(\mathbf{x}(t)) \quad \text{(원자 술어 $\mu : f(\mathbf{x}) > 0$)}

\rho(\square_{[a,b]} \varphi, \mathbf{x}, t) = \min_{t' \in [t+a, t+b]} \rho(\varphi, \mathbf{x}, t')

\rho(\diamondsuit_{[a,b]} \varphi, \mathbf{x}, t) = \max_{t' \in [t+a, t+b]} \rho(\varphi, \mathbf{x}, t')

\rho > 0이면 속성이 만족되며, \rho의 절대값이 클수록 만족 또는 위반의 정도가 크다.

6. 스케줄링 이론과의 연계

시간 제약 조건의 정식화는 스케줄링 이론의 프레임워크와 밀접하게 연관된다. 로봇 임무의 시간 제약 문제는 단일 기계 스케줄링(single-machine scheduling), 잡 숍 스케줄링(job-shop scheduling), 자원 제약 프로젝트 스케줄링(Resource-Constrained Project Scheduling Problem, RCPSP) 등의 고전적 스케줄링 문제로 환원될 수 있다.

RCPSP는 다음과 같이 정식화된다:

\min \; C_{\max} = \max_{i \in \mathcal{T}} e_i

\text{s.t.} \quad e_i \leq s_j, \quad \forall (\tau_i, \tau_j) \in \mathcal{P}

\sum_{i : \tau_i \text{ active at } t} r_{ik} \leq R_k, \quad \forall k, \; \forall t

여기서 C_{\max}는 메이크스팬(makespan), 즉 전체 임무의 완료 시각이며, r_{ik}는 과업 \tau_i의 자원 k 요구량, R_k는 자원 k의 총 가용량이다.

7. 참고문헌

• Dechter, R., Meiri, I., and Pearl, J. (1991). “Temporal Constraint Networks.” Artificial Intelligence, 49(1–3), 61–95.
• Morris, P.H., Muscettola, N., and Vidal, T. (2001). “Dynamic Control of Plans with Temporal Uncertainty.” Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2001.
• Alur, R. and Henzinger, T.A. (1993). “Real-Time Logics: Complexity and Expressiveness.” Information and Computation, 104(1), 35–77.
• Maler, O. and Nickovic, D. (2004). “Monitoring Temporal Properties of Continuous Signals.” Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems (FORMATS/FTRTFT), Springer, 152–166.
• Brucker, P. (2007). Scheduling Algorithms. 5th Edition, Springer.
• Kress-Gazit, H., Fainekos, G.E., and Pappas, G.J. (2009). “Temporal-Logic-Based Reactive Mission and Motion Planning.” IEEE Transactions on Robotics, 25(6), 1370–1381.

본 절은 로봇공학 서적 Volume 9, Part 53, Chapter 396의 일부로 작성되었다. 버전: 2026-03-23 v1.0