397.1 임무 계획 수립의 정의와 개념

1. 임무 계획 수립의 정의

임무 계획 수립(Mission Planning)이란 자율 로봇 시스템이 특정 임무 목표(Mission Objective)를 달성하기 위하여 필요한 행동, 자원, 경로, 시간 등의 요소를 사전에 체계적으로 결정하는 과정을 의미한다. 보다 형식적으로 정의하면, 임무 계획 수립은 주어진 초기 상태(Initial State) s_0로부터 목표 상태(Goal State) s_g \in \mathcal{S}_{\text{goal}}까지 도달할 수 있는 행동 순서(Action Sequence) \sigma = \langle a_0, a_1, \ldots, a_{T-1} \rangle를 구성하는 것이다. 이때 각 행동 a_t \in \mathcal{A}는 환경의 상태를 변화시키며, 전체 행동 순서는 주어진 제약 조건(Constraints)을 만족하면서 목적 함수(Objective Function)를 최적화하여야 한다 (Ghallab et al., 2004).

\text{Mission Planning}: \quad \langle s_0, \mathcal{S}_{\text{goal}}, \mathcal{A}, f, \mathcal{C} \rangle \rightarrow \sigma^*

여기서 f: \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{S}는 상태 전이 함수(State Transition Function), \mathcal{C}는 제약 조건의 집합, \sigma^*는 최적 행동 순서를 각각 나타낸다.

2. 임무의 개념적 정의

임무(Mission)는 로봇 시스템이 특정 목적을 달성하기 위하여 수행하여야 할 상위 수준의 작업(Task)을 포괄적으로 지칭하는 용어이다. 임무는 단순한 단일 작업으로 구성될 수도 있으나, 대부분의 실제 응용에서는 복수의 하위 작업(Sub-task)으로 분해(Decomposition)되는 복합적 구조를 갖는다.

임무의 형식적 표현은 일반적으로 다음과 같은 튜플(Tuple)로 정의된다.

\mathcal{M} = \langle \mathcal{G}, \mathcal{T}, \mathcal{R}, \mathcal{C}_t, \mathcal{C}_s, \mathcal{C}_r \rangle

각 구성 요소의 의미는 다음과 같다.

3. 임무 계획과 작업 계획의 구분

임무 계획 수립은 작업 계획(Task Planning) 및 동작 계획(Motion Planning)과 개념적으로 구분된다. 작업 계획이 이산적인 상태 공간(Discrete State Space)에서의 논리적 행동 순서를 결정하는 것에 초점을 맞추는 반면, 임무 계획은 그보다 더 상위의 추상화 수준에서 전체 임무의 구조, 자원 배분, 시간 관리 등을 포괄적으로 다룬다.

세 가지 계획 수준 간의 관계를 정리하면 다음과 같다.

\text{Mission Planning} \supseteq \text{Task Planning} \supseteq \text{Motion Planning}

• 임무 계획(Mission Planning): 전체 임무의 목표, 우선순위, 자원 할당, 시간 계획을 수립한다. “무엇을”, “언제”, “어떤 자원으로” 수행할 것인지를 결정한다.
• 작업 계획(Task Planning): 각 임무를 구성하는 개별 작업의 논리적 순서를 결정한다. “어떤 순서로” 수행할 것인지를 결정한다.
• 동작 계획(Motion Planning): 각 작업을 실현하기 위한 구체적인 경로와 궤적을 생성한다. “어떻게” 이동할 것인지를 결정한다.

이러한 계층적 분리는 시스템의 모듈성(Modularity)과 확장성(Scalability)을 향상시키며, 각 수준에서 적합한 알고리즘과 표현 방법을 독립적으로 적용할 수 있게 한다 (Kaelbling & Lozano-Pérez, 2011).

4. 임무 계획의 구성 요소

4.1 상태 공간 (State Space)

임무 계획에서 상태 공간 \mathcal{S}는 로봇과 환경의 가능한 모든 상태의 집합을 나타낸다. 상태 s \in \mathcal{S}는 로봇의 위치, 배터리 잔량, 탑재된 센서의 상태, 작업 완료 여부 등을 포함하는 복합적 벡터(Composite Vector)로 표현된다.

s = (q, e, \tau, \phi)

여기서 q \in \mathcal{Q}는 로봇의 구성(Configuration), e \in \mathbb{R}^+는 잔여 에너지, \tau \in \mathbb{R}^+는 경과 시간, \phi \in \{0, 1\}^n는 각 하위 작업의 완료 여부를 나타내는 이진 벡터이다.

4.2 행동 공간 (Action Space)

행동 공간 \mathcal{A}는 로봇이 수행할 수 있는 모든 행동의 집합을 나타낸다. 임무 계획 수준에서의 행동은 저수준 제어 명령이 아닌 추상적 행동(Abstract Action)으로 표현된다. 예를 들어, “지점 A로 이동”, “영역 B를 탐색”, “물체 C를 수거“와 같은 고수준 명령이 해당한다.

각 행동 a \in \mathcal{A}는 다음과 같은 속성을 갖는다.

a = \langle \text{Pre}(a), \text{Eff}(a), \text{Dur}(a), \text{Res}(a) \rangle

