Chapter 397. 임무 계획 수립 (Mission Planning)

1. 개요

임무 계획 수립(Mission Planning)은 자율 로봇 시스템이 주어진 목표를 달성하기 위하여 수행해야 할 행동의 순서, 자원 배분, 경로, 시간 제약 등을 사전에 결정하는 체계적 과정이다. 임무 계획은 단순한 경로 계획(Path Planning)이나 궤적 최적화(Trajectory Optimization)와는 구별되며, 보다 상위 수준의 추상화 계층에서 로봇이 수행해야 할 전체 작업의 구조를 설계하는 과정에 해당한다. 로봇 공학에서 임무 계획 수립은 단일 로봇 시스템뿐만 아니라 다중 로봇 시스템, 무인 항공기(UAV), 자율 주행 차량 등 다양한 플랫폼에 적용되며, 군사 작전, 재난 구조, 환경 탐사, 물류 배송 등 광범위한 응용 분야에서 핵심적 역할을 수행한다.

임무 계획 수립의 핵심 목표는 주어진 임무 목표(Mission Objective)를 만족하면서 동시에 자원 제약(Resource Constraints), 시간 제약(Temporal Constraints), 환경 제약(Environmental Constraints), 안전 제약(Safety Constraints) 등을 충족하는 최적의 행동 계획(Action Plan)을 도출하는 것이다. 이를 수학적으로 표현하면, 임무 계획 문제는 다음과 같은 최적화 문제로 정식화할 수 있다.

$\min_{\pi} J(\pi) = \sum_{t=0}^{T} c(s_t, a_t)$

여기서 $\pi$ 는 행동 정책(Policy), $J(\pi)$ 는 총 비용 함수(Total Cost Function), $s_t$ 는 시각 $t$ 에서의 상태(State), $a_t$ 는 해당 시각에서의 행동(Action), $c(\cdot, \cdot)$ 는 상태-행동 쌍에 대한 비용 함수(Cost Function), $T$ 는 임무의 시간 지평(Time Horizon)을 나타낸다. 이 최적화 문제에는 다음과 같은 제약 조건이 부과된다.

$s_{t+1} = f(s_t, a_t), \quad s_0 = s_{\text{init}}, \quad s_T \in \mathcal{S}_{\text{goal}}$

$g_i(s_t, a_t) \leq 0, \quad i = 1, \ldots, m$

$h_j(s_t, a_t) = 0, \quad j = 1, \ldots, p$

여기서 $f(\cdot, \cdot)$ 는 상태 전이 함수(State Transition Function), $s_{\text{init}}$ 는 초기 상태, $\mathcal{S}_{\text{goal}}$ 은 목표 상태 집합, $g_i(\cdot, \cdot)$ 는 부등식 제약 조건(Inequality Constraints), $h_j(\cdot, \cdot)$ 는 등식 제약 조건(Equality Constraints)을 각각 나타낸다.

2. 임무 계획 수립의 계층적 구조

임무 계획 수립은 일반적으로 계층적(Hierarchical) 구조를 따르며, 상위 수준에서 하위 수준으로 점진적으로 구체화되는 방식으로 진행된다. 이 계층적 구조는 크게 세 가지 수준으로 구분할 수 있다.

2.1 전략 수준 (Strategic Level)

전략 수준의 계획은 임무의 전체적인 목표와 우선순위를 결정하는 단계이다. 이 수준에서는 어떤 임무를 수행할 것인지, 어떤 순서로 수행할 것인지, 어떤 자원을 배분할 것인지에 대한 의사 결정이 이루어진다. 전략 수준의 계획은 주로 혼합 정수 선형 계획법(Mixed-Integer Linear Programming, MILP), 제약 만족 문제(Constraint Satisfaction Problem, CSP), 또는 마르코프 의사 결정 과정(Markov Decision Process, MDP)과 같은 수학적 프레임워크를 사용하여 정식화된다.

MILP 기반 임무 할당 문제의 일반적인 형태는 다음과 같다.

$\min_{x_{ij}} \sum_{i=1}^{n} \sum_{j=1}^{m} c_{ij} x_{ij}$

$\text{subject to} \quad \sum_{j=1}^{m} x_{ij} = 1, \quad \forall i$

