396.26 결정론적 임무와 확률적 임무의 구분

1. 서론

로봇 임무 관리에서 임무의 결과 예측 가능성은 임무 계획 및 실행 전략의 설계에 근본적 영향을 미친다. 행동의 결과가 확정적으로 예측 가능한 결정론적 임무(deterministic mission)와 행동의 결과가 확률적 분포를 따르는 확률적 임무(stochastic mission)의 구분은, 적용할 수 있는 계획 알고리즘, 의사 결정 프레임워크, 실행 모니터링 전략의 선택에 직접적으로 관여하는 핵심 분류 기준이다.

본 절에서는 결정론적 임무와 확률적 임무의 형식적 정의를 수립하고, 각각의 수학적 모델링 방법론, 계획 알고리즘, 실행 특성을 상세히 비교 분석한다.

2. 결정론적 임무의 정의와 모델링

2.1 형식적 정의

결정론적 임무(deterministic mission)란, 임무를 구성하는 각 행동(action)의 실행 결과가 현재 상태에 의하여 유일하게 결정되는 임무를 의미한다. 즉, 상태 s에서 행동 a를 실행하면 항상 동일한 후속 상태 s'로 전이되며, 이 전이에 불확실성이 개입하지 않는다.

결정론적 임무의 상태 전이는 다음과 같은 결정론적 전이 함수(deterministic transition function)로 형식화된다:

\delta : S \times A \rightarrow S

여기서 S는 상태 공간(state space)이고, A는 행동 공간(action space)이다. 임의의 상태 s \in S와 행동 a \in A에 대하여, 후속 상태 s' = \delta(s, a)는 유일하게 결정된다.

결정론적 임무 계획 문제는 고전적 계획(classical planning) 프레임워크로 정식화된다:

\Pi = \langle S, s_0, S_G, A, \delta \rangle

여기서:

• S: 유한 상태 집합
• s_0 \in S: 초기 상태
• S_G \subseteq S: 목표 상태 집합
• A: 행동 집합
• \delta: 결정론적 전이 함수

계획(plan)은 초기 상태 s_0에서 출발하여 목표 상태 s_g \in S_G에 도달하는 행동 시퀀스 \pi = (a_1, a_2, \ldots, a_n)이다.

2.2 계획 알고리즘

결정론적 임무에 대한 계획 수립은 상태 공간 탐색(state-space search) 문제로 환원된다. 대표적인 알고리즘은 다음과 같다:

1. 전방 탐색(forward search): 초기 상태에서부터 행동을 적용하여 목표 상태에 도달하는 경로를 탐색한다. A*, 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 등이 이에 해당한다.
2. 후방 탐색(backward search): 목표 상태에서 역방향으로 행동의 전조건(precondition)을 추적하여 초기 상태에 도달하는 경로를 탐색한다.
3. GraphPlan: 계획 그래프(planning graph)를 구성하여 상호 배제(mutex) 관계를 분석하고, 추출 단계에서 유효한 계획을 도출한다.
4. SAT 기반 계획: 계획 문제를 명제 논리의 충족 가능성(satisfiability, SAT) 문제로 인코딩하여 SAT 솔버를 통해 해를 구한다.

결정론적 계획의 최적해는 비용 함수 c : A \rightarrow \mathbb{R}^+에 대하여 다음을 만족한다:

\pi^* = \arg\min_{\pi} \sum_{i=1}^{|\pi|} c(a_i)

2.3 특성과 장점

결정론적 임무 모델의 주요 장점은 다음과 같다:

• 예측 가능성: 계획된 행동 시퀀스의 실행 결과가 확정적으로 예측 가능하다.
• 완전성 보장: 해가 존재하면 반드시 발견할 수 있는 완전(complete) 알고리즘의 적용이 가능하다.
• 최적성 보장: 허용적(admissible) 휴리스틱을 사용하면 최적 해를 보장할 수 있다.
• 검증 용이성: 계획의 정확성을 실행 전에 형식 검증을 통하여 확인할 수 있다.

2.4 한계

결정론적 모델은 현실 세계의 불확실성을 반영하지 못한다는 근본적 한계를 지닌다. 로봇의 행동 실행은 센서 잡음(sensor noise), 액추에이터 오차(actuator error), 환경 변동(environmental perturbation) 등으로 인하여 항상 결정론적이지 않으며, 이러한 불확실성을 무시할 경우 임무 실패의 원인이 된다.

3. 확률적 임무의 정의와 모델링

3.1 형식적 정의

