1291.3 상태 폭발 문제의 실제 사례
1. 상태 폭발의 정의와 발생 메커니즘
상태 폭발(state explosion)이란 시스템의 독립적 상태 변수가 증가함에 따라 유한 상태 머신(FSM)의 전체 상태 수가 조합적으로 폭증하는 현상을 지칭한다. m개의 독립 상태 변수가 각각 k_i개의 값을 가질 때, 평탄화(flattened) FSM의 총 상태 수는 \prod_{i=1}^{m} k_i이며, 이에 수반되는 전이 규칙의 수는 상태 수의 제곱에 비례하여 증가한다. 본 절에서는 로봇공학 분야에서 상태 폭발이 실제로 발생하는 대표적 사례를 분석한다.
2. 사례 1: 자율 이동 로봇의 순찰 임무
자율 이동 로봇이 실내 환경에서 순찰 임무를 수행하는 시나리오를 고려한다. 임무 수행 중 로봇이 관리해야 하는 상태 변수는 다음과 같다:
| 상태 변수 | 가능한 값 | 값의 수 |
|---|---|---|
| 임무 단계 | 대기, 순찰, 이상 감지, 보고, 충전 복귀 | 5 |
| 배터리 수준 | 충분, 경고, 위험 | 3 |
| 장애물 감지 | 미감지, 정적 장애물, 동적 장애물 | 3 |
| 통신 상태 | 정상, 불안정, 단절 | 3 |
| 위치 추정 품질 | 양호, 저하, 실패 | 3 |
| 비상 정지 | 비활성, 활성 | 2 |
이 6개 상태 변수의 조합에 의한 전체 상태 수는 5 \times 3 \times 3 \times 3 \times 3 \times 2 = 810이다. 이 810개의 각 상태에 대하여 가능한 입력 이벤트에 따른 전이 규칙을 정의해야 하며, 입력 이벤트가 10종이라고 가정하면 최대 810 \times 10 = 8{,}100개의 전이 규칙이 필요하다.
실제로는 다수의 상태 조합이 물리적으로 불가능하거나 의미가 없으므로 유효한 상태의 수는 이보다 적을 수 있으나, 설계자가 모든 유효 상태와 무효 상태를 분별하여 관리하는 것 자체가 상당한 인지적 부하(cognitive load)를 유발한다.
3. 사례 2: 드론의 자율 비행 임무
무인 항공기(Unmanned Aerial Vehicle, UAV)가 자율 비행 임무를 수행하는 시나리오에서는 3차원 운동 상태, 환경 조건, 페이로드 상태 등 추가적인 상태 차원이 개입한다:
| 상태 변수 | 가능한 값 | 값의 수 |
|---|---|---|
| 비행 단계 | 이륙 전, 이륙, 상승, 순항, 하강, 착륙, 비상 착륙 | 7 |
| GPS 상태 | 정상(RTK Fix), 불안정(Float), 실패 | 3 |
| 풍속 조건 | 정상, 강풍 경고, 비행 불가 | 3 |
| 배터리 수준 | 정상, 경고, 비상 | 3 |
| 모터 상태 | 전체 정상, 부분 이상, 다중 실패 | 3 |
| 통신 링크 | 정상, 지연, 단절 | 3 |
| 지오펜스 상태 | 내부, 경계, 침범 | 3 |
| 페이로드 상태 | 장착, 투하 완료, 이상 | 3 |
이 8개 변수의 곱공간은 7 \times 3^7 = 7 \times 2{,}187 = 15{,}309개의 상태를 생성한다. 각 상태에 대한 전이 규칙과 행동 정의를 개별적으로 관리하는 것은 사실상 불가능하며, 이는 대규모 FSM 설계의 비실용성을 단적으로 보여준다.
4. 사례 3: 매니퓰레이터의 물체 조작 임무
산업용 매니퓰레이터가 물체를 파지(grasp)하고 원하는 위치에 배치(place)하는 pick-and-place 임무에서는 다음과 같은 상태 변수가 관련된다:
| 상태 변수 | 가능한 값 | 값의 수 |
|---|---|---|
| 임무 단계 | 대기, 접근, 파지, 이송, 배치, 복귀 | 6 |
| 그리퍼 상태 | 개방, 폐쇄, 파지 확인, 오류 | 4 |
| 물체 인식 | 감지, 미감지, 불확실 | 3 |
| 충돌 감지 | 정상, 경고, 충돌 | 3 |
| 관절 상태 | 정상, 과부하, 위치 오차 초과 | 3 |
| 힘/토크 한계 | 정상 범위, 경고 범위, 초과 | 3 |
이 조합의 총 상태 수는 6 \times 4 \times 3 \times 3 \times 3 \times 3 = 1{,}944이다. 특히 매니퓰레이션 작업에서는 각 상태에서의 행동이 물리적 안전에 직결되므로, 모든 전이에 대한 안전 검증이 필수적이며, 이는 상태 폭발 시 검증 비용의 기하급수적 증가로 이어진다.
5. 사례 4: 다중 로봇 협업 시스템
N대의 로봇이 협업하여 임무를 수행하는 다중 로봇 시스템(Multi-Robot System, MRS)에서는 상태 폭발이 더욱 심각하게 발현된다. 각 로봇이 s개의 상태를 가지며 로봇 간의 조정(coordination) 상태가 c개의 값을 가질 경우, 시스템 전체의 상태 수는
|Q_{\text{system}}| = s^N \cdot c^{\binom{N}{2}}
에 비례한다. 3대의 로봇이 각각 10개의 상태를 가지고, 로봇 쌍별 조정 상태가 3개의 값(독립, 협업, 충돌 회피)을 가질 경우, 10^3 \times 3^3 = 27{,}000개의 상태가 발생한다. 로봇의 수가 5대로 증가하면 10^5 \times 3^{10} = 5{,}904{,}900{,}000개 이상의 상태가 생성되며, 이는 FSM 기반 접근이 다중 로봇 시스템에서 근본적으로 비확장적(non-scalable)임을 명시한다.
6. 상태 폭발이 초래하는 실무적 문제
상태 폭발은 다음과 같은 실무적 문제를 연쇄적으로 유발한다:
- 설계 비용의 폭증: 전체 상태와 전이를 정의하는 초기 설계 비용이 상태 수에 비례하여 증가한다.
- 검증의 비실용성: 모든 상태 전이 경로에 대한 테스트 커버리지 확보가 불가능해지며, 미검증 경로에서의 예기치 않은 행동이 발생할 위험이 증대한다.
- 유지보수의 비경제성: 하나의 상태 변수를 추가하는 것만으로도 상태 수가 상수 배만큼 증가하며, 모든 기존 전이와의 상호작용을 재검토해야 한다.
- 가독성의 상실: 상태 전이 다이어그램은 상태 수가 20–30개를 초과하면 시각적으로 해독 불가능한 수준의 복잡도에 도달한다 (Colledanchise & Ögren, 2018).
7. 참고 문헌
- 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.
- 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