1293.26 제어 노드에서의 Tick 전파 규칙

1293.26 제어 노드에서의 Tick 전파 규칙

1. 제어 노드의 역할

제어 노드(Control Node)는 행동 트리(Behavior Tree)에서 자식 노드들에 대한 Tick의 전파 순서와 조건을 결정하는 내부 노드이다. 리프 노드가 실제 작업을 수행하거나 조건을 평가하는 반면, 제어 노드는 자식 노드들의 반환 상태를 수집하고 해석하여 자신의 반환 상태를 결정하는 제어 흐름(control flow) 로직을 구현한다(Colledanchise & Ogren, 2018).

제어 노드의 Tick 전파 규칙은 행동 트리의 실행 의미론(execution semantics)을 정의하는 핵심 요소이며, 각 제어 노드 유형은 고유한 전파 규칙을 가진다.

2. Tick 전파의 기본 원칙

모든 제어 노드에 공통적으로 적용되는 Tick 전파의 기본 원칙은 다음과 같다.

2.1 하향식 전파

Tick은 항상 부모 노드에서 자식 노드로 하향 전파된다. 자식 노드가 스스로 Tick을 생성하거나 부모 노드에 Tick을 역전파하는 것은 허용되지 않는다. 루트 노드에서 시작된 Tick만이 유일한 Tick 생성원이다.

2.2 반환 상태 기반 결정

제어 노드는 자식 노드의 반환 상태(SUCCESS, FAILURE, RUNNING)에 기반하여 다음 동작을 결정한다. 자식의 반환 상태에 따라 후속 자식에 Tick을 전파할지, Tick 전파를 중단할지, 또는 RUNNING 중인 자식을 Halt할지를 결정한다.

2.3 왼쪽에서 오른쪽 순서

자식 노드에 대한 Tick 전파는 트리 정의에서의 순서(일반적으로 왼쪽에서 오른쪽)를 따른다. 이 순서는 자식 노드의 우선순위를 암시적으로 표현하며, 왼쪽에 배치된 자식이 먼저 평가된다.

3. 제어 노드 유형별 전파 규칙 개요

행동 트리에서 사용되는 주요 제어 노드 유형과 그 Tick 전파 규칙의 개요는 다음과 같다.

제어 노드 유형성공 조건실패 조건Tick 전파 방식
Sequence모든 자식 SUCCESS하나의 자식 FAILURE순차, FAILURE 시 중단
Fallback하나의 자식 SUCCESS모든 자식 FAILURE순차, SUCCESS 시 중단
ParallelM개 이상 SUCCESSN-M+1개 이상 FAILURE모든 자식에 동시 전파
ReactiveSequence모든 자식 SUCCESS하나의 자식 FAILURE매 Tick 처음부터 재평가
ReactiveFallback하나의 자식 SUCCESS모든 자식 FAILURE매 Tick 처음부터 재평가

4. 조기 종료 규칙

제어 노드의 가장 중요한 최적화 기법 중 하나는 조기 종료(short-circuit)이다. 자식 노드의 반환 상태가 제어 노드의 최종 상태를 이미 결정하는 경우, 나머지 자식에 대한 Tick 전파를 생략한다.

  • Sequence의 조기 종료: 자식이 FAILURE를 반환하면 나머지 자식을 Tick하지 않고 즉시 FAILURE를 반환한다. 이미 결과가 확정되었으므로 후속 자식의 평가는 불필요하다.
  • Fallback의 조기 종료: 자식이 SUCCESS를 반환하면 나머지 자식을 Tick하지 않고 즉시 SUCCESS를 반환한다.

조기 종료는 논리 연산에서의 단축 평가(short-circuit evaluation)와 동일한 원리이다. Sequence는 논리 AND 연산, Fallback은 논리 OR 연산에 대응된다.

5. RUNNING 상태에서의 전파 규칙

자식 노드가 RUNNING을 반환하는 경우, 제어 노드의 후속 동작은 메모리 속성에 따라 결정된다.

5.1 WithMemory 모드

RUNNING을 반환한 자식의 인덱스를 기억하고, 다음 Tick에서 해당 인덱스의 자식부터 재진입한다. 이전에 SUCCESS(Sequence의 경우) 또는 FAILURE(Fallback의 경우)를 반환한 자식은 재평가하지 않는다.

Tick k: Sequence[Memory] → C0(SUCCESS) → C1(RUNNING)
                           기억: 인덱스 1
Tick k+1: Sequence[Memory] → C1(재진입)  [C0 건너뜀]

5.2 WithoutMemory (Reactive) 모드

RUNNING 상태의 자식이 존재하더라도 다음 Tick에서 첫 번째 자식부터 모든 자식을 재평가한다. RUNNING 중이던 자식에 도달하기 전에 다른 자식이 제어 흐름을 변경하면, RUNNING 중이던 자식에 Halt가 호출된다.

Tick k: ReactiveSequence → C0(SUCCESS) → C1(RUNNING)
Tick k+1: ReactiveSequence → C0(재평가, SUCCESS) → C1(재진입)
Tick k+2: ReactiveSequence → C0(재평가, FAILURE) → C1(Halt)
                             즉시 FAILURE 반환

6. Halt 전파 규칙

제어 노드가 RUNNING 상태에서 다른 상태로 전이할 때, 또는 Reactive 모드에서 조건 변화가 감지될 때, RUNNING 중인 자식 노드에 대해 Halt를 호출한다. Halt 전파의 규칙은 다음과 같다.

  1. 제어 노드 자체가 Halt되면, RUNNING 상태인 모든 자식에 Halt를 전파한다.
  2. Reactive 제어 노드에서 조건 변화로 인해 RUNNING 중인 자식의 실행이 불필요해지면, 해당 자식에 Halt를 호출한다.
  3. Halt는 깊이 우선 순서로 전파되어, 하위 트리의 모든 RUNNING 노드가 순차적으로 중단된다.

7. 의사 코드를 통한 전파 규칙 요약

7.1 Sequence 전파 규칙

function Sequence.tick():
    for i = start_index to children.size():
        status = children[i].tick()
        if status == RUNNING:
            return RUNNING
        if status == FAILURE:
            halt_running_children()
            return FAILURE
    return SUCCESS

7.2 Fallback 전파 규칙

function Fallback.tick():
    for i = start_index to children.size():
        status = children[i].tick()
        if status == RUNNING:
            return RUNNING
        if status == SUCCESS:
            halt_running_children()
            return SUCCESS
    return FAILURE

여기서 start_index는 WithMemory 모드에서는 이전에 기억된 인덱스, WithoutMemory 모드에서는 항상 0이다.

8. 제어 노드 선택의 설계 기준

적절한 제어 노드를 선택하기 위해서는 다음 기준을 고려해야 한다.

설계 요구 사항적합한 제어 노드
모든 조건이 순차적으로 만족되어야 함Sequence
대안 중 하나가 성공하면 충분Fallback
복수 작업의 동시 수행Parallel
조건 변화에 즉각적 반응 필요ReactiveSequence, ReactiveFallback
이미 완료된 단계의 재실행 방지SequenceWithMemory

이러한 기준은 상호 배타적이지 않으며, 복잡한 행동은 다양한 유형의 제어 노드를 계층적으로 조합하여 구현한다.

참고 문헌

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