1292.8 제어 흐름 노드의 자식 노드 관리

1. 서론

행동 트리(Behavior Tree)에서 제어 흐름 노드(Control Flow Node)는 하나 이상의 자식 노드(Child Node)를 보유하며, 이들의 실행 순서와 결과 해석을 결정하는 내부 노드(Internal Node)이다. 제어 흐름 노드의 핵심적 역할은 자식 노드 집합의 구성, 순서 유지, 상태 전파, 그리고 생명주기 관리를 체계적으로 수행하는 데 있다. 본 절에서는 제어 흐름 노드가 자식 노드를 관리하는 구조적·의미론적 원리를 형식적으로 기술한다.

2. 자식 노드의 정의와 구성

제어 흐름 노드 C는 순서가 보존된 자식 노드 목록 \langle c_1, c_2, \ldots, c_n \rangle을 보유한다. 여기서 n \geq 1이며, 각 c_i는 제어 흐름 노드, 실행 노드(Execution Node), 또는 데코레이터 노드(Decorator Node) 중 하나이다. 자식 노드 목록은 정적 정의 시점에 확정되며, 트리의 구조적 정의가 완료된 이후에는 실행 중 동적 변경이 허용되지 않는 것이 표준 행동 트리 모델의 원칙이다.

자식 노드의 순서는 행동 트리의 실행 의미론(Execution Semantics)에 직접적인 영향을 미친다. 왼쪽에서 오른쪽으로의 순서(Left-to-Right Order)는 자식 노드의 우선순위를 암시적으로 정의하며, 이 순서는 Sequence 노드와 Fallback 노드의 동작 원리에서 핵심적인 역할을 수행한다.

2.1 자식 노드 목록의 형식적 표현

제어 흐름 노드 C의 자식 노드 관계를 형식적으로 정의하면 다음과 같다:

\text{children}(C) = \langle c_1, c_2, \ldots, c_n \rangle, \quad n \geq 1

이 순서 목록에서 c_i의 인덱스 i는 해당 자식 노드의 실행 우선순위를 결정한다. 인덱스가 작을수록 먼저 Tick을 수신하며, 이는 깊이 우선 탐색(Depth-First Search, DFS) 기반 순회에서 왼쪽 자식이 우선 방문되는 원리와 일치한다.

3. 자식 노드의 순서 보장 메커니즘

행동 트리에서 자식 노드의 실행 순서는 결정론적(Deterministic)이어야 한다. 동일한 입력 조건과 상태에서 동일한 실행 순서가 반복적으로 보장되지 않으면, 행동 트리의 예측 가능성과 디버깅 용이성이라는 설계 목표가 훼손된다.

3.1 정적 순서 정의

자식 노드의 순서는 트리 정의 시점에 확정된다. XML 기반 행동 트리 정의에서는 자식 요소(Child Element)의 기술 순서가 곧 실행 순서를 나타낸다. 예를 들어, 다음과 같은 XML 정의에서:

<Sequence>
    <Action ID="MoveForward"/>
    <Action ID="CheckObstacle"/>
    <Action ID="Stop"/>
</Sequence>

MoveForward, CheckObstacle, Stop의 순서가 실행 시 엄격히 보장된다.

3.2 인덱스 기반 접근

내부 구현에서 자식 노드 목록은 일반적으로 순서가 보존되는 선형 자료 구조(예: 배열, 벡터)로 유지된다. 각 자식 노드는 0 또는 1 기반의 인덱스를 통해 접근되며, 이 인덱스는 Tick 전파 시 순회 순서를 결정하는 데 직접 활용된다.

4. 자식 노드에 대한 Tick 전파

제어 흐름 노드가 상위 노드 또는 루트 노드로부터 Tick을 수신하면, 자체적인 제어 정책(Control Policy)에 따라 자식 노드에 Tick을 전파한다. 이 전파 과정은 제어 흐름 노드의 유형에 따라 상이하다.

4.1 Sequence 노드의 Tick 전파

