1292.24 Tick의 전파 방향 (루트에서 리프)

1292.24 Tick의 전파 방향 (루트에서 리프)

1. 하향 전파의 원리

행동 트리(Behavior Tree)에서 tick의 전파는 항상 루트 노드(Root Node)에서 시작하여 리프 노드(Leaf Node) 방향으로 진행된다. 이 하향 전파(top-down propagation) 원칙은 행동 트리의 실행 의미론(execution semantics)에서 가장 기본적인 규칙 중 하나이다. 리프 노드나 중간 노드가 자발적으로 실행을 개시하는 것은 허용되지 않으며, 모든 노드의 실행은 반드시 상위 노드로부터 전달된 tick에 의해서만 유발된다 (Colledanchise & Ogren, Behavior Trees in Robotics and AI, 2018).

이 원칙은 행동 트리의 실행 제어가 트리의 상위 계층에 집중됨을 의미한다. 상위의 제어 흐름 노드(Control Flow Node)가 하위 노드의 실행 여부와 순서를 결정하며, 하위 노드는 상위 노드의 결정에 종속적이다.

2. 하향 전파의 구체적 과정

2.1 루트 노드에서의 시작

Tick의 전파는 행동 트리의 실행 엔진(execution engine)이 루트 노드에 tick을 전달하는 것으로 시작된다. 루트 노드는 자신의 유일한 자식 노드에게 tick을 전달하고, 자식의 반환 상태를 수신하여 이를 실행 엔진에 보고한다.

루트 노드는 tick의 전파를 중개하는 역할만 수행하며, 자체적인 제어 논리나 상태 변환을 수행하지 않는다. 자식이 반환하는 상태가 곧 루트 노드의 반환 상태가 된다.

2.2 제어 흐름 노드에서의 선택적 전파

제어 흐름 노드는 tick을 수신하면 자신의 제어 정책(control policy)에 따라 자식 노드에게 선택적으로 tick을 전달한다. 모든 자식에게 tick이 전달되는 것이 아니라, 제어 정책에 의해 결정된 특정 자식에게만 tick이 전달된다.

Sequence 노드의 tick 전파: Sequence 노드는 왼쪽 첫 번째 자식부터 순차적으로 tick을 전달한다. 자식이 Success를 반환하면 다음 자식에게 tick을 전달하고, Failure를 반환하면 후속 자식에 대한 tick 전달을 중단한다. Running을 반환하면 해당 자식의 인덱스를 기억하고 후속 자식에 대한 tick 전달을 중단한다.

Fallback 노드의 tick 전파: Fallback 노드는 왼쪽 첫 번째 자식부터 순차적으로 tick을 전달한다. 자식이 Failure를 반환하면 다음 자식에게 tick을 전달하고, Success를 반환하면 후속 자식에 대한 tick 전달을 중단한다. Running을 반환하면 해당 자식의 인덱스를 기억하고 후속 자식에 대한 tick 전달을 중단한다.

Parallel 노드의 tick 전파: Parallel 노드는 모든 자식에게 tick을 전달한다. 이는 Sequence나 Fallback과 달리 선택적 전파가 아닌 전면적 전파(broadcast propagation)에 해당한다.

2.3 데코레이터 노드에서의 전파

데코레이터 노드(Decorator Node)는 단일 자식을 가지며, tick을 수신하면 자식에게 tick을 전달한다. 데코레이터 노드는 자식의 반환 상태를 변환하는 역할을 수행하지만, tick의 전파 자체는 단순히 자식에게 전달하는 형태이다. 다만, 일부 데코레이터(예: RunOnce)는 특정 조건에서 자식에 대한 tick 전달을 억제할 수 있다.

2.4 리프 노드에서의 종단

Tick의 하향 전파는 리프 노드에서 종단(termination)된다. 리프 노드는 자식이 없으므로 tick을 더 이상 하위로 전달하지 않으며, 자신의 내부 로직을 실행하여 반환 상태를 결정한다. 액션 노드(Action Node)는 작업을 수행하고, 조건 노드(Condition Node)는 조건 술어를 평가하여 반환 상태를 산출한다.

3. 반환 상태의 상향 전파

Tick의 하향 전파와 대칭적으로, 반환 상태(Return Status)는 리프 노드에서 루트 노드 방향으로 상향 전파(bottom-up propagation)된다. 리프 노드가 반환 상태를 결정하면 이를 부모 노드에게 보고하고, 부모 노드는 자식의 반환 상태를 기반으로 자신의 반환 상태를 결정하여 다시 상위 노드에게 보고한다.

이 과정은 재귀적(recursive)으로 진행되며, 최종적으로 루트 노드가 반환 상태를 수신하여 하나의 tick 순환이 완료된다. 따라서 하나의 tick 순환은 tick의 하향 전파와 반환 상태의 상향 전파가 결합된 왕복 과정(round-trip process)이다.

