1293.31 Parallel 노드에서의 Tick 전파

1. Parallel 노드의 정의

Parallel 노드는 행동 트리(Behavior Tree)에서 모든 자식 노드에 동시에 Tick을 전파하는 제어 노드이다. Sequence나 Fallback과 달리 자식의 반환 상태에 의한 조기 종료가 즉시 적용되지 않으며, 모든 자식이 Tick된 후에 전체 결과를 판정한다. Parallel 노드는 복수의 행동을 동시에 수행하거나, 복수의 조건을 동시에 감시하는 데 사용된다(Colledanchise & Ogren, 2018).

2. 성공 임계값과 실패 임계값

Parallel 노드의 동작은 성공 임계값(success threshold) $M$ 과 자식 수 $N$ 에 의해 결정된다. $M$ 개 이상의 자식이 SUCCESS를 반환하면 Parallel 노드는 SUCCESS를 반환하고, $N - M + 1$ 개 이상의 자식이 FAILURE를 반환하면 FAILURE를 반환한다. 그 외의 경우에는 RUNNING을 반환한다.

BehaviorTree.CPP에서는 success_count와 failure_count 파라미터를 통해 이 임계값을 설정한다(Faconti, 2022).

$\text{Parallel 반환 상태} = \begin{cases} \text{SUCCESS} & \text{if } |\{c_i \mid c_i = \text{SUCCESS}\}| \geq M \\ \text{FAILURE} & \text{if } |\{c_i \mid c_i = \text{FAILURE}\}| > N - M \\ \text{RUNNING} & \text{otherwise} \end{cases}$

3. Tick 전파 알고리즘

Parallel 노드가 Tick을 수신하면, 다음 알고리즘에 따라 자식 노드에 Tick을 전파한다.

function Parallel.tick():
    success_count = 0
    failure_count = 0
    
    for each child in children:
        if child.status() != SUCCESS and child.status() != FAILURE:
            child_status = child.tick()
        else:
            child_status = child.status()  // 이미 완료된 자식
        
        if child_status == SUCCESS:
            success_count++
        elif child_status == FAILURE:
            failure_count++
    
    if success_count >= success_threshold:
        haltRunningChildren()
        return SUCCESS
    
    if failure_count > children.size() - success_threshold:
        haltRunningChildren()
        return FAILURE
    
    return RUNNING

3.1 핵심 동작

모든 자식에 대해 왼쪽에서 오른쪽으로 순차적으로 Tick을 전파한다(논리적으로는 “동시“이나 실제로는 순차 실행).
이미 SUCCESS 또는 FAILURE를 반환한 자식은 재Tick하지 않고 이전 상태를 유지한다.
모든 자식의 Tick이 완료된 후, 성공/실패 카운트에 기반하여 전체 상태를 판정한다.
SUCCESS 또는 FAILURE가 결정되면, 아직 RUNNING 중인 자식에 Halt를 호출한다.

4. 구체적 실행 흐름 예시

다음과 같은 Parallel 노드 구조를 가정한다. 성공 임계값 $M = 2$ , 자식 수 $N = 3$ 이다.

Parallel (success_count=2)
├── Action_A (비동기)
├── Action_B (비동기)
└── Action_C (비동기)

Tick	Action_A	Action_B	Action_C	성공/실패 수	Parallel
1	RUNNING	RUNNING	RUNNING	0/0	RUNNING
2	SUCCESS	RUNNING	RUNNING	1/0	RUNNING
3	SUCCESS	SUCCESS	RUNNING	2/0	SUCCESS

Tick 3에서 성공 카운트가 임계값 2에 도달하므로 Parallel은 SUCCESS를 반환하고, 아직 RUNNING 중인 Action_C에 Halt를 호출한다.

5. Parallel 노드의 완료 정책

BehaviorTree.CPP v4에서 Parallel 노드의 동작을 제어하는 완료 정책은 success_count와 failure_count 파라미터로 설정된다.

설정	의미
success_count = N	모든 자식이 성공해야 SUCCESS (AND 의미론)
success_count = 1	하나만 성공해도 SUCCESS (OR 의미론)
failure_count = 1	하나만 실패해도 FAILURE
failure_count = N	모든 자식이 실패해야 FAILURE

6. Parallel에서의 자식 상태 관리

Parallel 노드는 이미 완료된(SUCCESS 또는 FAILURE) 자식을 추적하여, 후속 Tick에서 해당 자식을 재Tick하지 않는다. 이는 Sequence나 Fallback과 구별되는 중요한 특성이다.

Tick 1: Parallel → A(RUNNING), B(SUCCESS), C(RUNNING)
Tick 2: Parallel → A(RUNNING), B(유지), C(RUNNING)  
         B는 이미 SUCCESS이므로 재Tick하지 않음

이 동작은 완료된 액션이 불필요하게 재실행되는 것을 방지하며, 특히 부수 효과를 가지는 액션 노드에서 중요하다.

7. Parallel과 순차 실행의 관계

Parallel 노드의 이름에도 불구하고, 자식 노드들은 실제로 병렬 스레드에서 실행되지 않는다. 단일 Tick 내에서 모든 자식이 순차적으로 Tick되며, 각 자식의 tick() 메서드가 순서대로 호출된다. “Parallel“이라는 명칭은 논리적으로 복수의 행동이 동시에 진행되는 것처럼 모델링된다는 의미이다.

실제 병렬 실행은 각 자식 노드가 비동기 노드(StatefulActionNode)로 구현되어, onStart()에서 별도 스레드나 외부 시스템에 작업을 위임하고, onRunning()에서 완료 여부만 확인하는 방식으로 달성된다.

8. Parallel에서의 Halt 처리

Parallel 노드가 최종 상태(SUCCESS 또는 FAILURE)를 결정하면, 아직 RUNNING 중인 모든 자식에 대해 Halt를 호출한다. 이는 불필요한 작업의 계속을 방지하고 자원을 해제하기 위함이다.

Tick 3: Parallel(success_count=2)
  A: SUCCESS, B: SUCCESS, C: RUNNING
  → 성공 카운트 = 2 ≥ 임계값 2
  → C에 Halt 호출
  → Parallel 반환: SUCCESS

참고 문헌

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