1291.68 상태 머신과 행동 트리의 형식적 관계

행동 트리(Behavior Tree, BT)와 유한 상태 머신(Finite State Machine, FSM)은 모두 반응형 시스템(Reactive System)의 행동을 기술하는 형식 체계이다. 두 체계 간의 형식적 관계를 명확히 규명하는 것은 이론적 이해의 심화뿐 아니라, 상호 변환 가능성 평가와 하이브리드 아키텍처 설계의 이론적 기반을 제공하는 데 핵심적 의의를 지닌다.

1. 유한 상태 머신의 형식적 정의

유한 상태 머신은 5-튜플 $M = (S, \Sigma, \delta, s_0, F)$ 로 정의된다. 여기서 $S$ 는 유한 상태 집합, $\Sigma$ 는 입력 알파벳(사건 집합), $\delta: S \times \Sigma \rightarrow S$ 는 상태 전이 함수, $s_0 \in S$ 는 초기 상태, $F \subseteq S$ 는 수용 상태(또는 최종 상태) 집합이다. 로봇 행동 제어에서는 출력이 포함된 미얼리 머신(Mealy Machine) $M = (S, \Sigma, \Lambda, \delta, \omega, s_0)$ 이 주로 사용되며, $\Lambda$ 는 출력 알파벳, $\omega: S \times \Sigma \rightarrow \Lambda$ 는 출력 함수이다.

유한 상태 머신의 핵심적 특성은 상태 메모리(State Memory)의 보유이다. 매 시간 단계에서 시스템은 정확히 하나의 상태에 존재하며, 이 상태는 시스템의 과거 이력을 유한한 정보로 압축하여 보존한다.

2. 행동 트리의 형식적 정의

Colledanchise와 Ögren(2018)에 의한 행동 트리의 형식적 정의에서, 행동 트리는 유향 비순환 그래프(Directed Acyclic Graph, DAG)의 특수한 형태인 루트 트리(Rooted Tree) $\mathcal{T} = (V, E, r)$ 로 정의된다. 여기서 $V$ 는 노드 집합, $E \subseteq V \times V$ 는 간선 집합, $r \in V$ 는 루트 노드이다.

각 노드 $v \in V$ 는 틱 신호를 수신하면 함수 $f_v: \mathcal{X} \rightarrow \{$ Success, Failure, Running $\}$ 을 실행하며, 여기서 $\mathcal{X}$ 는 환경 상태 공간(블랙보드 포함)이다. 제어 흐름 노드(시퀀스, 폴백, 병렬)는 자식 노드의 반환 상태를 조합하여 자신의 반환 상태를 결정하는 합성 함수를 정의한다.

3. 표현력의 형식적 동치성

Colledanchise와 Ögren(2018)은 행동 트리와 유한 상태 머신의 형식적 표현력이 동등함을 증명하였다. 구체적으로, 다음의 두 가지 명제가 성립한다.

명제 1 (FSM에서 BT로의 변환): 임의의 유한 상태 머신 $M = (S, \Sigma, \delta, s_0)$ 에 대하여, $M$ 과 동일한 입출력 관계를 실현하는 행동 트리 $\mathcal{T}_M$ 이 존재한다.

명제 2 (BT에서 FSM으로의 변환): 유한한 환경 상태 공간 위에서 정의된 임의의 행동 트리 $\mathcal{T}$ 에 대하여, $\mathcal{T}$ 와 동일한 입출력 관계를 실현하는 유한 상태 머신 $M_\mathcal{T}$ 가 존재한다.

이 동치성은 두 체계가 동일한 클래스의 반응형 시스템을 기술할 수 있음을 의미한다. 그러나 변환 과정에서의 구조적 복잡도 변화는 양 체계의 실용적 상이점을 반영한다.

4. 구조적 복잡도 변화

FSM에서 BT로의 변환에서, $n$ 개의 상태와 $m$ 개의 전이를 갖는 유한 상태 머신을 행동 트리로 변환할 경우, 블랙보드에 현재 상태를 나타내는 변수를 도입하고 각 상태에 대한 조건 분기와 전이 조건에 대한 검사를 트리 구조로 전개해야 한다. 이 과정에서 생성되는 행동 트리의 노드 수는 원래의 상태 수와 전이 수에 비례하여 증가한다.

역방향 변환인 BT에서 FSM으로의 변환에서는 보다 현저한 구조적 팽창이 발생할 수 있다. 행동 트리의 리액티브 노드와 병렬 노드의 동작을 유한 상태 머신으로 기술하려면, 트리의 각 노드의 실행 상태 조합을 상태로 정의해야 하므로, 상태 수가 노드 수에 대해 지수적으로 증가할 수 있다. 특히 병렬 노드의 $k$ 개 자식이 각각 3가지 반환 상태(Success, Failure, Running)를 가질 때, 이론적으로 $3^k$ 개의 조합 상태가 생성될 수 있다.

5. 의미론적 차이

형식적 표현력의 동치성에도 불구하고, 두 체계의 실행 의미론(Operational Semantics)에는 근본적인 차이가 존재한다.

첫째, 상태 유지 방식이 상이하다. 유한 상태 머신은 내부 상태 변수에 의해 시스템의 상태를 명시적으로 유지한다. 행동 트리는 기본적으로 무상태(Stateless) 실행 모델을 따르며, 상태 정보는 블랙보드라는 외부 메모리 구조에 위임된다.

둘째, 제어 흐름 구성 방식이 상이하다. 유한 상태 머신에서는 상태 전이 규칙이 제어 흐름을 결정하며, 전이는 현재 상태와 입력 사건의 함수이다. 행동 트리에서는 트리의 구조 자체가 제어 흐름을 정의하며, 매 틱마다 루트로부터의 하향 순회에 의해 실행 경로가 결정된다.

셋째, 모듈성의 수준이 상이하다. 행동 트리에서 서브트리는 인터페이스(포트)만 일치하면 독립적으로 교체 가능한 모듈로 작용한다. 유한 상태 머신에서는 상태와 전이의 긴밀한 결합으로 인해 부분 구조의 독립적 교체가 전체 전이 관계에 파급 효과를 미칠 수 있다.

6. 범주론적 관점

Biggar, Zamani, Shames(2021)는 행동 트리를 범주론(Category Theory)의 관점에서 분석하여, 행동 트리의 합성 연산(시퀀스, 폴백, 병렬)이 특정 대수적 구조를 형성함을 보였다. 이 관점에서 유한 상태 머신과 행동 트리의 관계는 서로 다른 대수적 구조 간의 함자(Functor) 관계로 해석될 수 있으며, 이는 두 체계 간의 변환이 구조를 보존하는 사상(Morphism)으로 형식화될 수 있음을 시사한다.

참고 문헌

Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
Biggar, O., Zamani, M., & Shames, I. (2021). “An Algebraic Theory of Behavior Trees.” arXiv preprint arXiv:2109.10803.
Biggar, O., Zamani, M., & Shames, I. (2020). “A Framework for Formal Verification of Behavior Trees with Linear Temporal Logic.” IEEE Robotics and Automation Letters, 5(2), 2435–2442.
Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation. 3rd Edition, Pearson.