1292.36 Fallback 노드의 동작 원리

1. Fallback 노드의 정의

Fallback 노드는 행동 트리(Behavior Tree)의 제어 흐름 노드 중 하나로, 자식 노드를 왼쪽에서 오른쪽 순서로 순차적으로 실행하며, 자식 중 하나라도 성공(Success)을 반환하면 자신도 즉시 성공을 반환하는 노드이다. Fallback 노드는 “자식 중 하나만 성공하면 된다“는 논리합(logical OR) 의미론을 구현한다. 모든 자식이 실패(Failure)를 반환하는 경우에만 Fallback 노드 자신도 실패를 반환한다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

Fallback 노드는 일부 문헌에서 Selector 노드로도 지칭된다. 행동 트리 다이어그램에서 Fallback 노드는 일반적으로 물음표 기호(?)로 표기된다.

2. Fallback 노드의 알고리즘

Fallback 노드의 동작을 의사 코드로 표현하면 다음과 같다.

function Fallback.tick():
    for i = current_child_index to N:
        status = child[i].tick()
        if status == Running:
            current_child_index = i
            return Running
        if status == Success:
            current_child_index = 0
            return Success
    current_child_index = 0
    return Failure

이 알고리즘은 Sequence 노드의 알고리즘과 대칭적(symmetric) 구조를 가진다. Sequence 노드에서 Success가 다음 자식으로의 진행을 허용하고 Failure가 조기 종료를 유발하는 것과 반대로, Fallback 노드에서는 Failure가 다음 자식으로의 진행을 허용하고 Success가 조기 종료를 유발한다.

3. Fallback 노드의 논리적 의미론

Fallback 노드는 단락 평가(short-circuit evaluation)를 동반한 논리합(OR) 연산과 구조적으로 동등하다. 자식 노드 c_1, c_2, \ldots, c_N의 반환 상태를 s_1, s_2, \ldots, s_N이라 하면, Fallback 노드의 반환 상태 F는 다음과 같이 정의된다.

F = \begin{cases} Success & \text{if } \exists\, i \in \{1, \ldots, N\} : s_i = Success \\ Running & \text{if } \exists\, i \in \{1, \ldots, N\} : s_i = Running \wedge \forall\, j < i : s_j = Failure \\ Failure & \text{if } \forall\, i \in \{1, \ldots, N\} : s_i = Failure \end{cases}

이 정의에서 Success가 먼저 발견되면 즉시 Success를 반환하고, Running이 발견되면 Running을 반환하며, 모든 자식이 Failure일 때에만 Failure를 반환한다 (Colledanchise & Ögren, 2018).

Sequence 노드와의 쌍대 관계

Fallback 노드와 Sequence 노드는 수학적으로 쌍대(dual) 관계에 있다. 이 관계는 드모르간 법칙(De Morgan’s laws)의 행동 트리 판본으로 이해할 수 있다.

이 쌍대 관계에 의해, Sequence 노드에 대해 성립하는 모든 정리(theorem)는 Success와 Failure를 교환하면 Fallback 노드에 대한 대응하는 정리가 된다.

상태 기억 메커니즘

일반 Fallback 노드(비반응형)는 Sequence 노드와 동일한 상태 기억 메커니즘을 적용한다. 자식이 Running을 반환하면 해당 자식의 인덱스를 기억하고, 후속 tick에서는 해당 인덱스의 자식부터 실행을 재개한다. 이전에 Failure를 반환한 자식에는 tick을 재전달하지 않는다 (Faconti, BehaviorTree.CPP Documentation, 2024).

실행 흐름 예제

다음의 Fallback 노드를 고려한다. 이 트리는 로봇이 대안적 경로를 탐색하는 행동을 모델링한 것이다.

Fallback [F1]
 ├─ Action [A1: 주요 경로 추종]
 ├─ Action [A2: 대체 경로 추종]
 └─ Action [A3: 제자리 대기]

첫 번째 자식이 Success를 반환하는 경우

A1이 Success를 반환하면, F1은 즉시 Success를 반환한다. A2와 A3에는 tick이 전달되지 않는다.

\tau_k = \langle (A1, Success) \rangle \quad \rightarrow \quad F1: Success

3.1 첫 번째 자식이 Failure를 반환하는 경우

A1이 Failure를 반환하면, F1은 다음 자식인 A2에 tick을 전달한다. A2가 Success를 반환하면 F1도 Success를 반환한다.

\tau_k = \langle (A1, Failure), (A2, Success) \rangle \quad \rightarrow \quad F1: Success

모든 자식이 Failure를 반환하는 경우

A1, A2, A3가 모두 Failure를 반환하면, F1도 Failure를 반환한다.

\tau_k = \langle (A1, F), (A2, F), (A3, F) \rangle \quad \rightarrow \quad F1: Failure

이 경우 Fallback 노드의 모든 대안이 소진되었음을 의미한다.

4. 우선순위 기반 대안 탐색

Fallback 노드의 핵심적인 설계 의도는 우선순위 기반 대안 탐색(priority-based fallback search)이다. 왼쪽에 배치된 자식이 오른쪽에 배치된 자식보다 높은 우선순위를 가지며, Fallback 노드는 가장 높은 우선순위의 대안부터 시도한다. 선호하는 대안이 실패할 경우에만 차선의 대안을 시도하는 이 패턴은 로봇 공학에서 빈번하게 활용된다.

Fallback
 ├─ Sequence: [최적 경로 시도]
 │   ├─ Condition: 최적 경로 존재
 │   └─ Action: 최적 경로 추종
 ├─ Sequence: [대체 경로 시도]
 │   ├─ Condition: 대체 경로 존재
 │   └─ Action: 대체 경로 추종
 └─ Action: 안전 정지

이 구조에서 최적 경로가 존재하면 최적 경로를 추종하고, 존재하지 않으면 대체 경로를 시도하며, 대체 경로도 존재하지 않으면 안전 정지를 수행한다. 각 대안은 왼쪽에서 오른쪽 순서로 우선순위가 부여되며, Fallback 노드는 이 우선순위를 자동으로 존중한다 (Colledanchise & Ögren, 2018).

5. Fallback 노드의 설계적 활용

5.1 예외 처리 패턴

Fallback 노드는 행동 트리에서 예외 처리(exception handling) 패턴을 구현하는 데 활용된다. 정상적인 행동을 첫 번째 자식으로 배치하고, 예외 상황에서의 복구 행동을 후속 자식으로 배치하면, 정상 행동이 실패할 경우 자동으로 복구 행동이 시도된다.

5.2 점진적 퇴화 패턴

로봇 시스템에서 센서 고장이나 환경 변화에 대응하기 위한 점진적 퇴화(graceful degradation) 패턴도 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/