1293.41 WithMemory Fallback의 Tick 재진입 규칙

1. 재진입 규칙의 정의

WithMemory Fallback의 Tick 재진입 규칙이란, 이전 Tick에서 자식 노드가 RUNNING을 반환한 경우 후속 Tick에서 해당 자식에 직접 Tick을 전달하고, 이전에 FAILURE를 반환한 자식들을 건너뛰는 동작 규칙이다. 이 규칙은 Fallback 노드의 메모리 인덱스를 통해 구현되며, 이미 실패한 것으로 판명된 대안의 불필요한 재시도를 방지한다(Colledanchise & Ogren, 2018).

2. 재진입 알고리즘

WithMemory Fallback의 Tick 재진입은 다음 알고리즘에 따라 수행된다.

function FallbackWithMemory.tick():
    // current_index는 클래스 멤버 변수 (메모리)
    while current_index < children.size():
        child_status = children[current_index].tick()
        
        if child_status == RUNNING:
            return RUNNING              // current_index 유지
        
        if child_status == SUCCESS:
            haltRunningChildren()
            current_index = 0           // 리셋
            return SUCCESS
        
        // FAILURE: 다음 대안으로 진행
        current_index++
    
    current_index = 0                   // 리셋
    return FAILURE

핵심은 current_index가 Tick 간에 유지된다는 것이다. 자식이 RUNNING을 반환하면 current_index가 해당 자식의 인덱스를 유지하고, 다음 Tick에서 이전에 FAILURE를 반환한 자식들을 건너뛰어 RUNNING 중인 자식부터 Tick을 재개한다.

3. Sequence와의 대칭 관계

WithMemory Fallback의 재진입 규칙은 WithMemory Sequence의 재진입 규칙과 대칭적이다.

4. 구체적 실행 흐름 추적

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

Fallback (WithMemory)
├── Child_0: NavigateDirect      (비동기, 직선 경로)
├── Child_1: NavigateDetour      (비동기, 우회 경로)
└── Child_2: WaitAndRetry        (비동기, 대기 후 재시도)

4.1 첫 번째 대안 실패 후 두 번째 대안 시도

Tick 1: current_index=0
  Child_0.tick() → RUNNING      (직선 경로 시도 중)
  반환: RUNNING

Tick 2: current_index=0
  Child_0.tick() → FAILURE      (직선 경로 차단됨)
  current_index=1
  Child_1.tick() → RUNNING      (우회 경로 시작)
  반환: RUNNING

Tick 3: current_index=1          (Child_0 건너뜀)
  Child_1.tick() → RUNNING      (우회 경로 진행 중)
  반환: RUNNING

Tick 4: current_index=1          (Child_0 건너뜀)
  Child_1.tick() → SUCCESS      (우회 경로 도착)
  current_index=0 (리셋)
  반환: SUCCESS

Tick 3과 4에서 Child_0은 건너뛰어진다. 이전 Tick에서 이미 FAILURE를 반환하였으므로, 직선 경로가 여전히 차단되어 있을 가능성이 높기 때문에 재시도하지 않는 것이 합리적이다.

4.2 모든 대안 실패

Tick 1: current_index=0
  Child_0.tick() → FAILURE      (직선 경로 실패)
  current_index=1
  Child_1.tick() → FAILURE      (우회 경로 실패)
  current_index=2
  Child_2.tick() → RUNNING      (대기 시작)
  반환: RUNNING

Tick 2: current_index=2          (Child_0, Child_1 건너뜀)
  Child_2.tick() → FAILURE      (대기 후에도 실패)
  current_index=0 (리셋)
  반환: FAILURE

5. 성공 시 재진입 규칙

WithMemory Fallback에서 자식이 SUCCESS를 반환하면, 메모리 인덱스가 0으로 리셋되고 Fallback 전체가 SUCCESS를 반환한다. 다음 Tick에서 Fallback이 다시 Tick되면, 첫 번째 자식(가장 우선순위가 높은 대안)부터 시작한다.

Tick 4: current_index=1
  Child_1.tick() → SUCCESS      (우회 경로 성공)
  current_index=0 (리셋)
  반환: SUCCESS

(상위 트리에 의해 다시 Tick될 경우)
Tick 5: current_index=0           (처음부터 재시작)
  Child_0.tick() → RUNNING      (직선 경로 재시도)
  반환: RUNNING

SUCCESS에 의한 리셋은 모든 대안의 실패 기록을 무효화하므로, 다음 실행 시 가장 우선순위가 높은 대안부터 다시 시도한다.

6. Halt 시 재진입 규칙

WithMemory Fallback에 Halt가 호출되면, 메모리 인덱스가 0으로 리셋되고 RUNNING 중인 자식에 Halt가 전파된다.

void FallbackWithMemory::halt() {
    current_child_index_ = 0;    // 메모리 리셋
    ControlNode::halt();         // 자식에 Halt 전파
}

7. 건너뛰는 자식의 상태 추적

8. WithMemory Fallback의 한계

WithMemory Fallback의 재진입 규칙은 이전에 실패한 대안이 이후에 사용 가능해지더라도 이를 감지하지 못한다는 한계가 있다.

Tick 1: Child_0(FAILURE), Child_1(RUNNING) → current_index=1
Tick 2: Child_0(건너뜀), Child_1(RUNNING) → current_index=1
  ↑ Child_0의 실패 원인이 해소되었더라도 감지 불가

이러한 상황에서 상위 우선순위 대안으로의 복귀가 필요한 경우에는 ReactiveFallback을 사용해야 한다. WithMemory Fallback은 이전 대안의 재시도가 무의미하거나 비용이 높은 경우에 적합하다.

9. 교착 방지를 위한 타임아웃 적용

WithMemory Fallback에서 현재 시도 중인 대안이 무한히 RUNNING을 유지하는 경우, 후속 대안으로의 전환이 이루어지지 않는 교착 상태가 발생할 수 있다. 이를 방지하기 위해 각 대안에 Timeout 데코레이터를 적용하여, 일정 시간 내에 완료되지 않으면 FAILURE를 반환하도록 한다.

<Fallback>
    <Timeout msec="10000">
        <NavigateDirect goal="{target}"/>
    </Timeout>
    <Timeout msec="20000">
        <NavigateDetour goal="{target}"/>
    </Timeout>
    <WaitAndRetry duration="5000"/>
</Fallback>

이 구조에서 직선 경로 시도는 10초, 우회 경로 시도는 20초의 시간 제한을 가지며, 제한 시간을 초과하면 자동으로 다음 대안으로 전환된다.

10. 적용 사례

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