1291.70 행동 트리에서 상태 머신으로의 변환

행동 트리(Behavior Tree, BT)에서 유한 상태 머신(Finite State Machine, FSM)으로의 변환은, 행동 트리로 설계된 시스템의 형식적 검증이나 기존 상태 머신 기반 인프라와의 호환성 확보가 필요한 경우에 요구된다. 본 절에서는 이 역방향 변환의 원리, 방법론, 그리고 변환 과정에서 발생하는 구조적 복잡도 증가를 분석한다.

1. 변환의 이론적 근거

Colledanchise와 Ögren(2018)의 분석에 의해, 유한한 환경 상태 공간 위에서 정의된 임의의 행동 트리를 동등한 유한 상태 머신으로 변환하는 것이 형식적으로 가능함이 보장된다. 이 결과는 행동 트리의 각 틱에서의 동작이 현재 환경 조건과 트리 내부의 실행 상태에 의해 결정론적으로 결정되므로, 이 결정 과정을 유한 상태 머신의 상태 전이로 표현할 수 있다는 점에 기초한다.

2. 기본 변환 과정

행동 트리에서 유한 상태 머신으로의 변환은 다음의 단계로 수행된다.

단계 1: 트리 실행 상태 공간의 열거. 행동 트리의 각 노드는 틱 시점에서 Success, Failure, Running 중 하나의 상태를 반환한다. 메모리를 갖는 시퀀스(SequenceWithMemory) 노드의 경우, 이전 틱에서 성공한 자식 노드의 인덱스를 내부적으로 보존한다. 이러한 내부 상태를 포함하여 트리 전체의 가능한 실행 상태 조합을 열거한다.

단계 2: 환경 조건 공간의 이산화. 행동 트리의 조건 노드가 평가하는 환경 조건의 가능한 값 조합을 열거한다. 조건 노드가 $k$ 개이고 각각 이진(Boolean) 평가를 수행하는 경우, 환경 조건 공간의 크기는 최대 $2^k$ 이다.

단계 3: 상태 집합의 구성. 유한 상태 머신의 상태 집합 $S$ 는 트리 실행 상태 공간과 블랙보드 변수 공간의 곱집합(Cartesian Product)의 부분집합으로 정의된다. 도달 가능한(Reachable) 상태만을 포함하도록 축소하여 불필요한 상태를 제거한다.

단계 4: 전이 함수의 정의. 각 상태와 환경 조건 조합에 대하여, 행동 트리의 틱 순회 알고리즘을 시뮬레이션하여 다음 상태를 결정한다. 이 결과를 전이 함수 $\delta: S \times \Sigma \rightarrow S$ 로 기록한다.

3. 상태 폭발 문제

행동 트리에서 유한 상태 머신으로의 변환에서 가장 심각한 문제는 상태 폭발(State Explosion)이다. 행동 트리의 노드 수가 $N$ 이고, 블랙보드 변수가 $p$ 개이며 각 변수의 가능한 값이 $v$ 개인 경우, 이론적 상태 공간의 상한은 $O(3^N \times v^p)$ 에 달한다.

특히 병렬(Parallel) 노드를 포함하는 행동 트리의 변환에서 상태 폭발이 현저하다. $k$ 개의 자식을 갖는 병렬 노드에서 각 자식이 독립적으로 3가지 반환 상태를 가질 수 있으므로, 병렬 노드만으로도 $3^k$ 개의 상태 조합이 생성된다. 이는 동시 행동의 표현에서 행동 트리가 유한 상태 머신 대비 지수적으로 간결한 표현을 제공함을 의미하며, 역변환 시 이 간결성이 소실된다.

4. 리액티브 노드의 변환 복잡성

리액티브 시퀀스(ReactiveSequence)나 리액티브 폴백(ReactiveFallback) 노드는 매 틱마다 첫 번째 자식부터 재평가를 수행하므로, 유한 상태 머신으로 변환할 때 추가적인 복잡성이 발생한다. 리액티브 노드의 매 틱 재평가 동작을 상태 전이로 표현하려면, 조건 노드의 평가 결과가 변경될 수 있는 모든 시점에서의 전이를 정의해야 한다. 이는 환경 조건의 변화에 따른 전이 규칙의 조합적 증가를 초래한다.

5. 블랙보드 변수의 상태 통합

행동 트리에서 블랙보드를 통해 관리되는 변수들은 유한 상태 머신으로의 변환 시 상태 공간의 차원을 증가시키는 요인이다. 블랙보드 변수의 값이 유한하고 이산적인 경우에만 유한 상태 머신으로의 변환이 가능하며, 연속적(Continuous) 값을 갖는 변수가 존재하는 경우에는 이산화(Discretization)가 선행되어야 한다. 이산화의 정밀도와 상태 공간의 크기 사이에는 직접적인 상충 관계가 존재한다.

6. 변환의 실용적 한계와 적용 맥락

행동 트리에서 유한 상태 머신으로의 완전한 변환은 소규모 트리에 대해서는 실현 가능하지만, 실무적 규모의 행동 트리에 대해서는 상태 폭발로 인해 비실용적인 경우가 대부분이다. 따라서 이 변환은 주로 다음의 목적으로 제한적으로 활용된다.

첫째, 형식적 검증을 위한 추상화 변환이다. 행동 트리의 핵심 논리만을 추출하여 축소된 유한 상태 머신으로 변환하고, 이 추상 모델에 대해 모델 검사(Model Checking)를 수행한다. Biggar, Zamani, Shames(2020)는 이러한 추상화 기반 검증 방법론을 제안하였다.

둘째, 레거시 시스템과의 인터페이스 구축이다. 기존의 유한 상태 머신 기반 제어 시스템과 행동 트리 기반 시스템 간의 호환성을 위해, 행동 트리의 외부 인터페이스를 유한 상태 머신의 형태로 변환하여 기존 시스템에 제공한다.

참고 문헌

Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
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.
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.