1291.1 상태 머신 기반 행동 제어의 성과와 한계 개요

1291.1 상태 머신 기반 행동 제어의 성과와 한계 개요

1. 서론

유한 상태 머신(Finite State Machine, FSM)은 자율 에이전트의 행동 제어 분야에서 가장 오랜 역사를 가진 형식적 모델 중 하나이다. FSM은 시스템의 동적 행동을 유한 개의 이산적 상태(discrete state)와 상태 간 전이(transition)의 쌍으로 명확하게 정의하며, 이를 통하여 로봇의 행동 전환 로직을 결정론적(deterministic)으로 기술할 수 있다. 로봇공학, 산업 자동화, 게임 인공지능 등 다수의 공학 분야에서 FSM은 행동 제어의 근간 아키텍처로 광범위하게 채택되어 왔다 (Wagner et al., 2006).

그러나 현대 로봇 시스템이 수행해야 하는 임무의 복잡도가 급격히 증가함에 따라, FSM 기반 행동 제어는 다수의 구조적 한계를 노출하게 되었다. 본 절에서는 FSM이 로봇 행동 제어에 기여한 성과를 체계적으로 정리하고, 동시에 대규모 자율 시스템에서 드러나는 근본적 한계를 개관한다.

2. 유한 상태 머신의 성과

2.1 명시적 행동 정의와 직관적 설계

FSM은 시스템의 모든 가능한 행동 상태와 전이 조건을 명시적으로 정의한다. 이러한 명시성은 설계자가 시스템의 행동 로직을 완전하게 파악할 수 있게 하며, 상태 전이 다이어그램(state transition diagram)을 통한 시각적 표현이 가능하여 설계의 직관성이 높다. 소규모 상태 공간을 가진 시스템에서는 FSM의 설계, 구현, 검증이 비교적 단순하며, 이는 초기 프로토타이핑 단계에서 특히 유용하다.

2.2 결정론적 검증 가능성

FSM의 상태 공간이 유한하고 모든 전이가 명시적으로 정의되어 있으므로, 모델 검사(model checking) 기법을 활용한 형식적 검증(formal verification)이 가능하다. Promela/SPIN (Holzmann, 2004)이나 NuSMV와 같은 도구를 사용하여 안전성(safety) 속성과 활동성(liveness) 속성을 검증할 수 있으며, 이는 안전 임계 시스템(safety-critical system)에서 중요한 장점이다.

2.3 구현 용이성

FSM은 switch-case 구문, 상태 테이블(state table), 또는 상태 패턴(State Pattern) 등 다양한 방식으로 구현될 수 있으며, 대부분의 프로그래밍 언어와 플랫폼에서 직접적인 구현이 가능하다. SMACH(Bohren & Cousins, 2010)와 같은 ROS 기반 상태 머신 라이브러리는 로봇공학 분야에서 FSM의 실용적 적용을 촉진하였다.

2.4 반복적 패턴의 효율적 처리

순차적 단계(sequential phase)로 구성된 임무에서 FSM은 각 단계를 상태로, 단계 간 전환 조건을 전이로 대응시킴으로써, 임무 흐름을 명확하게 표현한다. “초기화 → 탐색 → 접근 → 작업 수행 → 복귀“와 같은 선형 임무 구조에서 FSM은 높은 표현 효율성을 보인다.

3. 유한 상태 머신의 근본적 한계

3.1 상태 폭발 문제

FSM의 가장 심각한 한계는 상태 폭발(state explosion) 문제이다. m개의 독립적 상태 변수가 각각 k_i개의 가능한 값을 가질 경우, 전체 상태 공간의 크기는 곱공간(product space)의 크기인 \prod_{i=1}^{m} k_i이 된다. 예를 들어, 4개의 이진 상태 변수(배터리 상태, 센서 정상 여부, 통신 연결 여부, 비상 정지 여부)만으로도 2^4 = 16개의 상태가 필요하며, 각 상태에서의 전이 규칙이 개별적으로 정의되어야 한다. 실제 로봇 시스템에서는 수십 개의 상태 변수가 동시에 존재하므로, 상태 공간은 관리 불가능한 수준으로 폭증한다 (Colledanchise & Ögren, 2018).

