1293.6 Tick의 전파 방향과 순서

1293.6 Tick의 전파 방향과 순서

1. 전파의 기본 원칙

행동 트리에서 tick의 전파(propagation)는 두 가지 기본 원칙을 따른다. 첫째, tick은 루트 노드에서 단말 노드(leaf node) 방향으로 하향 전파(top-down propagation)된다. 둘째, 동일 계층의 형제 노드(sibling node) 간에는 왼쪽에서 오른쪽(left-to-right) 순서로 전파된다. 이 두 원칙의 조합은 깊이 우선 탐색(depth-first search)의 전위 순회(pre-order traversal)와 동일한 노드 방문 순서를 형성한다 (Colledanchise & Ögren, 2018).

2. 하향 전파 (Top-Down Propagation)

tick의 전파 방향은 항상 부모에서 자식으로의 하향이다. 자식 노드가 부모 노드에 tick을 전파하는 상향 전파(bottom-up propagation)는 발생하지 않는다. 이 단방향 전파는 행동 트리의 계층적 제어 흐름(hierarchical control flow)을 구현하는 핵심 메커니즘이다.

[루트 노드]        tick 수신 (외부로부터)
    │
    ▼ tick 하향 전파
[제어 노드 A]
    │
    ├──▼ tick 하향 전파
    │  [자식 1]
    │
    └──▼ tick 하향 전파 (조건부)
       [자식 2]

하향 전파에서 부모 노드는 자식에게 tick을 전달할지 여부를 자신의 제어 규칙에 따라 결정한다. 즉, 부모 노드는 tick의 게이트키퍼(gatekeeper) 역할을 수행하며, 이를 통해 불필요한 노드의 실행을 방지하고 계산 자원을 절약한다.

3. 반환 상태의 상향 전달

tick의 전파 방향이 하향인 반면, 노드의 반환 상태(return status)는 자식에서 부모로 상향 전달(bottom-up return)된다. 자식 노드는 tick을 수신하여 자신의 로직을 실행한 후, 결과 상태(\text{Success}, \text{Failure}, \text{Running})를 부모 노드에 반환한다. 부모 노드는 자식의 반환 상태를 종합하여 자신의 반환 상태를 결정하고, 이를 다시 자신의 부모에게 반환한다.

tick 전파 방향:    루트 → 자식 (하향)
상태 반환 방향:    자식 → 루트 (상향)

이 하향 전파와 상향 반환의 이중 흐름이 행동 트리의 실행 주기를 구성한다. tick의 하향 전파가 트리의 “질문“이라면, 반환 상태의 상향 전달은 트리의 “응답“이다.

4. 왼쪽에서 오른쪽 순서 (Left-to-Right Order)

동일 부모의 자식 노드들 사이에서 tick은 왼쪽(첫 번째 자식)에서 오른쪽(마지막 자식) 순서로 전파된다. 이 순서는 행동 트리의 XML 또는 코드 정의에서 자식 노드가 선언된 순서와 일치한다.

[Sequence]
    ├→ [Child_1]   ← 첫 번째로 tick 수신
    ├→ [Child_2]   ← 두 번째로 tick 수신 (조건부)
    └→ [Child_3]   ← 세 번째로 tick 수신 (조건부)

왼쪽에서 오른쪽 순서는 행동 트리에서 우선순위(priority)를 암묵적으로 표현한다. 왼쪽에 배치된 자식은 오른쪽에 배치된 자식보다 먼저 평가되므로, 더 높은 우선순위를 가진 행동이나 조건을 왼쪽에 배치하는 것이 행동 트리 설계의 일반적인 관행이다 (Colledanchise & Ögren, 2018).

5. 깊이 우선 순회의 형성

하향 전파와 왼쪽에서 오른쪽 순서의 조합은 깊이 우선 전위 순회(depth-first pre-order traversal)를 형성한다. 구체적인 방문 순서를 예시로 나타내면 다음과 같다.

        [Root: Sequence]           방문 순서: 1
           /         \
    [Fallback]      [Action_C]     방문 순서: 2, 7
      /     \
[Cond_A] [Action_B]               방문 순서: 3, 4 (또는 5, 6)

