1293.35 ReactiveFallback 노드에서의 Tick 전파

1. ReactiveFallback의 정의

ReactiveFallback은 행동 트리(Behavior Tree)에서 WithoutMemory 속성을 가지는 Fallback 노드의 변형이다. 표준 Fallback(WithMemory)이 이전에 FAILURE를 반환한 자식을 건너뛰고 RUNNING 중인 자식부터 재개하는 것과 달리, ReactiveFallback은 매 Tick마다 첫 번째 자식부터 모든 자식을 재평가한다. 이를 통해 상위 우선순위 대안이 다시 사용 가능해지면 즉시 해당 대안으로 전환하는 우선순위 기반 행동 선택을 구현한다(Colledanchise & Ogren, 2018).

2. Tick 전파 알고리즘

function ReactiveFallback.tick():
    for each child in children (왼쪽에서 오른쪽):
        child_status = child.tick()
        
        if child_status == RUNNING:
            haltChildrenAfter(current_index + 1)
            return RUNNING
        
        if child_status == SUCCESS:
            haltRunningChildren()
            return SUCCESS
    
    return FAILURE

2.1 핵심 동작

1. 매 Tick마다 첫 번째 자식부터 시작: 이전 Tick의 상태와 무관하게 항상 인덱스 0부터 자식을 Tick한다.
2. 자식이 SUCCESS 반환 시: 즉시 SUCCESS를 반환하고, RUNNING 중인 하위 자식에 Halt를 호출한다.
3. 자식이 RUNNING 반환 시: 해당 자식 이후의 자식은 Tick하지 않고 RUNNING을 반환하며, 이후 인덱스의 RUNNING 중인 자식에 Halt를 호출한다.
4. 모든 자식이 FAILURE: 모든 자식이 FAILURE를 반환하면 FAILURE를 반환한다.

3. ReactiveSequence와의 대칭 구조

ReactiveFallback의 Tick 전파 알고리즘은 ReactiveSequence와 대칭적 관계에 있다. 두 노드 모두 매 Tick마다 첫 번째 자식부터 재평가하지만, 전파를 중단하는 조건이 상반된다.

4. 구체적 실행 흐름 예시

다음과 같은 ReactiveFallback 구조를 가정한다.

ReactiveFallback
├── UseHighPrecisionSensor (우선 전략)
├── UseLowPrecisionSensor  (대안 전략)
└── UseDeadReckoning       (최후 수단)

4.1 정상 실행 흐름

첫 번째 자식이 SUCCESS를 반환하면, 나머지 자식은 Tick되지 않으며 ReactiveFallback은 즉시 SUCCESS를 반환한다.

4.2 우선 전략 실패 시 대안 사용

고정밀 센서가 실패하면, 저정밀 센서가 대안으로 사용된다.

4.3 비동기 대안의 실행

두 번째 자식이 RUNNING을 반환하면, 세 번째 자식은 Tick되지 않고 ReactiveFallback은 RUNNING을 반환한다.

4.4 우선순위 복귀

Tick 3에서 고정밀 센서가 복구되어 SUCCESS를 반환하면, ReactiveFallback은 즉시 SUCCESS를 반환하고 RUNNING 중이던 저정밀 센서에 Halt를 호출한다. 이것이 ReactiveFallback의 우선순위 복귀(priority restoration) 메커니즘이다.

5. 우선순위 복귀의 상세 메커니즘

ReactiveFallback에서 우선순위 복귀가 발생하는 과정을 단계별로 분석한다.

Tick N-1:
  Child_0.tick() → FAILURE     (우선 전략 사용 불가)
  Child_1.tick() → RUNNING     (대안 전략 실행 중)
  → ReactiveFallback 반환: RUNNING

Tick N:
  Child_0.tick() → SUCCESS     (우선 전략 복구!)
  → Child_1에 Halt 호출        (대안 전략 중단)
  → ReactiveFallback 반환: SUCCESS

이 메커니즘에서 핵심적인 관찰은 다음과 같다.

