1293.40 WithMemory Sequence의 Tick 재진입 규칙

1. 재진입 규칙의 정의

WithMemory Sequence의 Tick 재진입 규칙이란, 이전 Tick에서 자식 노드가 RUNNING을 반환한 경우 후속 Tick에서 해당 자식에 직접 Tick을 전달하고, 이전에 SUCCESS를 반환한 자식들을 건너뛰는 동작 규칙이다. 이 규칙은 Sequence 노드의 메모리 인덱스를 통해 구현되며, 순차적 작업 수행에서 이미 완료된 단계의 불필요한 재실행을 방지한다(Colledanchise & Ogren, 2018).

2. 재진입 알고리즘

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

function SequenceWithMemory.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 == FAILURE:
            haltRunningChildren()
            current_index = 0           // 리셋
            return FAILURE
        
        // SUCCESS: 다음 자식으로 진행
        current_index++
    
    current_index = 0                   // 리셋
    return SUCCESS

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

3. 구체적 실행 흐름 추적

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

Sequence (WithMemory)
├── Child_0: CheckPrecondition  (동기)
├── Child_1: MoveToPosition     (비동기)
├── Child_2: GraspObject        (비동기)
└── Child_3: ReturnToBase       (비동기)

3.1 단계별 실행 흐름

Tick 1: current_index=0
  Child_0.tick() → SUCCESS      (전제 조건 확인)
  current_index=1
  Child_1.tick() → RUNNING      (이동 시작)
  반환: RUNNING

Tick 2: current_index=1          (Child_0 건너뜀)
  Child_1.tick() → RUNNING      (이동 중)
  반환: RUNNING

Tick 3: current_index=1          (Child_0 건너뜀)
  Child_1.tick() → SUCCESS      (이동 완료)
  current_index=2
  Child_2.tick() → RUNNING      (파지 시작)
  반환: RUNNING

Tick 4: current_index=2          (Child_0, Child_1 건너뜀)
  Child_2.tick() → RUNNING      (파지 중)
  반환: RUNNING

Tick 5: current_index=2          (Child_0, Child_1 건너뜀)
  Child_2.tick() → SUCCESS      (파지 완료)
  current_index=3
  Child_3.tick() → RUNNING      (복귀 시작)
  반환: RUNNING

Tick 6: current_index=3          (Child_0, Child_1, Child_2 건너뜀)
  Child_3.tick() → SUCCESS      (복귀 완료)
  current_index=0 (리셋)
  반환: SUCCESS

4. 재진입 시 건너뛰는 자식의 상태

WithMemory Sequence에서 건너뛰어지는 자식은 이전 Tick에서 SUCCESS를 반환한 자식이다. 이 자식들은 후속 Tick에서 Tick을 수신하지 않으며, 자신의 마지막 반환 상태(SUCCESS)를 유지한다.

5. 실패 시 재진입 규칙

WithMemory Sequence에서 자식이 FAILURE를 반환하면, 메모리 인덱스가 0으로 리셋되고 Sequence 전체가 FAILURE를 반환한다. 다음 Tick에서 Sequence가 다시 Tick되면, 첫 번째 자식부터 시작한다.

Tick 3: current_index=1
  Child_1.tick() → SUCCESS
  current_index=2
  Child_2.tick() → FAILURE      (파지 실패)
  current_index=0 (리셋)
  반환: FAILURE

Tick 4: current_index=0           (처음부터 재시작)
  Child_0.tick() → SUCCESS
  current_index=1
  Child_1.tick() → RUNNING
  반환: RUNNING

FAILURE에 의한 리셋은 이전에 성공한 모든 단계를 무효화한다. 따라서 Tick 4에서 Child_0이 다시 평가되고, Child_1도 처음부터 재시작된다.

6. Halt 시 재진입 규칙

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

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

Halt 후 다음 Tick에서 Sequence가 다시 Tick되면, 첫 번째 자식부터 시작한다. 이는 FAILURE 시의 리셋과 동일한 효과를 가진다.

7. 재진입과 부수 효과

WithMemory Sequence의 재진입 규칙에서 중요한 고려 사항은 건너뛰어지는 자식의 부수 효과(side effect)이다. 이전에 SUCCESS를 반환한 자식이 물리적 작업(모터 구동, 센서 캘리브레이션 등)을 수행한 경우, 해당 작업의 결과가 후속 자식의 실행에 유효하다는 전제가 필요하다.

7.1 유효한 경우

<Sequence>
    <CalibrateIMU/>        <!-- 한 번 수행하면 유효 -->
    <NavigateToGoal/>      <!-- IMU 캘리브레이션 결과 사용 -->
</Sequence>

IMU 캘리브레이션은 한 번 수행되면 일정 시간 동안 유효하므로, NavigateToGoal이 RUNNING 중일 때 CalibrateIMU를 재실행할 필요가 없다.

7.2 주의가 필요한 경우

<Sequence>
    <OpenDoor/>            <!-- 문 열기: 시간이 지나면 닫힐 수 있음 -->
    <WalkThroughDoor/>     <!-- 문 통과 -->
</Sequence>

문을 열어놓은 상태가 시간 경과로 변할 수 있는 경우, WithMemory Sequence는 문이 닫혔음을 감지하지 못한다. 이런 경우에는 ReactiveSequence가 더 적합하다.

8. Tick당 실행 비용

WithMemory Sequence의 재진입 규칙에 따른 Tick당 실행 비용은 현재 활성 자식만의 Tick 비용이다.

T_{tick} = T_{child_{current\_index}}

이전에 완료된 자식들은 Tick되지 않으므로 추가 비용이 발생하지 않는다. 이는 ReactiveSequence가 매 Tick마다 모든 조건 노드를 재평가하는 것에 비해 효율적이다.

T_{reactive} = \sum_{i=0}^{current\_index} T_{child_i} \quad \geq \quad T_{memory} = T_{child_{current\_index}}

9. 적용 사례

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