1294.29 Fallback 노드의 개념과 정의
1. Fallback 노드의 정의
Fallback 노드는 행동 트리의 제어 흐름 노드로, 자식 노드를 왼쪽에서 오른쪽으로 순차적으로 평가하면서 첫 번째로 SUCCESS를 반환하는 자식을 찾는 노드이다. 하나의 자식이 SUCCESS를 반환하면 나머지 자식의 평가를 중단하고 즉시 SUCCESS를 반환하며, 모든 자식이 FAILURE를 반환한 경우에만 FAILURE를 반환한다. Fallback 노드는 “여러 대안 중 하나라도 성공하면 성공“이라는 의미론을 구현한다(Colledanchise & Ogren, 2018).
2. Fallback의 논리적 근거
2.1 OR 의미론
Fallback 노드는 논리 연산의 OR(논리합)에 대응한다. Sequence 노드가 AND 의미론(“모든 자식이 성공해야 성공”)을 구현하는 것과 대칭적으로, Fallback 노드는 OR 의미론(“하나의 자식이라도 성공하면 성공”)을 구현한다.
| 자식 반환 상태 | Fallback 반환 | 논리 OR 대응 |
|---|---|---|
| 첫 번째 자식 SUCCESS | SUCCESS | \text{true} \lor \cdots = \text{true} |
| 모든 자식 FAILURE | FAILURE | \text{false} \lor \text{false} \lor \cdots = \text{false} |
| k번째 자식 RUNNING | RUNNING | 3치 논리 확장 |
2.2 치 논리에서의 Fallback
행동 트리의 3치 논리(SUCCESS, FAILURE, RUNNING)에서 Fallback의 반환값은 다음과 같이 정의된다:
\text{Fallback}(c_1, c_2, ..., c_N) = \begin{cases} \text{SUCCESS} & \text{if } \exists i: c_i = \text{SUCCESS} \land \forall j < i: c_j = \text{FAILURE} \\ \text{RUNNING} & \text{if } \exists i: c_i = \text{RUNNING} \land \forall j < i: c_j = \text{FAILURE} \\ \text{FAILURE} & \text{if } \forall i: c_i = \text{FAILURE} \end{cases}
3. Fallback의 명칭과 유래
“Fallback“이라는 명칭은 “대안으로 되돌아감(falling back to an alternative)“에서 유래한다. 첫 번째 자식(선호 방안)이 실패하면 두 번째 자식(대안 1)으로, 두 번째도 실패하면 세 번째 자식(대안 2)으로 순차적으로 되돌아가는 동작을 표현한다. 이 명칭은 BehaviorTree.CPP를 비롯한 다수의 현대 프레임워크에서 공식 명칭으로 채택되었다(Faconti, 2022).
일부 프레임워크와 학술 문헌에서는 “Selector“라는 대안 명칭을 사용한다. 두 명칭은 동일한 노드를 지칭하며, 기능적 차이는 없다.
4. Fallback의 그래픽 표현
행동 트리의 그래픽 표기법에서 Fallback 노드는 물음표(?) 기호로 표시된다. 이는 Sequence 노드의 화살표(→) 기호와 구별된다.
Fallback: [?] (물음표 기호)
Sequence: [→] (화살표 기호)
BehaviorTree.CPP의 시각화 도구인 Groot2에서도 Fallback 노드는 물음표 기호가 포함된 사각형으로 표시된다.
5. Fallback의 구조적 역할
5.1 Sequence와의 대칭성
Fallback과 Sequence는 행동 트리의 두 가지 기본 제어 흐름 노드로서 대칭적 관계를 형성한다.
| 특성 | Sequence | Fallback |
|---|---|---|
| 논리 연산 | AND | OR |
| 성공 조건 | 모든 자식 SUCCESS | 하나의 자식 SUCCESS |
| 실패 조건 | 하나의 자식 FAILURE | 모든 자식 FAILURE |
| 조기 종료 조건 | FAILURE 발생 시 | SUCCESS 발생 시 |
| 그래픽 기호 | → | ? |
| 의미 | “모두 수행하라” | “하나만 성공하면 된다” |
이 대칭성은 행동 트리의 표현력을 보장하는 기반이며, Sequence와 Fallback의 조합으로 복잡한 의사 결정 구조를 표현할 수 있다.
5.2 대안 탐색 메커니즘
Fallback의 본질적 역할은 대안의 순차적 탐색이다. 자식 노드를 우선순위 순서로 배치하면, Fallback은 가장 선호되는 방안부터 시도하고, 실패 시 차순위 대안으로 자동 전환한다.
<Fallback>
<Action ID="PreferredApproach"/> <!-- 1순위: 선호 방안 -->
<Action ID="AlternativeApproach"/> <!-- 2순위: 대안 방안 -->
<Action ID="LastResort"/> <!-- 3순위: 최후 수단 -->
</Fallback>
PreferredApproach가 SUCCESS를 반환하면 나머지는 평가되지 않는다. FAILURE를 반환하면 AlternativeApproach가 평가되고, 이것도 FAILURE를 반환하면 LastResort가 평가된다.
6. Fallback의 형식적 정의
자식 노드 c_1, c_2, ..., c_N을 가진 Fallback 노드의 형식적 정의는 다음과 같다(Colledanchise & Ogren, 2018).
정의: Fallback 노드는 자식 c_1, c_2, ..., c_N을 왼쪽에서 오른쪽으로 순차적으로 평가한다. 자식 c_i가 SUCCESS 또는 RUNNING을 반환하면, Fallback은 해당 상태를 즉시 반환하고 후속 자식의 평가를 중단한다. 모든 자식이 FAILURE를 반환하면, Fallback은 FAILURE를 반환한다.
이 정의에서 핵심은:
- 순차적 평가: 인덱스 순서대로 평가한다.
- SUCCESS 조기 종료: 하나의 자식이 SUCCESS를 반환하면 즉시 종료한다.
- RUNNING 전파: 자식이 RUNNING을 반환하면 Fallback도 RUNNING을 반환한다.
- 전체 FAILURE: 모든 자식이 FAILURE인 경우에만 FAILURE를 반환한다.
7. BehaviorTree.CPP v4에서의 Fallback
BehaviorTree.CPP v4에서 Fallback 노드는 <Fallback> XML 태그로 정의된다(Faconti, 2022).
<Fallback>
<Action ID="TryPrimaryPath"/>
<Action ID="TryAlternativePath"/>
<Action ID="StopAndWait"/>
</Fallback>
기본 <Fallback> 태그는 WithMemory 동작을 수행하며, 이전 Tick에서 RUNNING을 반환한 자식의 인덱스를 기억하여 다음 Tick에서 해당 인덱스부터 재개한다. 매 Tick에서 처음부터 재평가하는 변형은 <ReactiveFallback> 태그로 별도 정의된다.
참고 문헌
- 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/