396.3 임무(Mission)의 수학적 정의와 형식화

1. 임무의 집합론적 정의

임무(Mission)는 로봇 시스템이 달성해야 하는 목표와 이를 위한 구성 요소를 수학적으로 엄밀하게 정의한 형식적 객체이다. 집합론(Set Theory)에 기초하여, 임무는 다음과 같은 튜플(Tuple)로 정의된다:

\mathcal{M} = \langle \mathcal{G}, \mathcal{T}, \mathcal{R}, \mathcal{C}, \mathcal{E}, \Phi, \Gamma \rangle

각 구성 요소의 정의는 다음과 같다:

• \mathcal{G} = \{g_1, g_2, \ldots, g_k\}: 임무 목표 집합(Mission Goal Set). 각 g_i는 달성해야 하는 명시적 목표를 나타낸다.
• \mathcal{T} = \{t_1, t_2, \ldots, t_n\}: 과업 집합(Task Set). 목표 달성을 위해 수행해야 하는 개별 작업의 유한 집합이다.
• \mathcal{R} = \{r_1, r_2, \ldots, r_m\}: 자원 집합(Resource Set). 임무 수행에 필요한 물리적·논리적 자원이다.
• \mathcal{C}: 제약 조건 집합(Constraint Set). 임무 수행 과정에서 준수해야 하는 시간적, 공간적, 자원적 제약이다.
• \mathcal{E}: \mathbb{R}^+ \rightarrow \mathcal{S}: 환경 상태 함수(Environment State Function). 시간에 따른 환경 상태의 변화를 기술한다.
• \Phi: \mathcal{G} \rightarrow 2^{\mathcal{T}}: 목표-과업 매핑 함수. 각 목표를 달성하기 위해 필요한 과업의 부분 집합을 지정한다.
• \Gamma: \mathcal{T} \times \mathcal{T} \rightarrow \{\text{precedence}, \text{concurrent}, \text{independent}\}: 과업 간 관계 함수. 과업 쌍 사이의 선행, 동시 수행, 독립 관계를 정의한다.

2. 임무 목표의 형식적 명세

2.1 도달 목표와 유지 목표

임무 목표는 그 성격에 따라 두 가지 범주로 분류된다:

**도달 목표(Reachability Goal)**는 특정 상태에 도달하는 것을 요구한다:

g_{\text{reach}} = \Diamond \varphi

여기서 \Diamond는 시간 논리의 “결국(Eventually)” 연산자이며, \varphi는 목표 상태를 기술하는 명제이다.

**유지 목표(Safety/Maintenance Goal)**는 특정 조건이 지속적으로 유지되는 것을 요구한다:

g_{\text{safe}} = \Box \psi

여기서 \Box는 “항상(Always)” 연산자이며, \psi는 유지해야 하는 조건을 나타낸다.

2.2 복합 목표

실제 임무는 다수의 단순 목표의 논리적 조합으로 구성된다. 복합 목표(Composite Goal)는 다음과 같이 표현된다:

g_{\text{composite}} = g_1 \wedge g_2 \wedge \cdots \wedge g_k = \bigwedge_{i=1}^{k} g_i

목표 간의 우선순위가 존재하는 경우, 가중치 벡터 \mathbf{w} = (w_1, w_2, \ldots, w_k)를 도입하여 다음과 같이 유용도 함수(Utility Function)로 변환할 수 있다:

U(\mathcal{M}) = \sum_{i=1}^{k} w_i \cdot \mathbb{1}[g_i \text{ 달성}]

여기서 \mathbb{1}[\cdot]은 지시 함수(Indicator Function)이다.

3. 임무 공간의 정의

3.1 상태 공간

임무가 수행되는 환경은 상태 공간(State Space) \mathcal{S}으로 모델링된다. 상태 공간은 로봇의 물리적 상태, 환경의 상태, 그리고 임무의 진행 상태를 모두 포함한다:

\mathcal{S} = \mathcal{S}_{\text{robot}} \times \mathcal{S}_{\text{env}} \times \mathcal{S}_{\text{mission}}

