396.45 행동 트리(Behavior Tree)의 기본 구조

1. 개요

행동 트리(Behavior Tree, BT)는 자율 로봇 시스템의 행동 제어와 임무 관리를 위해 개발된 트리 구조 기반의 실행 모델이다. 행동 트리는 원래 게임 AI 분야에서 비플레이어 캐릭터(Non-Player Character, NPC)의 지능적 행동을 설계하기 위해 개발되었으나, 2010년대 이후 로봇 공학 분야에서 임무 관리의 핵심적 실행 모델로 자리 잡았다(Colledanchise & Ögren, 2018). 행동 트리는 모듈성(Modularity), 재사용성(Reusability), 반응성(Reactivity)의 세 가지 핵심 특성을 통해 유한 상태 머신(FSM)의 한계를 구조적으로 극복한다.

2. 행동 트리의 형식적 정의

2.1 트리 구조

행동 트리는 방향 비순환 그래프(Directed Acyclic Graph, DAG)의 특수한 형태인 루트 트리(Rooted Tree)로 정의된다. 형식적으로, 행동 트리 $\mathcal{T}$ 는 다음과 같이 정의된다.

$\mathcal{T} = (N, E, r)$

여기서 $N$ 은 노드의 유한 집합, $E \subseteq N \times N$ 은 간선의 집합, $r \in N$ 은 루트 노드(Root Node)이다.

2.2 노드의 분류

행동 트리의 노드는 두 가지 범주로 구분된다.

제어 흐름 노드(Control Flow Node): 하위 노드(Child Node)를 갖는 내부 노드(Internal Node)로, 자식 노드의 실행 순서와 흐름을 결정한다.

$n \in N_{\text{control}} \iff \text{children}(n) \neq \emptyset$

실행 노드(Execution Node): 하위 노드를 갖지 않는 단말 노드(Leaf Node)로, 로봇의 실제 행동이나 조건 확인을 수행한다.

$n \in N_{\text{execution}} \iff \text{children}(n) = \emptyset$

2.3 반환 상태(Return Status)

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

$\text{Status} \in \{\text{SUCCESS}, \text{FAILURE}, \text{RUNNING}\}$

SUCCESS: 노드의 실행이 성공적으로 완료되었음을 의미한다.
FAILURE: 노드의 실행이 실패하였음을 의미한다.
RUNNING: 노드의 실행이 아직 진행 중임을 의미한다.

이 3-값(Three-Valued) 반환 체계는 행동 트리의 핵심적 특성이다. RUNNING 상태는 비동기적 장기 실행 행동의 표현을 가능하게 하며, 이는 FSM에서는 직접적으로 지원되지 않는 기능이다.

3. 틱(Tick) 기반 실행 모델

3.1 틱의 정의

행동 트리의 실행은 틱(Tick) 기반으로 이루어진다. 매 틱마다 루트 노드에서 시작하여 트리를 깊이 우선(Depth-First) 방식으로 순회하며, 각 노드의 실행 상태를 평가한다.

$\text{tick}(\mathcal{T}) : r \xrightarrow{\text{tick}} \text{Status}$

틱의 주기 $\Delta t_{\text{tick}}$ 은 시스템의 반응성 요구사항에 따라 설정된다. 일반적으로 10~100ms 범위가 사용된다.

3.2 실행 순서

루트 노드에 틱이 전달되면, 루트 노드는 자신의 유형에 따라 자식 노드에 틱을 전파한다. 자식 노드의 반환 상태에 기반하여 루트 노드의 반환 상태가 결정된다. 이 과정은 재귀적으로 모든 활성 경로의 단말 노드까지 전파된다.

$\text{tick}(n) = \begin{cases} n.\text{execute}() & \text{if } n \in N_{\text{execution}} \\ n.\text{propagate}(\text{children}(n)) & \text{if } n \in N_{\text{control}} \end{cases}$

4. 제어 흐름 노드의 기본 유형

4.1 시퀀스 노드(Sequence Node)

시퀀스 노드( $\rightarrow$ )는 자식 노드를 왼쪽에서 오른쪽으로 순차적으로 실행한다. 현재 자식이 SUCCESS를 반환하면 다음 자식으로 진행하고, FAILURE를 반환하면 시퀀스 전체가 FAILURE를 반환한다.

