1295.3 Parallel 노드의 모든 자식 Tick 전파

1. 전체 자식 틱 전파의 원칙

Parallel 노드의 가장 본질적인 특성은 매 틱(tick) 주기마다 모든 자식 노드에 틱을 전파한다는 점이다. 이는 Sequence 노드나 Fallback 노드와 같은 다른 제어 노드들이 조기 종료(short-circuit) 조건에 따라 일부 자식에만 틱을 전달하는 것과 근본적으로 대비되는 동작 방식이다(Colledanchise & Ögren, 2018).

Parallel 노드 $P$ 가 $N$ 개의 자식 $C_1, C_2, \ldots, C_N$ 을 보유할 때, 각 틱 주기에서의 틱 전파 규칙은 다음과 같다.

$\forall k \in \{1, 2, \ldots, N\}, \quad \text{tick}(C_k) \text{ 가 실행됨}$

이 규칙은 자식의 현재 상태와 무관하게 적용된다. 즉, 이전 틱에서 어떤 자식이 SUCCESS를 반환했든, FAILURE를 반환했든, RUNNING을 반환했든, 다음 틱에서 해당 자식은 다시 틱을 수신한다. 단, 이미 완료된 자식의 재틱 처리에 관해서는 구현에 따라 상이한 정책이 적용될 수 있다.

2. 다른 제어 노드와의 틱 전파 비교

각 제어 노드의 틱 전파 방식을 비교하면 Parallel 노드의 고유한 특성이 명확히 드러난다.

2.1 Sequence 노드의 틱 전파

Sequence 노드는 첫 번째 자식부터 순서대로 틱을 전달하되, 어떤 자식이 FAILURE를 반환하면 즉시 이후 자식에 대한 틱 전파를 중단하고 FAILURE를 반환한다. 또한 어떤 자식이 RUNNING을 반환하면 해당 자식에서 틱 전파를 중단하고 RUNNING을 반환한다. 따라서 단일 틱 주기에서 모든 자식이 틱을 수신하는 것이 보장되지 않는다.

2.2 Fallback 노드의 틱 전파

Fallback 노드는 첫 번째 자식부터 순서대로 틱을 전달하되, 어떤 자식이 SUCCESS를 반환하면 이후 자식에 대한 틱 전파를 중단하고 SUCCESS를 반환한다. 마찬가지로 RUNNING 반환 시 해당 자식에서 중단된다.

2.3 Parallel 노드의 틱 전파

Parallel 노드는 단락 평가를 수행하지 않는다. 모든 자식 $C_1$ 부터 $C_N$ 까지 순서대로 틱을 전달하고, 전체 결과를 수집한 후에야 최종 상태를 결정한다.

제어 노드	틱 전파 범위	조기 중단 조건	단일 틱 내 최대 틱 수신 자식 수
Sequence	첫 번째부터 실패 또는 RUNNING까지	FAILURE 또는 RUNNING 반환 시	$1 \leq k \leq N$
Fallback	첫 번째부터 성공 또는 RUNNING까지	SUCCESS 또는 RUNNING 반환 시	$1 \leq k \leq N$
Parallel	모든 자식	없음 (정책 판정은 전파 후)	$N$ (항상)

3. 틱 전파의 순서와 결정론성

Parallel 노드는 모든 자식에 틱을 전파하지만, 그 순서는 자식의 정의 순서(declaration order)를 따른다. 즉, XML이나 코드에서 먼저 정의된 자식이 먼저 틱을 수신한다.

<Parallel success_count="2">
    <ActionA/>   <!-- 첫 번째로 틱 수신 -->
    <ActionB/>   <!-- 두 번째로 틱 수신 -->
    <ActionC/>   <!-- 세 번째로 틱 수신 -->
</Parallel>

이 순서가 고정되어 있으므로, 동일한 입력 상태에서 동일한 실행 결과가 보장된다. 이 결정론적 순서는 다음의 실질적 함의를 갖는다.

