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

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

유한 상태 머신(Finite State Machine, FSM)으로 설계된 기존의 행동 제어 시스템을 행동 트리(Behavior Tree, BT) 기반으로 재설계하는 것은, 모듈성과 반응성의 향상을 위해 실무적으로 빈번하게 수행되는 작업이다. 본 절에서는 유한 상태 머신을 행동 트리로 변환하는 체계적인 방법론과 변환 과정에서 발생하는 구조적 변화를 분석한다.

1. 기본 변환 원리

유한 상태 머신 M = (S, \Sigma, \delta, s_0)을 행동 트리로 변환하는 과정에서 핵심적인 매핑 관계는 다음과 같다.

첫째, 상태의 매핑이다. 유한 상태 머신의 각 상태 s_i \in S는 해당 상태에서 수행되는 행동을 구현하는 액션(Action) 노드 또는 서브트리로 변환된다. 유한 상태 머신에서 상태는 행동의 실행과 함께 시스템의 현재 위치를 명시적으로 나타내지만, 행동 트리에서는 행동의 실행만이 노드에 의해 표현되며 현재 위치 정보는 블랙보드(Blackboard) 변수에 위임된다.

둘째, 전이 조건의 매핑이다. 유한 상태 머신의 전이 조건 \sigma \in \Sigma는 행동 트리의 조건(Condition) 노드로 변환된다. 전이 조건이 현재 상태에서 다음 상태로의 이동을 결정하듯, 조건 노드는 해당 액션 노드의 실행 여부를 결정한다.

셋째, 현재 상태 추적의 명시화이다. 유한 상태 머신에서 암묵적으로 유지되는 현재 상태 정보를 블랙보드 변수(예: current_state)로 명시적으로 관리한다. 각 액션 노드의 실행 전에 해당 상태에 대응하는 블랙보드 변수 값을 검사하고, 실행 완료 후 다음 상태에 대응하는 값으로 갱신한다.

2. 직접 변환 방법

가장 직관적인 변환 방법은 유한 상태 머신의 구조를 행동 트리에 직접 반영하는 것이다. n개의 상태를 갖는 유한 상태 머신을 변환하면 다음과 같은 행동 트리 구조가 생성된다.

Fallback
├── Sequence [상태 s_1 처리]
│   ├── Condition: current_state == s_1?
│   ├── Action: s_1의 행동 수행
│   └── SetBlackboard: current_state = 전이 결과
├── Sequence [상태 s_2 처리]
│   ├── Condition: current_state == s_2?
│   ├── Action: s_2의 행동 수행
│   └── SetBlackboard: current_state = 전이 결과
...
└── Sequence [상태 s_n 처리]
    ├── Condition: current_state == s_n?
    ├── Action: s_n의 행동 수행
    └── SetBlackboard: current_state = 전이 결과

최상위 폴백(Fallback) 노드는 자식 시퀀스 노드들을 순차적으로 시도하며, 현재 상태에 해당하는 시퀀스만이 조건 검사를 통과하여 실행된다. 이 방법은 원래의 유한 상태 머신과 동일한 동작을 보장하지만, 행동 트리의 장점인 반응성과 모듈성을 충분히 활용하지 못하는 구조적 한계가 존재한다.

3. 구조적 재설계를 동반하는 변환

유한 상태 머신의 구조를 단순히 행동 트리로 번역하는 것이 아니라, 행동 트리의 설계 원칙에 부합하도록 재설계하는 변환 방법이 실무적으로 권장된다. 이 접근에서는 다음의 재설계 원칙이 적용된다.

첫째, 전역 반응 조건의 분리이다. 유한 상태 머신에서 다수의 상태에 중복적으로 정의된 전이 조건(예: 긴급 정지, 배터리 부족)을 행동 트리의 상위 계층에 리액티브 노드로 배치하여, 하위의 모든 행동에 일괄 적용한다. 이를 통해 중복 전이 규칙이 제거되고, 전역 조건의 관리가 단일 지점에서 이루어진다.

둘째, 상태 변수의 제거 또는 최소화이다. 직접 변환에서 도입된 블랙보드 기반 상태 추적을 가능한 한 제거하고, 행동 트리의 구조적 흐름에 의해 행동 순서가 자연스럽게 결정되도록 재설계한다. 시퀀스 노드를 활용하여 순차적 행동 흐름을 표현하면, 명시적 상태 변수 없이도 행동 순서를 보장할 수 있다.

셋째, 반응적 구조의 도입이다. 유한 상태 머신에서는 현재 상태에서만 전이 조건을 평가하지만, 행동 트리에서는 리액티브 노드를 통해 상위 우선순위 조건을 매 틱마다 재평가하도록 구성한다. 이를 통해 유한 상태 머신보다 향상된 반응성을 달성할 수 있다.

4. 변환 과정의 구조적 복잡도

유한 상태 머신에서 행동 트리로의 변환에서 발생하는 구조적 복잡도 변화는 다음과 같이 분석된다.

직접 변환의 경우, n개의 상태와 m개의 전이를 갖는 유한 상태 머신은 O(n)개의 시퀀스 분기와 각 분기 내에 전이 조건에 비례하는 조건 노드를 포함하는 행동 트리로 변환된다. 전체 노드 수는 O(n + m)에 비례한다.

구조적 재설계를 동반하는 변환에서는 중복 전이의 제거와 반응적 구조의 도입으로 인해 노드 수가 감소할 수 있으나, 재설계의 정도에 따라 결과물이 상이하며 자동화가 어렵다.

5. 변환의 완전성과 한계

Colledanchise와 Ögren(2018)의 이론적 결과에 의해 임의의 유한 상태 머신을 행동 트리로 변환하는 것이 형식적으로 가능함이 보장된다. 그러나 변환된 행동 트리가 원래의 유한 상태 머신과 정확히 동일한 동작을 보이는지 검증하기 위해서는, 동일한 입력 시퀀스에 대해 동일한 출력 시퀀스를 생성하는지를 확인하는 동작 동치성(Behavioral Equivalence) 검증이 필요하다.

실무적으로는 변환 과정에서 타이밍 특성, 상태 진입/탈출 이벤트, 이력 상태(History State) 등 유한 상태 머신의 확장 기능이 행동 트리에서 직접적으로 대응되지 않는 경우가 존재하며, 이러한 기능의 변환에는 추가적인 설계 노력이 요구된다.

참고 문헌

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