396.43 상태 머신의 한계와 상태 폭발 문제

1. 개요

유한 상태 머신(FSM)은 직관적이고 형식적으로 분석 가능한 실행 모델이지만, 임무의 복잡도가 증가함에 따라 근본적인 한계를 드러낸다. 특히 상태 폭발(State Explosion) 문제는 FSM 기반 임무 관리 시스템의 확장성을 심각하게 제약하며, 이는 로봇 공학 분야에서 대안적 실행 모델의 탐구를 촉진하는 주요 동기가 되었다.

2. 상태 폭발 문제의 정의

2.1 상태 공간의 기하급수적 증가

상태 폭발(State Explosion, State Space Explosion)은 시스템을 구성하는 독립적 측면(Aspect)이 증가할 때, 이를 표현하는 데 필요한 상태의 수가 기하급수적으로 증가하는 현상을 말한다(Clarke et al., 1999).

n개의 독립적인 이진 변수(Binary Variable)를 FSM으로 표현할 경우, 필요한 상태의 수는 다음과 같다.

|Q| = 2^n

보다 일반적으로, k개의 독립적 구성 요소가 각각 m_i개의 상태를 가질 때, 직교적 합성(Cartesian Product)을 통한 전체 상태 수는 다음과 같다.

|Q_{\text{total}}| = \prod_{i=1}^{k} m_i

예를 들어, 로봇의 임무 상태(5개), 배터리 상태(3개), 통신 상태(3개), 센서 상태(4개), 환경 조건(3개)을 모두 단일 FSM으로 표현하면, 필요한 상태의 수는 5 \times 3 \times 3 \times 4 \times 3 = 540개가 된다. 여기에 전이의 수는 상태 수의 제곱에 비례하여 증가할 수 있다.

|\delta|_{\text{max}} = |Q|^2 \cdot |\Sigma| = 540^2 \cdot |\Sigma|

2.2 조합적 폭발의 본질

상태 폭발의 본질은 FSM이 시스템의 모든 독립적 측면을 단일 상태 변수로 평탄화(Flatten)하는 데서 기인한다. 독립적으로 변화할 수 있는 시스템 속성들이 FSM에서는 모든 가능한 조합으로 명시적으로 열거되어야 하므로, 속성의 수가 선형적으로 증가하더라도 상태의 수는 지수적으로 증가한다.

이를 형식적으로 표현하면, n개의 독립 구성 요소 C_1, C_2, \ldots, C_n이 각각 유한 상태 머신 M_i = (Q_i, \Sigma_i, \delta_i, q_{0,i})로 모델링될 때, 이들의 동기적 합성(Synchronous Composition)은 다음과 같다.

M_{\text{composed}} = M_1 \times M_2 \times \ldots \times M_n

Q_{\text{composed}} = Q_1 \times Q_2 \times \ldots \times Q_n

이 합성의 복잡도는 O(\prod_{i=1}^{n} |Q_i|)이다.

3. FSM의 구조적 한계

3.1 재사용성의 결여(Lack of Reusability)

평탄한(Flat) FSM에서 상태와 전이는 특정 맥락에 종속되어 정의된다. 동일한 기능적 행동(예: 장애물 회피)이 서로 다른 임무 맥락에서 사용될 때, 각 맥락에 대해 별도의 상태와 전이를 중복 정의하여야 한다.

\text{NavigateState}_{\text{patrol}} \neq \text{NavigateState}_{\text{search}} \neq \text{NavigateState}_{\text{escort}}

이는 코드 중복을 야기하고, 하나의 행동을 수정할 때 관련된 모든 상태를 개별적으로 갱신하여야 하는 유지보수의 부담을 초래한다.

3.2 모듈성의 부재(Lack of Modularity)

FSM은 모든 상태와 전이가 전역적(Global) 수준에서 정의되는 단일체(Monolithic) 구조를 갖는다. 새로운 기능을 추가하거나 기존 기능을 수정할 때, 기존 전이 구조와의 상호작용을 모두 고려하여야 하므로 변경의 파급 효과(Ripple Effect)가 크다.

상태 q_{\text{new}}를 기존 FSM에 추가하는 경우, 최악의 경우 |Q|개의 기존 상태 각각에 대해 q_{\text{new}}와의 전이를 정의하여야 한다.

\Delta|\delta|_{\text{max}} = 2 \cdot |Q| \cdot |\Sigma|

3.3 반응성의 한계

FSM에서 특정 상태는 특정 이벤트에만 반응하도록 설계된다. 임무 수행 중 언제든지 발생할 수 있는 전역적 이벤트(예: 긴급 정지, 배터리 부족 경고)를 처리하기 위해서는 모든 상태에서 해당 이벤트에 대한 전이를 명시적으로 정의하여야 한다.

|Q|개의 상태에서 k개의 전역 이벤트를 처리하려면, 추가로 |Q| \times k개의 전이가 필요하다.

\Delta|\delta|_{\text{global}} = |Q| \cdot k

이는 FSM의 복잡도를 더욱 증가시키며, 전이 다이어그램의 가독성을 현저히 저하시킨다.

3.4 동시성 표현의 어려움

FSM은 본질적으로 한 시점에 하나의 상태만 활성화되는 단일 스레드(Single-Thread) 실행 모델이다. 로봇 시스템에서 빈번하게 요구되는 병렬 행동의 동시 실행(예: 이동하면서 센서 데이터 수집)을 FSM으로 표현하기 어렵다.

두 개의 독립적인 행동 A와 B가 각각 m개와 n개의 상태를 가질 때, 이들의 동시 실행을 단일 FSM으로 표현하면 m \times n개의 상태가 필요하다.

