1292.37 Fallback 노드의 자식 실행 순서

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

Fallback 노드는 Sequence 노드와 동일하게 자식 노드를 왼쪽에서 오른쪽(left-to-right) 순서로 순차적으로 실행한다. 이 순서는 트리 정의에서 자식이 나열된 순서와 동일하며, 결정론적이고 불변적이다. Fallback 노드에서 자식의 배치 순서는 대안의 우선순위(priority)를 직접적으로 인코딩하며, 왼쪽에 배치된 자식이 오른쪽에 배치된 자식보다 높은 우선순위를 가진다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

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

Fallback 노드에서 자식 $c_i$ 에 tick이 전달되기 위한 필요조건은, 모든 선행 자식 $c_1, c_2, \ldots, c_{i-1}$ 이 현재 또는 이전 tick에서 Failure를 반환한 것이다.

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

이 규칙은 Sequence 노드의 대응 규칙에서 Success를 Failure로 치환한 쌍대(dual) 형태이다. Fallback 노드에서 선행 자식의 실패가 후행 자식의 실행을 위한 전제 조건이 되며, 이는 “선호하는 대안이 실패해야만 차선의 대안을 시도한다“는 우선순위 기반 대안 탐색의 의미론을 구현한다.

단일 Tick 내에서의 실행 순서

단일 tick 내에서 Fallback 노드의 자식 실행은 다음과 같이 진행된다.

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

각 화살표는 선행 자식이 Failure를 반환한 후 후행 자식에 tick이 전달되는 것을 나타낸다. 임의의 자식이 Success 또는 Running을 반환하면, 순차 실행은 해당 지점에서 중단된다.

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

3.1 상태 기억형 Fallback

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

Tick $t_k$ : $c_1$ (Failure) $\rightarrow$ $c_2$ (Running) $\rightarrow$ Fallback(Running)

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

$c_1$ 은 tick $t_{k+1}$ 에서 재실행되지 않는다. 이미 실패한 대안을 재시도하지 않으므로, 현재 시도 중인 대안에 집중할 수 있다.

3.2 반응형 Fallback (ReactiveFallback)

반응형 Fallback 노드는 매 tick마다 첫 번째 자식부터 재평가한다. 이전에 Failure를 반환한 자식이 환경 변화에 의해 Success를 반환할 수 있으며, 이 경우 Running 상태의 후속 자식에 halt가 요청된다.

Tick $t_k$ : $c_1$ (Failure) $\rightarrow$ $c_2$ (Running) $\rightarrow$ Fallback(Running)

Tick $t_{k+1}$ : $c_1$ (Success) $\rightarrow$ $c_2$ 에 halt 요청 $\rightarrow$ Fallback(Success)

$c_1$ 이 tick $t_{k+1}$ 에서 Success를 반환하면, 더 높은 우선순위의 대안이 가용해졌으므로 현재 실행 중인 $c_2$ 를 중단하고 즉시 Success를 반환한다.

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

Fallback 노드에서 자식의 배치 순서는 대안의 선호도(preference)를 나타낸다. 설계 시 다음의 원칙을 따른다.

최선의 대안 우선 배치: 가장 선호하는 대안을 가장 왼쪽에 배치한다. Fallback 노드는 왼쪽 자식부터 시도하므로, 선호 대안이 성공하면 나머지 대안은 시도되지 않는다.

최후의 대안 후방 배치: 최후의 수단(last resort)에 해당하는 행동을 가장 오른쪽에 배치한다. 이 행동은 모든 선호 대안이 실패한 경우에만 실행된다. 안전 정지, 비상 착륙과 같은 보수적 행동이 이 위치에 배치된다.

5. 실행 순서의 예제

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

Fallback [F1]
 ├─ Sequence [S1: 주요 센서 기반 항법]
 │   ├─ Condition [C1: LiDAR 정상]
 │   └─ Action [A1: LiDAR 기반 항법]
 ├─ Sequence [S2: 보조 센서 기반 항법]
 │   ├─ Condition [C2: 카메라 정상]
 │   └─ Action [A2: 카메라 기반 항법]
 └─ Action [A3: 안전 정지]

사례	C1	S1 결과	C2	S2 결과	A3	F1 반환
1	Success	A1 실행	미실행	미실행	미실행	Success
2	Failure	Failure	Success	A2 실행	미실행	Success
3	Failure	Failure	Failure	Failure	실행	Success

사례 1에서 LiDAR가 정상이므로 최우선 대안(LiDAR 기반 항법)이 성공하고, 나머지 대안은 시도되지 않는다. 사례 2에서 LiDAR가 비정상이므로 S1이 실패하고, 차선 대안(카메라 기반 항법)이 시도된다. 사례 3에서 모든 센서가 비정상이므로 최후의 수단(안전 정지)이 실행된다 (Colledanchise & Ögren, 2018).

6. Sequence 노드 실행 순서와의 비교

Fallback 노드와 Sequence 노드의 실행 순서는 동일한 왼쪽에서 오른쪽 방향을 따르지만, 자식 간 진행 조건이 상반된다.

속성	Sequence 노드	Fallback 노드
실행 방향	왼쪽에서 오른쪽	왼쪽에서 오른쪽
다음 자식 진행 조건	현재 자식이 Success	현재 자식이 Failure
조기 종료 조건	현재 자식이 Failure	현재 자식이 Success
배치 순서의 의미	실행 선후 관계	대안 우선순위

이 비교에서 두 노드의 실행 순서가 구조적으로 동일하되, 진행과 종료의 조건이 정확히 반대임을 확인할 수 있다. 이 쌍대 관계는 행동 트리의 핵심적인 설계 원리이며, Sequence와 Fallback의 조합을 통해 복잡한 조건부 실행 논리를 구성하는 기반이 된다.

참고 문헌

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/