396.12 임무 계획(Mission Planning) 기능

1. 임무 계획의 정의와 범위

임무 계획(Mission Planning)은 임무 관리 시스템의 핵심 기능으로, 주어진 임무 목표를 달성하기 위한 과업 시퀀스를 체계적으로 생성하는 과정이다. 이 과정은 현재의 세계 상태(World State), 로봇의 능력(Capability), 가용 자원(Available Resource), 그리고 제약 조건(Constraint)을 종합적으로 고려하여 실행 가능하고 최적에 가까운 계획을 산출한다.

형식적으로, 임무 계획 문제는 다음과 같이 정의된다:

\text{Planning Problem} = \langle \mathcal{S}_0, \mathcal{G}, \mathcal{O}, \mathcal{C} \rangle

여기서 \mathcal{S}_0는 초기 상태, \mathcal{G}는 목표 상태 조건, \mathcal{O}는 사용 가능한 연산자(Operator) 집합, \mathcal{C}는 제약 조건 집합이다.

2. 고전적 계획 수립

2.1 STRIPS 형식의 계획

고전적 AI 계획(Classical AI Planning)에서 계획 수립은 초기 상태에서 목표 상태에 도달하는 연산자(행동)의 시퀀스를 탐색하는 문제이다(Fikes and Nilsson, 1971). STRIPS 형식에서 각 연산자는 전제 조건(Precondition), 추가 리스트(Add List), 삭제 리스트(Delete List)로 기술된다.

계획은 초기 상태에서 연산자를 순차적으로 적용하여 목표 상태에 도달하는 시퀀스이다:

\pi = \langle o_1, o_2, \ldots, o_k \rangle \quad \text{such that} \quad \mathcal{G} \subseteq \gamma(\mathcal{S}_0, \pi)

여기서 \gamma(\mathcal{S}_0, \pi)는 초기 상태에 계획 \pi의 모든 연산자를 순차 적용한 결과 상태이다.

2.2 상태 공간 탐색

계획 수립은 상태 공간 그래프(State Space Graph)에서의 탐색 문제로 환원된다. 탐색 전략은 크게 전진 탐색(Forward Search)과 후진 탐색(Backward Search)으로 구분된다:

전진 탐색(Forward Search): 초기 상태에서 시작하여 적용 가능한 연산자를 적용하며 목표 상태를 향해 탐색한다.

\mathcal{S}_0 \xrightarrow{o_1} \mathcal{S}_1 \xrightarrow{o_2} \mathcal{S}_2 \xrightarrow{} \cdots \xrightarrow{o_k} \mathcal{S}_{\text{goal}}

후진 탐색(Backward Search): 목표 상태에서 시작하여 목표를 달성하는 데 필요한 연산자를 역방향으로 탐색한다.

2.3 휴리스틱 탐색

상태 공간의 크기가 방대한 경우, 휴리스틱 함수 h(s)를 활용한 정보 있는 탐색(Informed Search)이 필수적이다. A* 알고리즘은 f(s) = g(s) + h(s)를 평가 함수로 사용하여 최적해를 보장한다.

대표적인 휴리스틱:

• 삭제 완화 휴리스틱(Delete Relaxation Heuristic): 삭제 효과를 무시한 완화 문제의 해를 휴리스틱으로 사용한다.
• 패턴 데이터베이스(Pattern Database): 추상화된 부분 문제의 최적 비용을 사전에 계산하여 저장한다.
• 랜드마크 휴리스틱(Landmark Heuristic): 모든 유효 계획에 반드시 포함되어야 하는 사실(Landmark)의 수를 세어 하한을 산출한다.

3. 계층적 계획 수립

3.1 HTN 계획

계층적 작업 네트워크(HTN) 계획은 고수준 과업을 메서드(Method)를 통해 반복적으로 분해하여 원시 행동의 시퀀스를 생성한다(Nau et al., 2003).

HTN 계획 문제는 다음과 같이 정의된다:

\text{HTN Problem} = \langle \mathcal{S}_0, \mathcal{D}, d_0 \rangle

여기서 \mathcal{D}는 도메인 지식(메서드와 연산자의 집합), d_0는 초기 과업 네트워크이다.

HTN 계획의 장점:

• 도메인 지식의 효과적 활용으로 탐색 공간을 대폭 축소한다.
• 계층적 구조가 임무 관리의 자연스러운 추상화와 일치한다.
• 비전문가도 직관적으로 이해할 수 있는 계획을 생성한다.

3.2 SHOP2 알고리즘

SHOP2(Simple Hierarchical Ordered Planner 2)는 대표적인 HTN 계획기로, 순서화된 과업 분해(Ordered Task Decomposition)를 통해 효율적인 계획 수립을 수행한다(Nau et al., 2003).

4. 시간 계획

실제 로봇 임무에서는 행동의 시간적 속성(지속 시간, 동시 실행, 시간 제약)이 핵심적이다. PDDL2.1의 시간 계획(Temporal Planning)은 지속적 행동(Durative Action)과 시간 제약을 명시적으로 지원한다(Fox and Long, 2003).

지속적 행동의 형식적 표현:

\text{DurativeAction}(a) = \langle \text{dur}(a), \text{cond}_{\text{start}}, \text{cond}_{\text{over}}, \text{cond}_{\text{end}}, \text{eff}_{\text{start}}, \text{eff}_{\text{end}} \rangle

여기서 \text{dur}(a)는 행동 지속 시간, \text{cond}_{\text{start/over/end}}은 시작/진행/종료 시점의 조건, \text{eff}_{\text{start/end}}은 시작/종료 시점의 효과이다.

5. 확률적 계획

5.1 조건부 계획

환경의 비결정성을 고려하는 조건부 계획(Contingent Planning)은 관측 결과에 따라 분기(Branch)하는 트리 구조의 계획을 생성한다:

\pi_{\text{contingent}} = \begin{cases} \pi_1 & \text{if } o = o_1 \\ \pi_2 & \text{if } o = o_2 \\ \vdots \end{cases}

5.2 순응적 계획

순응적 계획(Conformant Planning)은 관측 없이도 모든 가능한 초기 상태에서 목표를 달성하는 계획을 생성한다. 이는 초기 불확실성이 존재하지만 관측이 불가능한 경우에 적용된다.

6. 온라인 계획과 오프라인 계획

현대의 임무 관리 시스템은 오프라인에서 초기 계획을 수립하고, 온라인에서 실시간 정보를 반영하여 계획을 갱신하는 하이브리드 접근법을 채택한다.

7. 다중 목표 계획

다중 목표(Multi-Objective) 계획에서는 경쟁적 관계에 있는 복수의 최적화 목표를 동시에 고려해야 한다:

\min_\pi \mathbf{J}(\pi) = [J_1(\pi), J_2(\pi), \ldots, J_p(\pi)]^T

이 경우, 파레토 최적(Pareto Optimal) 해의 집합을 구하고, 의사 결정자(운용자 또는 자율 시스템)가 적절한 해를 선택하는 과정이 필요하다.

8. 참고 문헌

• Fikes, R. E., and Nilsson, N. J. (1971). “STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving.” Artificial Intelligence, 2(3-4), 189-208.
• Fox, M., and Long, D. (2003). “PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains.” Journal of Artificial Intelligence Research, 20, 61-124.
• Ghallab, M., Nau, D., and Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.
• Nau, D., Au, T. C., Ilghami, O., Kuter, U., Murdock, J. W., Wu, D., and Yaman, F. (2003). “SHOP2: An HTN Planning System.” Journal of Artificial Intelligence Research, 20, 379-404.

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