1292.32 Sequence 노드의 자식 실행 순서

1. 왼쪽에서 오른쪽 순차 실행 원칙

Sequence 노드는 자식 노드를 왼쪽에서 오른쪽(left-to-right) 순서로 순차적으로 실행한다. 이 순서는 행동 트리(Behavior Tree) 정의에서 자식 노드가 나열된 순서와 동일하며, 결정론적(deterministic)이고 불변적(invariant)이다. 즉, 동일한 트리 구조에서 Sequence 노드의 자식 실행 순서는 환경 조건이나 실행 시점에 관계없이 항상 동일하다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

자식 노드 $c_1, c_2, \ldots, c_N$ 이 이 순서로 정의되어 있으면, Sequence 노드는 반드시 $c_1$ 부터 시작하여 $c_2, c_3, \ldots$ 순으로 실행한다. 이 순서는 자식 간의 논리적 선후 관계(precedence relation)를 인코딩하며, 선행 자식의 성공이 후행 자식의 실행을 위한 전제 조건이 된다.

2. 순차 실행의 형식적 정의

Sequence 노드의 자식 실행 순서는 다음의 형식적 규칙으로 정의된다. 자식 $c_i$ 에 tick이 전달되기 위한 필요조건은 모든 선행 자식 $c_1, c_2, \ldots, c_{i-1}$ 이 현재 또는 이전 tick에서 Success를 반환한 것이다.

$\text{ticked}(c_i, t_k) \implies \forall\, j < i : \text{status}(c_j) = Success$

이 규칙은 Sequence 노드가 자식의 성공을 확인한 후에만 다음 자식으로 진행하는 순차적 실행 보장(sequential execution guarantee)을 형식적으로 명시한다.

단일 Tick 내에서의 실행 순서

단일 tick 내에서 Sequence 노드의 자식 실행은 동기적(synchronous)으로 이루어진다. 첫 번째 자식에 tick을 전달하고 반환 상태를 수신한 후, 해당 반환 상태가 Success인 경우에만 다음 자식에 tick을 전달한다. 이 과정이 모든 자식이 Success를 반환하거나, 임의의 자식이 Failure 또는 Running을 반환할 때까지 반복된다.

단일 tick 내에서의 실행 순서를 시간 순서로 나타내면 다음과 같다.

$c_1 \xrightarrow{Success} c_2 \xrightarrow{Success} c_3 \xrightarrow{Success} \cdots \xrightarrow{Success} c_N$

각 화살표는 선행 자식이 Success를 반환한 후 후행 자식에 tick이 전달되는 것을 나타낸다. 이 순차적 실행은 단일 tick의 실행 시간 내에서 모두 완료된다.

3. 다중 Tick에 걸친 실행 순서

자식 노드가 Running을 반환하면, 해당 tick에서의 순차 실행은 중단되고 Sequence 노드는 Running을 반환한다. 후속 tick에서의 실행 재개 방식은 Sequence 노드의 유형에 따라 두 가지로 구분된다.

3.1 상태 기억형 Sequence (SequenceWithMemory)

상태 기억형 Sequence 노드는 이전 tick에서 Running을 반환한 자식의 인덱스를 기억하며, 후속 tick에서 해당 인덱스의 자식부터 실행을 재개한다. 이전에 Success를 반환한 자식에는 tick이 재전달되지 않는다.

다음 예제에서 $c_2$ 가 tick $t_k$ 에서 Running을 반환한 경우를 고려한다.

Tick $t_k$ : $c_1$ (Success) $\rightarrow$ $c_2$ (Running) $\rightarrow$ Sequence(Running)

Tick $t_{k+1}$ : $c_2$ (Success) $\rightarrow$ $c_3$ (Success) $\rightarrow$ Sequence(Success)

$c_1$ 은 tick $t_{k+1}$ 에서 실행되지 않는다. 이 방식은 이미 성공한 작업의 재실행을 방지하여 효율성을 확보한다 (Faconti, BehaviorTree.CPP Documentation, 2024).

3.2 반응형 Sequence (ReactiveSequence)

