1291.35 행동 트리의 트리 (Tree) 자료 구조 기반

1291.35 행동 트리의 트리 (Tree) 자료 구조 기반

1. 트리 자료 구조의 정의

행동 트리(Behavior Tree, BT)는 그래프 이론(graph theory)에서 정의하는 트리(tree) 자료 구조를 기반으로 설계된 행동 제어 프레임워크이다. 트리란 비순환 연결 그래프(acyclic connected graph)의 한 형태로서, 임의의 두 노드 사이에 정확히 하나의 경로만 존재하는 구조를 가진다. 형식적으로, 트리 T는 노드 집합 V와 간선 집합 E로 구성되는 그래프 T = (V, E)이며, 다음 조건을 만족한다.

|E| = |V| - 1, \quad T \text{는 연결 그래프}

행동 트리는 이러한 트리 구조에 루트(root)를 지정한 유근 트리(rooted tree)이다. 유근 트리에서는 하나의 특정 노드가 루트로 지정되며, 루트로부터 다른 모든 노드까지의 경로가 유일하게 결정된다. 이로 인하여 각 노드에는 부모-자식(parent-child) 관계가 자연스럽게 정의되고, 이 계층적 구조가 행동 트리의 실행 흐름을 결정하는 핵심 원리가 된다.

2. 유근 유향 트리로서의 행동 트리

행동 트리는 단순한 유근 트리를 넘어서 유근 유향 트리(rooted directed tree)의 성질을 갖는다. 행동 트리에서 각 간선은 부모 노드로부터 자식 노드를 향하는 방향성을 가지며, 이 방향이 Tick 신호의 전파 방향과 일치한다. 루트 노드에서 시작된 Tick 신호는 간선의 방향을 따라 자식 노드로 전달되고, 각 자식 노드는 처리 결과를 반환 상태(return status)의 형태로 부모 노드에게 역방향으로 전달한다.

이 유향 구조는 다음과 같이 형식화할 수 있다. 행동 트리 \mathcal{T}는 유향 그래프 \mathcal{T} = (V, A)로 정의된다. 여기서 V는 노드 집합이고 A \subseteq V \times V는 유향 간선(arc)의 집합이다. 루트 노드 r \in V는 진입 간선(incoming arc)이 존재하지 않는 유일한 노드이며, 루트를 제외한 모든 노드 v \in V \setminus \{r\}는 정확히 하나의 진입 간선을 갖는다.

3. 행동 트리 노드의 계층적 분류

트리 자료 구조의 관점에서 행동 트리의 노드는 다음과 같이 분류된다.

3.1 루트 노드

루트 노드(root node)는 트리의 최상위에 위치하며, 부모 노드가 존재하지 않는 유일한 노드이다. 행동 트리의 실행은 항상 루트 노드로부터 개시되며, 외부에서 Tick 신호를 수신하는 진입점 역할을 수행한다. 루트 노드는 일반적으로 하나의 자식 노드만을 가지며, Tick을 해당 자식에게 전달하고 반환 상태를 외부로 전파하는 단순한 역할을 담당한다.

3.2 내부 노드

내부 노드(internal node)는 부모 노드와 하나 이상의 자식 노드를 동시에 갖는 노드이다. 행동 트리에서 내부 노드는 제어 흐름 노드(control flow node)에 해당하며, Sequence, Fallback(Selector), Parallel, Decorator 등의 유형이 이에 속한다. 내부 노드는 자식 노드들의 반환 상태를 조합하여 자신의 반환 상태를 결정하는 역할을 수행한다. 내부 노드의 자식 수(차수, degree)에는 원칙적으로 제한이 없으나, Decorator 노드는 정확히 하나의 자식만을 허용하는 단항(unary) 노드로 정의된다.

3.3 리프 노드

리프 노드(leaf node)는 자식 노드가 존재하지 않는 말단 노드이다. 행동 트리에서 리프 노드는 실행 노드(execution node)에 해당하며, 액션 노드(action node)와 조건 노드(condition node)가 이에 속한다. 리프 노드는 행동 트리가 외부 환경과 상호작용하는 접점으로서, 실제 로봇의 행동 실행이나 환경 상태 확인과 같은 구체적 기능을 수행한다.

4. 트리 구조의 핵심 속성과 행동 트리에서의 활용

4.1 계층적 분해

트리 자료 구조의 가장 핵심적인 특성은 계층적 분해(hierarchical decomposition)를 자연스럽게 지원한다는 것이다. 복잡한 행동을 최상위 수준에서 추상적으로 정의하고, 하위 수준으로 내려가면서 점진적으로 구체화하는 방식이 트리의 부모-자식 관계를 통하여 직관적으로 표현된다. 예를 들어, “물건을 집어서 운반하라“라는 상위 임무는 “물건을 탐색하라”, “물건을 파지하라”, “목적지로 이동하라“라는 하위 행동으로 분해되며, 각 하위 행동은 다시 더 세부적인 행동으로 재귀적 분해가 가능하다.

4.2 유일 경로 보장

트리 구조에서는 루트 노드로부터 임의의 노드까지 정확히 하나의 경로만 존재한다. 이 성질은 행동 트리의 실행 흐름에서 중요한 의미를 갖는다. Tick 신호가 특정 노드에 도달하는 경로가 유일하므로, 해당 노드가 실행되는 맥락(context)이 명확하게 결정된다. 이는 순환(cycle)이 존재하는 일반 그래프 기반 구조에서 발생할 수 있는 무한 루프나 실행 경로의 모호성 문제를 원천적으로 방지한다.

4.3 서브트리의 독립성

