Chapter 1291. 상태 머신의 한계와 행동 트리의 등장 (Limitations of State Machines and Emergence of Behavior Trees)

1. 개요

로봇 시스템의 자율적 행동 제어에서 유한 상태 머신(Finite State Machine, FSM)은 오랜 기간 지배적인 설계 패러다임으로 활용되어 왔다. FSM은 시스템의 행동을 이산적 상태(discrete state)와 상태 간 전이(transition)의 쌍으로 명시적으로 정의하며, 소규모 시스템에서는 직관적이고 검증 가능한 행동 모델을 제공한다. 그러나 로봇 임무의 복잡도가 증가함에 따라 FSM 기반 설계는 상태 폭발(state explosion), 모듈성 부족, 재사용성 저하, 반응성 한계 등 다수의 구조적 문제를 노출하게 되었다.

행동 트리(Behavior Tree, BT)는 이러한 FSM의 구조적 제약을 극복하기 위하여 등장한 계층적 행동 제어 아키텍처이다. 행동 트리는 1990년대 후반에서 2000년대 초반에 걸쳐 컴퓨터 게임 산업에서 비플레이어 캐릭터(NPC)의 인공지능 행동 모델링을 목적으로 개발되었으며, 이후 그 구조적 장점이 학술적으로 체계화되면서 로봇공학, 자율 주행, 자율 비행, 제조 자동화 등 다양한 자율 시스템 분야로 확산되었다 (Colledanchise & Ögren, 2018).

본 장에서는 FSM 기반 행동 제어의 성과와 근본적 한계를 분석하고, 이를 극복하기 위한 대안으로서 행동 트리가 등장하게 된 역사적 배경과 기술적 동기를 고찰한다. 나아가 행동 트리의 개념적·수학적 정의, 기본 구조, 설계 철학, 그리고 FSM 대비 구조적 장점과 잔존하는 한계를 체계적으로 서술한다.

2. 유한 상태 머신의 구조적 성과와 한계

2.1 상태 머신 기반 행동 제어의 역할

유한 상태 머신은 시스템을 유한 개의 상태 Q = \{q_1, q_2, \ldots, q_n\}, 입력 알파벳 \Sigma, 전이 함수 \delta: Q \times \Sigma \rightarrow Q, 초기 상태 q_0, 수락 상태 집합 F \subseteq Q의 5-튜플 (Q, \Sigma, \delta, q_0, F)로 형식화한다. 로봇공학에서 FSM은 각 상태를 특정 행동(예: 대기, 이동, 회피, 복귀)에 대응시키고, 센서 입력이나 내부 조건에 따른 전이 규칙을 정의하여 로봇의 행동 전환을 명시적으로 제어한다.

이러한 명시적 상태 정의와 전이 규칙은 소수의 상태를 가진 단순한 임무에서는 설계의 직관성, 결정론적 검증 가능성, 구현의 용이성이라는 명확한 장점을 제공한다. 초기 로봇 시스템에서 FSM은 순찰, 장애물 회피, 목표 지점 도달 등 단일 임무의 행동 제어에 효과적으로 적용되었다.

2.2 상태 폭발 문제

FSM의 가장 근본적인 한계는 상태 폭발(state explosion) 문제이다. n개의 독립적 상태 변수가 각각 k개의 값을 가질 경우, 전체 상태 공간의 크기는 k^n으로 조합적으로 폭증한다. 실제 로봇 임무에서 배터리 상태, 센서 이상 여부, 통신 상태, 임무 진행 단계, 장애물 존재 여부 등 다수의 상태 변수가 동시에 존재하며, 이들의 조합은 관리 불가능한 수준의 상태 공간을 생성한다.

상태 수 n에 대하여 모든 상태 쌍 간의 전이 가능성을 고려하면, 전이의 최대 수는 O(n^2 \cdot |\Sigma|)에 달한다. 상태 수가 증가함에 따라 전이 규칙의 정의, 검증, 유지보수에 소요되는 비용이 급격히 증가하며, 이는 사실상 대규모 FSM의 실용적 운용을 불가능하게 만든다 (Marzinotto et al., 2014).

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

FSM에서 각 상태와 전이는 전체 시스템의 맥락에 강하게 결합(tightly coupled)되어 있다. 특정 행동을 수행하는 상태를 다른 FSM으로 이식하려면, 해당 상태와 연결된 모든 전이 규칙을 새로운 맥락에 맞추어 재정의해야 한다. 이러한 구조적 결합은 행동 모듈의 독립적 설계와 재사용을 근본적으로 방해한다.

계층적 상태 머신(Hierarchical State Machine, HSM)과 Statecharts(Harel, 1987)는 복합 상태(composite state)와 직교 영역(orthogonal region)을 도입하여 FSM의 확장성을 개선하였으나, 계층 간 전이의 정의, 직교 영역 간의 동기화, 진입/퇴출 행동의 관리 등에서 추가적인 복잡도가 발생하며, 근본적인 모듈성 문제는 해소되지 않는다.