반응형 Sequence 노드는 매 tick마다 반드시 첫 번째 자식부터 재실행한다. 이전에 Success를 반환한 자식이라도 매 tick마다 다시 평가된다.

Tick $t_k$ : $c_1$ (Success) $\rightarrow$ $c_2$ (Running) $\rightarrow$ Sequence(Running)

Tick $t_{k+1}$ : $c_1$ (Success) $\rightarrow$ $c_2$ (Success) $\rightarrow$ $c_3$ (Success) $\rightarrow$ Sequence(Success)

$c_1$ 이 tick $t_{k+1}$ 에서 다시 평가된다. 만약 $c_1$ 이 tick $t_{k+1}$ 에서 Failure를 반환하면, Running 상태의 $c_2$ 에 halt가 요청되고 Sequence는 즉시 Failure를 반환한다.

4. 실행 순서와 우선순위의 관계

Sequence 노드에서 자식의 배치 순서는 암묵적 우선순위(implicit priority)를 부여한다. 왼쪽에 배치된 자식이 오른쪽에 배치된 자식보다 먼저 실행되므로, 왼쪽 자식은 높은 실행 우선순위를 가진다. 이 우선순위는 다음과 같은 설계 원칙으로 활용된다.

선행 조건 우선 배치: 조건 노드를 Sequence의 왼쪽에 배치하면, 해당 조건이 충족되지 않을 경우 후속 액션 노드가 실행되지 않는 가드(guard) 패턴을 구현할 수 있다. 조건 검사가 액션 수행보다 계산 비용이 적으므로, 불필요한 액션의 실행을 조기에 차단하여 효율성을 높인다.

빠른 실패 원칙: 실패 가능성이 높은 자식을 왼쪽에 배치하면, 조기 종료(short-circuit)가 빈번하게 발생하여 단일 tick에서 실행되는 노드의 수가 감소한다. 이는 tick당 계산 비용을 절감하는 효과를 가진다.

5. 실행 순서의 결정론적 보장

Sequence 노드의 자식 실행 순서는 다음의 성질을 만족한다.

첫째, 전순서(total order) 관계이다. 모든 자식 쌍 $(c_i, c_j)$ 에 대해 $i < j$ 이면 $c_i$ 가 $c_j$ 보다 먼저 실행된다. 두 자식이 동시에 실행되는 경우는 없다.

둘째, 결정론적(deterministic) 순서이다. 동일한 트리 구조와 동일한 환경 조건에서 자식의 실행 순서는 항상 동일하다. 임의성(randomness)이나 비결정론적(non-deterministic) 선택이 개입되지 않는다.

셋째, **조건부 진행(conditional progression)**이다. 자식 $c_{i+1}$ 의 실행은 자식 $c_i$ 의 Success 반환에 의존한다. 이 의존성에 의해 실행 순서가 조건부로 단축될 수 있다 (Colledanchise & Ögren, 2018).

6. 실행 순서의 예제

다음의 Sequence 노드를 고려한다.

Sequence [S1]
 ├─ Condition [C1: 센서 정상 확인]
 ├─ Condition [C2: 경로 존재 확인]
 ├─ Action [A1: 경로 추종]
 └─ Action [A2: 도착 보고]

가능한 실행 순서의 사례는 다음과 같다.

사례	C1	C2	A1	A2	S1 반환
1	Success	Success	Success	Success	Success
2	Failure	미실행	미실행	미실행	Failure
3	Success	Failure	미실행	미실행	Failure
4	Success	Success	Running	미실행	Running

사례 2에서 C1이 Failure를 반환하면, C2, A1, A2는 실행되지 않으며 왼쪽에서 오른쪽 순서 내에서 조기 종료가 발생한다. 사례 4에서 A1이 Running을 반환하면, A2에는 tick이 전달되지 않으며 Sequence 노드는 Running 상태를 유지한다.

이처럼 Sequence 노드의 자식 실행 순서는 왼쪽에서 오른쪽으로 고정되어 있으나, 각 자식의 반환 상태에 따라 실제 실행되는 자식의 범위가 동적으로 결정된다.

참고 문헌

Colledanchise, M. & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
Faconti, D. (2024). BehaviorTree.CPP Documentation. https://www.behaviortree.dev/