1295.54 ReactiveSequence의 실행 알고리즘 상세

1. 알고리즘 개요

ReactiveSequence의 실행 알고리즘은 매 Tick에서 첫 번째 자식부터 순차적으로 평가하고, 모든 자식이 SUCCESS를 반환하면 SUCCESS를, 하나의 자식이라도 FAILURE를 반환하면 즉시 FAILURE를, 자식 중 하나가 RUNNING을 반환하면 RUNNING을 반환하는 구조이다. 일반 Sequence와의 핵심적 차이는 평가 시작점에 있다. 일반 Sequence는 이전 Tick에서 마지막으로 RUNNING이었던 자식부터 평가를 재개하지만, ReactiveSequence는 항상 인덱스 0의 자식부터 평가를 시작한다.

2. 알고리즘의 단계별 기술

ReactiveSequence의 tick() 메서드가 호출되면, 다음의 단계가 순차적으로 수행된다.

2.1 단계 1: 반복 시작점 초기화

반복 인덱스를 0으로 설정한다. 이전 Tick에서의 실행 상태와 무관하게 항상 첫 번째 자식부터 시작한다.

2.2 단계 2: 자식 순차 평가

인덱스 $i = 0$ 부터 $N-1$ 까지 ( $N$ 은 자식 수) 순차적으로 각 자식에 Tick을 전파한다.

2.3 단계 3: 자식 반환값에 따른 분기

자식 $C_i$ 의 반환값에 따라 다음과 같이 처리한다.

SUCCESS: 다음 자식 $C_{i+1}$ 로 진행한다.
FAILURE: 반복을 즉시 중단한다. 이전에 RUNNING이었던 후행 자식들에 Halt를 전파한다. ReactiveSequence는 FAILURE를 반환한다.
RUNNING: 반복을 중단한다. 현재 자식 이후에 RUNNING이었던 자식들에 Halt를 전파한다. ReactiveSequence는 RUNNING을 반환한다.

2.4 단계 4: 모든 자식 SUCCESS

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

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

자식 노드 집합을 $\{C_0, C_1, \ldots, C_{N-1}\}$ 이라 하자. ReactiveSequence의 tick() 함수는 다음과 같이 정의된다.

function ReactiveSequence.tick():
    for i ← 0 to N-1:
        status ← C_i.tick()
        
        if status == RUNNING:
            // i 이후의 RUNNING 상태 자식에 Halt 전파
            for j ← i+1 to N-1:
                if C_j.status() == RUNNING:
                    C_j.halt()
            return RUNNING
        
        if status == FAILURE:
            // i 이후의 RUNNING 상태 자식에 Halt 전파
            for j ← i+1 to N-1:
                if C_j.status() == RUNNING:
                    C_j.halt()
            return FAILURE
    
    // 모든 자식이 SUCCESS
    return SUCCESS

4. Halt 전파의 대상 결정

알고리즘에서 Halt 전파의 대상은 “현재 평가 중인 자식 이후에 위치하면서 RUNNING 상태인 자식“이다. 이 조건은 다음의 상황에서 성립한다.

이전 Tick에서 자식 $C_k$ ( $k > i$ )가 RUNNING을 반환하였고, 현재 Tick에서 자식 $C_i$ ( $i < k$ )가 FAILURE 또는 RUNNING을 반환한 경우, $C_k$ 는 현재 Tick에서 Tick을 수신하지 못하였으므로 여전히 이전의 RUNNING 상태를 유지한다. 이 $C_k$ 에 Halt가 전파되어야 한다.

구체적으로, 다음과 같은 시나리오를 고려한다.

ReactiveSequence
├── C₀ (조건)
├── C₁ (조건)
└── C₂ (행동)

Tick t:
  C₀.tick() → SUCCESS
  C₁.tick() → SUCCESS
  C₂.tick() → RUNNING
  ReactiveSequence → RUNNING

Tick t+1:
  C₀.tick() → FAILURE
  → C₂는 Tick을 수신하지 않았으나 여전히 RUNNING 상태
  → C₂.halt() 호출
  ReactiveSequence → FAILURE

Tick $t+1$ 에서 $C_0$ 가 FAILURE를 반환하면, $C_1$ 과 $C_2$ 는 평가되지 않는다. 그러나 $C_2$ 는 이전 Tick에서 RUNNING이었으므로 Halt를 수신하여야 한다. $C_1$ 은 이전 Tick에서 SUCCESS였으므로 Halt 대상이 아니다.

5. 상태 전이 다이어그램

ReactiveSequence의 반환값은 자식들의 반환값 조합에 의해 결정된다. 자식이 3개인 경우를 기준으로 가능한 상태 전이를 정리한다.

