1292.93 전위 순회와 Tick

1. 전위 순회의 정의

전위 순회(pre-order traversal)는 트리 자료 구조의 순회 방법 중 하나로, 부모 노드를 먼저 방문한 후 자식 노드를 왼쪽에서 오른쪽 순서로 재귀적으로 방문하는 방식이다. 행동 트리에서 tick의 전파는 전위 순회의 방문 순서를 따르며, 이는 행동 트리의 실행 순서를 결정하는 근본적인 알고리즘이다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

2. 전위 순회와 Tick 전파의 대응

전위 순회의 방문 순서와 tick 전파의 대응 관계는 다음과 같다.

전위 순회에서 “현재 노드 방문“은 행동 트리에서 해당 노드의 tick 함수 호출에 해당한다. 제어 흐름 노드의 tick 함수 내부에서 자식 노드에 대한 tick 전달이 수행되며, 이것이 자식 서브트리의 재귀적 순회에 해당한다.

3. Tick 전파의 의사 코드

function tick_preorder(node):
    // 전위 순회: 현재 노드를 먼저 처리
    if node is leaf:
        return node.evaluate()

    // 제어 흐름 노드: 자식을 왼쪽부터 순차 방문
    for each child in node.children:
        child_status = tick_preorder(child)
        // 제어 흐름 노드의 의미론에 따라
        // 조기 종료 여부 결정
        if should_stop(node, child_status):
            break

    return compute_status(node, results)

4. 전위 순회 순서의 예시

Root [R]
 └─ Fallback [F]
      ├─ Sequence [S]
      │   ├─ Condition [C1]
      │   └─ Action [A1]
      └─ Action [A2]

전위 순회 방문 순서: R → F → S → C1 → A1 → A2

실제 tick 전파에서 조기 종료가 발생하지 않는다면, 노드는 위의 순서로 tick을 수신한다. 조기 종료가 발생하면 일부 노드의 방문이 생략된다 (Faconti, BehaviorTree.CPP Documentation, 2024).

5. 전위 순회 선택의 근거

행동 트리가 전위 순회를 채택하는 근거는 다음과 같다.

• 부모 우선 처리: 제어 흐름 노드가 자식보다 먼저 처리되어, 자식의 실행 여부를 결정할 수 있다
• 왼쪽 우선: 우선순위가 높은 자식이 먼저 평가되어, 우선순위 기반 의사 결정이 자연스럽게 구현된다
• 조기 종료 호환: 순차적 방문에 의해 조기 종료 규칙이 자연스럽게 적용된다

6. 로봇 공학에서의 의의

전위 순회 기반의 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/