$\sum_{i=1}^{n} x_{ij} \leq k_j, \quad \forall j$

$x_{ij} \in \{0, 1\}$

여기서 $x_{ij}$ 는 임무 $i$ 가 자원 $j$ 에 할당되는지를 나타내는 이진 변수(Binary Variable), $c_{ij}$ 는 임무 $i$ 를 자원 $j$ 에 할당할 때의 비용, $n$ 은 총 임무 수, $m$ 은 총 자원 수, $k_j$ 는 자원 $j$ 의 용량 제약을 각각 나타낸다.

2.2 전술 수준 (Tactical Level)

전술 수준의 계획은 전략 수준에서 결정된 임무를 구체적으로 어떻게 수행할 것인지를 결정하는 단계이다. 이 수준에서는 각 임무의 세부 작업(Sub-task)을 정의하고, 작업 간의 선후 관계(Precedence Relations)를 설정하며, 각 작업에 필요한 자원과 시간을 산정한다. 전술 수준의 계획에서는 계층적 작업 네트워크(Hierarchical Task Network, HTN) 계획법이나 시간 논리(Temporal Logic) 기반 계획법이 널리 활용된다.

HTN 계획법에서 복합 작업(Compound Task) $t_c$ 는 다수의 기본 작업(Primitive Task) $t_{p_1}, t_{p_2}, \ldots, t_{p_k}$ 로 분해(Decomposition)되며, 이 분해 과정은 분해 방법(Method) $m$ 에 의하여 정의된다.

$t_c \xrightarrow{m} \langle t_{p_1}, t_{p_2}, \ldots, t_{p_k} \rangle$

각 기본 작업 $t_{p_i}$ 는 전제 조건(Precondition) $\text{pre}(t_{p_i})$ 와 효과(Effect) $\text{eff}(t_{p_i})$ 를 가지며, 이를 통하여 상태 공간에서의 전이가 정의된다.

2.3 실행 수준 (Execution Level)

실행 수준의 계획은 전술 수준에서 정의된 각 세부 작업을 실제 로봇 하드웨어에서 실행 가능한 명령으로 변환하는 단계이다. 이 수준에서는 구체적인 경로 계획, 모션 계획(Motion Planning), 제어 명령 생성 등이 포함된다. 실행 수준의 계획은 로봇의 동역학적 제약(Dynamic Constraints), 센서의 한계, 통신 지연 등을 고려하여야 한다.

3. 임무 계획 수립의 주요 접근법

3.1 고전적 계획법 (Classical Planning)

고전적 계획법은 완전 관측 가능(Fully Observable)하고 결정론적(Deterministic)인 환경을 가정하며, 주어진 초기 상태에서 목표 상태로의 행동 순서를 탐색하는 방법이다. STRIPS(Stanford Research Institute Problem Solver)와 PDDL(Planning Domain Definition Language)은 고전적 계획법의 대표적인 프레임워크이다 (Fikes & Nilsson, 1971; McDermott et al., 1998).

STRIPS 표현에서 상태는 논리적 명제(Logical Proposition)의 집합으로 표현되며, 각 행동은 전제 조건, 추가 효과(Add Effects), 삭제 효과(Delete Effects)의 삼중쌍으로 정의된다.

$a = \langle \text{Pre}(a), \text{Add}(a), \text{Del}(a) \rangle$

행동 $a$ 가 상태 $s$ 에서 적용 가능하려면 $\text{Pre}(a) \subseteq s$ 이어야 하며, 적용 후의 후속 상태 $s'$ 는 다음과 같이 계산된다.

$s' = (s \setminus \text{Del}(a)) \cup \text{Add}(a)$

3.2 시간 논리 기반 계획법 (Temporal Logic-Based Planning)

선형 시간 논리(Linear Temporal Logic, LTL)나 계산 트리 논리(Computation Tree Logic, CTL)를 사용하여 임무 사양(Mission Specification)을 형식적으로 기술하고, 이를 만족하는 행동 계획을 자동으로 합성하는 방법이다 (Kress-Gazit et al., 2009). LTL 사양 $\varphi$ 는 다음과 같은 시간 연산자(Temporal Operators)를 포함한다.