블랙보드 갱신 순서: $C_1$ 이 블랙보드에 기록한 값은 동일 틱 내에서 $C_2$ 와 $C_3$ 가 읽을 수 있다. 반대로 $C_3$ 가 기록한 값은 동일 틱 내에서 $C_1$ 이나 $C_2$ 가 읽을 수 없으며, 다음 틱에서야 가용해진다.
상태 반환 순서: $C_1$ 이 먼저 상태를 반환하므로, 구현에 따라서는 $C_1$ 의 결과에 따라 성공 또는 실패 임계값에 조기 도달하여 $C_2$ , $C_3$ 의 틱을 스킵하는 최적화가 가능하다. 그러나 표준 구현에서는 이러한 조기 종료를 수행하지 않고 모든 자식에 반드시 틱을 전달한다.

4. 완료된 자식의 재틱 처리

Parallel 노드에서 중요한 설계 결정은 이미 SUCCESS 또는 FAILURE를 반환한 자식 노드에 대한 후속 틱 처리 방식이다. BehaviorTree.CPP에서는 두 가지 접근법이 존재한다.

4.1 재틱 스킵 방식

이미 최종 상태(SUCCESS 또는 FAILURE)를 반환한 자식은 이후 틱에서 틱을 수신하지 않고, 마지막으로 반환한 상태가 그대로 유지된다. 이 방식은 완료된 행동의 불필요한 재실행을 방지한다.

Tick 1: C1=RUNNING, C2=SUCCESS, C3=RUNNING
Tick 2: C1=RUNNING, C2=(스킵, SUCCESS 유지), C3=SUCCESS
Tick 3: C1=SUCCESS, C2=(스킵, SUCCESS 유지), C3=(스킵, SUCCESS 유지)
→ 성공 임계값 충족 시 SUCCESS 반환

4.2 매 틱 재실행 방식

모든 자식에 매 틱마다 무조건 틱을 전달하며, 이전에 완료된 자식도 처음부터 다시 실행한다. 이 방식은 조건 노드와 같이 매 틱마다 재평가가 필요한 자식에 적합하다.

BehaviorTree.CPP 4.x 버전에서는 기본적으로 재틱 스킵 방식을 채택하되, ParallelAll 노드와 같은 변형을 통해 재실행 방식도 지원한다.

5. 틱 전파의 시간 복잡도

Parallel 노드가 매 틱마다 모든 $N$ 개의 자식에 틱을 전파하므로, 단일 틱에서의 시간 복잡도는 최소 $O(N)$ 이다. 각 자식 노드 $C_i$ 의 틱 실행 시간을 $t_i$ 라 하면, Parallel 노드의 단일 틱 실행 시간 $T_P$ 는 다음과 같다.

$T_P = \sum_{i=1}^{N} t_i + O(N)$

여기서 $O(N)$ 은 상태 수집 및 정책 판정에 소요되는 오버헤드이다. 이는 Sequence나 Fallback 노드에서 조기 종료가 발생하여 일부 자식만 틱을 수신하는 경우의 실행 시간보다 크거나 같다. 따라서 Parallel 노드의 자식 수를 불필요하게 증가시키면 전체 행동 트리의 틱 주기가 연장될 수 있으므로, 성능에 민감한 실시간 시스템에서는 자식 수를 적절히 제한해야 한다.

6. 틱 전파 실패 시의 처리

개별 자식 노드의 tick() 호출이 예외(exception)를 발생시키는 경우, Parallel 노드의 동작은 프레임워크의 예외 처리 정책에 따라 달라진다. BehaviorTree.CPP에서는 자식 노드의 예외가 포착되지 않으면 상위로 전파되어 전체 행동 트리의 실행이 중단된다. 따라서 각 자식 노드는 내부적으로 예외를 적절히 처리하고, 오류 상황에서는 FAILURE를 반환하는 방식으로 구현해야 한다.

7. 참고 문헌

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

Version: 1.0-2026.04.03