Sequence 노드는 자식 노드 c_1부터 순차적으로 Tick을 전파한다. c_i가 Success를 반환하면 c_{i+1}에 Tick을 전파하고, Failure를 반환하면 즉시 전파를 중단하고 Failure를 상위 노드에 반환한다. 모든 자식 노드가 Success를 반환한 경우에만 Sequence 노드 자체가 Success를 반환한다.

\text{Sequence}(c_1, \ldots, c_n) = \begin{cases} \text{Failure} & \text{if } \exists\, i : \text{status}(c_i) = \text{Failure} \\ \text{Running} & \text{if } \exists\, i : \text{status}(c_i) = \text{Running} \\ \text{Success} & \text{if } \forall\, i : \text{status}(c_i) = \text{Success} \end{cases}

4.2 Fallback 노드의 Tick 전파

Fallback 노드(또는 Selector 노드)는 c_1부터 순차적으로 Tick을 전파하되, c_i가 Failure를 반환하면 c_{i+1}에 Tick을 전파한다. c_i가 Success를 반환하면 즉시 전파를 중단하고 Success를 상위 노드에 반환한다.

\text{Fallback}(c_1, \ldots, c_n) = \begin{cases} \text{Success} & \text{if } \exists\, i : \text{status}(c_i) = \text{Success} \\ \text{Running} & \text{if } \exists\, i : \text{status}(c_i) = \text{Running} \\ \text{Failure} & \text{if } \forall\, i : \text{status}(c_i) = \text{Failure} \end{cases}

4.3 Parallel 노드의 Tick 전파

Parallel 노드는 모든 자식 노드에 동시적으로(또는 의사 동시적으로) Tick을 전파한다. 모든 자식 노드가 하나의 Tick 주기 내에서 실행되며, 결과의 해석은 성공 임계값(Success Threshold) 또는 실패 임계값(Failure Threshold) 정책에 의해 결정된다.

5. 자식 노드의 상태 추적

제어 흐름 노드는 각 자식 노드의 현재 반환 상태(Return Status)를 내부적으로 추적하여야 한다. 이 상태 추적은 다음 Tick 주기에서 어느 자식 노드부터 실행을 재개할지를 결정하는 데 필수적이다.

5.1 현재 자식 인덱스의 유지

Sequence 노드와 Fallback 노드에서 자식 노드가 Running 상태를 반환한 경우, 해당 자식 노드의 인덱스를 내부적으로 저장하여야 한다. 다음 Tick이 도달하면, 저장된 인덱스의 자식 노드부터 실행을 재개함으로써 이미 완료된 자식 노드의 불필요한 재실행을 방지한다. 이를 형식적으로 표현하면:

\text{resume\_index}(C) = \begin{cases} i & \text{if } \text{status}(c_i) = \text{Running} \\ 1 & \text{otherwise (초기 상태)} \end{cases}

단, Reactive 계열의 제어 흐름 노드(ReactiveSequence, ReactiveFallback)에서는 이 원칙이 적용되지 않으며, 매 Tick마다 첫 번째 자식 노드부터 재평가가 수행된다.

5.2 상태 벡터의 관리

Parallel 노드의 경우, 모든 자식 노드의 상태를 동시에 추적하여야 하므로 상태 벡터(Status Vector)를 유지한다:

\mathbf{s} = \langle s_1, s_2, \ldots, s_n \rangle, \quad s_i \in \{\text{Success}, \text{Failure}, \text{Running}, \text{Idle}\}

이 상태 벡터를 기반으로 성공 또는 실패 임계값에 도달하였는지를 판정한다.

6. 자식 노드의 중단(Halt) 관리

제어 흐름 노드가 자식 노드의 실행을 중단하여야 하는 상황은 다음과 같이 발생한다:

1. 상위 노드로부터의 Halt 요청: 제어 흐름 노드 자체가 Halt 요청을 수신하면, 현재 Running 상태에 있는 모든 자식 노드에 Halt를 전파하여야 한다.
2. 조기 종료(Short-Circuit) 조건 충족: Sequence 노드에서 특정 자식이 Failure를 반환하거나, Fallback 노드에서 특정 자식이 Success를 반환한 경우, 이후의 자식 노드는 Tick을 수신하지 않으며, 이전에 Running 상태였던 자식 노드에는 Halt가 전파된다.
3. Reactive 노드의 재평가: ReactiveSequence 또는 ReactiveFallback 노드에서 선행 조건 노드의 재평가 결과 변경 시, 기존에 Running 상태이던 후속 자식 노드에 Halt를 전파한다.