2.4 반응성과 동적 재구성의 한계

FSM에서 행동 전환은 반드시 사전에 정의된 전이 규칙에 의해서만 발생한다. 예상하지 못한 환경 변화나 새로운 임무 요구사항에 대응하려면 기존 전이 규칙을 수정하거나 새로운 전이를 추가해야 하며, 이는 기존 행동 로직에 파급 효과(ripple effect)를 미친다. 런타임에 상태와 전이를 동적으로 재구성하는 것은 FSM의 결정론적 특성과 상충하며, 구현 및 검증의 난이도를 대폭 증가시킨다.

3. 게임 인공지능에서의 행동 트리 기원

3.1 초기 게임 AI와 상태 머신

컴퓨터 게임 분야에서 NPC의 행동 제어는 FSM을 기반으로 발전하였다. 초기 게임에서는 “순찰-추적-공격-복귀“와 같은 단순한 상태 전환 모델이 효과적으로 활용되었다. 그러나 게임의 복잡도가 증가하고 NPC의 행동이 다양화됨에 따라, 수백 개의 상태와 수천 개의 전이를 관리해야 하는 상황이 발생하였으며, FSM 기반 AI의 개발 및 디버깅 비용이 감당하기 어려운 수준에 이르렀다.

3.2 행동 트리의 도입과 확산

행동 트리는 2000년대 초반 게임 개발 커뮤니티에서 FSM의 대안으로 제안되었다. Bungie Studios의 Halo 시리즈(특히 Halo 2, 2004)에서 행동 트리가 NPC AI에 도입된 것은 게임 산업에서의 행동 트리 채택을 촉진한 대표적 사례로 알려져 있다 (Isla, 2005). 이후 Epic Games의 Unreal Engine이 행동 트리를 내장 AI 시스템으로 채택하면서, 행동 트리는 게임 AI의 사실상 표준 아키텍처로 자리 잡았다.

게임 분야에서 입증된 행동 트리의 구조적 장점—모듈성, 재사용성, 가독성, 확장 용이성—은 학술 연구자들의 관심을 끌었으며, Colledanchise와 Ögren (2018)의 체계적 연구를 통하여 행동 트리의 형식적 기초가 수립되었다. 이후 로봇공학, 자율 시스템, 산업 자동화 등 다양한 분야에서 행동 트리의 적용이 활발히 진행되었다 (Iovino et al., 2022).

4. 행동 트리의 개념적·수학적 정의

4.1 개념적 정의

행동 트리는 자율 에이전트의 행동 전환 로직을 계층적 트리 구조로 표현하는 제어 아키텍처이다. 트리의 각 노드는 특정 행동, 조건 확인, 또는 자식 노드의 실행 제어를 담당하며, 노드의 실행 결과는 성공(Success), 실패(Failure), **실행 중(Running)**의 세 가지 상태 중 하나로 반환된다. 이 삼진(ternary) 반환 체계는 행동 트리의 핵심적 설계 원리이며, 동기적(synchronous) 행동과 비동기적(asynchronous) 행동의 통합적 표현을 가능하게 한다.

4.2 수학적 정의

행동 트리 \mathcal{T}는 근트리(rooted tree) \mathcal{T} = (V, E, r)로 정의되며, 여기서 V는 노드의 유한 집합, E \subseteq V \times V는 간선의 집합, r \in V는 루트 노드이다. 각 노드 v \in V에는 Tick 함수 f_v: \mathcal{S} \rightarrow \{S, F, R\}이 배정되며, \mathcal{S}는 시스템 상태 공간, S는 Success, F는 Failure, R은 Running을 나타낸다.

내부 노드(internal node)는 제어 흐름 노드로서 자식 노드의 반환값을 조합하여 자신의 반환값을 결정하며, 리프 노드(leaf node)는 실제 행동을 수행하거나 조건을 평가하는 실행 노드이다.

5. 행동 트리의 기본 구조

5.1 루트 노드

루트 노드는 행동 트리의 최상위 진입점으로서, Tick 신호의 시작점 역할을 수행한다. 루트 노드는 단일 자식 노드를 가지며, Tick 주기마다 루트로부터 하향식으로 실행 흐름이 전파된다.

5.2 제어 흐름 노드

제어 흐름 노드(control flow node)는 자식 노드의 실행 순서와 논리적 조합 방식을 결정하는 내부 노드이다. 대표적인 제어 흐름 노드로 Sequence, Fallback(Selector), Parallel 등이 있으며, 각 노드 유형은 자식 노드의 반환값에 대한 고유한 조합 규칙을 적용한다.

5.3 실행 노드

