1293.51 조기 종료 (Short-Circuit) 메커니즘

1. 조기 종료의 정의

조기 종료(short-circuit)란, 제어 노드가 자식의 반환 상태를 평가하는 과정에서 나머지 자식의 평가 없이 즉시 최종 결과를 결정하는 메커니즘이다. 이는 프로그래밍 언어에서의 단락 평가(short-circuit evaluation)와 동일한 원리이며, 불필요한 노드 실행을 방지하여 Tick 실행 시간을 단축한다. 행동 트리에서 조기 종료는 Sequence와 Fallback 노드의 핵심적 동작 특성이다(Colledanchise & Ogren, 2018).

2. 논리 연산과의 대응

행동 트리의 제어 노드는 논리 연산과 대응된다.

제어 노드	논리 연산	조기 종료 조건
Sequence	AND ( $\wedge$ )	자식이 FAILURE 반환
Fallback	OR ( $\vee$ )	자식이 SUCCESS 반환

논리적 AND 연산에서 피연산자 중 하나가 FALSE이면 나머지 피연산자와 무관하게 결과가 FALSE인 것과 마찬가지로, Sequence에서 자식 중 하나가 FAILURE를 반환하면 나머지 자식의 결과와 무관하게 Sequence 전체가 FAILURE이다. Fallback과 OR 연산의 관계도 동일하다.

3. Sequence에서의 조기 종료

Sequence 노드에서 자식이 FAILURE를 반환하면, 이후 자식은 Tick되지 않고 Sequence가 즉시 FAILURE를 반환한다.

function Sequence.tick():
    for each child in children:
        status = child.tick()
        if status == FAILURE:
            return FAILURE      // 조기 종료: 이후 자식 Tick 안 함
        if status == RUNNING:
            return RUNNING      // 현재 자식에서 멈춤
    return SUCCESS              // 모든 자식 SUCCESS

3.1 실행 예시

Sequence
├── Child_0 → SUCCESS     (Tick됨)
├── Child_1 → FAILURE     (Tick됨, 조기 종료 발생)
├── Child_2 → (Tick 안 됨)
└── Child_3 → (Tick 안 됨)

Child_1이 FAILURE를 반환하면, Child_2와 Child_3은 Tick되지 않는다. Sequence는 즉시 FAILURE를 반환한다.

4. Fallback에서의 조기 종료

Fallback 노드에서 자식이 SUCCESS를 반환하면, 이후 자식은 Tick되지 않고 Fallback이 즉시 SUCCESS를 반환한다.

function Fallback.tick():
    for each child in children:
        status = child.tick()
        if status == SUCCESS:
            return SUCCESS      // 조기 종료: 이후 자식 Tick 안 함
        if status == RUNNING:
            return RUNNING      // 현재 자식에서 멈춤
    return FAILURE              // 모든 자식 FAILURE

4.1 실행 예시

Fallback
├── Child_0 → FAILURE     (Tick됨)
├── Child_1 → SUCCESS     (Tick됨, 조기 종료 발생)
├── Child_2 → (Tick 안 됨)
└── Child_3 → (Tick 안 됨)

5. RUNNING에 의한 조기 종료

RUNNING 상태도 일종의 조기 종료를 유발한다. Sequence와 Fallback 모두에서 자식이 RUNNING을 반환하면, 이후 자식은 Tick되지 않고 제어 노드가 RUNNING을 반환한다. 이는 비동기 작업의 완료를 대기하면서 후속 자식의 불필요한 실행을 방지한다.

Sequence:
  Child_i → RUNNING → 이후 자식 Tick 안 됨 → Sequence 반환 RUNNING

Fallback:
  Child_i → RUNNING → 이후 자식 Tick 안 됨 → Fallback 반환 RUNNING

6. 조기 종료의 성능 이점

조기 종료에 의한 성능 이점은 건너뛰어진 자식들의 Tick 실행 시간의 합이다.

$T_{saved} = \sum_{i=j+1}^{N-1} T_{child_i}$

여기서 $j$ 는 조기 종료를 유발한 자식의 인덱스이고, $N$ 은 전체 자식 수이다. 조기 종료가 앞쪽 자식에서 발생할수록 절약되는 시간이 크다.

6.1 자식 배치 순서 최적화

조기 종료의 성능 이점을 극대화하려면, 조기 종료를 유발할 가능성이 높은 자식을 앞쪽에 배치해야 한다.

Sequence: FAILURE 반환 가능성이 높은 자식을 앞에 배치
Fallback: SUCCESS 반환 가능성이 높은 자식을 앞에 배치

<!-- Sequence: 실패 가능성 높은 조건을 앞에 -->
<Sequence>
    <IsBatteryOk/>           <!-- 자주 실패 가능 -->
    <IsPathClear/>           <!-- 가끔 실패 -->
    <NavigateToGoal/>        <!-- 장기 실행 -->
</Sequence>

<!-- Fallback: 성공 가능성 높은 대안을 앞에 -->
<Fallback>
    <UsePrimaryMethod/>      <!-- 대부분 성공 -->
    <UseBackupMethod/>       <!-- 가끔 성공 -->
    <UseLastResort/>         <!-- 거의 성공 안 함 -->
</Fallback>

7. 조기 종료와 Halt의 관계

조기 종료가 발생하면, 건너뛰어진 자식뿐 아니라 이전에 RUNNING이었던 다른 자식에도 Halt가 호출될 수 있다. 특히 Reactive 노드에서 조기 종료 조건이 변경될 때, 이전 Tick에서 RUNNING이었던 자식에 Halt가 필요하다.

ReactiveSequence:
  Tick N-1: Child_0(SUCCESS), Child_1(SUCCESS), Child_2(RUNNING)
  Tick N:   Child_0(FAILURE) → 조기 종료
            → Child_2에 Halt (이전 Tick에서 RUNNING)

8. Parallel 노드에서의 비적용

Parallel 노드에서는 조기 종료가 적용되지 않는다. Parallel 노드는 모든 활성 자식에 Tick을 전파한 후, 성공/실패 카운트를 집계하여 결과를 판정한다. 개별 자식의 반환 상태에 의한 즉시 종료가 발생하지 않으며, 모든 자식의 Tick이 완료된 후에야 최종 판정이 이루어진다.

참고 문헌

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/