1292.6 루트 노드의 단일 자식 제약

1292.6 루트 노드의 단일 자식 제약

1. 단일 자식 제약의 형식적 정의

행동 트리(Behavior Tree)의 루트 노드(Root Node)는 정확히 하나의 자식 노드만을 가져야 한다는 구조적 제약(structural constraint)을 따른다. 이를 형식적으로 정의하면, 행동 트리 \mathcal{T} = (V, E)에서 루트 노드 r \in V의 자식 집합 \text{children}(r)에 대해 다음 조건이 성립한다:

|\text{children}(r)| = 1

즉, 루트 노드에서 출발하는 간선의 수는 반드시 1이다. 이 제약은 트리 자료 구조의 일반적 정의에서는 요구되지 않는 행동 트리 고유의 설계 규약이다. 일반적인 루트 트리에서는 루트 노드가 임의의 수의 자식을 가질 수 있으나, 행동 트리에서는 루트 노드의 역할이 Tick 전파의 진입점으로 한정되므로 단일 자식 제약이 부과된다.

2. 단일 자식 제약의 설계 근거

루트 노드에 단일 자식 제약이 존재하는 이유는 행동 트리의 실행 의미론(execution semantics)과 밀접하게 관련된다.

2.1 실행 진입점의 명확성

루트 노드가 복수의 자식을 갖는다면, Tick이 루트 노드에 도달했을 때 자식 노드들을 어떤 방식으로 실행할 것인지에 대한 제어 정책(control policy)이 필요하다. 이 경우 루트 노드 자체가 Sequence, Fallback, Parallel 등의 제어 흐름 논리를 내재해야 하며, 이는 루트 노드의 역할과 제어 흐름 노드의 역할이 혼재되는 결과를 초래한다.

단일 자식 제약은 이러한 역할의 혼재를 방지한다. 루트 노드는 오직 Tick의 수신과 전달만을 담당하고, 자식 노드의 실행 제어는 해당 자식 노드(일반적으로 제어 흐름 노드)에 위임된다. 이로써 관심의 분리(separation of concerns) 원칙이 유지된다.

2.2 반환 상태의 무모호성

루트 노드가 복수의 자식을 가질 경우, 각 자식이 반환하는 상태를 어떻게 결합하여 트리 전체의 상태를 결정할 것인지에 대한 집약 규칙(aggregation rule)이 필요하다. 이 집약 규칙은 본질적으로 제어 흐름 노드의 동작과 동일하므로, 루트 노드가 불필요하게 제어 흐름 노드의 기능을 중복 수행하게 된다.

단일 자식 제약 하에서 루트 노드의 반환 상태는 유일한 자식 노드의 반환 상태와 동일하다:

\text{status}(r) = \text{status}(c), \quad \text{where} \; \text{children}(r) = \{c\}

이 항등 관계(identity relation)는 루트 노드의 동작을 완전히 투명(transparent)하게 만들며, 트리 실행 상태의 해석에 어떠한 모호성도 발생하지 않게 한다.

2.3 구조적 정규화

단일 자식 제약은 행동 트리의 구조를 정규 형식(normal form)으로 유지하는 역할을 한다. 루트 노드 바로 아래에 배치되는 단일 자식 노드는 전체 트리의 최상위 제어 논리를 명시적으로 표현한다. 예를 들어, 최상위 자식이 Sequence 노드이면 트리 전체가 순차적 임무 수행 구조임을 즉시 파악할 수 있고, Fallback 노드이면 대안적 행동 선택 구조임을 명확히 인지할 수 있다.

이러한 정규화는 트리의 가독성(readability)과 분석 용이성(analyzability)을 향상시킨다. 복수의 자식이 허용되면 루트 노드의 제어 정책이 암시적으로 존재하게 되어 트리의 의도를 파악하기 위해 추가적인 분석이 요구된다.

3. 제어 흐름 위임 구조

단일 자식 제약에 의해 루트 노드와 그 자식 노드 사이에는 위임(delegation) 관계가 형성된다. 루트 노드는 Tick을 수신하면 이를 자식 노드에 무조건 전달하며, 자식 노드로부터 반환된 상태를 그대로 외부에 보고한다. 이 구조를 도식적으로 표현하면 다음과 같다:

