1294.40 FallbackWithMemory의 재진입 규칙

1. 재진입의 정의

FallbackWithMemory의 재진입(re-entry)이란, 이전 Tick에서 자식이 RUNNING을 반환하여 Fallback이 RUNNING 상태인 경우, 다음 Tick에서 current_child_idx에 기억된 인덱스부터 평가를 재개하는 동작을 의미한다. 이 재진입 규칙에 의해 이전 Tick에서 FAILURE를 반환한 자식들의 재평가가 생략된다(Colledanchise & Ogren, 2018).

2. 재진입 규칙의 상세

2.1 규칙 1: RUNNING 자식 인덱스에서 재개

이전 Tick에서 자식 $c_k$ 가 RUNNING을 반환한 경우, 다음 Tick에서 인덱스 $k$ 부터 평가를 시작한다. 인덱스 $0$ 부터 $k-1$ 까지의 자식은 평가되지 않는다.

Tick N:
  children[0] → FAILURE
  children[1] → FAILURE
  children[2] → RUNNING
  current_child_idx ← 2
  → RUNNING

Tick N+1: (인덱스 2에서 재진입)
  children[0] → (건너뜀)
  children[1] → (건너뜀)
  children[2] → RUNNING
  → RUNNING

2.2 규칙 2: 건너뛰어진 자식은 재평가되지 않음

재진입 시 인덱스 $0$ 부터 $k-1$ 까지의 자식은 이전 Tick에서 FAILURE를 반환한 자식들이다. 이들은 재진입 Tick에서 재평가되지 않으므로, 해당 자식들의 상태 변화(FAILURE에서 SUCCESS로의 전환)를 감지하지 못한다.

Tick N:
  children[0](CondA) → FAILURE    (조건 미충족)
  children[1](ActB)  → RUNNING
  current_child_idx ← 1

Tick N+1: (CondA가 SUCCESS로 변경되었으나...)
  children[0](CondA) → (건너뜀 — 변화 미감지)
  children[1](ActB)  → RUNNING
  → RUNNING

2.3 규칙 3: RUNNING 자식이 FAILURE를 반환하면 다음으로 진행

재진입한 자식이 이번 Tick에서 FAILURE를 반환하면, 다음 인덱스의 자식으로 진행한다. 이전에 건너뛰어진 자식으로 되돌아가지 않는다.

Tick N:
  children[0] → FAILURE
  children[1] → RUNNING    (current_child_idx=1)

Tick N+1:
  children[1] → FAILURE    (RUNNING에서 FAILURE로 전환)
  children[2] → SUCCESS    (다음 대안으로 진행)
  current_child_idx ← 0
  → SUCCESS

2.4 규칙 4: SUCCESS 또는 전체 FAILURE 시 인덱스 초기화

어떤 자식이 SUCCESS를 반환하거나 모든 자식이 FAILURE를 반환하면, current_child_idx가 0으로 초기화된다. 다음 Tick(Fallback이 다시 IDLE에서 시작)에서는 첫 번째 자식부터 평가한다.

Tick N:
  children[1] → SUCCESS    (재진입 후 성공)
  current_child_idx ← 0    (초기화)
  → SUCCESS

Tick N+1: (새로운 평가 주기)
  children[0] → ...        (인덱스 0부터 시작)

3. 재진입 규칙의 실행 추적

3.1 전체 흐름 추적

children: [CondCheck, AsyncRecoveryA, AsyncRecoveryB, SafeStop]

Tick 1:
  i=0: CondCheck → FAILURE         (정상 상태 아님)
  i=1: AsyncRecoveryA → RUNNING    (복구 A 시도 중)
  current_child_idx ← 1
  → RUNNING

Tick 2: (인덱스 1에서 재진입)
  i=1: AsyncRecoveryA → RUNNING    (복구 A 계속)
  → RUNNING

Tick 3: (인덱스 1에서 재진입)
  i=1: AsyncRecoveryA → FAILURE    (복구 A 실패)
  i=2: AsyncRecoveryB → RUNNING    (복구 B 시도 시작)
  current_child_idx ← 2
  → RUNNING

Tick 4: (인덱스 2에서 재진입)
  i=2: AsyncRecoveryB → SUCCESS    (복구 B 성공)
  current_child_idx ← 0
  → SUCCESS

이 추적에서 주목할 점:

Tick 2에서 CondCheck가 건너뛰어진다 (정상 상태로 변했을 수 있지만 미확인).
Tick 3에서 AsyncRecoveryA 실패 후 AsyncRecoveryB로 자동 진행된다.
Tick 4에서 CondCheck와 AsyncRecoveryA가 모두 건너뛰어진다.

4. SequenceWithMemory 재진입 규칙과의 대칭성

규칙	SequenceWithMemory	FallbackWithMemory
재진입 위치	RUNNING 자식 인덱스	RUNNING 자식 인덱스
건너뛰는 자식	이전 SUCCESS 자식	이전 FAILURE 자식
진행 조건	현재 자식 SUCCESS	현재 자식 FAILURE
종료 및 초기화	FAILURE 또는 전체 SUCCESS	SUCCESS 또는 전체 FAILURE

두 변형의 재진입 규칙은 구조적으로 동일하며, 건너뛰는 대상과 진행/종료 조건에서 SUCCESS와 FAILURE가 교환된 관계이다.

5. 재진입 규칙의 장점과 한계

5.1 장점

불필요한 재시도 방지: 이미 실패한 대안을 매 Tick마다 재시도하지 않으므로 자원을 절약한다.
비동기 작업의 안정적 진행: RUNNING 자식에 대한 Tick이 앞쪽 자식의 재평가 없이 직접 전달되므로, 비동기 작업의 진행이 안정적이다.
예측 가능한 Tick 비용: RUNNING 상태에서 Tick당 1개의 노드만 방문하므로, 자식 수에 무관하게 Tick 비용이 일정하다.

5.2 한계

우선순위 높은 대안의 가용성 변화 미감지: 이전에 FAILURE였던 앞쪽 자식이 SUCCESS로 변경되어도 감지하지 못한다. 더 나은 대안이 가용해졌는데도 현재 대안을 계속 시도한다.
조건 재검사 불가: 앞쪽에 배치된 조건 노드가 건너뛰어지므로, 조건 기반의 대안 전환이 불가능하다.
환경 변화에 대한 반응 지연: 환경이 변화하여 이전 대안이 다시 성공 가능해져도, 현재 대안의 시도가 완료될 때까지 감지되지 않는다.

이러한 한계가 문제가 되는 경우에는 ReactiveFallback을 사용하여 매 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/