6.1 Halt 전파의 형식적 규칙

제어 흐름 노드 C가 Halt를 수신하였을 때, 자식 노드에 대한 Halt 전파 규칙은 다음과 같다:

\forall\, c_i \in \text{children}(C) : \text{status}(c_i) = \text{Running} \implies \text{halt}(c_i)

즉, 현재 Running 상태에 있는 모든 자식 노드에 대해 Halt를 호출하여, 해당 자식 노드가 자원 해제(Resource Release) 및 상태 초기화(State Reset)를 수행할 수 있도록 보장한다.

7. 자식 노드의 추가 및 제거 정책

표준 행동 트리 모델에서는 트리 구조가 실행 전에 정적으로 정의되며, 실행 중에 자식 노드를 동적으로 추가하거나 제거하는 것은 허용되지 않는다. 이는 행동 트리의 결정론적 실행 보장과 구조적 일관성 유지를 위한 핵심 원칙이다.

7.1 정적 구조의 원칙

행동 트리의 노드 구성은 트리 정의 파일(예: XML) 또는 프로그래밍 인터페이스를 통해 실행 전에 완전히 확정된다. 실행 중에 자식 노드를 동적으로 삽입하거나 삭제하면, Tick 전파의 순서와 상태 추적의 일관성이 파괴될 수 있다.

7.2 동적 행동 트리에서의 예외

일부 고급 행동 트리 프레임워크에서는 서브트리(Subtree) 교체 또는 동적 트리 전환(Dynamic Tree Switching)을 지원한다. 이 경우에도 자식 노드의 직접적인 추가·제거가 아닌, 전체 서브트리 단위의 교체가 이루어지며, 교체 시 기존 서브트리의 모든 Running 상태 노드에 대한 Halt 처리가 선행되어야 한다.

8. 자식 노드 관리와 메모리 모델

제어 흐름 노드는 자식 노드에 대한 참조(Reference) 또는 포인터(Pointer)를 내부적으로 유지한다. 자식 노드의 소유권(Ownership)은 일반적으로 부모 노드인 제어 흐름 노드에 귀속되며, 트리의 소멸(Destruction) 시 부모 노드가 자식 노드의 메모리 해제를 재귀적으로 수행한다.

8.1 소유권 모델

행동 트리 라이브러리의 구현에서 자식 노드의 소유권 모델은 크게 두 가지로 구분된다:

9. 자식 노드 관리의 설계 원칙 요약

제어 흐름 노드의 자식 노드 관리는 다음의 설계 원칙을 준수하여야 한다:

1. 순서 보존(Order Preservation): 자식 노드의 실행 순서는 정의 시점의 순서와 항상 일치하여야 한다.
2. 결정론적 전파(Deterministic Propagation): 동일한 조건에서 Tick과 Halt의 전파 순서가 항상 동일하여야 한다.
3. 상태 격리(State Isolation): 각 자식 노드의 반환 상태는 독립적으로 추적되며, 타 자식 노드의 내부 상태에 직접 접근하지 않는다.
4. 자원 안전성(Resource Safety): Halt 전파 시 모든 Running 상태의 자식 노드에 대해 자원 정리가 보장되어야 한다.
5. 구조적 불변(Structural Invariant): 실행 중에 자식 노드 목록의 구조적 변경이 발생하지 않아야 한다.

이러한 원칙들은 행동 트리가 복잡한 로봇 임무 수행 시에도 예측 가능하고 안정적인 행동 제어를 보장하는 근거가 된다.

참고 문헌

• Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC 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.
• Ionescu, D., & Piskur, P. (2021). “Formal Analysis of Behavior Trees for Autonomous Systems.” Robotics and Autonomous Systems, 145, 103869.
• BehaviorTree.CPP Documentation. https://www.behaviortree.dev/

v1.0