1291.4 상태 수 증가에 따른 전이 복잡도의 지수적 증가

1. 전이 복잡도의 이론적 분석

유한 상태 머신(FSM) $M = (Q, \Sigma, \delta, q_0, F)$ 에서 전이 함수 $\delta: Q \times \Sigma \rightarrow Q$ 는 모든 상태-입력 쌍 $(q, \sigma)$ 에 대하여 다음 상태를 결정한다. 완전 정의(totally defined) FSM에서 전이의 총 수는

$|\delta| = |Q| \times |\Sigma|$

이다. 상태 집합의 크기 $|Q| = n$ 이 증가함에 따라, 전이의 총 수는 $n$ 에 선형적으로 비례하여 증가한다. 그러나 이는 각 상태에서 단일 입력에 대하여 단일 전이만 정의하는 결정론적 FSM의 경우이며, 실제 로봇 시스템에서는 다음과 같은 요인에 의하여 전이 복잡도가 더 빠르게 증가한다.

2. 다중 상태 변수에 의한 상태 수의 곱적 증가

로봇 시스템에서 상태 수 $n$ 은 독립적 상태 변수의 곱공간(product space)으로 결정되므로, $m$ 개의 독립 변수가 각각 $k$ 개의 값을 가질 때

$n = k^m$

으로 상태 변수의 수 $m$ 에 대하여 지수적으로 증가한다. 이에 따라 전이의 총 수도

$|\delta| = k^m \times |\Sigma|$

로 지수적으로 증가하며, 이것이 “전이 복잡도의 지수적 증가“의 핵심 메커니즘이다.

2.1 정량적 분석

다음 표는 상태 변수의 수 $m$ 과 각 변수의 값의 수 $k$ 에 따른 전체 상태 수와 전이 수(입력 이벤트 $|\Sigma| = 10$ 으로 가정)를 보여준다:

| $m$ (변수 수) | $k$ (값의 수) | 상태 수 $k^m$ | 전이 수 $k^m \times |\Sigma\vert$ |
|:—:|:—:|—:|—:|
| 3 | 3 | 27 | 270 |
| 4 | 3 | 81 | 810 |
| 5 | 3 | 243 | 2,430 |
| 6 | 3 | 729 | 7,290 |
| 7 | 3 | 2,187 | 21,870 |
| 8 | 3 | 6,561 | 65,610 |
| 5 | 4 | 1,024 | 10,240 |
| 6 | 4 | 4,096 | 40,960 |

상태 변수가 5개에서 8개로 증가하는 것만으로 전이 수가 약 27배 폭증하며, 이는 설계, 구현, 검증에 필요한 노력이 지수적으로 증가함을 의미한다.

3. 교차 전이의 증가

현실의 FSM에서는 단순히 “현재 상태 + 입력 → 다음 상태“의 결정론적 전이만이 존재하는 것이 아니라, 가드 조건(guard condition)에 의하여 동일 입력에 대해서도 추가적인 조건 분기가 발생한다. 가드 조건이 $g$ 개의 독립적 조건으로 구성될 때, 각 전이에 대한 분기 수는 최대 $2^g$ 로 증가하며, 실질적인 전이 복잡도는

$|\delta_{\text{effective}}| = k^m \times |\Sigma| \times 2^g$

에 달할 수 있다. 이는 전이의 조건적 분기까지 고려할 경우 복잡도가 이중 지수적(doubly exponential)으로 증가할 수 있음을 시사한다.

4. 긴급 전이에 의한 추가 복잡도

로봇 시스템에서는 비상 정지, 긴급 회피, 통신 단절 대응 등 모든 상태에서 접근 가능해야 하는 긴급 전이(emergency transition)가 존재한다. $n$ 개의 상태에서 $e$ 개의 긴급 행동으로의 전이를 정의할 경우, 긴급 전이의 수는

$|\delta_{\text{emergency}}| = n \times e$

이며, 이는 기존 전이에 추가적으로 부과된다. $n = 1{,}000$ , $e = 3$ (비상 정지, 긴급 복귀, 안전 착륙)인 경우 3,000개의 추가 전이가 필요하고, 이 전이들 각각에 대한 가드 조건과 행동 정의가 수반된다.

5. 전이 복잡도 증가의 실무적 영향

5.1 설계 시간의 비선형적 증가

상태 수가 $n_1$ 에서 $n_2$ 로 증가할 때, 전이 규칙의 설계에 소요되는 시간은 대략 $(n_2/n_1)^2$ 에 비례하여 증가한다. 상태 수가 2배로 증가하면 전이 설계 시간은 약 4배 증가하며, 상태 변수 1개의 추가는 상태 수를 $k$ 배, 전이 설계 시간을 $k^2$ 배 증가시킨다.

5.2 테스트 경로의 폭증

FSM의 완전한 검증을 위해서는 모든 전이 경로(transition path)에 대한 테스트가 필요하다. 순환이 존재하는 FSM에서 유한 길이 $L$ 이하의 테스트 경로 수는 $O(n^L)$ 에 비례하며, 상태 수의 증가는 테스트 커버리지 확보를 기하급수적으로 어렵게 만든다.

5.3 회귀 오류의 위험 증대

전이 규칙 하나를 수정할 때, 해당 수정이 다른 전이 경로에 미치는 간접적 영향을 파악하기 위해서는 수정된 전이를 포함하는 모든 경로를 재검증해야 한다. 상태 수가 증가할수록 간접 영향의 탐지가 어려워지며, 이는 회귀 오류(regression error)의 발생 확률을 높인다.

6. 행동 트리에서의 복잡도 비교

행동 트리(Behavior Tree)에서는 새로운 행동의 추가가 트리에 새로운 노드를 삽입하는 것으로 이루어지며, 삽입된 노드는 부모 노드의 제어 흐름 규칙에 의하여 기존 트리와 상호작용한다. 전이 규칙을 개별적으로 정의할 필요가 없으므로, $n$ 개의 행동 노드를 가진 트리에서 새로운 행동의 추가에 따른 복잡도 증가는 $O(1)$ 또는 $O(\log n)$ 수준에 머무른다. 이는 FSM의 $O(n \cdot |\Sigma|)$ 수준의 추가 비용과 비교하여 근본적으로 우수한 확장성을 제공한다 (Colledanchise & Ögren, 2018).

7. 참고 문헌

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.
Marzinotto, A., Colledanchise, M., Smith, C., & Ögren, P. (2014). “Towards a Unified Behavior Trees Framework for Robot Control.” IEEE International Conference on Robotics and Automation (ICRA), 5420–5427.

v0.1.0