$\text{Sequence}(c_1, c_2, \ldots, c_n) = \begin{cases} \text{FAILURE} & \text{if } \exists i : c_i = \text{FAILURE} \\ \text{RUNNING} & \text{if } \exists i : c_i = \text{RUNNING} \wedge \forall j < i : c_j = \text{SUCCESS} \\ \text{SUCCESS} & \text{if } \forall i : c_i = \text{SUCCESS} \end{cases}$

시퀀스 노드는 논리적 AND 연산에 대응된다. 모든 자식이 성공하여야 시퀀스가 성공한다.

4.2 폴백 노드(Fallback Node)

폴백 노드( $?$ , 또는 Selector Node)는 자식 노드를 왼쪽에서 오른쪽으로 순차적으로 실행한다. 현재 자식이 FAILURE를 반환하면 다음 자식으로 진행하고, SUCCESS를 반환하면 폴백 전체가 SUCCESS를 반환한다.

$\text{Fallback}(c_1, c_2, \ldots, c_n) = \begin{cases} \text{SUCCESS} & \text{if } \exists i : c_i = \text{SUCCESS} \\ \text{RUNNING} & \text{if } \exists i : c_i = \text{RUNNING} \wedge \forall j < i : c_j = \text{FAILURE} \\ \text{FAILURE} & \text{if } \forall i : c_i = \text{FAILURE} \end{cases}$

폴백 노드는 논리적 OR 연산에 대응된다. 하나의 자식이라도 성공하면 폴백이 성공한다. 대안적 전략의 시도에 활용된다.

4.3 병렬 노드(Parallel Node)

병렬 노드( $\Rightarrow$ )는 모든 자식 노드를 동시에 실행한다. 성공 임계값 $M$ 이 정의되며, $M$ 개 이상의 자식이 SUCCESS를 반환하면 병렬 노드가 SUCCESS를 반환한다.

$\text{Parallel}_M(c_1, c_2, \ldots, c_n) = \begin{cases} \text{SUCCESS} & \text{if } |\{i : c_i = \text{SUCCESS}\}| \geq M \\ \text{FAILURE} & \text{if } |\{i : c_i = \text{FAILURE}\}| > n - M \\ \text{RUNNING} & \text{otherwise} \end{cases}$

5. 실행 노드의 기본 유형

5.1 행동 노드(Action Node)

행동 노드는 로봇의 물리적 행동을 실행하는 단말 노드이다. 행동이 완료되면 SUCCESS 또는 FAILURE를 반환하고, 진행 중이면 RUNNING을 반환한다.

$\text{Action}.\text{execute}() \rightarrow \text{Status} \in \{\text{SUCCESS}, \text{FAILURE}, \text{RUNNING}\}$

예시: NavigateTo(goal), PickObject(id), SendReport()

5.2 조건 노드(Condition Node)

조건 노드는 특정 조건의 참/거짓을 평가하는 단말 노드이다. 조건 평가는 즉시 완료되므로 RUNNING을 반환하지 않는다.

$\text{Condition}.\text{execute}() \rightarrow \text{Status} \in \{\text{SUCCESS}, \text{FAILURE}\}$

예시: BatteryAbove(threshold), ObstacleDetected(), GoalReached()

6. 트리 구조의 시각적 표현

행동 트리는 다음과 같은 시각적 표기법으로 표현된다.

        [?] Fallback
       / | \
      /  |  \
  [→]   [→]  Action:
 Seq1   Seq2  ReturnToBase
  / \   / \
 C1 A1 C2 A2

여기서 $C_i$ 는 조건 노드, $A_i$ 는 행동 노드, $[?]$ 는 폴백 노드, $[\rightarrow]$ 는 시퀀스 노드이다.

7. 행동 트리의 수학적 성질

7.1 구조적 합성(Structural Composition)

행동 트리의 핵심적 강점은 서브트리(Subtree)의 독립적 합성이 가능하다는 점이다. 두 개의 행동 트리 $\mathcal{T}_1$ 과 $\mathcal{T}_2$ 는 제어 흐름 노드를 통해 새로운 행동 트리 $\mathcal{T}_3$ 으로 합성된다.

$\mathcal{T}_3 = \text{Sequence}(\mathcal{T}_1, \mathcal{T}_2)$

$\mathcal{T}_4 = \text{Fallback}(\mathcal{T}_1, \mathcal{T}_2)$