여기서 \text{Pre}(a)는 행동의 전제 조건(Preconditions), \text{Eff}(a)는 행동의 효과(Effects), \text{Dur}(a)는 행동의 소요 시간(Duration), \text{Res}(a)는 행동에 필요한 자원(Resources)을 각각 나타낸다.

4.3 제약 조건 (Constraints)

임무 계획에서의 제약 조건은 크게 경성 제약(Hard Constraints)과 연성 제약(Soft Constraints)으로 구분된다.

**경성 제약(Hard Constraints)**은 반드시 만족되어야 하는 조건으로, 이를 위반하는 계획은 실행 불가능(Infeasible)하다. 경성 제약의 예시는 다음과 같다.

e(t) \geq e_{\min}, \quad \forall t \in [0, T]

\|q(t) - q_{\text{obs}}\| > d_{\text{safe}}, \quad \forall t \in [0, T]

여기서 e(t)는 시각 t에서의 잔여 에너지, e_{\min}은 최소 에너지 임계값, q_{\text{obs}}는 장애물의 위치, d_{\text{safe}}는 안전 거리를 나타낸다.

**연성 제약(Soft Constraints)**은 가능한 한 만족되는 것이 바람직하나 위반 시 비용(Penalty)을 부과하는 방식으로 처리되는 조건이다. 연성 제약은 목적 함수에 벌칙 항(Penalty Term)으로 반영된다.

J_{\text{total}} = J_{\text{primary}} + \sum_{k} \lambda_k \max(0, g_k(s, a))

여기서 J_{\text{primary}}는 주 목적 함수, \lambda_k는 가중치(Weight), g_k(\cdot, \cdot)는 연성 제약 함수를 나타낸다.

4.4 목적 함수 (Objective Function)

임무 계획의 목적 함수는 계획의 품질(Quality)을 정량적으로 평가하는 기준이다. 일반적인 목적 함수에는 총 임무 수행 시간의 최소화, 총 에너지 소비의 최소화, 임무 달성율의 최대화, 위험도의 최소화 등이 포함된다. 다중 목적 최적화(Multi-Objective Optimization)의 경우, 파레토 최적(Pareto Optimal) 해의 집합을 탐색하여 의사 결정자에게 대안을 제시한다.

\min_{\sigma} \mathbf{J}(\sigma) = \left[ J_1(\sigma), J_2(\sigma), \ldots, J_K(\sigma) \right]^T

여기서 \mathbf{J}(\sigma)는 K개의 목적 함수로 구성된 벡터 목적 함수(Vector Objective Function)이다.

5. 임무 계획의 계산적 특성

임무 계획 문제는 일반적으로 NP-난해(NP-Hard)에 해당하는 계산 복잡도(Computational Complexity)를 갖는다 (Bylander, 1994). 이는 상태 공간과 행동 공간의 크기가 증가함에 따라 최적 해를 구하는 데 필요한 계산 시간이 지수적으로 증가함을 의미한다. 따라서 실제 응용에서는 휴리스틱(Heuristic) 기법, 근사 알고리즘(Approximation Algorithm), 메타휴리스틱(Metaheuristic) 기법 등을 활용하여 합리적인 시간 내에 양질의 준최적 해(Near-Optimal Solution)를 도출하는 것이 일반적인 전략이다.

계획 문제의 복잡도는 문제의 특성에 따라 다음과 같이 분류된다.

6. 임무 계획 수립의 핵심 원칙

임무 계획 수립에서는 다음과 같은 핵심 원칙이 적용된다.

완전성(Completeness): 해가 존재할 경우 유한 시간 내에 반드시 해를 찾을 수 있어야 한다. 완전성은 계획기(Planner)의 이론적 보증(Theoretical Guarantee)으로서, 특히 안전 필수(Safety-Critical) 응용에서 중요하다.

최적성(Optimality): 주어진 목적 함수에 대하여 가능한 모든 해 중에서 최선의 해를 도출하여야 한다. 최적성은 자원이 제한된 환경에서 특히 중요하며, 최적 해를 보장하지 않는 경우에는 최적성 갭(Optimality Gap)을 정량적으로 분석하여야 한다.

건전성(Soundness): 계획기가 출력하는 모든 해는 실제로 실행 가능하고 목표를 달성하는 유효한 계획이어야 한다.

효율성(Efficiency): 계획 수립에 소요되는 시간과 메모리가 실시간 운용에 적합한 수준이어야 한다. 특히 동적 환경에서는 계획 수립 시간이 환경 변화의 시간 상수보다 충분히 짧아야 한다.

적응성(Adaptability): 환경의 변화나 예상치 못한 사건에 대하여 계획을 유연하게 수정할 수 있어야 한다. 이는 재계획(Replanning) 및 온라인 계획(Online Planning) 능력과 밀접한 관련이 있다.

7. 참고 문헌

• Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Elsevier.
• Kaelbling, L. P., & Lozano-Pérez, T. (2011). Hierarchical task and motion planning in the now. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 1470-1477.
• Bylander, T. (1994). The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1-2), 165-204.

버전: 2026-03-24 v1.0