[실행 엔진] → Tick → [루트 노드] → Tick → [자식 노드 (제어 흐름 노드)]
                        ↑                          ↓
                     status ← ─ ─ ─ ─ ─ ─ ─ ─  status

자식 노드는 대부분 Sequence, Fallback, Parallel 등의 제어 흐름 노드이며, 이 노드가 복수의 하위 자식 노드를 관리하고 실행 순서와 상태 결합 논리를 결정한다. 따라서 복수 자식의 실행 제어는 루트 노드가 아닌 그 아래의 제어 흐름 노드의 책임으로 명확히 귀속된다.

이러한 위임 구조는 행동 트리의 모듈성(modularity)을 강화한다. 트리의 최상위 제어 전략을 변경하고자 할 때 루트 노드를 수정할 필요 없이 자식 노드만 교체하면 되므로, 트리의 재구성(reconfiguration)이 용이하다.

4. 단일 자식 제약의 수학적 귀결

단일 자식 제약은 행동 트리의 수학적 성질에 다음과 같은 귀결을 가져온다.

첫째, 루트 노드의 팬아웃(fan-out)이 1로 고정되므로 루트 노드에서의 분기(branching)가 발생하지 않는다. 이는 트리의 최상위 계층에서의 실행 경로가 유일함을 보장한다.

둘째, 루트 노드의 상태 전이 함수(state transition function)가 항등 함수(identity function)로 환원된다. 루트 노드가 수행하는 연산은 자식의 상태를 그대로 전달하는 것이므로, 형식적으로 루트 노드는 상태 변환 없는 투과 노드(pass-through node)로 간주할 수 있다.

셋째, 트리의 높이(height) 관점에서 루트 노드와 자식 노드 사이의 간선은 논리적으로 의미 있는 제어 분기를 형성하지 않으므로, 실질적인 의사결정 깊이(effective decision depth)는 루트 노드의 자식 노드부터 계산된다.

5. 구현에서의 단일 자식 제약 보장

실제 행동 트리 라이브러리에서 단일 자식 제약은 다양한 기법으로 보장된다.

생성 시점 검증(construction-time validation) 방식에서는 트리 생성 과정에서 루트 노드에 두 번째 자식을 추가하려는 시도를 탐지하여 오류를 발생시킨다. BehaviorTree.CPP에서는 XML 파싱 시 <BehaviorTree> 태그 하위에 복수의 최상위 노드가 존재할 경우 파싱 오류를 발생시켜 단일 자식 제약을 강제한다.

타입 시스템(type system) 기반 방식에서는 루트 노드 클래스의 인터페이스가 단일 자식만을 수용하도록 설계된다. 자식 노드를 저장하는 멤버 변수를 컬렉션이 아닌 단일 포인터 또는 참조로 정의함으로써 컴파일 시점에 제약을 보장한다.

암시적 래핑(implicit wrapping) 방식에서는 사용자가 복수의 최상위 노드를 정의하더라도 라이브러리가 자동으로 이들을 하나의 제어 흐름 노드(예: Sequence)로 래핑하여 루트 노드의 단일 자식 제약을 충족시킨다. 이 방식은 사용 편의성을 제공하나, 암시적으로 삽입된 제어 노드의 동작을 사용자가 인지하지 못할 수 있으므로 명시적 방식에 비해 투명성이 낮다.

6. 단일 자식 제약과 서브트리의 관계

단일 자식 제약은 서브트리(subtree) 설계에서도 동일하게 적용된다. 서브트리는 독립적으로 정의된 행동 트리를 다른 트리 내에 삽입하여 재사용하는 구조적 패턴이다. 각 서브트리는 자체적인 루트 노드를 가지며, 이 루트 노드 역시 단일 자식 제약을 따른다.

서브트리의 루트 노드와 주 트리(main tree)의 루트 노드가 동일한 단일 자식 제약을 공유함으로써, 트리의 합성(composition)과 분해(decomposition)가 일관된 구조적 규칙 하에서 수행된다. 이는 대규모 행동 트리의 모듈화 설계에서 구조적 무결성을 유지하는 핵심 기반이 된다.

7. 참고 문헌

  • 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/