|Q_{A \parallel B}| = |Q_A| \times |Q_B| = m \times n

이 조합적 증가는 동시에 실행되는 행동의 수가 늘어날수록 급격히 심화된다.

4. 상태 폭발의 정량적 분석

4.1 실제 임무 시나리오에서의 상태 증가

다음 표는 임무 복잡도에 따른 FSM 상태 수의 증가를 보여준다.

이 분석은 임무의 복잡도가 실제적인 수준으로 증가할 때, 평탄한 FSM이 관리 불가능한 크기에 도달함을 명확히 보여준다.

4.2 전이 복잡도의 증가

상태 수의 증가에 따른 전이 복잡도의 증가율은 다음과 같이 분석된다. 완전 연결(Fully Connected) FSM에서 최대 전이 수는 다음과 같다.

|\delta|_{\text{max}} = |Q| \times (|Q| - 1) \times |\Sigma|

실제로는 모든 상태 쌍 사이에 전이가 존재하지 않으므로, 전이 밀도(Transition Density) \rho를 정의한다.

\rho = \frac{|\delta|}{|Q| \times (|Q| - 1) \times |\Sigma|}

전형적인 로봇 임무 FSM에서 \rho는 0.01에서 0.1 사이의 값을 가지지만, |Q|가 크면 |\delta|도 비례적으로 증가한다.

5. 유지보수성과 검증 비용의 증가

5.1 설계 복잡도

상태 수가 증가하면 FSM의 설계와 이해가 급격히 어려워진다. 인간 설계자가 효과적으로 관리할 수 있는 FSM의 상태 수는 일반적으로 수십 개 수준으로 알려져 있다(Harel, 1987). 이를 초과하면 설계 오류의 발생 확률이 급증하고, 오류의 발견과 수정이 극도로 어려워진다.

5.2 검증 비용

모델 검사(Model Checking) 기법을 적용한 형식적 검증의 계산 비용은 상태 공간의 크기에 직접적으로 의존한다. 대표적인 시간 논리(Temporal Logic) 속성의 검증 시간 복잡도는 다음과 같다.

T_{\text{verify}} = O(|Q| \times |\delta| \times |\phi|)

여기서 |\phi|는 검증 속성(Property)의 크기이다. 상태 폭발이 발생하면 검증 비용이 실용적 한계를 초과하게 된다(Clarke et al., 1999).

5.3 테스트 경로의 폭발

FSM의 모든 전이를 최소 한 번 이상 실행하는 전이 커버리지(Transition Coverage) 테스트를 위해 필요한 최소 테스트 경로의 수는 중국인 우편배달부 문제(Chinese Postman Problem)와 관련되며, FSM의 크기에 비례하여 증가한다.

6. 상태 폭발 완화 전략

6.1 직교 영역(Orthogonal Regions)

Harel(1987)이 제안한 스테이트차트(Statecharts)는 직교 영역(Orthogonal Regions)을 도입하여 독립적 구성 요소를 병렬적으로 표현한다. 이를 통해 상태의 명시적 조합 없이도 동시성을 표현할 수 있다.

|Q_{\text{statechart}}| = \sum_{i=1}^{k} m_i \quad \text{vs.} \quad |Q_{\text{flat FSM}}| = \prod_{i=1}^{k} m_i

직교 영역의 도입은 상태 수를 곱셈적에서 덧셈적으로 감소시킨다.

6.2 상태 변수의 도입

확장된 유한 상태 머신(EFSM)은 명시적 상태 대신 변수를 도입하여 시스템의 일부 측면을 데이터로 표현한다. 이를 통해 유사한 상태들을 하나의 변수화된 상태로 통합할 수 있다.

Q_{\text{EFSM}} = Q_{\text{core}} \times V

여기서 Q_{\text{core}}는 핵심 상태의 집합, V는 변수의 값 공간이다. |Q_{\text{core}}| \ll |Q_{\text{flat FSM}}|이므로, EFSM은 상태 폭발을 부분적으로 완화한다.

6.3 대안적 실행 모델로의 전환

상태 폭발 문제의 근본적 해결을 위해 다양한 대안적 실행 모델이 제안되었다.

계층적 상태 머신(Hierarchical FSM, HFSM): 상태를 계층적으로 구성하여 복잡도를 분산시킨다.

행동 트리(Behavior Tree): 트리 구조를 통해 모듈적이고 재사용 가능한 행동 조합을 지원한다(Colledanchise & Ögren, 2018).

페트리넷(Petri Net): 동시성과 자원 경합을 자연스럽게 표현한다.

이들 모델은 FSM의 표현력을 유지하면서도 상태 폭발 문제를 구조적으로 완화하는 특성을 갖는다.

7. 요약

FSM 기반 임무 관리의 핵심적 한계는 상태 폭발 문제에 있다. 독립적 구성 요소의 수가 증가할 때 상태 수가 기하급수적으로 증가하며, 이는 재사용성, 모듈성, 동시성 표현, 유지보수성, 검증 비용의 모든 측면에서 심각한 제약을 초래한다. 직교 영역, EFSM, 그리고 행동 트리나 계층적 상태 머신과 같은 대안적 모델은 이 문제를 구조적으로 완화하기 위한 접근법이다.

8. 참고 문헌

• Clarke, E. M., Grumberg, O., & Peled, D. A. (1999). Model Checking. MIT Press.
• Harel, D. (1987). “Statecharts: A Visual Formalism for Complex Systems.” Science of Computer Programming, 8(3), 231–274.
• Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
• Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley.
• Lee, E. A., & Seshia, S. A. (2017). Introduction to Embedded Systems: A Cyber-Physical Systems Approach (2nd ed.). MIT Press.

v0.1