1292.5 루트 노드 (Root Node)의 역할과 정의

1. 루트 노드의 형식적 정의

행동 트리(Behavior Tree)는 방향 비순환 그래프(Directed Acyclic Graph, DAG)의 특수한 형태인 루트 트리(rooted tree)로 구성된다. 루트 노드(Root Node)는 이 트리 구조에서 유일하게 부모 노드(parent node)를 갖지 않는 최상위 노드로 정의된다. 형식적으로, 행동 트리 \mathcal{T} = (V, E)에서 노드 집합 V와 간선 집합 E \subseteq V \times V가 주어질 때, 루트 노드 r \in V는 다음 조건을 만족하는 유일한 노드이다:

\forall v \in V, \quad (v, r) \notin E

즉, 어떠한 노드로부터도 루트 노드를 향하는 간선이 존재하지 않는다. 이 성질에 의해 루트 노드는 트리의 진입점(entry point)으로 기능하며, 모든 다른 노드는 루트 노드로부터의 유일한 경로(unique path)를 통해 도달할 수 있다.

트리 이론에서 루트 노드의 깊이(depth)는 0으로 정의되며, 루트 노드로부터 임의의 노드 v까지의 경로 길이가 해당 노드의 깊이를 결정한다. 이 계층적 구조는 행동 트리의 실행 흐름이 상위 계층에서 하위 계층으로 체계적으로 전파되는 기반을 형성한다.

2. 행동 트리에서 루트 노드의 구조적 위치

행동 트리의 노드는 기능에 따라 제어 흐름 노드(Control Flow Node), 실행 노드(Execution Node), 데코레이터 노드(Decorator Node)로 분류된다. 루트 노드는 이러한 기능적 분류와 독립적으로 존재하는 구조적(structural) 개념이다. 루트 노드는 트리 위상(topology)에서의 위치를 규정하는 것이지, 특정한 행동 논리(behavioral logic)를 수행하는 기능적 노드 유형이 아니다.

그러나 실제 구현에서 루트 노드는 대부분 단일 자식 노드를 갖는 특수한 제어 노드로 실체화된다. 예를 들어, BehaviorTree.CPP 라이브러리에서 루트 노드는 내부적으로 트리의 최상위 제어 흐름 노드를 감싸는 래퍼(wrapper)로 구현되며, Tick 신호의 최초 발신점(originator)으로 동작한다. 이 구현 방식에서 루트 노드는 트리의 논리적 구조와 실행 엔진(execution engine) 사이의 인터페이스 역할을 수행한다.

3. Tick 발신의 기원으로서의 루트 노드

행동 트리의 핵심 실행 메커니즘인 Tick은 루트 노드에서 시작된다. Tick은 트리의 각 노드를 활성화(activate)하여 해당 노드의 실행 로직을 호출하는 제어 신호이다. 루트 노드는 외부 실행 루프(execution loop) 또는 타이머 이벤트에 의해 주기적으로 Tick을 수신하며, 이를 자신의 자식 노드로 전파(propagate)한다.

Tick의 전파는 깊이 우선 탐색(Depth-First Search, DFS) 순서를 따르며, 루트 노드로부터 시작하여 리프 노드(leaf node)까지 상위에서 하위로(top-down) 진행된다. 이 과정에서 각 노드는 자신의 실행 결과를 반환 상태(return status)로 부모 노드에 보고하며, 최종적으로 루트 노드가 전체 트리의 실행 결과를 수집하여 외부 시스템에 전달한다.

루트 노드의 Tick 발신 과정을 수식으로 표현하면, 시간 t에서 루트 노드 r이 Tick을 수신할 때 자식 노드 c에 대해 다음 연산이 수행된다:

\text{status}(r, t) = \text{tick}(c, t)

여기서 \text{tick}(c, t)는 자식 노드 c가 시간 t의 Tick에 대해 반환하는 상태값이다. 루트 노드의 반환 상태는 곧 전체 행동 트리의 실행 상태를 대표한다.

4. 트리 실행 상태의 집약

루트 노드는 전체 행동 트리의 실행 상태를 단일 반환값으로 집약(aggregate)하는 최종 수렴점이다. 행동 트리의 각 노드는 실행 결과로 Success, Failure, Running 중 하나의 상태를 반환하며, 이러한 상태는 부모-자식 관계를 따라 하위에서 상위로(bottom-up) 전파된다. 루트 노드는 이 전파 사슬의 종착점으로서, 자식 노드로부터 수신한 상태를 최종 트리 상태로 확정한다.

