1292.41 Parallel 노드의 동작 원리

1. Parallel 노드의 정의

Parallel 노드는 행동 트리(Behavior Tree)의 제어 흐름 노드 중 하나로, 모든 자식 노드에 동시에 tick을 전달하여 병렬적으로 실행하는 노드이다. Sequence 노드와 Fallback 노드가 자식을 순차적으로 실행하는 것과 달리, Parallel 노드는 매 tick마다 모든 자식에 tick을 전달한다. Parallel 노드의 반환 상태는 성공 임계값(success threshold)과 실패 임계값(failure threshold) 정책에 의해 결정된다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

행동 트리 다이어그램에서 Parallel 노드는 일반적으로 이중 수평선 기호(\rightrightarrows) 또는 “Parallel“이라는 레이블로 표기된다.

2. Parallel 노드의 알고리즘

Parallel 노드의 동작을 의사 코드로 표현하면 다음과 같다.

function Parallel.tick():
    success_count = 0
    failure_count = 0
    for i = 0 to N:
        if child[i].status != Success and child[i].status != Failure:
            status = child[i].tick()
        else:
            status = child[i].status
        if status == Success:
            success_count++
        if status == Failure:
            failure_count++

    if success_count >= success_threshold:
        halt_all_running_children()
        return Success
    if failure_count >= failure_threshold:
        halt_all_running_children()
        return Failure
    return Running

이 알고리즘에서 Parallel 노드는 매 tick마다 아직 완료되지 않은(Running 또는 Idle 상태의) 모든 자식에 tick을 전달하고, 성공 및 실패 횟수를 집계하여 임계값 정책에 따라 자신의 반환 상태를 결정한다 (Faconti, BehaviorTree.CPP Documentation, 2024).

3. Sequence 및 Fallback 노드와의 구조적 차이

Parallel 노드는 Sequence 및 Fallback 노드와 근본적으로 다른 실행 모델을 가진다. 이 차이를 다음 표로 요약한다.

Parallel 노드는 “N개의 자식 중 M개가 성공하면 성공“이라는 M-of-N 의미론을 구현하며, 이는 논리곱이나 논리합으로는 표현할 수 없는 보다 유연한 조합 논리를 제공한다.

4. 동시 실행의 의미론적 해석

Parallel 노드의 “동시 실행“은 운영체제 수준의 멀티스레딩(multithreading)이나 실제 물리적 병렬 실행을 의미하지 않는다. 행동 트리의 실행 엔진은 단일 스레드(single thread)에서 동작하며, Parallel 노드는 단일 tick 내에서 모든 자식에 순차적으로 tick을 전달한다. 따라서 “동시 실행“이란 “동일한 tick에서 모든 자식이 tick을 수신한다“는 의미로 해석하여야 한다 (Colledanchise & Ögren, 2018).

이 논리적 동시성(logical concurrency)은 물리적 동시성과 구별된다. 각 자식은 단일 tick 내에서 왼쪽에서 오른쪽 순서로 tick을 수신하므로, 미시적(microscopic) 수준에서는 순차적이지만 거시적(macroscopic) 수준에서는 모든 자식이 매 tick마다 실행 기회를 받는다는 점에서 동시적이다.

5. 임계값 정책

Parallel 노드의 핵심 매개변수는 성공 임계값 M_S와 실패 임계값 M_F이다.

성공 임계값 M_S: Success를 반환한 자식의 수가 M_S 이상이면 Parallel 노드는 Success를 반환한다.

실패 임계값 M_F: Failure를 반환한 자식의 수가 M_F 이상이면 Parallel 노드는 Failure를 반환한다.

BehaviorTree.CPP에서는 기본적으로 M_S = N(모든 자식이 성공해야 성공)이고 M_F = 1(하나라도 실패하면 실패)로 설정되어 있으나, 이 값은 설계자가 자유롭게 조정할 수 있다 (Faconti, 2024).

6. 반환 상태의 결정 규칙

단일 tick에서 Parallel 노드의 반환 상태는 다음의 우선순위 규칙에 따라 결정된다. 성공한 자식의 수를 n_S, 실패한 자식의 수를 n_F라 하면:

\text{status}(P) = \begin{cases} Success & \text{if } n_S \geq M_S \\ Failure & \text{if } n_F \geq M_F \\ Running & \text{otherwise} \end{cases}

성공 임계값과 실패 임계값이 동시에 충족되는 경우, 구현에 따라 Success 또는 Failure 중 하나가 우선될 수 있다. BehaviorTree.CPP에서는 성공 임계값의 검사가 먼저 수행된다.

완료된 자식의 처리

Parallel 노드에서 이미 Success 또는 Failure를 반환한 자식은, 후속 tick에서 다시 tick을 수신하지 않는다. 해당 자식의 반환 상태는 기억되어 집계에 포함되며, 아직 Running 상태에 있는 자식만이 후속 tick에서 tick을 수신한다. 이 메커니즘은 이미 완료된 작업의 불필요한 재실행을 방지한다.

Parallel 노드와 Halt

Parallel 노드가 자신의 반환 상태를 확정하면(Success 또는 Failure), 아직 Running 상태에 있는 모든 자식에 halt를 요청한다. 이는 Parallel 노드의 결과가 확정된 후 더 이상 필요하지 않은 진행 중인 작업을 정리하는 역할을 한다.

예를 들어, 성공 임계값 M_S = 2인 Parallel 노드에서 세 자식 중 두 자식이 Success를 반환하면, 세 번째 자식이 아직 Running 상태이더라도 Parallel 노드는 Success를 반환하고, 세 번째 자식에 halt를 요청한다.

실행 흐름 예제

다음의 Parallel 노드를 고려한다. 성공 임계값 M_S = 2, 실패 임계값 M_F = 2로 설정되어 있다.

Parallel [P1, M_S=2, M_F=2]
 ├─ Action [A1: 센서 데이터 수집]
 ├─ Action [A2: 장애물 감지]
 └─ Action [A3: 위치 추정]

tick t_3에서 n_S = 2 \geq M_S = 2이므로 P1은 Success를 반환하고, 아직 Running 상태인 A3에 halt를 요청한다 (Colledanchise & Ögren, 2018).

로봇 공학에서의 활용

동시적 행동 수행

로봇이 이동하면서 동시에 주변 환경을 감시하는 행동을 모델링할 때 Parallel 노드가 활용된다. 이동과 감시는 독립적인 작업이므로, 두 작업을 동시에 수행하는 것이 효율적이다.

다중 센서 융합

복수의 센서 데이터를 동시에 수집하고 처리하는 작업을 Parallel 노드로 모델링할 수 있다. 모든 센서의 데이터가 수집되어야 후속 처리가 가능한 경우 M_S = N으로 설정하고, 일부 센서만으로도 충분한 경우 M_S < N으로 설정한다.

감시와 실행의 분리

Parallel 노드의 한 자식으로 감시 조건을, 다른 자식으로 실행 행동을 배치하면, 행동 수행 중에 조건을 지속적으로 감시하는 패턴을 구현할 수 있다. 이는 ReactiveSequence와 유사한 기능을 제공하되, 임계값 정책을 통한 보다 세밀한 제어가 가능하다.

참고 문헌

• 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/