확률적 임무(stochastic mission)란, 임무를 구성하는 행동의 결과가 확률적으로 결정되는 임무를 의미한다. 상태 s에서 행동 a를 실행하면 여러 가능한 후속 상태 중 하나로 전이되며, 각 전이는 확률 분포를 따른다.

확률적 임무의 상태 전이는 확률적 전이 함수(stochastic transition function)로 형식화된다:

T : S \times A \times S \rightarrow [0, 1]

여기서 T(s, a, s') = P(s' \mid s, a)는 상태 s에서 행동 a를 실행했을 때 상태 s'로 전이될 확률이다. 전이 확률은 다음 조건을 만족한다:

\sum_{s' \in S} T(s, a, s') = 1, \quad \forall s \in S, \; a \in A

3.2 마르코프 결정 과정 기반 모델링

확률적 임무의 가장 대표적인 수학적 프레임워크는 마르코프 결정 과정(Markov Decision Process, MDP)이다. MDP는 다음과 같은 튜플로 정의된다:

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

여기서:

• S: 상태 공간
• A: 행동 공간
• T(s, a, s'): 전이 확률 함수
• R(s, a): 보상 함수(reward function)로, 상태 s에서 행동 a를 실행한 결과에 대한 즉각적 보상을 정의한다
• \gamma \in [0, 1): 할인 인자(discount factor)

MDP에서의 최적 정책(optimal policy)은 기대 누적 보상(expected cumulative reward)을 최대화하는 상태-행동 매핑이다:

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

최적 정책은 벨만 최적 방정식(Bellman optimality equation)을 만족한다:

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

3.3 부분 관측 마르코프 결정 과정

로봇이 환경 상태를 직접 관측할 수 없고 센서를 통한 간접적 관측만 가능한 경우, 부분 관측 마르코프 결정 과정(Partially Observable MDP, POMDP)이 적용된다:

\text{POMDP} = \langle S, A, T, R, \Omega, O, \gamma \rangle

여기서:

• \Omega: 관측 공간(observation space)
• O(o \mid s', a): 관측 확률 함수로, 행동 a를 실행하여 상태 s'에 도달했을 때 관측 o를 수신할 확률

POMDP에서 에이전트는 상태에 대한 확률적 믿음(belief) b(s) = P(s \mid h)을 유지하며, h는 관측 이력(history)이다. 믿음 갱신(belief update)은 베이즈 정리(Bayes’ theorem)에 의하여 수행된다:

b'(s') = \eta \cdot O(o \mid s', a) \sum_{s \in S} T(s, a, s') b(s)

여기서 \eta는 정규화 상수이다.

3.4 계획 알고리즘

확률적 임무에 대한 계획 알고리즘은 결정론적 임무와 본질적으로 다른 접근을 취한다:

1. 가치 반복(Value Iteration): MDP의 벨만 방정식을 반복적으로 풀어 최적 가치 함수와 정책을 도출한다.
2. 정책 반복(Policy Iteration): 정책 평가(policy evaluation)와 정책 개선(policy improvement)을 교대로 수행하여 최적 정책에 수렴한다.
3. 점 기반 가치 반복(Point-Based Value Iteration): POMDP의 믿음 공간에서 대표 점들을 표본 추출하여 근사적으로 최적 정책을 계산한다.
4. 몬테카를로 트리 탐색(Monte Carlo Tree Search, MCTS): 확률적 시뮬레이션을 통하여 전방 탐색을 수행하며, 대규모 상태 공간에서 효과적이다.

4. 비교 분석

4.1 모델링 관점의 비교

4.2 계획 형태의 근본적 차이

결정론적 임무의 계획 결과는 고정된 행동 시퀀스(action sequence), 즉 개루프 계획(open-loop plan)이다:

\pi_{\text{det}} = (a_1, a_2, \ldots, a_n)

이 시퀀스는 초기 상태에서 순차적으로 실행되며, 실행 중 상태 피드백을 활용하지 않는다.

반면, 확률적 임무의 계획 결과는 상태에 따라 행동을 선택하는 정책 함수(policy function), 즉 폐루프 계획(closed-loop plan)이다:

\pi_{\text{stoch}} : S \rightarrow A \quad \text{또는} \quad \pi_{\text{stoch}} : B \rightarrow A

여기서 B는 믿음 공간(belief space)이다. 정책은 현재 상태(또는 믿음 상태)에 따라 행동을 동적으로 결정하므로, 실행 중 발생하는 불확실성에 대한 적응적 대응이 가능하다.

이 차이는 임무 관리 시스템의 아키텍처에 근본적 영향을 미친다. 결정론적 임무는 계획과 실행의 분리(separation)가 자연스러우나, 확률적 임무는 계획과 실행의 긴밀한 결합(tight coupling)을 요구한다.

4.3 계산 복잡도

결정론적 계획 문제는 일반적으로 PSPACE-완전(PSPACE-complete)이다. 그러나 실제론 구조적 성질을 활용한 효율적 알고리즘(A*, Fast Downward 등)이 개발되어 있어, 중대규모 문제까지 실용적 시간 내에 해를 구할 수 있다.

확률적 계획 문제는 결정론적 문제보다 계산 복잡도가 현저히 높다. MDP는 다항 시간(polynomial time)에 풀 수 있으나, POMDP는 PSPACE-난해(PSPACE-hard)이며 정확한 최적해의 계산이 대규모 문제에서는 사실상 불가능하다. 따라서, 근사 알고리즘(approximate algorithm)과 온라인 계획(online planning) 기법이 필수적이다.

4.4 강건성과 안전성

결정론적 계획은 불확실성에 대한 대비가 부재하므로, 실행 중 예기치 않은 전이가 발생하면 계획이 무효화되어 임무 실패로 이어질 수 있다. 이를 보완하기 위하여 조건부 계획(contingency planning)이나 실행 감시(execution monitoring)가 부가적으로 요구된다.

확률적 계획은 불확실성을 모델 내에 명시적으로 반영하므로, 다양한 환경 변동에 대하여 사전에 대비된 정책을 생성할 수 있다. 이는 안전-필수 시스템에서 중요한 강점으로 작용한다. 특히, 위험 인지 MDP(risk-aware MDP)에서는 기대 보상뿐 아니라 최악의 경우(worst-case) 성능까지 고려하여 정책을 최적화할 수 있다:

\pi^*_{\text{risk}} = \arg\max_{\pi} \left\{ \mathbb{E}[R_\pi] - \lambda \cdot \text{CVaR}_\alpha(R_\pi) \right\}

여기서 \text{CVaR}_\alpha는 조건부 가치 위험(Conditional Value-at-Risk)이고, \lambda는 위험 회피 계수이다.

5. 하이브리드 접근법

실제 로봇 임무에서는 순수한 결정론적 또는 확률적 모델만으로는 불충분한 경우가 많다. 이에 따라, 두 접근법을 결합한 하이브리드 전략이 활용된다.

5.1 결정론화(Determinization)

확률적 문제를 결정론적 문제로 근사하는 결정론화 기법이 있다. FF-Replan (Yoon et al., 2007)은 확률적 전이에서 가장 가능성 높은(most likely) 결과만을 고려하여 결정론적 계획을 수립하고, 예상과 다른 결과가 관측되면 재계획을 수행한다. 이 접근법은 계산 효율성과 적응성 간의 균형을 추구한다.

5.2 확률적 도로 지도 위의 결정론적 계획

경로 계획 수준에서는 확률적 도로 지도(Probabilistic Roadmap, PRM)를 구성하고, 그 위에서 결정론적 탐색 알고리즘을 적용하는 방법이 있다. 이는 연속 공간의 불확실성을 이산 그래프 구조로 변환하여 계산 가능성을 확보한다.

5.3 조건부 계획(Contingency Planning)

결정론적 계획에 실패 분기(failure branch)를 추가하여, 특정 조건에서의 대안 계획을 사전에 준비하는 조건부 계획이 있다. 이는 결정론적 프레임워크 내에서 제한적으로 불확실성에 대응하는 방법이다:

\pi_{\text{contingent}} = \begin{cases} \pi_A & \text{if } \text{condition}_1 \\ \pi_B & \text{if } \text{condition}_2 \\ \vdots \end{cases}

6. 적용 도메인별 적합성

7. 참고문헌

• Puterman, M.L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons.
• Kaelbling, L.P., Littman, M.L., and Cassandra, A.R. (1998). “Planning and Acting in Partially Observable Stochastic Domains.” Artificial Intelligence, 101(1–2), 99–134.
• Ghallab, M., Nau, D., and Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
• Yoon, S.W., Fern, A., and Givan, R. (2007). “FF-Replan: A Baseline for Probabilistic Planning.” Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 2007.
• Thrun, S., Burgard, W., and Fox, D. (2005). Probabilistic Robotics. MIT Press.
• Kurniawati, H., Hsu, D., and Lee, W.S. (2008). “SARSOP: Efficient Point-Based POMDP Planning by Approximating Optimally Reachable Belief Spaces.” Proceedings of Robotics: Science and Systems IV.

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