이 집약 메커니즘은 행동 트리의 의사결정 과정을 외부 시스템이 단일 인터페이스를 통해 관찰할 수 있게 한다. 로봇 시스템에서 행동 트리의 루트 노드 상태는 다음과 같이 해석된다:

외부 실행 루프는 루트 노드의 반환 상태를 기반으로 트리의 재실행 여부, 대체 트리로의 전환, 또는 시스템 상태 변경 등의 상위 수준 의사결정을 수행한다.

5. 루트 노드의 단일성 보장

행동 트리에서 루트 노드는 반드시 하나만 존재해야 한다. 이는 트리 자료 구조의 정의로부터 직접 도출되는 속성이다. 만약 두 개 이상의 루트 노드가 존재한다면, 이는 연결 트리(connected tree)가 아닌 포레스트(forest) 구조를 형성하게 되어 행동 트리의 기본 공리(axiom)를 위반한다.

루트 노드의 단일성은 다음과 같은 실행 의미론적(semantic) 보장을 제공한다:

• 결정론적 실행 진입: 실행의 시작점이 유일하므로 Tick의 전파 경로가 결정론적으로 확정된다.
• 상태 일관성: 트리 전체의 실행 상태가 단일 루트 노드의 반환값으로 수렴하므로, 상태의 모호성이 제거된다.
• 구조적 무결성: 모든 노드가 루트 노드로부터 도달 가능함이 보장되어 고립 노드(isolated node)의 발생이 방지된다.

6. 루트 노드와 실행 엔진의 인터페이스

루트 노드는 행동 트리의 내부 구조와 외부 실행 환경 사이의 경계(boundary)에 위치한다. 실행 엔진(execution engine)은 루트 노드를 통해서만 트리와 상호작용하며, 이 인터페이스를 통해 다음과 같은 기능이 수행된다:

첫째, **Tick 주입(injection)**이다. 실행 엔진은 설정된 주기(period) 또는 이벤트 기반(event-driven) 방식으로 루트 노드에 Tick을 주입한다. 루트 노드는 이 Tick을 수신하여 트리 내부로 전파하는 관문(gateway) 역할을 수행한다.

둘째, **상태 보고(reporting)**이다. 루트 노드는 Tick 처리 완료 후 트리의 최종 실행 상태를 실행 엔진에 반환한다. 실행 엔진은 이 반환값을 활용하여 후속 처리를 결정한다.

셋째, **생명주기 관리(lifecycle management)**이다. 루트 노드를 통해 전체 트리의 초기화(initialization), 실행(execution), 중단(halt), 정리(cleanup) 등의 생명주기 이벤트가 제어된다. 트리의 중단 요청은 루트 노드에서 시작하여 깊이 우선 순서로 모든 활성 노드에 전파된다.

7. 루트 노드의 구현 패턴

실제 행동 트리 라이브러리에서 루트 노드의 구현은 라이브러리마다 상이하나, 공통적인 설계 패턴이 존재한다.

암시적 루트(implicit root) 패턴에서는 사용자가 명시적으로 루트 노드를 생성하지 않는다. 라이브러리가 트리 생성 시 자동으로 루트 노드를 삽입하며, 사용자가 정의한 최상위 노드를 해당 루트 노드의 자식으로 설정한다. BehaviorTree.CPP는 이 패턴을 채택하고 있으며, XML로 정의된 트리의 <BehaviorTree> 태그가 암시적 루트 노드에 대응한다.

명시적 루트(explicit root) 패턴에서는 사용자가 직접 루트 노드 객체를 생성하고 자식 노드를 연결한다. 이 패턴은 루트 노드의 동작을 사용자 정의(customization)할 수 있는 유연성을 제공하나, 루트 노드의 단일성 제약을 프로그래머가 직접 보장해야 하는 부담이 존재한다.

두 패턴 모두 루트 노드가 단일 자식만을 허용하는 제약을 공유하며, 이 제약은 트리의 실행 진입점이 명확하게 하나의 하위 트리(subtree)로 귀결됨을 보장한다.

8. 참고 문헌

• Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
• Colledanchise, M., & Ögren, P. (2017). “How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees.” IEEE Transactions on Robotics, 33(2), 372–389.
• 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.
• BehaviorTree.CPP Documentation. https://www.behaviortree.dev/