1294.6 Sequence 노드의 실행 알고리즘

1. 알고리즘의 개요

Sequence 노드의 실행 알고리즘은 자식 노드들을 왼쪽에서 오른쪽으로 순차적으로 Tick하며, 각 자식의 반환 상태에 따라 계속 진행할지 중단할지를 결정하는 반복 절차이다. 이 알고리즘은 단순하고 직관적이면서도, 행동 트리의 핵심 의미론인 순차 실행과 조기 종료를 정확히 구현한다(Colledanchise & Ogren, 2018).

2. 기본 실행 알고리즘

2.1 단계별 절차

1. 현재 자식 인덱스를 시작 위치로 설정한다.
2. 현재 자식에게 Tick을 전달하고 반환 상태를 수신한다.
3. 반환 상태를 확인한다:

• FAILURE: Sequence는 즉시 FAILURE를 반환한다. 이후의 자식은 Tick하지 않는다.
• RUNNING: Sequence는 RUNNING을 반환한다. 이후의 자식은 Tick하지 않는다.
• SUCCESS: 다음 자식으로 이동하여 단계 2로 돌아간다.

4. 모든 자식이 SUCCESS를 반환하면 Sequence는 SUCCESS를 반환한다.

2.2 의사 코드

function Sequence.tick():
    for i = start_index to N-1:
        status = children[i].executeTick()
        
        if status == FAILURE:
            // RUNNING 중인 이후 자식이 있다면 Halt
            haltRunningChildren()
            return FAILURE
        
        if status == RUNNING:
            return RUNNING
        
        // status == SUCCESS → 다음 자식으로 진행
    
    // 모든 자식이 SUCCESS
    return SUCCESS

3. 시작 인덱스의 결정

시작 인덱스(start_index)는 Sequence의 변형에 따라 다르게 결정된다.

WithMemory 모드에서는 이전 Tick에서 SUCCESS를 반환한 자식을 건너뛰고, RUNNING이었던 자식부터 재개한다. 이를 위해 내부적으로 현재 자식 인덱스를 멤버 변수로 유지한다.

4. 알고리즘의 상세 실행 흐름

4.1 예시 트리

<Sequence>
    <Condition ID="CondA"/>   <!-- 자식 0 -->
    <Condition ID="CondB"/>   <!-- 자식 1 -->
    <Action ID="ActionC"/>    <!-- 자식 2 -->
</Sequence>

4.2 시나리오 1: 전체 성공

Tick:
  i=0: CondA.tick() → SUCCESS → 다음으로
  i=1: CondB.tick() → SUCCESS → 다음으로
  i=2: ActionC.tick() → SUCCESS → 다음으로
  모든 자식 SUCCESS → Sequence 반환: SUCCESS

4.3 시나리오 2: 중간 실패

Tick:
  i=0: CondA.tick() → SUCCESS → 다음으로
  i=1: CondB.tick() → FAILURE → 즉시 반환
  i=2: ActionC → (Tick되지 않음)
  Sequence 반환: FAILURE

4.4 시나리오 3: RUNNING 후 재진입 (WithMemory)

Tick 1:
  i=0: CondA.tick() → SUCCESS → 다음으로
  i=1: CondB.tick() → SUCCESS → 다음으로
  i=2: ActionC.tick() → RUNNING → current_index = 2
  Sequence 반환: RUNNING

Tick 2 (start_index = 2):
  i=2: ActionC.tick() → SUCCESS → 다음으로
  모든 자식 완료 → Sequence 반환: SUCCESS

4.5 시나리오 4: RUNNING 후 재진입 (Reactive)

Tick 1:
  i=0: CondA.tick() → SUCCESS → 다음으로
  i=1: CondB.tick() → SUCCESS → 다음으로
  i=2: ActionC.tick() → RUNNING
  Sequence 반환: RUNNING

Tick 2 (start_index = 0):
  i=0: CondA.tick() → SUCCESS → 다음으로
  i=1: CondB.tick() → FAILURE → 즉시 반환
       ActionC가 RUNNING 중이므로 Halt 호출
  Sequence 반환: FAILURE

ReactiveSequence에서는 매 Tick마다 첫 번째 자식부터 재평가하므로, 중간의 조건 변화를 감지할 수 있다.

5. RUNNING 자식의 Halt 처리

Sequence가 FAILURE를 반환하기로 결정했을 때, 현재 RUNNING 상태인 자식이 존재하면 해당 자식에게 Halt를 전달하여 진행 중인 작업을 중단시킨다.

// Sequence의 tick() 내부에서
if (child_status == NodeStatus::FAILURE) {
    // 이전에 RUNNING이었던 자식들을 Halt
    haltChildren(current_index + 1);
    return NodeStatus::FAILURE;
}

이 Halt 처리는 ReactiveSequence에서 특히 중요하다. 조건 노드의 재평가에서 FAILURE가 발생하면, 이미 RUNNING 중인 액션 노드를 반드시 중단해야 한다.

6. 알고리즘의 시간 복잡도

단일 Tick에서의 Sequence 알고리즘 시간 복잡도는 다음과 같다.

• 최선의 경우: O(1) — 첫 번째 자식이 FAILURE를 반환
• 최악의 경우: O(N) — 모든 자식이 SUCCESS를 반환 (N은 자식 수)
• 평균의 경우: O(k) — k번째 자식에서 결과가 확정 (1 \leq k \leq N)

WithMemory 모드에서는 이전 Tick에서 완료된 자식을 건너뛰므로, 전체 임무 수행 과정에서의 총 방문 노드 수가 ReactiveSequence보다 적다.

참고 문헌

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