$C_0$ 결과	$C_1$ 결과	$C_2$ 결과	ReactiveSequence 결과	Halt 대상
FAILURE	(미평가)	(미평가)	FAILURE	이전 RUNNING 자식
SUCCESS	FAILURE	(미평가)	FAILURE	이전 RUNNING 자식
SUCCESS	SUCCESS	FAILURE	FAILURE	없음
SUCCESS	SUCCESS	RUNNING	RUNNING	없음
SUCCESS	SUCCESS	SUCCESS	SUCCESS	없음
SUCCESS	RUNNING	(미평가)	RUNNING	이전 $C_2$ RUNNING 시 $C_2$ Halt
RUNNING	(미평가)	(미평가)	RUNNING	이전 $C_1$ , $C_2$ RUNNING 시 Halt

6. RUNNING 반환 시의 의미론

ReactiveSequence가 RUNNING을 반환하는 경우는 두 가지이다.

6.1 경우 1: 행동 자식이 RUNNING

모든 선행 조건이 SUCCESS를 반환하고, 행동 자식이 RUNNING을 반환한 경우이다. 이는 전제 조건이 충족된 상태에서 행동이 진행 중임을 의미한다.

C₀ → SUCCESS, C₁ → SUCCESS, C₂ → RUNNING
ReactiveSequence → RUNNING

6.2 경우 2: 조건 자식이 RUNNING

선행 조건 자식이 RUNNING을 반환한 경우이다. 조건의 평가가 완료되지 않았으므로 후행 자식은 평가되지 않는다. 일반적으로 조건 노드는 SUCCESS 또는 FAILURE만을 반환하도록 설계하므로 이 경우는 드물지만, 비동기적 조건 평가(예: 원격 서비스 호출에 의한 조건 확인)에서 발생할 수 있다.

C₀ → SUCCESS, C₁ → RUNNING
→ C₂가 이전에 RUNNING이었으면 C₂.halt()
ReactiveSequence → RUNNING

7. 일반 Sequence 알고리즘과의 비교

일반 Sequence의 알고리즘을 병렬로 제시하여 차이를 명확히 한다.

function Sequence.tick():
    for i ← running_child_index to N-1:   // ← 차이점: 시작 인덱스
        status ← C_i.tick()
        
        if status == RUNNING:
            running_child_index ← i        // ← 차이점: 인덱스 기억
            return RUNNING
        
        if status == FAILURE:
            running_child_index ← 0
            return FAILURE
    
    running_child_index ← 0
    return SUCCESS

function ReactiveSequence.tick():
    for i ← 0 to N-1:                     // ← 항상 0부터 시작
        status ← C_i.tick()
        
        if status == RUNNING:
            haltRunningChildren(i+1, N-1)  // ← Halt 전파
            return RUNNING
        
        if status == FAILURE:
            haltRunningChildren(i+1, N-1)  // ← Halt 전파
            return FAILURE
    
    return SUCCESS

핵심적 차이는 두 가지이다. 첫째, ReactiveSequence는 반복 시작 인덱스가 항상 0이다. 둘째, ReactiveSequence는 RUNNING 또는 FAILURE 반환 시 후행 자식에 대한 Halt 전파를 수행한다.

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

ReactiveSequence의 단일 Tick 시간 복잡도는 $O(N)$ 이다. 매 Tick에서 최대 $N$ 개의 자식을 평가하여야 하기 때문이다. 일반 Sequence의 최선의 경우 시간 복잡도가 $O(1)$ 인 것과 대비된다(이전 RUNNING 자식부터 바로 시작하므로).

그러나 ReactiveSequence에서 앞부분의 조건 노드가 FAILURE를 반환하면 나머지 자식은 평가되지 않으므로, 평균적인 시간 복잡도는 조건 노드의 FAILURE 빈도에 의존한다. 조건이 대부분의 Tick에서 SUCCESS를 반환하는 경우 전체 $N$ 개의 자식이 평가되고, 첫 번째 조건이 자주 FAILURE를 반환하는 경우 $O(1)$ 에 근사한다.

9. 알고리즘의 정확성 보증

ReactiveSequence의 실행 알고리즘은 다음의 속성을 보장한다.

전제 조건 불변성: 행동 자식이 RUNNING인 모든 Tick에서, 모든 선행 조건 자식이 SUCCESS를 반환하였다.
Halt 안전성: 전제 조건 위반 시, RUNNING 상태의 모든 후행 자식에 Halt가 전파된다. 어떤 RUNNING 자식도 Halt 없이 방치되지 않는다.
단조적 평가: 자식은 항상 좌에서 우로(인덱스 순으로) 평가된다. 평가 순서가 역전되지 않는다.
결정론적 결과: 동일한 자식 반환값 조합에 대해 ReactiveSequence의 반환값은 항상 동일하다.

이러한 속성은 ReactiveSequence를 안전 관련 행동 트리에 적용하기 위한 이론적 근거를 제공한다.