1293.29 Fallback 노드에서의 Tick 전파

1. Fallback 노드의 정의

Fallback 노드(Selector 노드라고도 함)는 행동 트리(Behavior Tree)에서 자식 노드들을 왼쪽에서 오른쪽으로 순차적으로 시도하며, 하나의 자식이라도 SUCCESS를 반환하면 자신도 SUCCESS를 반환하는 제어 노드이다. Fallback 노드는 논리 OR 연산에 대응하며, “이 중 하나라도 성공하면 된다“는 의미론을 가진다. 이 이름은 첫 번째 대안이 실패할 경우 다음 대안으로 ’후퇴(fallback)’하는 동작에서 유래한다(Colledanchise & Ogren, 2018).

2. Tick 전파 알고리즘

Fallback 노드가 Tick을 수신하면, 다음 알고리즘에 따라 자식 노드에 Tick을 전파한다.

function Fallback.tick():
    for each child in children (왼쪽에서 오른쪽):
        child_status = child.tick()
        
        if child_status == RUNNING:
            return RUNNING
        
        if child_status == SUCCESS:
            return SUCCESS
    
    // 모든 자식이 FAILURE를 반환한 경우
    return FAILURE

이 알고리즘의 핵심 동작은 다음과 같다.

1. 첫 번째 자식부터 순서대로 Tick을 전파한다.
2. 자식이 FAILURE를 반환하면 다음 자식으로 진행한다(대안 시도).
3. 자식이 SUCCESS를 반환하면 나머지 자식을 Tick하지 않고 즉시 SUCCESS를 반환한다(조기 종료).
4. 자식이 RUNNING을 반환하면 나머지 자식을 Tick하지 않고 RUNNING을 반환한다.
5. 모든 자식이 FAILURE를 반환하면 FAILURE를 반환한다.

3. Sequence와의 대칭 관계

Fallback 노드의 Tick 전파 규칙은 Sequence 노드와 정확히 대칭적이다.

이 대칭성을 통해 Sequence와 Fallback을 조합하면 복잡한 조건부 행동 로직을 구성할 수 있다.

4. 구체적 실행 흐름 예시

다음과 같은 Fallback 노드 구조를 가정한다.

Fallback
├── Strategy_A (비동기 액션)
├── Strategy_B (비동기 액션)
└── Strategy_C (동기 액션)

4.1 시나리오 1: 첫 번째 대안이 성공

Strategy_A가 SUCCESS를 반환하면, Strategy_B와 Strategy_C는 시도하지 않는다.

4.2 시나리오 2: 첫 번째 실패, 두 번째 성공

*WithMemory 모드에서 이미 FAILURE인 자식은 재평가하지 않음

4.3 시나리오 3: 모든 대안 실패

모든 대안이 실패하면 Fallback 전체가 FAILURE를 반환한다.

5. Fallback의 메모리 모드별 동작

5.1 FallbackWithMemory

이전 Tick에서 FAILURE를 반환한 자식의 다음 인덱스를 기억하고, 후속 Tick에서 해당 인덱스부터 재개한다. 이미 FAILURE를 반환한 자식은 재시도하지 않는다.

Tick 1: Fallback[Memory]
  → Child_0.tick() → FAILURE  (인덱스 기억: 1)
  → Child_1.tick() → RUNNING  (인덱스 기억: 1)
  반환: RUNNING

Tick 2: Fallback[Memory]
  → Child_1.tick() → RUNNING  (Child_0 건너뜀)
  반환: RUNNING

5.2 ReactiveFallback

매 Tick마다 첫 번째 자식부터 모든 자식을 재평가한다. 이전에 FAILURE를 반환한 자식도 다시 Tick된다.

Tick 1: ReactiveFallback
  → Child_0.tick() → FAILURE
  → Child_1.tick() → RUNNING
  반환: RUNNING

Tick 2: ReactiveFallback
  → Child_0.tick() → SUCCESS  (재평가, 조건 변화)
  → Child_1에 Halt 호출       (RUNNING 중인 자식 중단)
  반환: SUCCESS

ReactiveFallback에서 이전에 FAILURE였던 자식이 SUCCESS로 전환되면, 현재 RUNNING 중인 하위 우선순위 자식이 Halt되고 우선순위가 높은 전략이 즉시 채택된다.

6. Fallback에서의 Halt 전파

6.1 SUCCESS에 의한 조기 종료 시 Halt

Fallback의 자식이 SUCCESS를 반환하면, 다른 자식 중 RUNNING 상태인 노드에 Halt가 호출된다. 이는 ReactiveFallback에서 우선순위가 높은 자식이 다시 성공하여 하위 자식의 실행이 불필요해지는 경우에 발생한다.

6.2 외부 Halt

Fallback 노드 자체가 부모 노드로부터 Halt를 수신하면, RUNNING 상태인 자식에 Halt를 전파한다.

7. Fallback 노드의 사용 패턴

7.1 대안적 행동 전략

동일한 목표를 달성하기 위한 복수의 전략을 우선순위 순서로 시도한다.

<Fallback>
    <NavigateDirectly goal="{target}"/>     <!-- 직선 이동 시도 -->
    <NavigateAroundObstacle goal="{target}"/>  <!-- 우회 이동 시도 -->
    <RequestHumanAssistance/>               <!-- 최후 수단 -->
</Fallback>

7.2 조건 분기

조건에 따라 다른 행동을 수행하는 if-else 구조를 구현한다.

<Fallback>
    <Sequence>
        <IsObjectNear/>
        <PickObject/>
    </Sequence>
    <Sequence>
        <IsObjectFar/>
        <MoveToObject/>
    </Sequence>
</Fallback>

첫 번째 Sequence의 조건이 충족되면 해당 행동을 수행하고, 그렇지 않으면 두 번째 Sequence의 조건을 평가한다.

8. Fallback의 반환 상태 요약

참고 문헌

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