1294.36 Fallback 노드의 조기 종료 (Short-Circuit) 동작

1. 조기 종료의 정의

Fallback 노드의 조기 종료(short-circuit)란, 자식의 순차 평가 과정에서 하나의 자식이 SUCCESS를 반환하면 나머지 자식의 평가를 생략하고 즉시 SUCCESS를 반환하는 동작이다. 이는 논리 OR 연산의 단락 평가(short-circuit evaluation)와 동일한 원리이며, 첫 번째 참(true) 값이 발견되면 나머지 평가가 불필요해지는 성질에 기반한다(Colledanchise & Ogren, 2018).

2. Sequence의 조기 종료와의 대칭성

Fallback과 Sequence의 조기 종료는 SUCCESS와 FAILURE가 교환된 대칭 관계이다.

특성	Sequence의 조기 종료	Fallback의 조기 종료
종료 트리거	FAILURE	SUCCESS
논리 연산 대응	AND 단락 평가	OR 단락 평가
계속 진행 조건	SUCCESS	FAILURE
최악 경우	모든 자식 SUCCESS (종료 없음)	모든 자식 FAILURE (종료 없음)

3. 조기 종료의 동작 과정

3.1 SUCCESS에 의한 조기 종료

children: [A, B, C, D, E]

tick():
  A.executeTick() → FAILURE    (다음으로 진행)
  B.executeTick() → SUCCESS    ← 조기 종료 지점
  → return SUCCESS

미평가: C, D, E

자식 B가 SUCCESS를 반환하는 순간, C, D, E는 평가되지 않으며 Fallback은 SUCCESS를 반환한다.

3.2 RUNNING에 의한 조기 종료

RUNNING 반환도 일종의 조기 종료를 유발한다. 현재 자식의 결과가 미결정이므로 후속 자식의 평가를 보류한다.

tick():
  A.executeTick() → FAILURE
  B.executeTick() → RUNNING    ← 조기 종료 (결과 미결정)
  → return RUNNING

미평가: C, D, E

3.3 조기 종료가 발생하지 않는 경우

모든 자식이 FAILURE를 반환하면 조기 종료 없이 전체 자식이 평가된다.

tick():
  A.executeTick() → FAILURE
  B.executeTick() → FAILURE
  C.executeTick() → FAILURE
  D.executeTick() → FAILURE
  E.executeTick() → FAILURE
  → return FAILURE

평가된 자식: 5개 (전부)

4. 조기 종료의 성능 효과

4.1 평균 평가 비용 절감

자식이 $N$ 개이고, 각 자식의 SUCCESS 확률이 $p$ 인 경우, 조기 종료에 의해 평균적으로 평가되는 자식 수는 다음과 같다:

$E[\text{평가 수}] = \sum_{k=1}^{N} k \cdot (1-p)^{k-1} \cdot p + N \cdot (1-p)^N$

첫 번째 항은 $k$ 번째 자식에서 조기 종료되는 확률, 두 번째 항은 모든 자식이 FAILURE인 확률을 나타낸다.

$p = 0.5$ , $N = 5$ 인 경우:

$E[\text{평가 수}] = 1 \times 0.5 + 2 \times 0.25 + 3 \times 0.125 + 4 \times 0.0625 + 5 \times 0.03125 + 5 \times 0.03125 \approx 1.94$

평균적으로 5개 자식 중 약 1.94개만 평가된다.

4.2 자식 배치 순서의 최적화

조기 종료의 성능 효과를 극대화하려면, SUCCESS 확률이 높은 자식을 왼쪽에 배치해야 한다. 이렇게 하면 평균 평가 비용이 최소화된다.

<!-- 최적 배치: 성공 확률 높은 순서 -->
<Fallback>
    <Action ID="HighSuccessRate"/>     <!-- 성공 확률 80% -->
    <Action ID="MediumSuccessRate"/>   <!-- 성공 확률 50% -->
    <Action ID="LowSuccessRate"/>      <!-- 성공 확률 20% -->
</Fallback>

그러나 실무에서는 성공 확률만이 아니라 비용, 안전성, 선호도 등의 복합적 기준에 의해 배치 순서가 결정된다.

5. 조건 노드를 활용한 조기 종료 패턴

5.1 가드 패턴 (Guard Pattern)

Fallback의 첫 번째 자식으로 조건 노드를 배치하면, 조건이 이미 충족된 경우 액션의 실행을 방지하는 가드 역할을 수행한다.

<Fallback>
    <Condition ID="IsGoalAchieved"/>    <!-- 가드: 이미 달성? -->
    <Action ID="AchieveGoal"/>          <!-- 미달성 시에만 실행 -->
</Fallback>

IsGoalAchieved가 SUCCESS를 반환하면 조기 종료에 의해 AchieveGoal은 실행되지 않는다. 이 패턴은 불필요한 액션 실행을 방지하는 효율적 구조이다.

5.2 다중 가드 패턴

<Fallback>
    <Condition ID="IsObjectAlreadyGrasped"/>
    <Sequence>
        <Condition ID="IsObjectVisible"/>
        <Action ID="GraspObject"/>
    </Sequence>
    <Action ID="SearchAndGrasp"/>
</Fallback>

이미 물체를 잡고 있으면 → 조기 종료 (SUCCESS)
물체가 보이면 → 잡기 시도
보이지 않으면 → 탐색 후 잡기

각 단계에서 SUCCESS가 반환되면 후속 대안의 평가가 생략된다.

6. 조기 종료와 부수 효과

조기 종료에 의해 평가가 생략된 자식의 부수 효과는 발생하지 않는다. 이는 설계 시 의도된 동작이며, 특정 자식이 반드시 실행되어야 하는 경우에는 Fallback의 조기 종료 메커니즘이 부적합할 수 있다.

<Fallback>
    <Action ID="TryMethod"/>       <!-- SUCCESS 시 조기 종료 -->
    <Action ID="LogFailure"/>      <!-- TryMethod 성공 시 실행되지 않음 -->
</Fallback>

TryMethod가 성공하면 LogFailure는 실행되지 않는다. 실패 로깅이 항상 필요한 경우, 이 구조는 부적합하며 별도의 메커니즘을 사용해야 한다.

참고 문헌

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/