1292.4 행동 트리의 구성 요소 분류
1. 구성 요소 분류의 개요
행동 트리는 서로 다른 기능적 역할을 수행하는 복수의 노드 유형으로 구성된다. 이러한 노드 유형들을 체계적으로 분류하는 것은 행동 트리의 설계, 구현, 분석에 있어 필수적인 기초 작업이다. Colledanchise와 Ögren(2018)은 행동 트리의 노드를 기능적 역할에 따라 크게 세 범주로 분류하였으며, 이 분류 체계는 현재 행동 트리 연구 및 구현의 표준적 기반으로 활용되고 있다.
2. 차 분류: 트리 내 위치에 따른 분류
행동 트리의 노드는 트리 구조 내에서의 위치에 따라 다음의 두 범주로 분류한다.
2.1 내부 노드 (Internal Node)
내부 노드는 하나 이상의 자식 노드를 가지는 노드이다. 내부 노드는 자식 노드의 실행을 제어하거나 자식 노드의 반환 상태를 변환하는 역할을 수행한다. 내부 노드 자체는 외부 환경과 직접적으로 상호 작용하지 않으며, 자식 노드들의 반환 상태에 기반하여 자신의 반환 상태를 결정한다.
2.2 리프 노드 (Leaf Node)
리프 노드는 자식 노드를 가지지 않는 단말 노드이다. 리프 노드는 행동 트리에서 실제 행동의 수행이나 환경 조건의 평가가 이루어지는 지점이며, 외부 환경 또는 시스템 상태와 직접적으로 상호 작용한다.
3. 차 분류: 기능적 역할에 따른 분류
기능적 역할에 따라 행동 트리의 노드는 다음의 세 범주로 분류한다.
3.1 제어 흐름 노드 (Control Flow Node)
제어 흐름 노드는 내부 노드에 해당하며, 두 개 이상의 자식 노드를 가질 수 있다. 이 노드의 핵심 역할은 자식 노드들의 실행 순서와 조건을 결정하는 것이다. 제어 흐름 노드는 Tick 신호를 수신하면 정의된 정책(policy)에 따라 자식 노드에 Tick 신호를 전파하고, 자식 노드의 반환 상태를 종합하여 자신의 반환 상태를 결정한다. 주요 제어 흐름 노드의 유형은 다음과 같다.
| 노드 유형 | 자식 수 | 핵심 동작 |
|---|---|---|
| Sequence | \geq 2 | 모든 자식이 성공해야 성공 |
| Fallback | \geq 2 | 하나의 자식이 성공하면 성공 |
| Parallel | \geq 2 | 임계값 기반 동시 실행 |
| ReactiveSequence | \geq 2 | 매 Tick마다 처음부터 재평가 |
| ReactiveFallback | \geq 2 | 매 Tick마다 처음부터 재평가 |
| IfThenElse | 2~3 | 조건 기반 분기 실행 |
| WhileDoElse | 2~3 | 조건 기반 반복 실행 |
| Switch | \geq 2 | 다중 분기 선택 실행 |
3.2 실행 노드 (Execution Node)
실행 노드는 리프 노드에 해당하며, 행동 트리에서 실제 연산이 수행되는 지점이다. 실행 노드는 자식 노드를 가지지 않으며, Tick 신호를 수신하면 할당된 과업을 직접 수행하거나 환경 상태를 평가한다. 실행 노드는 다시 두 하위 유형으로 세분화된다.
액션 노드 (Action Node): 로봇의 물리적 행동이나 시스템 연산을 수행하는 노드이다. 액션 노드는 실행 과정에서 환경이나 시스템의 상태를 변경하는 부수 효과(side effect)를 발생시킬 수 있다. 반환 상태로 Success, Failure, Running을 모두 반환할 수 있다.
조건 노드 (Condition Node): 환경이나 시스템의 특정 조건을 평가하는 노드이다. 조건 노드는 부수 효과를 발생시키지 않으며, 평가 결과에 따라 Success 또는 Failure만을 반환한다. 조건 노드는 즉각적(instantaneous)으로 평가가 완료되어야 하므로 Running 상태를 반환하지 않는다.
3.3 데코레이터 노드 (Decorator Node)
데코레이터 노드는 내부 노드에 해당하되, 정확히 하나의 자식 노드만을 가지는 단항(unary) 노드이다. 데코레이터 노드의 역할은 자식 노드의 반환 상태를 변환하거나, 자식 노드의 실행 빈도 또는 실행 조건을 제어하는 것이다. 데코레이터 노드는 소프트웨어 공학의 데코레이터 패턴(decorator pattern)에서 그 명칭이 유래하였다. 주요 데코레이터 노드의 유형은 다음과 같다.
| 데코레이터 유형 | 핵심 동작 |
|---|---|
| Inverter | Success와 Failure를 상호 반전 |
| ForceSuccess | 자식 결과를 항상 Success로 변환 |
| ForceFailure | 자식 결과를 항상 Failure로 변환 |
| Repeat | 자식을 지정 횟수만큼 반복 실행 |
| Retry | 자식 실패 시 지정 횟수만큼 재시도 |
| Timeout | 지정 시간 초과 시 Failure 반환 |
| Delay | 지정 시간 동안 실행 지연 |
| RunOnce | 자식을 최초 1회만 실행 |
| KeepRunningUntilFailure | 자식이 실패할 때까지 Running 유지 |
4. 특수 노드: 루트 노드
루트 노드(root node)는 행동 트리의 최상위에 위치하는 유일한 노드이다. 루트 노드는 제어 흐름 노드의 특수한 형태로 분류될 수 있으나, 다른 제어 흐름 노드와 달리 정확히 하나의 자식 노드만을 가지며 부모 노드가 존재하지 않는다. 루트 노드는 Tick 메커니즘의 시작점으로서, 외부로부터 Tick 신호를 수신하여 자식 노드로 전파하는 역할을 수행한다.
5. 구성 요소 간의 관계
행동 트리의 구성 요소들은 명확한 계층적 관계를 형성한다. 이 관계를 집합론적으로 표현하면 다음과 같다.
N = N_{\text{internal}} \cup N_{\text{leaf}}
N_{\text{internal}} = N_{\text{root}} \cup N_{\text{control}} \cup N_{\text{decorator}}
N_{\text{leaf}} = N_{\text{action}} \cup N_{\text{condition}}
여기서 각 하위 집합은 상호 배타적(mutually exclusive)이다.
N_{\text{root}} \cap N_{\text{control}} = N_{\text{control}} \cap N_{\text{decorator}} = N_{\text{action}} \cap N_{\text{condition}} = \emptyset
6. 노드 유형별 자식 수 제약
각 노드 유형은 가질 수 있는 자식 노드의 수에 대한 제약을 가지며, 이를 형식적으로 정의하면 다음과 같다. 노드 v의 진출 차수(out-degree)를 \text{deg}^+(v)로 표기할 때:
\text{deg}^+(v) = \begin{cases} 1 & \text{if } v \in N_{\text{root}} \\ \geq 2 & \text{if } v \in N_{\text{control}} \\ 1 & \text{if } v \in N_{\text{decorator}} \\ 0 & \text{if } v \in N_{\text{leaf}} \end{cases}
이 제약은 행동 트리의 구조적 유효성(structural validity)을 검증하는 데 사용되며, 위반 시 트리 구성 단계에서 오류로 감지되어야 한다.
7. 노드 유형별 반환 상태 제약
각 노드 유형이 반환할 수 있는 상태의 범위도 유형에 따라 제한된다.
| 노드 유형 | 반환 가능 상태 |
|---|---|
| 제어 흐름 노드 | Success, Failure, Running |
| 데코레이터 노드 | Success, Failure, Running |
| 액션 노드 | Success, Failure, Running |
| 조건 노드 | Success, Failure |
조건 노드가 Running 상태를 반환하지 않는다는 제약은 행동 트리의 설계 원칙에서 비롯된 것으로, 조건 평가의 즉각성(immediacy)을 보장하기 위한 것이다.
8. 참고 문헌
- Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
- 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.
- Gamma, E., Helm, R., Johnson, R., & Vlissides, J. (1994). Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley.
- Faconti, D., & Colledanchise, M. (2022). BehaviorTree.CPP 4.x Documentation. https://www.behaviortree.dev/
본 절은 Version 1로 작성되었다.