1292.10 실행 노드의 리프 노드 특성
1. 서론
행동 트리(Behavior Tree)의 실행 노드(Execution Node)는 트리 자료 구조의 리프 노드(Leaf Node)에 해당한다. 리프 노드란 자식 노드를 갖지 않는 말단 노드를 의미하며, 트리 순회(Tree Traversal)에서 더 이상 하향 탐색이 진행되지 않는 종단점(Terminal Point)이다. 본 절에서는 실행 노드가 리프 노드로서 보유하는 구조적·의미론적 특성을 형식적으로 분석한다.
2. 리프 노드의 형식적 정의
트리 자료 구조에서 리프 노드 L은 자식 노드 집합이 공집합인 노드로 정의된다:
\text{children}(L) = \emptyset
행동 트리의 실행 노드 E는 이 조건을 만족하므로, 임의의 실행 노드는 항상 리프 노드이다. 이를 명제 논리로 표현하면 다음과 같다:
\forall\, N \in \mathcal{T} : N \in \mathcal{E} \implies \text{children}(N) = \emptyset
여기서 \mathcal{T}는 행동 트리의 전체 노드 집합, \mathcal{E}는 실행 노드의 집합이다. 역으로, 행동 트리에서 리프 노드는 반드시 실행 노드에 해당한다:
\forall\, N \in \mathcal{T} : \text{children}(N) = \emptyset \implies N \in \mathcal{E}
이 두 명제를 결합하면, 행동 트리에서 리프 노드와 실행 노드는 동치 관계에 있다:
N \in \mathcal{E} \iff \text{children}(N) = \emptyset
3. 리프 노드와 트리 깊이
3.1 깊이의 정의
노드 N의 깊이(Depth) d(N)은 루트 노드(Root Node)로부터 해당 노드까지의 경로 길이(간선 수)로 정의된다:
d(N) = \text{경로 길이}(\text{Root}, N)
리프 노드의 깊이는 트리의 구조에 따라 상이할 수 있다. 행동 트리는 균형 트리(Balanced Tree)일 것을 요구하지 않으므로, 각 리프 노드의 깊이는 해당 노드가 속한 분기(Branch)의 제어 흐름 노드 중첩 수준에 따라 결정된다.
3.2 트리 높이와 리프 노드의 관계
트리의 높이(Height) h(\mathcal{T})는 루트 노드로부터 가장 깊은 리프 노드까지의 최대 경로 길이이다:
h(\mathcal{T}) = \max_{L \in \mathcal{L}} d(L)
여기서 \mathcal{L}은 모든 리프 노드(실행 노드)의 집합이다. 트리의 높이는 Tick 전파의 최대 깊이를 결정하며, 이는 단일 Tick 주기의 최악 실행 시간(Worst-Case Execution Time)에 직접적인 영향을 미친다.
4. 리프 노드의 Tick 수신과 반환 상태 생성
4.1 Tick의 종착점으로서의 역할
Tick은 루트 노드에서 시작하여 제어 흐름 노드(Control Flow Node) 또는 데코레이터 노드(Decorator Node)를 경유하며 하향 전파된다. 이 전파가 리프 노드에 도달하면, 리프 노드는 Tick을 더 이상 하위로 전파하지 않고 자체적으로 작업을 수행한다. 즉, 리프 노드는 Tick 전파 체인의 종착점(Sink)이다.
\text{Tick 전파}: \text{Root} \rightarrow \cdots \rightarrow \text{Control Flow Node} \rightarrow \text{Leaf Node (종착)}
4.2 반환 상태의 원천
리프 노드가 Tick을 수신하면 작업 수행 또는 조건 평가 결과에 따라 반환 상태(Return Status)를 생성한다. 이 반환 상태는 상위 노드로 역전파(Backward Propagation)되어, 제어 흐름 노드의 의사결정에 활용된다. 행동 트리 전체의 실행 결과는 궁극적으로 리프 노드들이 생성한 반환 상태의 조합에 의해 결정된다.
\text{반환 상태 역전파}: \text{Leaf Node} \rightarrow \text{Control Flow Node} \rightarrow \cdots \rightarrow \text{Root}
따라서 리프 노드는 행동 트리의 정보 생성 원천(Information Source)으로 기능하며, 내부 노드들은 이 정보를 해석하고 집계하는 역할을 수행한다.
5. 리프 노드의 순수 계산 특성
5.1 하향 위임의 부재
제어 흐름 노드와 데코레이터 노드는 Tick을 수신하면 이를 자식 노드에 위임(Delegation)한다. 그러나 리프 노드는 자식 노드가 없으므로 위임이 불가능하며, 수신된 Tick에 대해 스스로 연산을 수행하여야 한다. 이 특성은 리프 노드가 행동 트리에서 유일하게 실질적인 계산(Computation)을 수행하는 노드임을 의미한다.
5.2 외부 시스템과의 인터페이스
리프 노드는 행동 트리와 외부 시스템(로봇 하드웨어, ROS2 노드, 센서, 액추에이터 등) 사이의 경계 인터페이스(Boundary Interface)를 형성한다. 행동 트리의 내부 구조는 추상적 의사결정 논리로 구성되며, 이 논리가 구체적인 물리적 행동이나 센서 데이터 조회로 변환되는 지점이 바로 리프 노드이다.
| 노드 유형 | Tick 수신 시 동작 | 외부 시스템 접근 |
|---|---|---|
| 제어 흐름 노드 | 자식 노드에 Tick 전파 | 없음 |
| 데코레이터 노드 | 단일 자식 노드에 Tick 전파 후 결과 변환 | 없음 |
| 실행 노드 (리프) | 직접 작업 수행 또는 조건 평가 | 있음 (액션 노드의 경우) |
6. 리프 노드의 차수와 구조적 제약
6.1 차수(Degree)의 정의
그래프 이론에서 노드의 차수(Degree)는 해당 노드에 연결된 간선의 수이다. 트리 자료 구조에서는 이를 자식 간선의 수(Out-degree)와 부모 간선의 수(In-degree)로 구분한다.
리프 노드 L의 경우:
\text{out-degree}(L) = 0
\text{in-degree}(L) = 1 \quad (\text{루트 노드 제외})
출력 차수(Out-degree)가 0이므로 하향 간선이 존재하지 않으며, 입력 차수(In-degree)가 1이므로 정확히 하나의 부모 노드에 연결된다. 이 부모 노드는 제어 흐름 노드 또는 데코레이터 노드이다.
6.2 구조적 불변 조건
행동 트리에서 리프 노드에 관한 구조적 불변 조건(Structural Invariant)은 다음과 같다:
- 자식 금지 제약: 리프 노드에 자식 노드를 추가하려는 시도는 구조적 오류(Structural Error)로 처리되어야 한다.
- 고립 금지 제약: 모든 리프 노드는 반드시 하나의 부모 노드에 연결되어야 한다. 부모가 없는 고립된 리프 노드는 Tick을 수신할 수 없으므로 실행 불가능하다.
- 순환 금지 제약: 리프 노드에서 조상 노드로의 역방향 간선이 존재하지 않아야 하며, 이는 방향 비순환 그래프(DAG) 속성에 의해 보장된다.
7. 리프 노드의 개수와 트리 복잡도
7.1 리프 노드 수의 의미
행동 트리에서 리프 노드의 총 개수 |\mathcal{L}|은 로봇이 수행할 수 있는 개별 행동(Action)과 평가할 수 있는 조건(Condition)의 총 수에 대응한다. 리프 노드의 수가 증가할수록 행동 트리의 행동적 표현력(Behavioral Expressiveness)이 확장되나, 동시에 트리의 복잡도가 증가하여 설계와 디버깅이 곤란해진다.
7.2 내부 노드 대비 리프 노드의 비율
이진 트리(Binary Tree)에서 리프 노드 수 |\mathcal{L}|과 내부 노드 수 |\mathcal{I}| 사이에는 다음 관계가 성립한다:
|\mathcal{L}| = |\mathcal{I}| + 1
행동 트리는 이진 트리가 아닌 다진 트리(N-ary Tree)이므로, 이 등식이 직접 적용되지는 않으나, 일반적으로 리프 노드의 수가 내부 노드의 수보다 많거나 같은 경향이 있다. 이는 제어 흐름 노드 하나가 다수의 실행 노드를 관리하는 구조에서 기인한다.
8. 리프 노드의 재사용성과 모듈화
8.1 범용 리프 노드의 설계
리프 노드는 특정 행동이나 조건을 캡슐화(Encapsulation)하므로, 적절히 설계된 리프 노드는 상이한 행동 트리 구조에서 재사용될 수 있다. 이를 위해 리프 노드는 블랙보드(Blackboard) 포트를 통해 매개변수를 외부로부터 주입받는 구조로 설계되어야 하며, 내부에 하드코딩된 상수나 특정 컨텍스트에 대한 의존성을 최소화하여야 한다.
8.2 서브트리에서의 리프 노드 공유
서브트리(Subtree) 메커니즘을 활용하면, 동일한 리프 노드 유형을 복수의 서브트리에서 인스턴스화하여 사용할 수 있다. 이때 각 인스턴스는 독립적인 상태를 유지하며, 블랙보드 포트의 바인딩(Binding)을 통해 서로 다른 매개변수로 동작한다.
9. 리프 노드 특성의 요약
리프 노드로서 실행 노드가 보유하는 핵심 특성을 정리하면 다음과 같다:
| 특성 | 설명 |
|---|---|
| 자식 부재 | \text{children}(E) = \emptyset; 하향 Tick 전파 불가 |
| Tick 종착점 | Tick 전파 체인의 최종 수신자 |
| 반환 상태 원천 | 행동 트리의 의사결정 정보를 생성하는 유일한 원천 |
| 외부 인터페이스 | 행동 트리와 외부 시스템 간의 경계를 형성 |
| 출력 차수 0 | \text{out-degree}(E) = 0 |
| 실질적 계산 수행 | 행동 트리에서 유일하게 구체적 연산을 실행 |
이러한 리프 노드 특성은 행동 트리의 구조적 명료성과 실행 의미론의 정확성을 보장하는 근간이 된다. 제어 흐름 노드가 의사결정의 “논리“를 정의한다면, 리프 노드로서의 실행 노드는 그 논리의 “실체“를 제공한다.
참고 문헌
- Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Marzinotto, A., Colledanchise, M., Smith, C., & Ögren, P. (2014). “Towards a Unified Behavior Trees Framework for Robot Control.” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 5420–5427.
- Faconti, D., & Contributors. (2024). BehaviorTree.CPP Documentation. https://www.behaviortree.dev/
v1.0