여기서:

• \mathcal{S}_{\text{robot}} \subseteq \mathbb{R}^{n_r}: 로봇의 구성(Configuration), 속도, 에너지 수준 등을 포함하는 로봇 상태 공간
• \mathcal{S}_{\text{env}} \subseteq \mathbb{R}^{n_e}: 장애물 위치, 기상 조건, 타 에이전트 위치 등을 포함하는 환경 상태 공간
• \mathcal{S}_{\text{mission}} = \{s_1, s_2, \ldots, s_p\}: 임무 진행 단계를 나타내는 이산 임무 상태 공간

3.2 행동 공간

로봇이 선택할 수 있는 행동의 집합은 행동 공간(Action Space) \mathcal{A}로 정의된다:

\mathcal{A} = \{a_1, a_2, \ldots, a_q\}

행동 공간은 이산적(Discrete)이거나 연속적(Continuous)일 수 있으며, 임무 관리 수준에서는 일반적으로 추상화된 이산 행동 집합을 다룬다.

3.3 전이 함수

상태 전이 함수(Transition Function) T는 현재 상태와 선택된 행동에 기반하여 다음 상태를 결정한다:

T: \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{S} \quad \text{(결정론적)}

T: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow [0, 1] \quad \text{(확률론적)}

확률론적 전이 함수의 경우, T(s, a, s') = P(s' | s, a)는 상태 s에서 행동 a를 수행했을 때 상태 s'로 전이할 확률을 나타낸다.

4. 마르코프 의사 결정 과정 기반 형식화

임무 관리 문제는 마르코프 의사 결정 과정(Markov Decision Process, MDP)으로 형식화할 수 있다:

\text{MDP} = \langle \mathcal{S}, \mathcal{A}, T, R, \gamma \rangle

여기서:

• R: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}: 보상 함수(Reward Function)
• \gamma \in [0, 1): 할인 인자(Discount Factor)

임무 관리의 목적은 누적 보상을 최대화하는 최적 정책(Optimal Policy) \pi^*를 구하는 것이다:

\pi^* = \arg\max_\pi \mathbb{E}\left[\sum_{t=0}^{\infty} \gamma^t R(s_t, \pi(s_t))\right]

4.1 보상 함수의 설계

임무 목표를 반영하는 보상 함수는 다음과 같이 설계된다:

R(s, a) = R_{\text{goal}}(s) + R_{\text{progress}}(s, a) + R_{\text{penalty}}(s, a)

여기서:

• R_{\text{goal}}(s): 목표 달성 시 부여되는 보상
• R_{\text{progress}}(s, a): 목표를 향한 진전에 대한 보상
• R_{\text{penalty}}(s, a): 제약 조건 위반이나 비효율적 행동에 대한 벌칙

5. 시간 논리 기반 형식화

5.1 선형 시간 논리(LTL) 기반 임무 명세

선형 시간 논리(Linear Temporal Logic, LTL)는 임무의 시간적 속성을 형식적으로 명세하는 데 널리 사용된다(Pnueli, 1977). LTL 공식은 다음의 구문론(Syntax)에 의해 재귀적으로 정의된다:

\varphi ::= p \mid \neg \varphi \mid \varphi_1 \wedge \varphi_2 \mid \bigcirc \varphi \mid \varphi_1 \mathcal{U} \varphi_2

여기서 p는 원자 명제(Atomic Proposition), \bigcirc는 다음(Next) 연산자, \mathcal{U}는 까지(Until) 연산자이다. 파생 연산자로 \Diamond \varphi = \text{true} \mathcal{U} \varphi (결국), \Box \varphi = \neg \Diamond \neg \varphi (항상)이 정의된다.

5.2 임무의 LTL 표현 예시

대표적인 임무 유형과 그 LTL 표현은 다음과 같다:

5.3 LTL에서 오토마톤으로의 변환

