1291.2 유한 상태 머신의 근본적 설계 한계
1. 형식적 정의와 구조적 제약
유한 상태 머신(Finite State Machine, FSM)은 형식적으로 5-튜플 M = (Q, \Sigma, \delta, q_0, F)로 정의된다. 여기서 Q는 유한 상태 집합, \Sigma는 입력 알파벳, \delta: Q \times \Sigma \rightarrow Q는 전이 함수, q_0 \in Q는 초기 상태, F \subseteq Q는 수락 상태 집합이다. 이 형식적 정의는 FSM이 임의의 시점에서 정확히 하나의 상태에만 존재하며, 입력에 따라 결정론적으로 상태를 전환함을 의미한다.
이러한 “단일 활성 상태(single active state)” 제약은 FSM의 가장 근본적인 설계 한계의 원천이다. 현실 세계의 로봇 시스템은 동시에 다수의 독립적인 관심사(concern)를 추적하고 다수의 병행 행동을 수행해야 하나, 기본 FSM 모델은 이러한 다차원적 상태 표현을 단일 상태 변수로 평탄화(flattening)할 것을 요구한다.
2. 상태 공간의 조합적 폭발
FSM의 가장 심각한 설계 한계는 상태 공간의 조합적 폭발(combinatorial explosion)이다. 시스템이 m개의 독립적 상태 차원(state dimension)을 가지고, 각 차원 i가 k_i개의 가능한 값을 가질 때, FSM에서 이를 표현하기 위한 총 상태 수는 곱공간의 크디널리티인
|Q| = \prod_{i=1}^{m} k_i
이 된다. 로봇 시스템에서 전형적으로 고려되는 상태 차원의 예시는 다음과 같다:
| 상태 차원 | 가능한 값의 수 | 예시 |
|---|---|---|
| 임무 단계 | 5–10 | 초기화, 탐색, 접근, 작업, 복귀 |
| 배터리 수준 | 3–4 | 정상, 경고, 위험, 고갈 |
| 센서 상태 | 2–3 | 정상, 이상, 미연결 |
| 통신 상태 | 2–3 | 연결, 불안정, 단절 |
| 장애물 여부 | 2 | 존재, 부재 |
| 비상 정지 | 2 | 활성, 비활성 |
이 6개 차원만으로도 10 \times 4 \times 3 \times 3 \times 2 \times 2 = 1{,}440개의 상태가 필요하며, 각 상태에서의 전이 규칙이 개별적으로 정의되어야 한다. 상태 수 n에 대하여 전이의 최대 수는 O(n^2 \cdot |\Sigma|)에 달하므로, 전이 규칙의 정의와 검증에 소요되는 비용은 상태 수의 제곱에 비례하여 증가한다.
3. 단일 상태 제약의 표현력 한계
FSM의 “단일 활성 상태” 제약은 다중 병행 행동의 표현에서 근본적인 한계를 드러낸다. 예를 들어, 이동 로봇이 “목표 지점으로 이동하면서 동시에 장애물을 감시하고, 배터리 잔량을 모니터링“해야 하는 상황을 고려하면, 이 세 가지 동시적 행동을 단일 상태로 표현하기 위해서는 모든 조합에 대한 복합 상태(예: “이동_중_감시_정상_배터리_정상”, “이동_중_감시_이상_배터리_경고” 등)를 개별적으로 정의해야 한다. 이는 상태 공간을 직접적으로 폭증시키는 원인이 된다.
4. 전이 규칙의 비국소성
FSM에서 하나의 상태를 추가하거나 제거할 때, 해당 상태와 관련된 모든 입력 전이(incoming transition)와 출력 전이(outgoing transition)를 함께 정의하거나 갱신해야 한다. 이러한 전이 규칙의 비국소성(non-locality)은 FSM의 확장을 전체 시스템에 대한 전면적 재검토를 요구하는 고비용 작업으로 만든다.
상태 q_{\text{new}}를 기존의 n개 상태를 가진 FSM에 추가할 때, 최악의 경우 q_{\text{new}}로의 입력 전이 n \cdot |\Sigma|개와 q_{\text{new}}로부터의 출력 전이 n \cdot |\Sigma|개를 정의해야 하므로, 전이 규칙의 추가량은 O(n \cdot |\Sigma|)에 비례한다. 이는 시스템의 규모가 커질수록 수정 비용이 선형적으로 증가함을 의미하며, 대규모 시스템에서의 점진적 확장(incremental extension)을 비실용적으로 만든다.
5. 계층적 확장의 한계
계층적 상태 머신(Hierarchical State Machine, HSM)과 Harel의 Statecharts (Harel, 1987)는 복합 상태(composite state)와 직교 영역(orthogonal region)을 도입하여 FSM의 상태 폭발 문제를 완화하고자 하였다. 복합 상태는 상태의 계층적 중첩(nesting)을 통하여 추상화 수준을 제공하며, 직교 영역은 독립적인 상태 차원의 병렬 표현을 가능하게 한다.
그러나 HSM과 Statecharts에서도 다음과 같은 근본적 문제가 잔존한다:
- 계층 간 전이의 복잡도: 내부 상태에서 외부 상태로의 전이, 깊은 이력(deep history) 상태로의 복귀 등 계층을 횡단하는 전이의 의미론(semantics)이 복잡하며, 이에 대한 정확한 구현이 어렵다.
- 직교 영역 간 동기화: 독립적으로 진행되는 직교 영역 간의 동기화와 상호작용을 정의하기 위한 이벤트 통신 메커니즘이 필요하며, 이는 추가적인 설계 복잡도를 유발한다.
- 진입/퇴출 행동의 관리: 복합 상태의 진입(entry) 및 퇴출(exit) 행동이 계층적으로 전파되며, 이에 대한 정확한 실행 순서의 보장이 구현 수준에서 어렵다.
6. 결정론적 구조의 한계
FSM의 결정론적 전이 모델은 설계 시점에서 모든 환경 변화를 예측하고 이에 대한 전이를 사전에 정의할 것을 요구한다. 이는 정적이고 예측 가능한 환경에서는 적합하나, 비구조적(unstructured) 환경에서 예측 불가능한 상황에 대응해야 하는 자율 로봇 시스템에서는 근본적으로 부적합하다. 새로운 환경 조건이 발생할 때마다 전이 규칙을 추가해야 하며, 이는 FSM의 지속적 팽창과 복잡화를 초래한다.
7. 종합
유한 상태 머신의 근본적 설계 한계는 단일 활성 상태 제약, 상태 공간의 조합적 폭발, 전이 규칙의 비국소성, 계층적 확장의 불완전성, 결정론적 사전 정의의 요구 등으로 요약된다. 이러한 한계들은 개별적으로도 심각하나, 실제 로봇 시스템에서는 복합적으로 작용하여 FSM 기반 행동 제어의 실용적 한계를 극대화한다. 행동 트리(Behavior Tree)는 이러한 구조적 제약을 트리 기반 계층적 분해, 노드 단위의 모듈화, 조합적 제어 흐름으로 대체함으로써 근본적으로 다른 설계 패러다임을 제시한다.
8. 참고 문헌
- Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
- Harel, D. (1987). “Statecharts: A Visual Formalism for Complex Systems.” Science of Computer Programming, 8(3), 231–274.
- Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation. 3rd ed., Addison-Wesley.
v0.1.0