1293.8 왼쪽에서 오른쪽 전파 규칙

1293.8 왼쪽에서 오른쪽 전파 규칙

1. 규칙의 정의

왼쪽에서 오른쪽 전파 규칙(left-to-right propagation rule)이란, 제어 흐름 노드가 자식 노드에 tick을 전파할 때 자식 목록의 첫 번째(왼쪽) 자식부터 마지막(오른쪽) 자식까지 순차적으로 전파하는 규칙이다. 이 규칙은 행동 트리의 모든 제어 흐름 노드에 적용되는 기본 전파 순서이며, 깊이 우선 순회와 결합하여 행동 트리의 결정론적 실행 순서를 형성한다 (Colledanchise & Ögren, 2018).

2. 왼쪽과 오른쪽의 의미

행동 트리에서 “왼쪽“과 “오른쪽“은 트리의 시각적 표현에서의 위치를 반영한다. 트리를 도식화할 때 자식 노드들은 부모 노드 아래에 수평으로 배열되며, 배열의 왼쪽 끝이 첫 번째 자식, 오른쪽 끝이 마지막 자식이다. 프로그래밍 구현에서 이는 자식 목록(children list)의 인덱스 순서와 일치한다. XML 기반 행동 트리 정의에서는 XML 요소의 선언 순서가 곧 왼쪽에서 오른쪽 순서이다.

<Sequence>
    <CheckBattery/>     <!-- 왼쪽: 인덱스 0, 최우선 평가 -->
    <NavigateToGoal/>   <!-- 중간: 인덱스 1 -->
    <PerformTask/>      <!-- 오른쪽: 인덱스 2, 최후 평가 -->
</Sequence>

3. 우선순위의 암묵적 표현

왼쪽에서 오른쪽 전파 규칙의 핵심적 설계 의의는 우선순위(priority)의 암묵적 표현에 있다. 왼쪽에 배치된 자식은 오른쪽에 배치된 자식보다 먼저 평가되며, 조건부 전파에 의해 왼쪽 자식의 결과가 오른쪽 자식의 실행 여부를 결정한다.

3.1 Sequence 노드에서의 우선순위

Sequence 노드에서 왼쪽 자식은 전제 조건(precondition)의 역할을 한다. 왼쪽 자식이 Failure를 반환하면 오른쪽 자식은 실행되지 않는다. 따라서 가장 중요한 전제 조건을 왼쪽에 배치하는 것이 합리적이다.

[Sequence]
    ├→ [IsBatteryOK]      ← 전제 조건 (최우선 확인)
    ├→ [IsPathClear]       ← 전제 조건 (차선 확인)
    └→ [NavigateToGoal]    ← 실제 행동 (조건 충족 시 실행)

3.2 Fallback 노드에서의 우선순위

Fallback 노드에서 왼쪽 자식은 선호되는 행동(preferred behavior)이다. 왼쪽 자식이 Success를 반환하면 오른쪽 자식(대안 행동)은 실행되지 않는다. 따라서 가장 선호되는 행동을 왼쪽에, 최후의 대안을 오른쪽에 배치한다.

[Fallback]
    ├→ [NavigateOptimalPath]   ← 최선의 행동
    ├→ [NavigateAlternatePath] ← 차선의 대안
    └→ [StopAndWait]           ← 최후의 대안

이러한 우선순위 표현은 유한 상태 머신(FSM)에서 명시적 전이 규칙으로 우선순위를 정의해야 하는 것과 대비되는 행동 트리의 구조적 장점이다. 행동 트리에서는 노드의 배치 위치만으로 우선순위가 결정되므로, 우선순위의 변경은 노드의 재배치만으로 달성된다 (Colledanchise & Ögren, 2018).

4. 조건-행동 쌍 패턴

왼쪽에서 오른쪽 전파 규칙은 조건-행동 쌍(condition-action pair) 패턴을 자연스럽게 구현한다. Sequence 노드에서 조건 노드를 왼쪽에, 액션 노드를 오른쪽에 배치하면, 조건이 충족될 때에만 행동이 실행되는 패턴이 형성된다.