LTL 공식 \varphi는 비결정적 뷔히 오토마톤(Nondeterministic Büchi Automaton, NBA)으로 변환할 수 있다. 이 변환은 임무 명세로부터 자동으로 실행 가능한 제어기를 합성하는 기반이 된다(Baier and Katoen, 2008):

\varphi \xrightarrow{\text{변환}} \mathcal{A}_\varphi = \langle Q, \Sigma, \delta, q_0, F \rangle

여기서 Q는 상태 집합, \Sigma = 2^{AP}는 알파벳(원자 명제의 멱집합), \delta: Q \times \Sigma \rightarrow 2^Q는 전이 함수, q_0는 초기 상태, F \subseteq Q는 수용 상태 집합이다.

6. 제약 만족 기반 형식화

6.1 제약 만족 문제로서의 임무

임무 관리 문제는 제약 만족 문제(Constraint Satisfaction Problem, CSP)로도 형식화할 수 있다:

\text{CSP} = \langle \mathcal{X}, \mathcal{D}, \mathcal{C} \rangle

여기서:

• \mathcal{X} = \{x_1, x_2, \ldots, x_n\}: 의사 결정 변수 집합 (과업 할당, 시작 시간 등)
• \mathcal{D} = \{D_1, D_2, \ldots, D_n\}: 각 변수의 정의역(Domain) 집합
• \mathcal{C} = \{c_1, c_2, \ldots, c_p\}: 변수 간 제약 조건 집합

6.2 최적화 문제로의 확장

제약 조건을 만족하면서 목적 함수를 최적화하는 문제로 확장하면, 제약 최적화 문제(Constrained Optimization Problem, COP)가 된다:

\begin{aligned} \min_{x \in \mathcal{X}} \quad & J(x) = \sum_{i=1}^{n} c_i(x_i) + \sum_{(i,j)} c_{ij}(x_i, x_j) \\ \text{subject to} \quad & h_k(x) = 0, \quad k = 1, \ldots, p \\ & g_l(x) \leq 0, \quad l = 1, \ldots, q \end{aligned}

여기서 J(x)는 총 비용 함수, h_k는 등식 제약, g_l은 부등식 제약이다.

7. 그래프 이론 기반 형식화

7.1 임무 그래프

임무의 구조는 방향성 비순환 그래프(Directed Acyclic Graph, DAG) G = (V, E)로 표현할 수 있다. 여기서 정점(Vertex) v \in V는 개별 과업을 나타내고, 간선(Edge) e \in E는 과업 간의 선행 관계를 나타낸다:

(t_i, t_j) \in E \iff t_i \text{ 선행 } t_j

이 그래프 표현을 통해 위상 정렬(Topological Sort)을 수행하면 과업의 유효한 실행 순서를 얻을 수 있으며, 임계 경로(Critical Path) 분석을 통해 최소 임무 수행 시간을 산출할 수 있다:

T_{\text{critical}} = \max_{\text{path } P \in G} \sum_{t_i \in P} \tau_i

여기서 \tau_i는 과업 t_i의 예상 수행 시간이다.

7.2 하이퍼그래프 확장

다중 로봇 임무 관리에서는 하나의 과업이 다수의 로봇의 동시 참여를 요구할 수 있다. 이 경우, 일반 그래프 대신 하이퍼그래프(Hypergraph) H = (V, E_H)가 사용된다. 여기서 하이퍼에지(Hyperedge) e_H \in E_H는 둘 이상의 정점을 동시에 연결할 수 있다.

8. 형식화의 비교와 선택 기준

각 형식화 방법은 고유한 장단점을 가지며, 적용 맥락에 따라 적절한 형식화 방법을 선택해야 한다:

9. 참고 문헌

• Baier, C., and Katoen, J. P. (2008). Principles of Model Checking. MIT Press.
• Bellman, R. (1957). Dynamic Programming. Princeton University Press.
• 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.
• Pnueli, A. (1977). “The Temporal Logic of Programs.” Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS), 46-57.
• Puterman, M. L. (2014). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons.

Version: v1.0 (2026-03-23)