1292.92 행동 트리의 트리 구조 순회 알고리즘

1. 트리 구조 순회의 정의

행동 트리의 트리 구조 순회 알고리즘(tree traversal algorithm)이란, 행동 트리의 모든 노드를 체계적으로 방문하는 절차이다. 행동 트리의 실행에서 tick 전파는 특정 순회 알고리즘을 따르며, 이 순회 알고리즘이 노드의 실행 순서를 결정한다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

2. 전위 순회 기반 실행

행동 트리의 tick 전파는 전위 순회(pre-order traversal)를 기반으로 한다. 전위 순회에서 노드의 방문 순서는 다음과 같다.

1. 현재 노드를 방문(tick 수신)한다
2. 왼쪽 자식의 서브트리를 재귀적으로 순회한다
3. 오른쪽 자식의 서브트리를 재귀적으로 순회한다

function preorder_tick(node):
    status = node.tick()       // 1. 현재 노드 방문
    // 자식 순회는 node.tick() 내부에서 수행
    return status

제어 흐름 노드의 tick 함수 내부에서 자식에 대한 순회가 수행된다. 제어 흐름 노드는 자신의 의미론(Sequence, Fallback 등)에 따라 자식을 순서대로 방문한다.

3. 조건부 순회

행동 트리의 순회는 일반적인 트리 순회와 달리, 모든 노드를 반드시 방문하지 않는다. 제어 흐름 노드의 조기 종료 규칙에 의해 일부 자식이 방문되지 않을 수 있다.

이러한 조건부 순회는 행동 트리의 실행 효율을 높이고, 불필요한 노드 평가를 방지한다 (Faconti, BehaviorTree.CPP Documentation, 2024).

4. 순회의 재귀적 구조

행동 트리의 순회는 재귀적 구조를 가진다. 루트 노드에서 시작된 tick은 제어 흐름 노드를 거쳐 리프 노드까지 재귀적으로 전파되며, 리프 노드의 반환 상태가 상위 노드로 역전파된다.

Root.tick()
 └→ Sequence.tick()
      ├→ Condition.tick() → Success
      └→ Action.tick() → Running
      ← Running
 ← Running

5. 반복적 순회와의 비교

재귀적 순회 대신 반복적(iterative) 순회를 사용하여 행동 트리를 실행하는 구현도 가능하다. 반복적 구현은 호출 스택의 깊이를 제한할 수 있으나, 재귀적 구현이 트리의 계층적 구조와 더 자연스럽게 대응하므로 대부분의 행동 트리 라이브러리에서 재귀적 구현을 채택한다.

6. 로봇 공학에서의 의의

트리 구조 순회 알고리즘은 행동 트리의 실행 순서를 결정하는 근본적인 메커니즘이다. 전위 순회 기반의 조건부 순회를 통해, 안전 조건 검사가 행동 실행에 선행하고, 불필요한 노드 평가가 생략되며, 실행 순서가 결정론적으로 보장된다 (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/