1293.7 깊이 우선 전파의 상세 알고리즘

1. 깊이 우선 전파의 정의

행동 트리에서 tick의 전파는 깊이 우선 탐색(Depth-First Search, DFS)의 전위 순회(pre-order traversal) 방식을 따른다. 깊이 우선 전파란, 현재 노드를 먼저 처리(tick)한 후, 자식 노드들을 왼쪽부터 재귀적으로 방문하는 순회 방식이다. 이 알고리즘에서 트리의 가장 깊은 곳까지 먼저 내려간 후, 형제 노드로 이동하는 순서를 따른다 (Colledanchise & Ögren, 2018).

2. 기본 알고리즘의 의사코드

행동 트리의 깊이 우선 tick 전파를 의사코드로 표현하면 다음과 같다.

function tick(node) → status:
    if node is LeafNode:
        return node.execute()
    
    // node is ControlFlowNode or DecoratorNode
    for each child in node.children (left to right):
        child_status = tick(child)
        result = node.evaluateChildStatus(child, child_status)
        if result is DETERMINED:
            return result
    
    return node.finalizeStatus()

이 의사코드에서 evaluateChildStatus는 부모 노드의 유형에 따른 조건부 전파 규칙을 구현하며, DETERMINED는 부모 노드가 더 이상 후속 자식의 평가 없이 자신의 반환 상태를 결정할 수 있음을 의미한다.

3. 노드 유형별 상세 알고리즘

3.1 Sequence 노드의 깊이 우선 전파

Sequence 노드는 자식을 왼쪽에서 오른쪽으로 순차적으로 tick하며, 자식이 Failure를 반환하면 즉시 Failure를 반환하고 나머지 자식의 평가를 중단한다.

function SequenceNode.tick() → status:
    for each child in children:
        child_status = child.tick()
        if child_status == FAILURE:
            return FAILURE
        if child_status == RUNNING:
            return RUNNING
    return SUCCESS

3.2 Fallback 노드의 깊이 우선 전파

Fallback 노드는 자식을 왼쪽에서 오른쪽으로 순차적으로 tick하며, 자식이 Success를 반환하면 즉시 Success를 반환하고 나머지 자식의 평가를 중단한다.

function FallbackNode.tick() → status:
    for each child in children:
        child_status = child.tick()
        if child_status == SUCCESS:
            return SUCCESS
        if child_status == RUNNING:
            return RUNNING
    return FAILURE

3.3 Parallel 노드의 깊이 우선 전파

Parallel 노드는 모든 자식에 tick을 전파하며, 성공 및 실패 임계값에 따라 반환 상태를 결정한다. 모든 자식에 무조건적으로 tick을 전파한다는 점에서 조건부 전파를 수행하는 Sequence 및 Fallback과 차별된다.

function ParallelNode.tick() → status:
    success_count = 0
    failure_count = 0
    for each child in children:
        child_status = child.tick()
        if child_status == SUCCESS:
            success_count += 1
        if child_status == FAILURE:
            failure_count += 1
    
    if success_count >= success_threshold:
        return SUCCESS
    if failure_count >= failure_threshold:
        return FAILURE
    return RUNNING

3.4 Decorator 노드의 깊이 우선 전파

Decorator 노드는 단일 자식에 tick을 전파하고, 자식의 반환 상태를 자신의 정책에 따라 변환한다.

function DecoratorNode.tick() → status:
    child_status = child.tick()
    return transform(child_status)

여기서 transform 함수는 데코레이터의 유형에 따라 다르다. 예를 들어, Inverter 데코레이터는 Success를 Failure로, Failure를 Success로 변환한다.

4. 전체 트리에 대한 순회 추적 예시

다음 트리 구조에 대한 깊이 우선 tick 전파를 단계별로 추적한다.

         [Sequence]
         /    |    \
   [Cond_A] [Fallback] [Action_D]
              /    \
        [Action_B] [Action_C]

단계 1: Sequence가 tick을 수신한다. 첫 번째 자식 Cond_A에 tick을 전파한다.

단계 2: Cond_A는 단말 노드이므로 조건을 평가한다. Success를 반환한다고 가정한다.

단계 3: Sequence는 Cond_A가 Success를 반환하였으므로, 다음 자식 Fallback에 tick을 전파한다.

단계 4: Fallback이 tick을 수신한다. 첫 번째 자식 Action_B에 tick을 전파한다.

단계 5: Action_B는 단말 노드이므로 행동을 실행한다. Failure를 반환한다고 가정한다.

단계 6: Fallback은 Action_B가 Failure를 반환하였으므로, 다음 자식 Action_C에 tick을 전파한다.

단계 7: Action_C는 단말 노드이므로 행동을 실행한다. Success를 반환한다고 가정한다.

단계 8: Fallback은 Action_C가 Success를 반환하였으므로, Success를 Sequence에 반환한다.

단계 9: Sequence는 Fallback이 Success를 반환하였으므로, 다음 자식 Action_D에 tick을 전파한다.

단계 10: Action_D는 단말 노드이므로 행동을 실행한다. 상태를 반환한다.

단계 11: Sequence는 모든 자식의 반환 상태를 종합하여 최종 상태를 반환한다.

노드 방문 순서를 정리하면 다음과 같다.

5. 재귀적 구현과 호출 스택

깊이 우선 전파의 재귀적 구현에서 각 노드의 tick() 호출은 호출 스택(call stack)에 프레임을 추가한다. 트리의 깊이가 d이면 호출 스택의 최대 깊이도 d이다. 따라서 트리의 깊이가 매우 깊은 경우 스택 오버플로(stack overflow)의 위험이 존재한다. 그러나 실무에서 행동 트리의 깊이는 일반적으로 10~20 수준 이내이므로, 스택 오버플로가 실질적 문제가 되는 경우는 드물다.

호출 스택의 깊이를 d, 각 스택 프레임의 크기를 s라 하면, tick 전파에 필요한 스택 메모리는 O(d \cdot s)이다. 이는 트리의 전체 노드 수 n에 비해 효율적이며, d = O(\log n)인 균형 트리에서 특히 메모리 효율적이다.

6. 시간 복잡도 분석

깊이 우선 tick 전파의 시간 복잡도는 트리의 구조와 노드의 반환 상태에 의존한다.

최선의 경우(Best Case): Sequence 노드의 첫 번째 자식이 즉시 Failure를 반환하면, 나머지 자식은 평가되지 않는다. 이 경우 방문 노드 수는 O(d)이다.

최악의 경우(Worst Case): 모든 노드가 평가되는 경우이다. Parallel 노드처럼 모든 자식에 무조건적으로 tick을 전파하는 경우, 방문 노드 수는 O(n)이다. 여기서 n은 트리의 전체 노드 수이다.

평균적 경우: 조건부 전파에 의해 일부 서브트리가 건너뛰어지므로, 실제 방문 노드 수는 O(d)와 O(n) 사이이다.

7. 깊이 우선 전파의 설계적 의의

깊이 우선 전파가 행동 트리의 순회 방식으로 채택된 것은 다음의 이유에 기인한다.

첫째, 계층적 우선순위의 자연스러운 표현이다. 트리의 상위 노드가 하위 노드보다 먼저 평가되므로, 상위 수준의 결정이 하위 수준의 행동에 우선한다.

둘째, 조건부 전파와의 자연스러운 결합이다. 깊이 우선 순회에서 부모 노드가 자식의 반환 상태를 즉시 수신하므로, 후속 자식의 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/