1291.66 행동 트리와 상태 머신의 표현력 비교

행동 트리(Behavior Tree, BT)와 유한 상태 머신(Finite State Machine, FSM)은 로봇 행동 제어를 위한 대표적인 형식 체계(Formalism)이다. 두 체계는 각기 상이한 설계 원리에 기반하며, 특정 유형의 행동 논리를 표현하는 데 있어 상대적 우위와 제약을 지닌다. 본 절에서는 두 체계의 표현력(Expressiveness)을 이론적 및 실용적 관점에서 비교 분석한다.

1. 형식적 표현력의 이론적 동치성

Colledanchise와 Ögren(2018)의 분석에 따르면, 행동 트리와 유한 상태 머신은 형식적 관점에서 동등한 표현력을 지닌다. 즉, 임의의 유한 상태 머신으로 표현 가능한 행동 논리는 행동 트리로도 표현할 수 있으며, 그 역 또한 성립한다. 이 동치성은 두 체계가 모두 유한한 행동 집합과 조건 집합 위에서 결정론적 반응형 시스템(Deterministic Reactive System)을 기술할 수 있다는 점에 기인한다.

그러나 형식적 표현력의 동치성이 실용적 표현 효율의 동등성을 의미하지는 않는다. 특정 행동 패턴을 하나의 체계에서는 간결하고 직관적으로 표현할 수 있는 반면, 다른 체계에서는 복잡한 보조 구조를 필요로 하는 경우가 존재한다.

2. 순차적 행동 구성의 표현

행동들의 순차적 실행, 즉 행동 $A_1$ 을 완료한 후 $A_2$ 를, $A_2$ 완료 후 $A_3$ 을 실행하는 논리는 두 체계에서 모두 직관적으로 표현된다.

유한 상태 머신에서는 $S_1 \xrightarrow{\text{success}} S_2 \xrightarrow{\text{success}} S_3$ 의 선형적 상태 전이로 기술한다. 행동 트리에서는 시퀀스(Sequence) 노드의 자식으로 $A_1, A_2, A_3$ 을 배치하여 동일한 논리를 표현한다. 이 경우 두 체계의 표현 효율은 유사하다.

그러나 순차적 행동 중 임의의 단계에서 실패 시 대안적 행동으로 전환하는 논리의 표현에서 차이가 발생한다. 행동 트리에서는 시퀀스 노드와 폴백(Fallback) 노드의 중첩을 통해 자연스럽게 표현할 수 있지만, 유한 상태 머신에서는 각 상태에서 실패에 대한 전이를 개별적으로 정의해야 하며, 대안 행동의 수에 비례하여 전이 규칙이 증가한다.

3. 반응적 행동 전환의 표현

환경 조건의 변화에 즉각적으로 반응하여 현재 행동을 중단하고 다른 행동으로 전환하는 반응적(Reactive) 행동 전환은 행동 트리의 핵심 강점이다. 리액티브 시퀀스(ReactiveSequence) 노드를 사용하면 매 틱마다 우선순위 조건을 재평가하여, 조건 실패 시 진행 중인 행동을 자동으로 중단하고 대안 행동을 실행할 수 있다.

유한 상태 머신에서 동일한 반응적 행동 전환을 구현하려면, 모든 상태에서 환경 조건 변화에 대응하는 전이 규칙을 중복적으로 정의해야 한다. $n$ 개의 상태와 $m$ 개의 반응 조건이 있을 때, 최악의 경우 $O(n \times m)$ 개의 전이 규칙이 필요하다. 이에 비해 행동 트리에서는 트리 상단에 조건 노드를 배치하는 것만으로 하위의 모든 행동에 대한 반응적 전환을 일괄적으로 달성할 수 있으므로, 반응적 행동 전환의 표현 효율에서 행동 트리가 현저한 우위를 보인다.

4. 상태 의존적 논리의 표현

시스템의 현재 상태에 따라 허용되는 행동과 금지되는 행동이 엄격하게 구분되는 상태 의존적 논리는 유한 상태 머신의 핵심 표현 영역이다. 상태 머신에서는 각 상태에서 유효한 전이만을 정의함으로써, 불법적 상태 전이를 구조적으로 차단한다. 시스템이 어떤 상태에 있는지가 곧 허용 가능한 행동의 집합을 결정하며, 이 관계가 전이 도표(State Transition Diagram)에 명시적으로 시각화된다.

행동 트리에서는 동일한 상태 의존적 논리를 블랙보드 변수와 조건 노드의 조합으로 표현해야 한다. 상태 변수의 값에 따라 행동의 실행을 허용하거나 차단하는 조건 분기를 트리 내에 수동으로 배치해야 하므로, 상태 의존적 논리의 복잡도가 증가할수록 트리의 구조가 비대해지고 논리의 명확성이 저하된다.

5. 동시 행동의 표현

다수의 행동이 동시에 수행되어야 하는 동시 행동(Concurrent Behavior)의 표현에서 행동 트리는 병렬(Parallel) 노드를 통해 비교적 직관적인 구성이 가능하다. 병렬 노드의 자식으로 동시에 실행할 행동들을 배치하고, 성공/실패 정책(Policy)을 설정하여 동시 행동의 완료 조건을 정의한다.

유한 상태 머신에서 동시 행동을 표현하려면 직교 영역(Orthogonal Region)을 도입한 Statecharts(Harel, 1987) 형식을 사용해야 하며, 직교 영역 간의 동기화와 통신 메커니즘을 별도로 설계해야 한다. 기본적인 유한 상태 머신에서는 동시 행동의 직접적 표현이 불가능하며, 행동 조합의 수만큼 복합 상태(Composite State)를 정의하는 상태 폭발(State Explosion) 문제가 발생한다.

6. 계층적 행동 분해의 표현

복잡한 임무를 하위 임무로 계층적으로 분해하는 계층적 행동 분해(Hierarchical Decomposition)에서 행동 트리는 트리 구조의 본질적 특성에 의해 자연스러운 표현이 가능하다. 서브트리를 통해 하위 임무를 독립적으로 정의하고 상위 트리에 삽입하는 구성은 모듈적이고 직관적이다.

유한 상태 머신에서는 계층적 상태 머신(Hierarchical State Machine) 또는 슈퍼 상태(Super State)를 도입하여 유사한 계층 구조를 표현할 수 있으나, 상위 상태와 하위 상태 간의 전이 관계, 진입/탈출 조건의 정의, 이력 상태(History State)의 관리 등 추가적인 설계 복잡도가 수반된다.

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.
Iovino, M., Scukins, E., Styrud, H., Ögren, P., & Smith, C. (2022). “A Survey of Behavior Trees in Robotics and AI.” Robotics and Autonomous Systems, 154, 104096.
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.