1293.50 Halt 전파의 깊이 우선 순서

1. 깊이 우선 Halt 전파의 정의

Halt 전파의 깊이 우선 순서(depth-first order)란, 부모 노드가 Halt를 수신하면 자신의 상태를 리셋하기 전에 먼저 자식 노드에 Halt를 전파하고, 자식 노드는 다시 자신의 자식(손자 노드)에 Halt를 전파하여, 트리의 리프 노드에서부터 자원 정리와 상태 리셋이 수행되는 전파 방식이다. 이 순서는 Tick의 깊이 우선 전파와 동일한 트리 순회 방향을 따른다(Colledanchise & Ogren, 2018).

2. 깊이 우선 전파의 과정

다음과 같은 트리 구조에서 루트에 Halt가 호출되는 경우를 추적한다.

Root (RUNNING)
├── ReactiveSequence (RUNNING)
│   ├── IsSafe (SUCCESS)
│   └── Sequence (RUNNING)
│       ├── MoveToA (SUCCESS, 건너뜀)
│       └── Parallel (RUNNING)
│           ├── Monitor (RUNNING)
│           └── PickObject (RUNNING)
└── LogStatus (IDLE)

2.1 Halt 전파 순서

1. Root.halt()
   2. ReactiveSequence.halt()
      3. Sequence.halt()
         4. Parallel.halt()
            5. Monitor.halt()        ← 리프 노드 (자원 정리)
               → Monitor.onHalted()
               → Monitor.resetStatus() → IDLE
            6. PickObject.halt()     ← 리프 노드 (자원 정리)
               → PickObject.onHalted()
               → PickObject.resetStatus() → IDLE
         → Parallel.resetStatus() → IDLE
         → Parallel.current_index 리셋
      → Sequence.resetStatus() → IDLE
      → Sequence.current_index = 0
   → ReactiveSequence.resetStatus() → IDLE
→ Root.resetStatus() → IDLE

3. 깊이 우선 순서의 필연성

깊이 우선 순서는 행동 트리의 재귀적 구조에서 자연스럽게 도출된다. 각 노드의 halt() 메서드는 자식에 Halt를 전파한 후 자신의 상태를 리셋하는 구조를 가진다.

void ControlNode::halt() {
    haltRunningChildren();  // 먼저 자식에 전파 (재귀적)
    resetStatus();          // 그 다음 자신의 상태 리셋
}

이 구조에서 haltRunningChildren()이 resetStatus() 이전에 호출되므로, 자식의 Halt가 완료된 후에야 부모의 상태가 리셋된다. 이는 자원 정리의 올바른 순서를 자연스럽게 보장한다.

4. RUNNING 자식만 Halt되는 규칙

Halt 전파 시 RUNNING 상태가 아닌 자식에는 Halt가 전파되지 않는다. 이는 RUNNING이 아닌 노드는 활성 자원을 보유하지 않으므로 정리가 필요하지 않기 때문이다.

Sequence (RUNNING)
├── Child_0 (SUCCESS)     ← Halt 전파 안 됨
├── Child_1 (SUCCESS)     ← Halt 전파 안 됨
└── Child_2 (RUNNING)     ← Halt 전파됨

void ControlNode::haltRunningChildren() {
    for (auto& child : children_nodes_) {
        if (child->status() == NodeStatus::RUNNING) {
            child->halt();    // RUNNING인 자식에만 Halt
        }
    }
}

5. 왼쪽에서 오른쪽 전파와의 관계

haltRunningChildren()은 자식을 왼쪽에서 오른쪽 순서로 순회하면서 RUNNING 자식에 Halt를 호출한다. Parallel 노드에서 복수의 자식이 동시에 RUNNING인 경우, 왼쪽 자식의 Halt가 먼저 처리된다.

Parallel (RUNNING)
├── ActionA (RUNNING)     ← 첫 번째로 Halt
├── ActionB (SUCCESS)     ← Halt 안 됨
└── ActionC (RUNNING)     ← 두 번째로 Halt

이 순서는 대부분의 경우 의미적 차이를 발생시키지 않으나, 자식 간 자원 의존 관계가 존재하는 경우에는 Halt 순서가 중요할 수 있다.

6. Tick 전파 순서와 Halt 전파 순서의 대비

Tick과 Halt는 모두 깊이 우선으로 전파되지만, 방향과 의미가 다르다.

7. Halt 전파의 시간 비용

깊이 우선 Halt 전파의 시간 비용은 트리 내 RUNNING 노드의 수와 각 노드의 onHalted() 실행 시간에 비례한다.

T_{halt} = \sum_{i \in \text{running\_nodes}} T_{onHalted_i}

onHalted()가 비블로킹으로 구현된 경우(비동기 취소 요청만 전송), 각 노드의 Halt 처리 시간은 매우 짧다. 그러나 블로킹 연산이 포함된 경우, Halt 전파의 총 시간이 Tick 주기를 초과할 수 있으므로 주의가 필요하다.

8. 부분 Halt과 전체 Halt

Halt 전파는 트리 전체에 적용될 수도 있고, 서브트리에만 적용될 수도 있다.

8.1 부분 Halt

제어 노드의 실행 논리에 의해 특정 자식에만 Halt가 호출되는 경우이다. ReactiveSequence에서 조건 위반 시 액션 노드에만 Halt가 호출되는 것이 이에 해당한다.

ReactiveSequence.tick():
  IsSafe.tick() → FAILURE
  haltRunningChildren()  // Navigate(RUNNING)에만 Halt

8.2 전체 Halt

tree.haltTree() 호출에 의해 루트부터 모든 RUNNING 노드에 Halt가 전파되는 경우이다. 시스템 종료나 트리 전환 시 사용된다.

// 트리 전체 Halt
tree.haltTree();  // 루트에서 모든 RUNNING 노드까지 깊이 우선 전파

참고 문헌

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