트리 자료 구조에서 임의의 내부 노드를 루트로 하는 서브트리(subtree)는 그 자체로 완전한 트리를 구성한다. 행동 트리에서는 이 성질을 활용하여, 서브트리 단위의 모듈화(modularization)를 실현한다. 특정 서브트리를 독립적으로 설계, 테스트, 재사용할 수 있으며, 기존 트리에 서브트리를 삽입하거나 제거하여도 다른 서브트리에 미치는 영향이 국소적이다. 이러한 특성이 행동 트리의 모듈성과 재사용성의 구조적 기반이 된다.

4.4 깊이와 너비

트리의 깊이(depth)는 루트 노드로부터 특정 노드까지의 경로 길이를 나타내며, 트리의 높이(height)는 모든 리프 노드의 깊이 중 최대값이다. 행동 트리에서 트리의 깊이는 행동 분해의 추상화 수준(abstraction level)에 대응하며, 너비(breadth)는 동일 수준에서의 행동 선택지 또는 순차적 행동의 수에 대응한다. 트리의 깊이가 증가하면 Tick 전파에 소요되는 시간이 증가하므로, 실시간 시스템에서는 트리의 깊이를 적절히 제한하는 설계가 요구된다.

5. 트리 구조와 다른 자료 구조의 비교

5.1 그래프 구조와의 차이

유한 상태 머신(Finite State Machine, FSM)은 일반 유향 그래프(directed graph)로 표현된다. 상태 간 전이가 자유롭게 정의되므로 순환 경로가 존재할 수 있으며, 이로 인하여 상태 폭발 문제가 발생한다. 반면 행동 트리는 비순환 트리 구조를 사용하므로, 순환 경로가 원천적으로 차단되며, 실행 흐름이 항상 루트에서 리프 방향으로의 하향식(top-down) 탐색으로 진행된다. 이는 행동 트리의 예측 가능성(predictability)을 보장하는 구조적 특성이다.

5.2 이진 트리와의 관계

행동 트리는 이진 트리(binary tree)가 아닌 일반 트리(general tree) 또는 n-진 트리(n-ary tree)이다. 제어 흐름 노드는 두 개 이상의 자식을 임의로 가질 수 있으므로, 순차적 실행(Sequence)이나 대체 실행(Fallback) 시 다수의 행동을 하나의 부모 아래에 나열하는 것이 가능하다. 다만, Decorator 노드는 단항 노드로서 정확히 하나의 자식만을 가지므로 이진 트리의 특수한 경우에 해당한다.

6. 트리 순회와 Tick 전파 메커니즘

행동 트리의 Tick 전파는 트리 순회(tree traversal) 알고리즘과 밀접한 관련이 있다. 표준 행동 트리에서 Tick 신호는 깊이 우선 탐색(Depth-First Search, DFS)의 방식으로 전파된다. 구체적으로는, 루트 노드로부터 시작하여 왼쪽 자식부터 우선적으로 방문하는 전위 순회(pre-order traversal)의 변형된 형태를 따른다.

Sequence 노드의 경우, 첫 번째 자식부터 순차적으로 Tick을 전달하되, 특정 자식이 Failure를 반환하면 나머지 자식의 순회를 중단한다. Fallback 노드의 경우, 첫 번째 자식부터 순차적으로 Tick을 전달하되, 특정 자식이 Success를 반환하면 나머지 자식의 순회를 중단한다. 이러한 단축 평가(short-circuit evaluation)는 불필요한 노드 방문을 방지하여 실행 효율을 향상시킨다.

이 순회 메커니즘의 시간 복잡도는 최악의 경우 O(n)이다. 여기서 n은 트리 내 전체 노드의 수이다. 그러나 단축 평가에 의하여 실제 방문되는 노드의 수는 일반적으로 n보다 훨씬 적으며, 이는 행동 트리가 실시간 로봇 시스템에서 효율적으로 운용될 수 있는 근거가 된다.

7. 트리 자료 구조가 행동 트리에 부여하는 설계적 이점

트리 자료 구조의 채택은 행동 트리에 다음과 같은 설계적 이점을 부여한다.

첫째, 결정론적 실행 순서(deterministic execution order)가 보장된다. 트리의 구조와 자식 노드의 배치 순서에 의하여 Tick 전파 경로가 유일하게 결정되므로, 동일한 환경 조건하에서 동일한 행동이 반복 재현된다.

둘째, 구조적 명료성(structural clarity)이 확보된다. 트리 구조는 인간이 직관적으로 이해할 수 있는 표현 형식이며, 이를 시각적으로 도식화하였을 때 행동의 계층적 관계와 실행 흐름이 명확하게 드러난다. 이는 대규모 로봇 시스템의 행동 설계에서 팀 구성원 간의 의사소통 효율을 향상시킨다.

셋째, 재귀적 구성(recursive composition)이 자연스럽게 지원된다. 서브트리가 그 자체로 완전한 행동 트리를 구성하므로, 복잡한 행동을 소규모 서브트리의 재귀적 합성을 통하여 구축할 수 있다. 이는 분할 정복(divide and conquer) 원리에 기반한 소프트웨어 공학적 설계 방법론과 부합한다.

넷째, 효율적 탐색과 갱신이 가능하다. 트리 구조에서 특정 노드의 삽입, 삭제, 탐색 연산은 트리의 높이에 비례하는 시간 복잡도를 가지며, 이는 행동 트리의 동적 재구성(dynamic reconfiguration)을 효율적으로 수행할 수 있는 기반이 된다.

8. 참고 문헌

  • 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).
  • Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.
  • 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.

버전: 2026-03-31