$\bigcirc \varphi$ : 다음 시각(Next)에 $\varphi$ 가 성립
$\square \varphi$ : 항상(Always) $\varphi$ 가 성립
$\lozenge \varphi$ : 결국(Eventually) $\varphi$ 가 성립
$\varphi_1 \mathcal{U} \varphi_2$ : $\varphi_2$ 가 성립할 때까지(Until) $\varphi_1$ 이 성립

LTL 사양을 뷔히 오토마톤(Büchi Automaton)으로 변환한 후, 로봇의 전이 시스템(Transition System)과의 곱 오토마톤(Product Automaton)을 구성하여 사양을 만족하는 경로를 탐색한다.

3.3 확률적 계획법 (Probabilistic Planning)

환경의 불확실성을 명시적으로 고려하는 계획법으로, 마르코프 의사 결정 과정(MDP)이나 부분 관측 마르코프 의사 결정 과정(Partially Observable MDP, POMDP)을 기반으로 한다 (Kaelbling et al., 1998). MDP는 4-튜플 $\langle \mathcal{S}, \mathcal{A}, P, R \rangle$ 로 정의되며, 여기서 $\mathcal{S}$ 는 상태 공간, $\mathcal{A}$ 는 행동 공간, $P(s' \mid s, a)$ 는 상태 전이 확률(Transition Probability), $R(s, a)$ 는 보상 함수(Reward Function)이다.

최적 정책 $\pi^*$ 는 벨만 최적 방정식(Bellman Optimality Equation)을 만족한다.

$V^*(s) = \max_{a \in \mathcal{A}} \left[ R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P(s' \mid s, a) V^*(s') \right]$

여기서 $V^*(s)$ 는 최적 가치 함수(Optimal Value Function), $\gamma \in [0, 1)$ 는 할인 인자(Discount Factor)이다.

3.4 메타휴리스틱 기반 계획법 (Metaheuristic-Based Planning)

대규모 임무 계획 문제에서 정확한 최적 해를 구하는 것이 계산적으로 불가능한 경우, 유전 알고리즘(Genetic Algorithm, GA), 개미 군집 최적화(Ant Colony Optimization, ACO), 입자 군집 최적화(Particle Swarm Optimization, PSO) 등의 메타휴리스틱 기법이 활용된다 (Dorigo & Stützle, 2004). 이들 기법은 전역 최적 해(Global Optimum)의 보장 없이도 합리적인 시간 내에 양질의 준최적 해(Near-Optimal Solution)를 도출할 수 있다.

4. 임무 계획 수립의 핵심 구성 요소

4.1 임무 목표 모델링 (Mission Objective Modeling)

임무 목표 모델링은 로봇이 달성해야 할 목표를 형식적으로 정의하는 과정이다. 목표는 단일 목표(Single Objective)일 수도 있으나, 대부분의 실제 응용에서는 다중 목표(Multi-Objective)로 구성된다. 다중 목표 최적화 문제에서는 파레토 최적성(Pareto Optimality)의 개념이 적용되며, 파레토 프론트(Pareto Front)를 탐색하여 의사 결정자에게 대안을 제공한다.

4.2 환경 표현 (Environment Representation)

임무 계획에서 환경 표현은 로봇이 활동하는 작업 공간(Workspace)을 수학적으로 모델링하는 것을 포함한다. 환경 표현의 주요 방법에는 격자 기반 표현(Grid-Based Representation), 그래프 기반 표현(Graph-Based Representation), 토폴로지 맵(Topological Map), 의미론적 맵(Semantic Map) 등이 있다.

4.3 자원 관리 (Resource Management)

임무 계획에서 자원 관리는 로봇의 배터리 잔량, 통신 대역폭, 탑재 하중(Payload) 용량, 센서 자원 등 유한한 자원을 효율적으로 배분하는 것을 의미한다. 자원 소모 모델은 일반적으로 다음과 같이 표현된다.

$r(t+1) = r(t) - d(a_t), \quad r(t) \geq r_{\min}, \quad \forall t$

여기서 $r(t)$ 는 시각 $t$ 에서의 잔여 자원량, $d(a_t)$ 는 행동 $a_t$ 에 의한 자원 소모량, $r_{\min}$ 은 최소 잔여 자원 제약을 나타낸다.

4.4 시간 제약 처리 (Temporal Constraint Handling)

임무 계획에서의 시간 제약은 시간 윈도우(Time Window), 마감 시한(Deadline), 작업 간 동기화(Synchronization) 등의 형태로 나타난다. 단순 시간 네트워크(Simple Temporal Network, STN)는 시간 제약을 관리하기 위한 대표적인 프레임워크로, 각 이벤트를 노드로, 이벤트 간의 시간 제약을 간선으로 표현한다 (Dechter et al., 1991).

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

여기서 $t_i$ 와 $t_j$ 는 이벤트 $i$ 와 $j$ 의 시각, $l_{ij}$ 와 $u_{ij}$ 는 각각 최소 및 최대 시간 간격을 나타낸다.

5. 대표적 응용 영역

임무 계획 수립은 다양한 로봇 공학 응용 분야에서 핵심적인 역할을 수행한다.

5.1 무인 항공기 임무 계획

무인 항공기(UAV)의 임무 계획에서는 비행 경로 설계, 관심 영역(Area of Interest) 탐색, 감시 영역 커버리지(Coverage) 최적화, 연료 또는 배터리 제약 관리 등이 주요 과제이다. 차량 경유 문제(Vehicle Routing Problem, VRP)의 변형으로 정식화하여 해결하는 경우가 많다 (Toth & Vigo, 2002).

5.2 재난 대응 로봇 임무 계획

재난 대응 환경에서의 임무 계획은 동적으로 변화하는 환경 조건, 불완전한 정보, 긴급한 시간 제약 등을 고려하여야 한다. 이러한 상황에서는 반응적(Reactive) 계획법과 심의적(Deliberative) 계획법을 결합한 하이브리드 아키텍처가 효과적이다 (Murphy, 2014).

5.3 해양 로봇 임무 계획

자율 수중 로봇(AUV) 및 수면 로봇(USV)의 임무 계획에서는 해류의 영향, 통신 제한, 수중 환경의 불확실성 등이 추가적인 도전 과제로 작용한다. 해류 모델을 고려한 에너지 최적 경로 계획이 핵심적 연구 주제이다 (Lolla et al., 2015).

6. 연구 동향 및 향후 전망

최근 임무 계획 수립 분야에서는 심층 강화 학습(Deep Reinforcement Learning)을 활용한 적응적 임무 계획, 대규모 언어 모델(Large Language Model)을 활용한 자연어 기반 임무 사양, 연합 학습(Federated Learning)을 활용한 프라이버시 보존 다중 로봇 임무 계획 등이 활발하게 연구되고 있다 (Shah et al., 2023). 또한, 디지털 트윈(Digital Twin) 기술과의 융합을 통하여 임무 계획의 시뮬레이션 기반 검증 및 최적화가 가능해지고 있으며, 이는 실세계 배포(Real-World Deployment) 전 안전성 검증에 기여하고 있다.

7. 참고 문헌

Fikes, R. E., & Nilsson, N. J. (1971). STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2(3-4), 189-208.
McDermott, D., et al. (1998). PDDL – The Planning Domain Definition Language. Technical Report, Yale Center for Computational Vision and Control.
Kress-Gazit, H., Fainekos, G. E., & Pappas, G. J. (2009). Temporal-logic-based reactive mission and motion planning. IEEE Transactions on Robotics, 25(6), 1370-1381.
Kaelbling, L. P., Littman, M. L., & Cassandra, A. R. (1998). Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1-2), 99-134.
Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press.
Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial Intelligence, 49(1-3), 61-95.
Toth, P., & Vigo, D. (2002). The Vehicle Routing Problem. SIAM.
Murphy, R. R. (2014). Disaster Robotics. MIT Press.
Lolla, T., Lermusiaux, P. F. J., Ueckermann, M. P., & Haley, P. J. (2015). Time-optimal path planning in dynamic flows using level set equations. Ocean Modelling, 94, 165-183.
Shah, D., et al. (2023). LM-Nav: Robotic navigation with large pre-trained models of language, vision, and action. Proceedings of the Conference on Robot Learning (CoRL).

버전: 2026-03-24 v1.0