[Sequence]
    ├→ [Condition: IsEnemyVisible]   ← 왼쪽: 조건 평가
    └→ [Action: Attack]              ← 오른쪽: 조건 충족 시 실행

이 패턴은 행동 트리에서 가장 빈번하게 사용되는 기본 설계 패턴이며, 왼쪽에서 오른쪽 전파 규칙에 의해 구조적으로 보장된다.

5. 반응형 노드에서의 왼쪽 우선 재평가

반응형 제어 노드(ReactiveSequence, ReactiveFallback)에서 왼쪽에서 오른쪽 규칙은 특히 중요한 의미를 가진다. 반응형 노드는 매 tick마다 첫 번째(왼쪽) 자식부터 재평가를 시작한다. 이전 tick에서 중간 자식이 Running을 반환했더라도, 다음 tick에서 왼쪽 자식부터 다시 평가한다.

[ReactiveSequence]
    ├→ [Condition: IsSafe]     ← 매 tick마다 재평가
    └→ [Action: Navigate]      ← Running 상태에서도 조건 재확인 후 실행

이 동작에서 왼쪽 자식(조건)이 Failure로 변하면, 오른쪽 자식(진행 중인 행동)은 중단(halt)된다. 이는 안전 조건을 왼쪽에 배치함으로써, 안전 조건 위반 시 진행 중인 행동을 즉시 중단하는 안전 보장 메커니즘을 구현한다.

6. 순서 의존 부작용

왼쪽에서 오른쪽 규칙은 자식 노드의 실행에 순서 의존적 부작용(order-dependent side effect)이 존재할 경우 주의를 요한다. 왼쪽 자식의 실행이 환경 상태를 변경하면, 오른쪽 자식의 조건 평가 결과에 영향을 미칠 수 있다. 이러한 순서 의존성은 의도된 것일 수도 있고 의도치 않은 것일 수도 있으므로, 설계 시 노드 간의 부작용 관계를 명확히 파악해야 한다.

[Sequence]
    ├→ [Action: OpenDoor]      ← 문 열기 (환경 상태 변경)
    └→ [Condition: IsDoorOpen] ← OpenDoor의 부작용에 의존

위 예시에서 왼쪽 자식의 행동 결과가 오른쪽 자식의 조건 평가에 영향을 미치는 것은 의도된 설계이다. 그러나 이러한 의존 관계가 명확하지 않으면 디버깅이 어려워질 수 있다.

7. 병렬 노드에서의 왼쪽에서 오른쪽 규칙

Parallel 노드에서도 왼쪽에서 오른쪽 규칙은 유지된다. 비록 Parallel 노드의 의미론(semantics)은 모든 자식을 “동시에” 실행하는 것이지만, 실제 구현에서 tick은 왼쪽에서 오른쪽 순서로 순차적으로 전파된다. 이는 Parallel 노드의 “병렬성“이 논리적 병렬성(logical parallelism)이지 물리적 병렬성(physical parallelism)이 아님을 의미한다 (Faconti, 2024).

따라서 Parallel 노드 내에서도 왼쪽 자식이 오른쪽 자식보다 먼저 tick을 수신하며, 왼쪽 자식의 부작용이 오른쪽 자식의 동작에 영향을 미칠 수 있다.

8. 규칙의 불변성

왼쪽에서 오른쪽 전파 규칙은 행동 트리의 표준 정의에서 불변(invariant)이다. 어떠한 제어 흐름 노드도 오른쪽에서 왼쪽으로 tick을 전파하지 않으며, 임의의 순서로 자식을 방문하지 않는다. 이 불변성은 행동 트리의 결정론적 실행과 예측 가능한 우선순위 체계의 기반이다. 만약 자식의 평가 순서가 무작위이거나 동적으로 변한다면, 행동 트리의 핵심 설계 원칙인 구조적 우선순위 표현과 결정론적 실행이 모두 무너지게 된다 (Colledanchise & Ögren, 2018).

참고 문헌

  • 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/