위 트리에서 tick의 전파 순서는 다음과 같다.

  1. Root(Sequence)가 tick을 수신한다.
  2. Root는 첫 번째 자식인 Fallback에 tick을 전파한다.
  3. Fallback은 첫 번째 자식인 Cond_A에 tick을 전파한다.
  4. Cond_A가 상태를 반환한다.
  5. Fallback은 Cond_A의 반환 상태에 따라 Action_B에 tick을 전파할지 결정한다.
  6. Fallback이 최종 상태를 Root에 반환한다.
  7. Root는 Fallback의 반환 상태에 따라 Action_C에 tick을 전파할지 결정한다.
  8. Root가 최종 상태를 반환한다.

이 순서는 재귀적으로 정의되며, 각 비단말 노드는 자신의 자식에 대해 동일한 전파 규칙을 적용한다.

6. 조건부 전파 (Conditional Propagation)

tick의 전파는 무조건적(unconditional)이 아니라 조건부(conditional)이다. 부모 노드의 유형에 따라 자식에게 tick을 전파할지 여부가 결정된다.

부모 노드 유형조건부 전파 규칙
Sequence자식이 Failure를 반환하면 후속 자식에 tick을 전파하지 않음
Fallback자식이 Success를 반환하면 후속 자식에 tick을 전파하지 않음
Parallel모든 자식에 tick을 전파함 (무조건적)
Decorator단일 자식에 tick을 전파함

조건부 전파는 행동 트리의 조기 종료(short-circuit) 메커니즘을 구현한다. Sequence 노드에서 자식이 실패하면 나머지 자식의 평가가 불필요하므로 tick을 전파하지 않으며, Fallback 노드에서 자식이 성공하면 나머지 대안의 시도가 불필요하므로 tick을 전파하지 않는다. 이 조건부 전파는 불필요한 계산을 방지하여 tick의 실행 효율성을 높인다.

7. 전파 순서의 결정론성

tick의 전파 순서는 트리의 구조에 의해 완전히 결정된다. 동일한 트리 구조와 동일한 노드 상태가 주어지면, tick은 항상 동일한 순서로 동일한 노드를 방문한다. 이 결정론성(determinism)은 다음과 같은 실질적 이점을 제공한다.

  1. 재현성(Reproducibility): 동일 조건에서 동일한 실행 결과가 보장되므로, 문제 상황의 재현과 디버깅이 가능하다.
  2. 예측 가능성(Predictability): 트리 구조를 분석함으로써 실행 경로를 사전에 예측할 수 있다.
  3. 형식 검증(Formal Verification): 결정론적 실행은 모델 검사(model checking) 등의 형식적 분석 기법 적용의 전제 조건이다 (Biggar et al., 2020).

8. 반응형 노드에서의 전파 순서 변형

반응형 제어 노드(ReactiveSequence, ReactiveFallback)에서는 매 tick마다 첫 번째 자식부터 다시 순회를 시작한다. 이전 tick에서 중간 자식이 Running을 반환했더라도, 반응형 노드는 다음 tick에서 첫 번째 자식부터 tick을 전파한다. 이는 비반응형(non-reactive) 제어 노드가 Running을 반환한 자식부터 재개하는 것과 대비된다.

ReactiveSequence:
  tick k:   Child_1 → Success, Child_2 → Running
  tick k+1: Child_1 → Success, Child_2 → ...   (Child_1부터 재시작)

Sequence (with memory):
  tick k:   Child_1 → Success, Child_2 → Running
  tick k+1: Child_2 → ...                       (Child_2부터 재개)

반응형 노드에서의 이 전파 규칙은 조건의 지속적 재평가를 보장하며, 이는 동적 환경에서 조건 변화에 즉각 반응하기 위한 핵심 메커니즘이다.

참고 문헌

  • Biggar, O., Zamani, M., & Shames, I. (2020). A Framework for Formal Verification of Behavior Trees with Linear Temporal Logic. IEEE Robotics and Automation Letters, 5(2), 2341–2348.
  • Colledanchise, M. & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
  • Faconti, D. (2024). BehaviorTree.CPP Documentation. https://www.behaviortree.dev/