396.48 상태 머신과 행동 트리의 비교 분석
1. 비교 분석의 필요성
유한 상태 머신(Finite State Machine, FSM)과 행동 트리(Behavior Tree, BT)는 자율 로봇 시스템에서 임무 제어를 위해 가장 널리 사용되는 두 가지 형식 체계이다. 두 접근법은 각기 다른 설계 철학에 기반하며, 시스템의 복잡도, 모듈성, 반응성, 유지보수성 등에서 상이한 특성을 나타낸다. 본 절에서는 FSM과 BT를 다양한 평가 기준에 따라 체계적으로 비교하여, 임무 관리 시스템 설계 시 적절한 선택을 위한 이론적 근거를 제공한다.
2. 구조적 비교
2.1 유한 상태 머신의 형식적 정의
유한 상태 머신 \mathcal{M}은 5-튜플(5-tuple)로 정의된다:
\mathcal{M} = (Q, \Sigma, \delta, q_0, F)
여기서 Q는 유한 상태 집합, \Sigma는 입력 알파벳(이벤트 집합), \delta: Q \times \Sigma \rightarrow Q는 전이 함수, q_0 \in Q는 초기 상태, F \subseteq Q는 수용 상태 집합이다. FSM에서 시스템의 행동은 현재 상태와 입력 이벤트에 의해 결정되며, 전이 규칙에 따라 상태가 변경된다.
2.2 행동 트리의 형식적 정의
행동 트리 T는 방향 비순환 그래프(Directed Acyclic Graph)의 특수한 형태인 루트 트리(rooted tree)로 정의된다:
T = (V, E, r, \tau)
여기서 V는 노드 집합, E \subseteq V \times V는 간선 집합, r \in V는 루트 노드, \tau: V \rightarrow \{\text{Sequence}, \text{Fallback}, \text{Parallel}, \text{Decorator}, \text{Action}, \text{Condition}\}는 노드 유형 함수이다. BT에서 실행 흐름은 루트에서 시작하여 트리 구조를 따라 하향 전파되며, 각 노드는 \{\texttt{SUCCESS}, \texttt{FAILURE}, \texttt{RUNNING}\} 중 하나의 상태를 반환한다.
2.3 구조적 차이의 핵심
| 비교 항목 | 유한 상태 머신 (FSM) | 행동 트리 (BT) |
|---|---|---|
| 기본 구조 | 그래프(상태와 전이) | 트리(노드와 간선) |
| 제어 흐름 | 이벤트 기반 전이 | 틱(tick) 기반 순회 |
| 실행 단위 | 상태(State) | 리프 노드(Leaf Node) |
| 흐름 결정 요소 | 현재 상태 + 이벤트 | 트리 구조 + 노드 반환값 |
| 전역 상태 | 현재 활성 상태 1개 | 틱이 순회하는 경로 |
FSM은 본질적으로 그래프(graph) 구조이며, 임의의 상태에서 임의의 상태로 전이할 수 있다. 반면, BT는 트리(tree) 구조로서 실행 흐름이 루트에서 리프로 향하는 단방향 구조를 따른다. 이러한 구조적 차이가 두 체계의 모든 특성 차이의 근본적 원인이 된다.
3. 모듈성(Modularity) 비교
3.1 FSM에서의 모듈성 한계
FSM에서 새로운 상태 q_{\text{new}}를 추가할 때, 기존 상태들과의 전이 관계를 모두 명시해야 한다:
\delta' = \delta \cup \{(q_i, \sigma_j) \rightarrow q_{\text{new}} \mid \text{relevant pairs}\} \cup \{(q_{\text{new}}, \sigma_k) \rightarrow q_l \mid \text{relevant pairs}\}
n개의 상태를 갖는 FSM에 하나의 상태를 추가하면, 최악의 경우 O(n \cdot |\Sigma|)개의 새로운 전이 규칙을 정의해야 한다. 이는 FSM의 모듈성을 심각하게 저해하는 요인이다.
3.2 BT에서의 모듈적 확장
BT에서 새로운 행동을 추가하는 것은 기존 트리에 서브트리를 삽입하는 연산으로 귀결된다:
T' = \text{Insert}(T, n_p, T_{\text{new}})
이 연산은 삽입 지점 n_p의 자식 목록에 T_{\text{new}}의 루트를 추가하는 것으로 완료되며, 기존 트리의 다른 부분에 영향을 미치지 않는다. 따라서 BT의 모듈적 확장 비용은 O(1)이다. Colledanchise and Ögren (2017)은 이 속성을 **구성성(compositionality)**이라 명명하고, BT의 핵심적 이론적 강점으로 제시하였다.
4. 반응성(Reactivity) 비교
4.1 FSM의 반응성 메커니즘
FSM에서 반응성은 **전이 규칙(transition rule)**의 명시적 정의에 의존한다. 특정 이벤트에 대한 반응은 해당 이벤트를 처리하는 전이가 현재 상태에서 정의되어 있을 때만 가능하다:
\text{React}(q, \sigma) = \begin{cases} \delta(q, \sigma) & \text{if } (q, \sigma) \in \text{dom}(\delta) \\ \text{undefined} & \text{otherwise} \end{cases}
따라서 모든 상태에서 특정 이벤트(예: 비상 정지)에 반응하려면, 모든 상태에 해당 전이를 명시적으로 추가해야 한다. n개 상태에 대해 전역적 비상 전이를 정의하면 n개의 전이 규칙이 필요하다.
4.2 BT의 구조적 반응성
BT에서 반응성은 트리 구조 자체에 내재화된다. 루트에 가까운 위치에 배치된 반응적 폴백(Reactive Fallback) 노드는 매 틱마다 재평가되므로, 전역적 반응 행동을 단 하나의 서브트리 삽입으로 구현할 수 있다:
Root [ReactiveFallback]
├── [ReactiveSequence] 비상 대응
│ ├── [Condition] 비상 조건 감지
│ └── [Action] 비상 행동
└── [기존 임무 서브트리]
이 구조에서 비상 조건은 임무 서브트리의 복잡도와 무관하게 매 틱마다 검사되며, 조건 충족 시 즉시 비상 행동이 실행된다. 추가적인 전이 규칙 없이 트리 구조의 위치적 배치만으로 우선순위 기반 반응이 보장된다.
5. 상태 폭발(State Explosion) 문제
5.1 FSM의 상태 폭발
FSM에서 다수의 독립적 속성(attribute)을 동시에 관리해야 할 경우, 상태 수가 지수적으로 증가하는 상태 폭발(state explosion) 문제가 발생한다. k개의 이진 속성을 갖는 시스템에서 FSM의 상태 수는 다음과 같다:
|Q| = 2^k
예를 들어, 배터리 상태(정상/부족), 장애물 존재 여부, 통신 상태(연결/두절), 목표 도달 여부 등 4개의 이진 속성을 관리하면 2^4 = 16개의 상태가 필요하며, 각 상태 간 전이 규칙까지 고려하면 시스템의 복잡도가 급격히 증가한다.
5.2 BT의 선형적 확장
BT에서 동일한 속성을 관리하는 경우, 각 속성은 독립적인 조건-행동 쌍으로 표현되며, 이들은 폴백 또는 병렬 노드의 자식으로 구성된다. k개의 속성을 관리하기 위한 BT의 노드 수는 다음과 같다:
|V| = O(k)
이는 FSM의 지수적 증가와 대비되는 **선형적 확장(linear scaling)**을 나타내며, BT가 복잡한 다속성 임무 관리에서 구조적으로 우월함을 보여준다.
6. 가독성과 유지보수성
6.1 FSM의 가독성
소규모 시스템에서 FSM의 상태 전이 다이어그램은 직관적이고 이해하기 용이하다. 그러나 상태 수가 증가할수록 전이 규칙 간의 교차가 복잡해져 시각적 가독성이 급격히 저하된다. 상태 수 n에 대한 가독성 저하를 나타내는 인지 복잡도(cognitive complexity) 지표 C는 다음과 같이 추정된다:
C_{\text{FSM}} = O(n \cdot |\Sigma|)
이는 상태 수와 이벤트 수의 곱에 비례하며, 대규모 시스템에서 FSM의 유지보수를 어렵게 만드는 주요 요인이다.
6.2 BT의 가독성
BT는 트리 구조의 계층적 특성으로 인해, 대규모 시스템에서도 서브트리 단위의 국소적(local) 이해가 가능하다. 트리의 깊이 d와 최대 분기 계수(branching factor) b에 대한 인지 복잡도는 다음과 같다:
C_{\text{BT}} = O(d \cdot b)
서브트리의 독립성 덕분에, 개발자는 전체 트리를 이해하지 않고도 특정 서브트리만을 분석하여 수정할 수 있다. 이는 대규모 프로젝트에서의 협업 개발과 유지보수를 용이하게 한다.
7. 표현력(Expressiveness) 비교
7.1 형식적 표현력의 동치성
Colledanchise and Ögren (2017)은 BT가 FSM과 동일한 형식적 표현력을 가짐을 증명하였다. 즉, 임의의 FSM을 등가의 BT로 변환하고, 그 역변환도 가능하다:
\forall \mathcal{M} \in \text{FSM}, \; \exists T \in \text{BT} : \text{Behavior}(\mathcal{M}) = \text{Behavior}(T)
\forall T \in \text{BT}, \; \exists \mathcal{M} \in \text{FSM} : \text{Behavior}(T) = \text{Behavior}(\mathcal{M})
따라서 두 체계는 표현할 수 있는 행동의 범위에서 이론적으로 동등하다. 차이는 표현의 효율성과 구조적 특성에서 발생한다.
7.2 FSM에서 BT로의 변환
FSM의 각 상태 q_i와 전이 규칙을 BT로 변환하는 체계적 방법이 존재한다. 상태 q_i에서의 행동 a_i와 해당 상태로의 전이 조건 \phi_i를 이용하면:
T_{\text{equiv}} = \text{Fallback}\bigl(\text{Seq}(\phi_1, a_1), \; \text{Seq}(\phi_2, a_2), \; \ldots, \; \text{Seq}(\phi_n, a_n)\bigr)
이 변환에서 FSM의 내부 상태 변수를 BT의 블랙보드(Blackboard)에 저장함으로써 상태 의존적 행동을 구현할 수 있다.
8. 실행 의미론(Execution Semantics) 비교
8.1 이벤트 기반 대 틱 기반
FSM과 BT의 실행 의미론에서 근본적 차이는 이벤트 기반(event-driven) 대 틱 기반(tick-driven) 실행 모델에 있다:
| 특성 | FSM (이벤트 기반) | BT (틱 기반) |
|---|---|---|
| 실행 트리거 | 외부 이벤트 발생 | 주기적 틱 신호 |
| 상태 재평가 | 이벤트 수신 시에만 | 매 틱마다 전체 재평가 |
| 계산 비용 | 이벤트 발생 시에만 비용 | 매 틱마다 일정 비용 |
| 반응 지연 | 이벤트 큐 의존적 | 틱 주기에 의해 상한 보장 |
| 누락된 이벤트 | 복구 불가 | 다음 틱에서 재평가 |
BT의 틱 기반 모델은 이벤트 누락 문제로부터 자유롭지만, 모든 틱에서 트리를 순회해야 하므로 일정한 계산 비용이 발생한다. 반면 FSM은 이벤트가 없으면 계산 비용이 발생하지 않지만, 이벤트 큐의 관리와 이벤트 누락에 대한 별도의 처리가 필요하다.
8.2 중단(Preemption) 메커니즘
FSM에서 현재 실행 중인 행동을 중단하려면 별도의 중단 이벤트와 전이 규칙을 정의해야 한다:
\delta(q_{\text{running}}, \sigma_{\text{preempt}}) = q_{\text{interrupt}}
BT에서는 반응적 노드의 구조적 특성에 의해, 상위 우선순위 조건이 충족되면 현재 실행 중인 RUNNING 노드가 자동으로 중단(halt)된다. 이 중단 메커니즘은 트리 구조에 내재되어 있으므로 별도의 설계가 불필요하다.
9. 종합 비교 평가
다음은 주요 평가 기준에 따른 FSM과 BT의 종합 비교 결과이다:
| 평가 기준 | FSM | BT |
|---|---|---|
| 소규모 시스템 가독성 | 우수 | 양호 |
| 대규모 시스템 가독성 | 열악 | 우수 |
| 모듈성 | 낮음 | 높음 |
| 반응성 | 명시적 설계 필요 | 구조적 보장 |
| 확장성 | O(2^k) 상태 폭발 | O(k) 선형 확장 |
| 중단 메커니즘 | 명시적 설계 필요 | 구조적 내재 |
| 형식적 표현력 | 동등 | 동등 |
| 형식 검증 용이성 | 모델 체킹 성숙 | 구성적 검증 가능 |
| 구현 생태계 | 광범위한 도구 지원 | BehaviorTree.CPP 등 |
| 학습 곡선 | 낮음 | 중간 |
10. 적용 기준과 선택 지침
FSM은 상태 수가 적고 전이 규칙이 명확한 소규모 임무에서 여전히 효율적인 선택이다. 그러나 다음과 같은 조건에서는 BT의 채택이 권장된다:
- 임무의 복잡도: 다수의 독립적 조건과 행동이 동시에 관리되는 복합 임무
- 동적 환경: 실시간 환경 변화에 대한 지속적 반응이 요구되는 경우
- 점진적 개발: 시스템이 반복적으로 확장되며, 기존 행동에 대한 영향을 최소화해야 하는 경우
- 안전성 요구: 우선순위 기반 비상 대응이 구조적으로 보장되어야 하는 임무
- 팀 개발: 다수의 개발자가 독립적으로 서브 행동을 개발하고 통합하는 프로젝트
한편, 두 체계를 **하이브리드(hybrid)**로 결합하는 접근도 활발히 연구되고 있다. BT의 리프 노드에서 국소적 FSM을 실행하거나, FSM의 각 상태에서 BT 서브트리를 호출하는 방식은 양 체계의 장점을 결합하여 유연하면서도 직관적인 임무 제어를 가능하게 한다.
11. 참고 문헌
- Colledanchise, M. and Ögren, P. (2017). “How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees.” IEEE Transactions on Robotics, 33(2), 372–389.
- Colledanchise, M. and Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
- Iovino, M., Scukins, E., Styrud, J., Ögren, P., and Smith, C. (2022). “A Survey of Behavior Trees in Robotics and AI.” Robotics and Autonomous Systems, 154, 104096.
- Harel, D. (1987). “Statecharts: A Visual Formalism for Complex Systems.” Science of Computer Programming, 8(3), 231–274.
- Biggar, O., Zamani, M., and Shames, I. (2021). “A Framework for Formal Verification of Behavior Trees with Linear Temporal Logic.” IEEE Robotics and Automation Letters, 6(3), 4620–4627.
본 절은 로봇공학 서적 Volume 9, Part 53, Chapter 396의 일부로 작성되었다. v1.0