1294.31 Fallback 노드의 실행 알고리즘

1. 알고리즘의 개요

Fallback 노드의 실행 알고리즘은 자식 노드를 왼쪽에서 오른쪽으로 순차적으로 평가하면서, 첫 번째로 SUCCESS 또는 RUNNING을 반환하는 자식을 찾는 과정이다. Sequence 알고리즘이 FAILURE에서 조기 종료하는 것과 대칭적으로, Fallback 알고리즘은 SUCCESS에서 조기 종료한다(Colledanchise & Ogren, 2018).

2. 알고리즘의 단계별 절차

2.1 단계 1: 시작 인덱스 결정

Fallback의 변형에 따라 시작 인덱스가 결정된다.

FallbackWithMemory: current_child_idx부터 시작 (이전 Tick에서 RUNNING이었던 인덱스)
ReactiveFallback: 항상 인덱스 0부터 시작

i ← start_index    // WithMemory: current_child_idx, Reactive: 0

2.2 단계 2: 자식 순차 평가

인덱스 i의 자식에 대해 executeTick()을 호출하고, 반환된 상태에 따라 분기한다.

status ← children[i].executeTick()

2.3 단계 3: 반환 상태에 따른 처리

경우 1: FAILURE 반환

현재 자식이 FAILURE를 반환하면, 인덱스를 증가시키고 다음 자식의 평가로 진행한다. 이는 Sequence에서 SUCCESS 시 다음으로 진행하는 것과 대칭적이다.

if status == FAILURE:
    i ← i + 1
    if i == N:        // 모든 자식이 FAILURE
        return FAILURE
    else:
        단계 2로 이동

경우 2: SUCCESS 반환

현재 자식이 SUCCESS를 반환하면, Fallback 전체가 즉시 SUCCESS를 반환한다. 나머지 자식은 평가되지 않는다.

if status == SUCCESS:
    haltRunningChildren()    // RUNNING 중인 후속 자식 Halt
    return SUCCESS

경우 3: RUNNING 반환

현재 자식이 RUNNING을 반환하면, Fallback 전체가 RUNNING을 반환한다.

if status == RUNNING:
    return RUNNING

3. 알고리즘의 형식적 기술

Fallback의 실행 알고리즘을 형식적으로 기술하면 다음과 같다.

$\text{Fallback.tick}() = \begin{cases} \text{FAILURE} & \text{if } \forall i \in [0, N): c_i = \text{FAILURE} \\ \text{SUCCESS} & \text{if } \exists k: c_k = \text{SUCCESS} \land \forall j < k: c_j = \text{FAILURE} \\ \text{RUNNING} & \text{if } \exists k: c_k = \text{RUNNING} \land \forall j < k: c_j = \text{FAILURE} \end{cases}$

이 형식적 정의는 Sequence의 정의와 SUCCESS/FAILURE가 교환된 대칭 구조를 보인다.

4. Sequence 알고리즘과의 대칭적 대응

Fallback과 Sequence의 알고리즘은 SUCCESS와 FAILURE의 역할이 교환된 대칭 관계에 있다.

알고리즘 단계	Sequence	Fallback
다음 자식 진행 조건	현재 자식 SUCCESS	현재 자식 FAILURE
조기 종료 조건	현재 자식 FAILURE	현재 자식 SUCCESS
모든 자식 평가 완료 시	SUCCESS 반환	FAILURE 반환
RUNNING 처리	RUNNING 반환	RUNNING 반환

이 대칭성은 두 알고리즘의 구조가 동일하며, SUCCESS와 FAILURE의 역할만 교환되었음을 의미한다.

5. 실행 추적 예시

5.1 예시 1: 첫 번째 자식 성공

자식: [ActionA, ActionB, ActionC]

tick() 호출:
  i=0: ActionA.executeTick() → SUCCESS
  → return SUCCESS    (ActionB, ActionC 미평가)

5.2 예시 2: 두 번째 자식 성공

tick() 호출:
  i=0: ActionA.executeTick() → FAILURE
  i=1: ActionB.executeTick() → SUCCESS
  → return SUCCESS    (ActionC 미평가)

5.3 예시 3: 비동기 자식 RUNNING

tick() 호출:
  i=0: ActionA.executeTick() → FAILURE
  i=1: ActionB.executeTick() → RUNNING
  → return RUNNING    (ActionC 미평가)

5.4 예시 4: 모든 자식 실패

tick() 호출:
  i=0: ActionA.executeTick() → FAILURE
  i=1: ActionB.executeTick() → FAILURE
  i=2: ActionC.executeTick() → FAILURE
  → return FAILURE

6. WithMemory 변형의 알고리즘

FallbackWithMemory의 알고리즘은 current_child_idx를 사용하여 RUNNING 자식의 인덱스를 기억한다.

function FallbackWithMemory.tick():
    for i ← current_child_idx to N-1:
        status ← children[i].executeTick()
        if status == RUNNING:
            current_child_idx ← i
            return RUNNING
        else if status == SUCCESS:
            current_child_idx ← 0
            haltChildren()
            return SUCCESS
    // 모든 자식 FAILURE
    current_child_idx ← 0
    return FAILURE

6.1 WithMemory 실행 추적

자식: [ActionA, ActionB, ActionC]

Tick 1:
  i=0: ActionA.executeTick() → FAILURE
  i=1: ActionB.executeTick() → RUNNING
  current_child_idx ← 1
  → return RUNNING

Tick 2:
  i=1: ActionB.executeTick() → RUNNING    (ActionA 건너뜀)
  → return RUNNING

Tick 3:
  i=1: ActionB.executeTick() → FAILURE    (ActionA 건너뜀)
  i=2: ActionC.executeTick() → SUCCESS
  current_child_idx ← 0
  → return SUCCESS

7. Reactive 변형의 알고리즘

ReactiveFallback의 알고리즘은 매 Tick에서 항상 인덱스 0부터 평가를 시작한다.

function ReactiveFallback.tick():
    for i ← 0 to N-1:
        status ← children[i].executeTick()
        if status == RUNNING:
            for j ← i+1 to N-1:
                haltChild(j)
            return RUNNING
        else if status == SUCCESS:
            resetChildren()
            return SUCCESS
    resetChildren()
    return FAILURE

7.1 Reactive 실행 추적

자식: [CondA, CondB, AsyncAct]

Tick 1:
  i=0: CondA.executeTick() → FAILURE
  i=1: CondB.executeTick() → FAILURE
  i=2: AsyncAct.executeTick() → RUNNING
  → return RUNNING

Tick 2:
  i=0: CondA.executeTick() → SUCCESS    (재평가 — 우선순위 높은 대안 성공)
  resetChildren()
  → return SUCCESS    (AsyncAct Halt)

ReactiveFallback에서는 이전에 FAILURE였던 앞쪽 자식이 SUCCESS로 변하면, 뒤쪽의 RUNNING 자식이 Halt되고 SUCCESS가 반환된다. 이는 우선순위가 높은 대안이 가용해지면 즉시 전환하는 동작이다.

8. 시간 복잡도

경우	노드 방문 수
최선 (첫 자식 SUCCESS)	$O(1)$
최악 (모든 자식 FAILURE)	$O(N)$
평균 (k번째 자식에서 종료)	$O(k)$

Fallback의 시간 복잡도는 Sequence와 동일한 구조를 가지며, 조기 종료의 효과는 자식 배치 순서에 의존한다.

참고 문헌

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/