1292.1 행동 트리의 트리 자료 구조 기반

1. 트리 자료 구조의 정의

행동 트리(Behavior Tree)는 컴퓨터 과학에서 정의하는 트리(tree) 자료 구조를 기반으로 구성된다. 트리 자료 구조란 하나의 루트 노드(root node)를 정점으로 하여 유한 개의 노드(node)가 간선(edge)으로 연결된 비순환(acyclic) 계층 구조를 의미한다. 형식적으로 트리 $T$ 는 다음과 같이 정의한다.

$T = (V, E)$

여기서 $V$ 는 노드의 유한 집합이며, $E \subseteq V \times V$ 는 간선의 집합이다. 트리가 성립하려면 다음 조건을 만족해야 한다.

$\lvert V \rvert \geq 1$ 이며, 정확히 하나의 루트 노드 $r \in V$ 가 존재한다.
루트 노드 $r$ 을 제외한 모든 노드 $v \in V \setminus \{r\}$ 는 정확히 하나의 부모 노드(parent node)를 가진다.
루트 노드 $r$ 에서 임의의 노드 $v$ 까지 정확히 하나의 경로(path)가 존재한다.
순환 경로(cycle)가 존재하지 않는다.

이러한 구조적 제약은 행동 트리가 의사 결정 과정에서 결정론적(deterministic)이고 예측 가능한 실행 흐름을 보장하는 근본적 기반이 된다.

2. 행동 트리에서의 노드 계층 구조

행동 트리는 트리 자료 구조의 계층적 특성을 활용하여 로봇의 행동을 조직화한다. 트리 내의 각 노드는 부모-자식(parent-child) 관계로 연결되며, 이 관계는 행동의 추상화 수준(abstraction level)을 반영한다. 상위 노드는 하위 노드의 실행을 제어하는 역할을 수행하며, 하위 노드로 내려갈수록 구체적인 행동 또는 조건 평가를 담당한다.

트리 자료 구조에서 노드 간의 관계를 정의하면 다음과 같다.

부모 노드(parent node): 간선을 통해 직접 연결된 상위 노드를 지칭한다. 루트 노드를 제외한 모든 노드는 정확히 하나의 부모 노드를 가진다.
자식 노드(child node): 간선을 통해 직접 연결된 하위 노드를 지칭한다. 하나의 부모 노드는 0개 이상의 자식 노드를 가질 수 있다.
리프 노드(leaf node): 자식 노드가 없는 노드를 의미한다. 행동 트리에서 리프 노드는 실제 행동(action)을 수행하거나 조건(condition)을 평가하는 실행 노드(execution node)에 해당한다.
내부 노드(internal node): 하나 이상의 자식 노드를 가지는 노드를 의미한다. 행동 트리에서 내부 노드는 자식 노드의 실행 흐름을 제어하는 제어 흐름 노드(control flow node)에 해당한다.

3. 루트 트리로서의 행동 트리

행동 트리는 엄밀히 루트 트리(rooted tree)에 해당한다. 루트 트리란 특정 노드 하나를 루트로 지정하여 모든 간선에 방향성을 부여한 트리를 의미한다. 루트 노드로부터 각 노드까지의 경로는 유일하며, 이 경로의 방향은 항상 루트에서 리프를 향한다.

루트 트리의 깊이(depth)와 높이(height) 개념은 행동 트리의 구조적 복잡성을 분석하는 데 활용된다.

$\text{depth}(v) = \begin{cases} 0 & \text{if } v = r \\ \text{depth}(\text{parent}(v)) + 1 & \text{otherwise} \end{cases}$

$\text{height}(T) = \max_{v \in V} \text{depth}(v)$

행동 트리의 높이는 의사 결정의 계층적 깊이를 나타내며, 높이가 증가할수록 보다 세분화된 행동 분해(behavioral decomposition)가 이루어짐을 의미한다.

4. 순서 트리로서의 행동 트리

행동 트리는 단순한 루트 트리가 아니라 순서 트리(ordered tree)이다. 순서 트리란 각 내부 노드의 자식 노드들 사이에 명시적인 순서가 정의된 트리를 의미한다. 즉, 노드 $v$ 의 자식 노드 집합 $\text{children}(v) = \{c_1, c_2, \ldots, c_k\}$ 에 대하여 다음 순서 관계가 성립한다.