3.2 모듈성과 재사용성의 부재

FSM에서 특정 상태는 해당 상태로 진입하는 전이와 해당 상태에서 발생하는 전이에 의하여 전체 시스템과 밀접하게 결합(tightly coupled)되어 있다. 따라서 하나의 FSM에서 동작하는 행동 모듈을 다른 FSM으로 이식하려면, 해당 모듈과 연결된 모든 전이 규칙을 새로운 맥락에 맞추어 전면적으로 재정의해야 한다. 이는 소프트웨어 공학에서 추구하는 모듈화(modularization)와 코드 재사용(code reuse)의 원칙에 배치된다.

3.3 반응성의 구조적 제약

FSM에서 행동 전환은 현재 상태에서 정의된 전이 규칙에 의해서만 발생한다. 환경의 급격한 변화에 대응하여 임의의 상태에서 특정 행동(예: 긴급 회피, 비상 착륙)으로 즉시 전환하려면, 모든 상태로부터 해당 행동으로의 전이를 명시적으로 정의해야 한다. n개의 상태에서 하나의 긴급 행동으로의 전이를 추가하는 것만으로도 n개의 새로운 전이 규칙이 필요하며, 이는 설계의 복잡도를 가중시킨다.

3.4 확장성의 한계

기존 FSM에 새로운 행동을 추가하거나 기존 행동을 수정할 때, 추가된 상태와 기존 상태 간의 전이 규칙을 전면적으로 재검토해야 한다. 이러한 수정의 파급 효과(ripple effect)는 FSM의 규모가 커질수록 비례적으로 증가하며, 회귀 오류(regression error)의 발생 위험을 높인다.

3.5 선언적 표현의 부족

FSM은 본질적으로 절차적(procedural) 모델이며, “무엇(what)을 수행할 것인가“보다 “어떻게(how) 전환할 것인가“에 초점을 맞춘다. 이로 인하여 비프로그래머(도메인 전문가, 임무 설계자 등)가 행동 로직을 직접 정의하거나 수정하기 어려우며, XML이나 스크립트 기반의 선언적 표현과의 통합이 자연스럽지 않다.

4. 한계의 종합적 평가

FSM은 소규모, 단일 임무, 결정론적 환경에서는 여전히 효과적이고 검증 가능한 행동 제어 도구이다. 그러나 현대 로봇 시스템이 요구하는 대규모 상태 공간, 다중 병행 행동, 동적 환경 적응, 모듈적 임무 구성 등의 요구사항에 대하여 FSM은 구조적으로 부적합하다. Statecharts(Harel, 1987)와 같은 확장 모델이 일부 한계를 완화하였으나, 근본적인 상태-전이 패러다임의 제약을 완전히 해소하지는 못하였다.

이러한 FSM의 구조적 한계가 행동 트리(Behavior Tree)라는 새로운 제어 아키텍처의 등장을 촉진한 핵심적 기술적 동기이며, 행동 트리는 FSM의 주요 한계인 상태 폭발, 모듈성 부재, 반응성 제약을 트리 구조의 계층적 분해와 조합 기반 제어 흐름을 통하여 체계적으로 극복하고자 한다.

5. 참고 문헌

  • Bohren, J., & Cousins, S. (2010). “The SMACH High-Level Executive.” IEEE Robotics & Automation Magazine, 17(4), 18–20.
  • 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.
  • Holzmann, G. J. (2004). The SPIN Model Checker: Primer and Reference Manual. Addison-Wesley.
  • Wagner, T., Ghallab, M., & Maler, O. (2006). “On the Role of State Machines in Autonomous Agent Control.” Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).

v0.1.0