이 합성은 $\mathcal{T}_1$ 과 $\mathcal{T}_2$ 의 내부 구조를 수정하지 않고 이루어지므로, 서브트리의 재사용성이 보장된다.

7.2 반응성(Reactivity)

행동 트리의 반응성은 매 틱마다 루트에서 트리를 재평가하는 데서 기인한다. 환경 변화로 인해 조건 노드의 평가 결과가 변하면, 현재 실행 중인 행동이 자동으로 중단되고 새로운 행동이 활성화된다.

$\text{at tick } t : C_1 = \text{TRUE} \implies A_1 \text{ active}$
$\text{at tick } t+1 : C_1 = \text{FALSE} \implies A_1 \text{ halted, try } A_2$

이 특성은 FSM에서 모든 상태에 전역 이벤트 전이를 명시적으로 정의하여야 하는 것과 대비되는 장점이다.

7.3 표현력(Expressiveness)

Colledanchise와 Ögren(2018)은 행동 트리가 유한 상태 머신과 동등한 표현력을 가짐을 증명하였다. 즉, 모든 FSM은 행동 트리로 변환될 수 있으며, 그 역도 성립한다.

$\mathcal{L}(\text{BT}) = \mathcal{L}(\text{FSM})$

그러나 동일한 행동을 표현할 때, 행동 트리는 FSM에 비해 모듈적이고 재사용 가능한 구조를 제공한다.

8. 블랙보드(Blackboard) 데이터 공유

행동 트리의 노드 간 데이터 공유는 블랙보드(Blackboard) 패턴을 통해 이루어진다. 블랙보드는 키-값(Key-Value) 쌍의 공유 저장소로, 노드들이 입출력 데이터를 교환하는 데 사용된다.

$\text{Blackboard} = \{(k_i, v_i) \mid k_i \in \mathcal{K}, v_i \in \mathcal{V}\}$

행동 노드는 블랙보드에서 입력 값을 읽고( $\text{read}$ ), 결과 값을 기록한다( $\text{write}$ ).

$v = \text{BB.get}(k), \quad \text{BB.set}(k, v')$

블랙보드 패턴은 노드 간의 직접적 결합을 피하고, 노드의 독립성을 보존하면서도 필요한 데이터 교환을 가능하게 한다.

9. 행동 트리의 실용적 구현

9.1 BehaviorTree.CPP 라이브러리

BehaviorTree.CPP는 로봇 공학 분야에서 가장 널리 사용되는 C++ 기반 행동 트리 라이브러리이다(Faconti, 2018). 이 라이브러리는 다음의 기능을 제공한다.

XML 기반의 트리 정의 및 동적 로딩
사용자 정의 노드의 플러그인 아키텍처
블랙보드 기반 데이터 공유
Groot 도구를 통한 시각적 편집 및 실시간 모니터링
로깅 및 리플레이 기능

9.2 ROS2 Nav2에서의 활용

ROS2 Navigation2(Nav2) 스택에서 행동 트리는 네비게이션 임무의 핵심 실행 모델로 채택되었다(Macenski et al., 2020). bt_navigator 노드는 BehaviorTree.CPP 라이브러리를 기반으로 네비게이션 과업의 실행 흐름을 관리한다.

10. 요약

행동 트리는 루트 트리 구조에 기반한 임무 실행 모델로, 제어 흐름 노드(시퀀스, 폴백, 병렬)와 실행 노드(행동, 조건)의 조합을 통해 복잡한 임무 행동을 구성한다. 틱 기반의 주기적 평가 메커니즘은 환경 변화에 대한 반응성을 보장하며, 서브트리의 독립적 합성은 모듈성과 재사용성을 제공한다. 블랙보드 패턴을 통한 데이터 공유와 BehaviorTree.CPP, Nav2 등의 실용적 구현체는 행동 트리가 로봇 임무 관리의 핵심 기술로 정착하는 데 기여하였다.

11. 참고 문헌

Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
Macenski, S., Martín, F., White, R., & Clavero, J. G. (2020). “The Marathon 2: A Navigation System.” Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2718–2725.
Marzinotto, A., Colledanchise, M., Smith, C., & Ögren, P. (2014). “Towards a Unified Behavior Trees Framework for Robot Control.” Proceedings of IEEE International Conference on Robotics and Automation (ICRA), pp. 5420–5427.
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.
Faconti, D. (2018). “BehaviorTree.CPP: A C++ Behavior Tree Library.” GitHub Repository.

v0.1