실행 노드(execution node)는 리프 노드에 해당하며, 액션 노드(action node)와 조건 노드(condition node)로 구분된다. 액션 노드는 로봇의 물리적 행동(모터 구동, 센서 데이터 취득 등)이나 계산적 작업을 수행하며, 조건 노드는 환경 상태나 내부 변수를 평가하여 참(Success) 또는 거짓(Failure)을 반환한다.

5.4 반환 상태

행동 트리의 모든 노드는 Tick 시 다음 세 가지 상태 중 하나를 반환한다:

Running 상태는 비동기적 장기 실행 행동(예: 목표 위치까지 이동, 물체 파지)의 표현에 핵심적 역할을 수행하며, FSM에서는 이러한 비동기 상태의 표현이 구조적으로 자연스럽지 않다.

6. 행동 트리의 설계 철학

행동 트리의 설계는 다음과 같은 핵심 원칙에 기반한다:

모듈성(Modularity): 각 노드와 서브트리는 독립적인 행동 단위로서 설계, 구현, 테스트될 수 있다. 노드 간의 결합은 부모-자식 관계와 블랙보드를 통한 간접적 데이터 공유로 제한되며, 직접적인 상태 의존성이 배제된다.

재사용성(Reusability): 한 번 설계된 노드나 서브트리는 다른 행동 트리에서 수정 없이 재사용될 수 있다. 이는 FSM에서 상태의 이식이 전이 규칙의 전면적 재정의를 요구하는 것과 대비되는 근본적 장점이다.

반응성(Reactivity): Tick 기반 실행 모델에 의하여 매 주기마다 루트로부터 트리를 재평가함으로써, 환경 변화에 즉각적으로 대응하는 반응적 행동의 구현이 가능하다.

선언적 설계(Declarative Design): 행동 트리는 XML 등의 선언적 형식으로 정의될 수 있으며, 이는 행동 로직의 가독성을 높이고 비프로그래머도 행동 설계에 참여할 수 있는 접근성을 제공한다.

확장성(Scalability): 새로운 행동의 추가와 기존 행동의 제거가 트리의 다른 부분에 국소적(local) 영향만 미치며, 전체 구조의 재설계를 요구하지 않는다.

7. 상태 머신 대비 행동 트리의 구조적 장점

행동 트리는 FSM 대비 다음과 같은 구조적 장점을 제공한다:

1. 전이 규칙의 부재: FSM에서 상태 간 전이를 명시적으로 정의해야 하는 것과 달리, 행동 트리에서는 제어 흐름 노드의 조합 규칙에 의하여 실행 순서가 암묵적으로 결정된다. 이는 전이 복잡도의 조합적 폭증을 원천적으로 방지한다.
2. 국소적 수정 영향: 행동 트리에서 노드의 추가, 제거, 교체는 해당 서브트리 내에서만 영향을 미치며, 트리의 다른 부분에 파급 효과가 전파되지 않는다.
3. 서브트리를 통한 구조적 분해: 복잡한 임무를 독립적인 서브트리로 분해하고 계층적으로 조합함으로써, 소프트웨어 공학에서의 함수 분해(functional decomposition)와 유사한 추상화 수준을 달성할 수 있다.
4. 시각적 편집 도구와의 친화성: 트리 구조의 시각적 직관성은 Groot 등의 그래픽 편집 도구를 통한 행동 설계를 가능하게 하며, 이는 개발 생산성과 협업 효율성을 향상시킨다.

8. 행동 트리의 한계와 단점

행동 트리가 FSM의 다수 한계를 극복하지만, 다음과 같은 잔존 한계가 존재한다:

1. 학습 곡선: 행동 트리의 Tick 메커니즘, 반환 상태 전파, 제어 노드의 조합 논리 등은 FSM에 비하여 높은 초기 학습 비용을 요구한다.
2. 디버깅 복잡도: 대규모 행동 트리에서 실행 흐름의 추적과 오류 원인의 파악이 어려울 수 있으며, 이를 위한 별도의 로깅 및 시각화 도구가 필요하다.
3. 비동기 행동 관리: Running 상태를 반환하는 복수의 액션 노드가 동시에 활성화될 경우, 중단 처리(halting)와 자원 해제의 올바른 구현이 필수적이며, 이에 대한 설계 오류는 예측하기 어려운 행동을 유발할 수 있다.
4. 최적성 보장의 부재: 행동 트리는 사전에 정의된 구조에 따라 행동을 실행하며, 비용 함수 기반의 최적 행동 선택이나 계획 수립 능력을 본질적으로 제공하지 않는다. 이는 태스크 플래닝(task planning) 기법과의 결합을 통하여 보완되어야 한다.

9. 참고 문헌

• 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.
• Iovino, M., Scukins, E., Styrud, J., Ögren, P., & Smith, C. (2022). “A Survey of Behavior Trees in Robotics and AI.” Robotics and Autonomous Systems, 154, 104096.
• Isla, D. (2005). “Handling Complexity in the Halo 2 AI.” Game Developers Conference (GDC) 2005.
• 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