$c_1 \prec c_2 \prec \cdots \prec c_k$

이 순서는 행동 트리의 실행 의미론(execution semantics)에서 핵심적 역할을 담당한다. Tick 신호가 제어 흐름 노드에 도달하면, 해당 노드는 자식 노드를 정의된 순서에 따라 왼쪽에서 오른쪽으로 순차적으로 평가한다. Sequence 노드의 경우 첫 번째 자식부터 평가를 시작하여 실패(Failure)를 반환하는 자식이 나타나면 즉시 평가를 중단하고, Fallback 노드의 경우 성공(Success)을 반환하는 자식이 나타나면 평가를 중단한다. 이러한 자식 노드의 순서가 곧 행동의 우선순위(priority)를 결정하며, 이는 행동 트리가 우선순위 기반 의사 결정(priority-based decision making)을 수행하는 기반이 된다.

5. 트리 자료 구조 기반의 구조적 이점

행동 트리가 트리 자료 구조를 기반으로 설계됨으로써 확보하는 구조적 이점은 다음과 같다.

5.1 모듈성

트리 자료 구조에서 임의의 노드 $v$ 와 그 하위의 모든 후손 노드(descendant node)는 독립적인 서브트리(subtree)를 구성한다. 이 서브트리는 나머지 트리 구조와 인터페이스가 동일하므로 독립적으로 설계, 검증 및 재사용이 가능하다. Colledanchise와 Ögren(2018)은 이러한 서브트리의 독립성이 행동 트리의 모듈성(modularity)을 보장하는 핵심 요인임을 제시하였다.

5.2 계층적 분해

트리의 계층 구조는 복잡한 행동을 상위 수준의 추상적 행동으로부터 하위 수준의 구체적 행동으로 점진적으로 분해(decomposition)하는 데 적합하다. 루트 노드에 가까운 상위 노드는 전략적 수준의 행동을 나타내고, 리프 노드에 가까운 하위 노드는 전술적 또는 실행적 수준의 행동을 나타낸다.

5.3 결정론적 순회

트리 자료 구조는 깊이 우선 탐색(depth-first search, DFS) 등의 잘 정의된 순회 알고리즘을 적용할 수 있다. 행동 트리의 Tick 메커니즘은 전위 순회(pre-order traversal) 방식을 기반으로 하며, 동일한 트리 구조와 동일한 노드 상태가 주어지면 항상 동일한 실행 순서를 보장한다. 이는 행동 트리의 결정론적 실행(deterministic execution)을 가능하게 하는 구조적 기반이다.

5.4 정적 분석 가능성

트리 자료 구조는 순환이 없으므로 정적 분석(static analysis)이 용이하다. 도달 가능성 분석(reachability analysis), 데드 노드 검출(dead node detection), 구조적 일관성 검증(structural consistency verification) 등의 형식적 분석 기법을 적용할 수 있으며, 이를 통해 설계 단계에서 논리적 오류를 사전에 검출하는 것이 가능하다.

6. 트리 자료 구조의 제약과 행동 트리의 확장

트리 자료 구조의 엄격한 정의에 의하면, 각 노드는 정확히 하나의 부모 노드를 가져야 하므로 동일한 노드를 여러 위치에서 공유하는 것이 허용되지 않는다. 그러나 실제 행동 트리 구현에서는 동일한 행동 패턴을 여러 위치에서 재사용해야 하는 요구가 빈번하게 발생한다. 이 문제를 해결하기 위해 서브트리 참조(subtree reference) 메커니즘이 도입되었다. 서브트리 참조는 트리 자료 구조의 단일 부모 제약을 위반하지 않으면서, 논리적으로 동일한 서브트리를 복수의 위치에서 인스턴스화(instantiation)하여 재사용할 수 있도록 한다. 이 메커니즘은 위상적(topological)으로는 방향 비순환 그래프(directed acyclic graph, DAG)의 특성을 일부 차용하지만, 실행 의미론적으로는 여전히 트리 순회 기반의 결정론적 실행을 유지한다.

7. 참고 문헌

Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.
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.

본 절은 Version 1로 작성되었다.