Tick 하향 전파:     Root → Control → ... → Leaf
반환 상태 상향 전파: Root ← Control ← ... ← Leaf

4. 깊이 우선 순회와 tick 전파

Tick의 하향 전파는 깊이 우선 순회(Depth-First Traversal) 방식을 따른다. 제어 흐름 노드가 자식에게 tick을 전달할 때, 첫 번째 자식의 전체 서브트리가 완전히 순회되어 반환 상태가 확정된 후에야 두 번째 자식의 순회가 시작된다. 이는 너비 우선 순회(Breadth-First Traversal)와 대비되는 방식이다.

깊이 우선 순회의 채택은 행동 트리의 왼쪽에서 오른쪽(left-to-right) 실행 순서와 직결된다. 왼쪽 자식의 서브트리가 먼저 완전히 처리되므로, 왼쪽에 배치된 행동이 오른쪽에 배치된 행동보다 높은 우선순위를 갖는다. 이 우선순위 관계는 트리의 시각적 구조에서 직관적으로 파악할 수 있다 (Colledanchise & Ogren, 2018).

5. 조기 종료와 tick 전파의 제한

5.1 조기 종료의 메커니즘

제어 흐름 노드의 제어 정책에 따라 tick의 전파가 조기에 중단될 수 있다. 이 조기 종료(short-circuit)는 불리언 논리의 단락 평가(short-circuit evaluation)와 동일한 원리에 기반한다.

Sequence 노드에서 자식이 Failure를 반환하면, 후속 자식의 서브트리에는 tick이 전달되지 않는다. 이는 논리곱(AND)에서 하나의 피연산자가 거짓이면 나머지 피연산자를 평가할 필요가 없는 것과 동일하다. Fallback 노드에서 자식이 Success를 반환하면, 후속 자식의 서브트리에는 tick이 전달되지 않는다. 이는 논리합(OR)에서 하나의 피연산자가 참이면 나머지 피연산자를 평가할 필요가 없는 것과 동일하다.

5.2 선택적 전파의 의의

조기 종료에 의한 tick 전파의 제한은 두 가지 중요한 효과를 갖는다.

첫째, 계산 효율성(computational efficiency)의 향상이다. 실행할 필요가 없는 노드의 서브트리를 건너뜀으로써 각 tick의 계산 비용을 감소시킨다. 대규모 행동 트리에서 이 효과는 실시간 실행 제약을 충족시키는 데 핵심적으로 기여한다.

둘째, 부작용(side effect)의 방지이다. tick이 전달되지 않은 노드는 실행되지 않으므로, 해당 노드의 액션이 수행되지 않는다. 이는 불필요한 행동의 실행을 원천적으로 차단한다.

6. Tick 전파와 Running 상태의 상호작용

6.1 Running 자식에 대한 직접 전파

일반(비반응형) Sequence 및 Fallback 노드에서 이전 tick에서 Running을 반환한 자식이 존재하면, 다음 tick에서는 해당 자식부터 tick 전파가 시작된다. 이전에 Success를 반환한 자식에게는 tick이 재전달되지 않는다. 이 메커니즘은 이미 완료된 작업의 불필요한 재실행을 방지한다.

6.2 반응형 노드에서의 전면 재전파

ReactiveSequence 및 ReactiveFallback 노드에서는 Running 자식이 존재하더라도 매 tick마다 첫 번째 자식부터 tick 전파가 다시 시작된다. 이를 통해 환경 변화에 의한 조건 변경이 즉각적으로 감지되며, 필요한 경우 현재 Running 상태의 자식이 중단되고 다른 행동으로의 전환이 이루어진다 (Colledanchise & Ogren, 2018).

7. 하향 전파 원칙의 설계적 함의

7.1 중앙 집중적 제어

Tick의 하향 전파 원칙은 행동 트리의 실행 제어가 트리의 상위 계층에 중앙 집중되어 있음을 의미한다. 이는 트리의 전역적(global) 행동이 상위 제어 흐름 노드의 구조에 의해 결정되며, 하위 노드는 상위 구조의 결정에 따라 실행 여부가 결정되는 하향식(top-down) 제어 구조이다.

7.2 예측 가능한 실행 순서

하향 전파와 깊이 우선 순회의 결합은 행동 트리의 실행 순서를 완전히 예측 가능하게 만든다. 동일한 트리 구조와 동일한 환경 상태가 주어지면, tick이 방문하는 노드의 순서는 항상 동일하다. 이 결정론적 실행 순서는 행동 트리의 분석, 디버깅, 테스트를 용이하게 한다.

참고 문헌

  • Colledanchise, M. & Ogren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
  • Faconti, D. (2024). BehaviorTree.CPP Documentation. https://www.behaviortree.dev/