1294.17 SequenceWithMemory의 실행 알고리즘

1. 알고리즘 개요

SequenceWithMemory의 실행 알고리즘은 기본 Sequence 알고리즘에 재진입 메커니즘을 추가한 것이다. 핵심은 내부 상태 변수 current_child_idx를 유지하여, 이전 Tick에서 RUNNING을 반환한 자식의 위치를 기억하고 다음 Tick에서 해당 위치부터 실행을 재개하는 것이다(Colledanchise & Ogren, 2018).

2. 알고리즘의 형식적 기술

2.1 입력과 출력

입력: 자식 노드 배열 $C_0, C_1, \ldots, C_{N-1}$
내부 상태: current_child_idx (초기값 0)
출력: SUCCESS, FAILURE, 또는 RUNNING

2.2 단계별 절차

Algorithm: SequenceWithMemory.tick()

Input: children[0..N-1], current_child_idx
Output: NodeStatus

1.  i ← current_child_idx
2.  while i < N do
3.      status ← children[i].executeTick()
4.      
5.      if status = SUCCESS then
6.          i ← i + 1
7.      else if status = RUNNING then
8.          current_child_idx ← i
9.          return RUNNING
10.     else if status = FAILURE then
11.         haltChildren(0, N-1)
12.         current_child_idx ← 0
13.         return FAILURE
14.     end if
15. end while
16. 
17. haltChildren(0, N-1)
18. current_child_idx ← 0
19. return SUCCESS

3. 알고리즘의 상세 분석

3.1 초기 진입 (current_child_idx = 0)

Sequence가 처음 Tick될 때(또는 이전 실행이 완료된 후 다시 Tick될 때), current_child_idx는 0이므로 첫 번째 자식부터 실행한다.

최초 Tick:
  i = 0 → children[0].tick()
  결과에 따라 진행 또는 반환

3.2 재진입 (current_child_idx > 0)

이전 Tick에서 자식 $C_k$ 가 RUNNING을 반환한 경우, current_child_idx는 $k$ 로 설정되어 있다. 다음 Tick에서 $C_k$ 부터 실행을 재개한다. $C_0$ 부터 $C_{k-1}$ 까지는 평가되지 않는다.

재진입 (current_child_idx = 2):
  i = 2 → children[2].tick()
  children[0], children[1]은 건너뜀

3.3 SUCCESS 처리 (행 5-6)

자식이 SUCCESS를 반환하면 인덱스를 증가시켜 다음 자식으로 이동한다. 이 과정은 동일한 Tick 내에서 연속적으로 수행된다. 즉, 한 자식이 SUCCESS를 반환하면 즉시 다음 자식에게 Tick이 전달된다.

3.4 RUNNING 처리 (행 7-9)

자식이 RUNNING을 반환하면 해당 인덱스를 current_child_idx에 저장하고 RUNNING을 반환한다. 이 시점에서 Tick이 종료되며, 이후의 자식에게는 Tick이 전달되지 않는다.

3.5 FAILURE 처리 (행 10-13)

자식이 FAILURE를 반환하면, 모든 자식을 Halt하고 current_child_idx를 0으로 초기화한 후 FAILURE를 반환한다. Halt는 RUNNING 상태인 자식의 비동기 작업을 중단하고 상태를 IDLE로 초기화한다.

3.6 전체 완료 처리 (행 17-19)

모든 자식이 SUCCESS를 반환하여 루프가 완료되면, 모든 자식을 Halt(IDLE로 초기화)하고 current_child_idx를 0으로 초기화한 후 SUCCESS를 반환한다.

4. 실행 추적 예시

4.1 개 자식, 자식 1과 3이 비동기

<Sequence>
    <Condition ID="CondA"/>        <!-- 자식 0: 동기 -->
    <Action ID="AsyncActB"/>       <!-- 자식 1: 비동기 -->
    <Condition ID="CondC"/>        <!-- 자식 2: 동기 -->
    <Action ID="AsyncActD"/>       <!-- 자식 3: 비동기 -->
</Sequence>

Tick 1 (current_child_idx = 0):
  i=0: CondA → SUCCESS, i=1
  i=1: AsyncActB → RUNNING
  current_child_idx = 1, return RUNNING

Tick 2 (current_child_idx = 1):
  i=1: AsyncActB → RUNNING
  return RUNNING

Tick 3 (current_child_idx = 1):
  i=1: AsyncActB → SUCCESS, i=2
  i=2: CondC → SUCCESS, i=3
  i=3: AsyncActD → RUNNING
  current_child_idx = 3, return RUNNING

Tick 4 (current_child_idx = 3):
  i=3: AsyncActD → SUCCESS, i=4
  루프 종료, current_child_idx = 0, return SUCCESS

4.2 중간 FAILURE 발생

Tick 1 (current_child_idx = 0):
  i=0: CondA → SUCCESS, i=1
  i=1: AsyncActB → RUNNING
  current_child_idx = 1, return RUNNING

Tick 2 (current_child_idx = 1):
  i=1: AsyncActB → FAILURE
  haltChildren(), current_child_idx = 0, return FAILURE

5. 시간 복잡도

상황	단일 Tick 복잡도
재진입 후 RUNNING 유지	$O(1)$
재진입 후 SUCCESS → 다음도 즉시 완료	$O(N - k)$ ( $k$ 는 재진입 인덱스)
최초 진입, 첫 자식 FAILURE	$O(1)$
모든 자식 즉시 SUCCESS	$O(N)$

WithMemory의 재진입에 의해, RUNNING 상태가 지속되는 동안의 Tick 비용은 $O(1)$ 로 최소화된다. 이는 ReactiveSequence의 $O(k+1)$ (처음부터 재평가)와 대비되는 효율성이다(Faconti, 2022).

참고 문헌

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/