1. Tick N에서 Child_0이 다시 Tick된다: WithMemory Fallback에서는 Child_0이 이미 FAILURE를 반환하였으므로 건너뛰어지지만, ReactiveFallback에서는 매 Tick마다 재평가된다.
2. Child_1에 Halt가 호출된다: Child_0이 SUCCESS를 반환하였으므로 Child_1은 Tick될 필요가 없으며, RUNNING 상태였던 Child_1은 Halt되어 IDLE 상태로 리셋된다.
3. Child_1은 이전 진행 상태를 소실한다: Halt에 의해 IDLE로 리셋되므로, 후속 Tick에서 다시 FAILURE → RUNNING 경로로 진입하면 처음부터 재시작된다.

6. 조건 노드와 액션 노드의 혼합 배치

ReactiveFallback에서 조건 노드와 액션 노드를 혼합하여 배치하는 패턴은, 조건이 충족되면 즉시 해당 경로를 선택하고, 조건이 모두 실패하면 기본 액션을 수행하는 구조를 형성한다.

<ReactiveFallback>
    <IsAtGoal/>                <!-- 조건: 이미 목표 도달? -->
    <NavigateToGoal/>          <!-- 액션: 목표로 이동 -->
</ReactiveFallback>

이 구조에서 로봇이 목표 지점에 도달하면 IsAtGoal이 SUCCESS를 반환하여 네비게이션이 즉시 중단된다. 로봇이 외력에 의해 목표 지점에서 이탈하면, 다음 Tick에서 IsAtGoal이 FAILURE를 반환하여 NavigateToGoal이 다시 시작된다.

7. ReactiveFallback에서의 Halt 전파

ReactiveFallback에서 Halt가 발생하는 시나리오는 두 가지이다.

7.1 상위 우선순위 자식의 성공에 의한 Halt

앞선 자식이 SUCCESS를 반환하면, 현재 RUNNING 중인 하위 자식에 Halt가 호출된다.

Child_0: FAILURE → SUCCESS  (복구)
Child_1: RUNNING → Halt     (중단)

7.2 앞선 자식의 RUNNING에 의한 Halt

앞선 자식이 RUNNING을 반환하면, 이후 인덱스에서 RUNNING 중인 자식에 Halt가 호출된다.

Tick N-1:
  Child_0: FAILURE, Child_1: FAILURE, Child_2: RUNNING
  → RUNNING

Tick N:
  Child_0: FAILURE, Child_1: RUNNING
  → Child_2에 Halt 호출 (이전 Tick에서 RUNNING이었으므로)
  → RUNNING

이 경우 더 높은 우선순위의 Child_1이 RUNNING 상태가 되었으므로, 하위 우선순위의 Child_2는 중단되어야 한다.

8. WithMemory Fallback과의 비교

9. Tick 전파의 비용 분석

ReactiveFallback에서 매 Tick의 실행 비용은 첫 번째 자식부터 현재 활성 자식까지의 평가 비용의 합이다.

T_{reactive\_fb} = \sum_{i=0}^{j} T_{child_i}

여기서 j는 현재 Tick에서 SUCCESS 또는 RUNNING을 반환한 최초의 자식 인덱스이다. 앞선 자식들이 모두 경량 조건 노드인 경우, 추가 비용은 미미하다. 그러나 앞선 자식이 비동기 액션 노드인 경우, 해당 노드의 재평가가 매 Tick마다 발생하므로 비용이 증가할 수 있다.

10. 설계 시 고려 사항

10.1 빈번한 우선순위 전환 방지

상위 자식의 반환 상태가 SUCCESS와 FAILURE 사이에서 빈번하게 진동하면, 하위 자식에 대한 반복적인 Halt와 재시작이 발생하여 어떤 대안도 완료되지 못하는 상황이 발생할 수 있다. 이를 방지하기 위해 조건 노드에 히스테리시스(hysteresis)를 적용하거나, 상태 전환에 최소 지속 시간을 부여하는 방법을 사용한다.

10.2 비동기 자식의 배치 순서

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/