1292.28 깊이 우선 탐색 (DFS) 기반 실행

1292.28 깊이 우선 탐색 (DFS) 기반 실행

1. 행동 트리 실행과 깊이 우선 탐색의 관계

행동 트리(Behavior Tree)의 tick 전파 메커니즘은 그래프 이론에서의 깊이 우선 탐색(Depth-First Search, DFS) 알고리즘과 구조적으로 동일한 순회 패턴을 따른다. 루트 노드에서 시작된 tick 신호는 트리의 깊이 방향으로 우선적으로 전파되어, 가능한 한 깊은 노드(리프 노드)까지 도달한 후 반환 상태를 상위 노드로 전파한다. 이러한 실행 방식은 행동 트리의 결정론적(deterministic) 실행 순서를 보장하는 근본적인 메커니즘이다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

깊이 우선 탐색 기반 실행은 행동 트리가 트리 자료 구조(tree data structure)에 기반한다는 구조적 특성으로부터 자연스럽게 도출된다. 트리 구조에서 각 노드는 정확히 하나의 부모 노드를 가지므로, 루트에서 임의의 노드까지의 경로는 유일하며, 이 유일한 경로를 따라 tick이 전파된다.

2. 깊이 우선 탐색의 형식적 정의

트리 T = (V, E)에서 깊이 우선 탐색은 루트 노드 r \in V에서 시작하여 다음의 재귀적 규칙에 따라 노드를 방문하는 순회 알고리즘이다.

  1. 현재 노드 v를 방문한다.
  2. v의 자식 노드 c_1, c_2, \ldots, c_n을 왼쪽에서 오른쪽 순서로 순회한다.
  3. 각 자식 c_i에 대해 동일한 절차를 재귀적으로 적용한다.

행동 트리의 tick 전파에서는 위 알고리즘에 조기 종료(short-circuit) 규칙이 추가된다. 제어 흐름 노드가 특정 자식의 반환 상태에 따라 후속 자식의 방문을 생략할 수 있으므로, 행동 트리의 실행은 조건부 깊이 우선 탐색(conditional DFS)으로 분류된다.

이를 의사 코드로 표현하면 다음과 같다.

function tick(node):
    if node is leaf:
        return node.execute()
    for each child in node.children:
        status = tick(child)
        result = node.evaluatePolicy(child, status)
        if result is determined:
            return result
    return node.finalResult()

위 의사 코드에서 evaluatePolicy는 제어 흐름 노드의 정책에 따라 현재 자식의 반환 상태를 평가하고, 후속 자식의 실행 여부와 자신의 반환 상태를 결정하는 함수이다.

3. DFS 기반 실행의 특성

3.1 전위 순회 순서

행동 트리의 tick 전파는 전위 순회(pre-order traversal) 순서를 따른다. 전위 순회에서는 부모 노드가 자식 노드보다 먼저 방문된다. 행동 트리에서 제어 흐름 노드는 자신이 먼저 tick을 수신한 후, 자신의 정책에 따라 자식 노드에 tick을 전달한다. 이 순서는 부모 노드가 자식 노드의 실행을 제어하는 하향식 제어 구조(top-down control structure)를 구현한다.

3.2 왼쪽에서 오른쪽 순서

동일한 부모를 가진 형제 노드(sibling nodes)는 왼쪽에서 오른쪽 순서로 방문된다. 이 순서는 행동 트리에서 자식 노드의 우선순위를 결정한다. Sequence 노드에서는 왼쪽 자식이 오른쪽 자식보다 먼저 실행되며, Fallback 노드에서도 동일한 순서가 적용된다. 따라서 트리 설계 시 높은 우선순위를 가진 행동이나 조건을 왼쪽에 배치하는 것이 관례이다 (Colledanchise & Ögren, 2018).

3.3 재귀적 구조

DFS 기반 실행은 본질적으로 재귀적(recursive) 구조를 가진다. 루트 노드의 tick 호출은 자식 노드의 tick 호출을 재귀적으로 유발하며, 이 재귀 호출의 깊이는 트리의 높이(height)와 동일하다. 재귀 호출이 리프 노드에 도달하면 해당 노드의 반환 상태가 재귀 스택(recursion stack)을 따라 상위 노드로 전파된다.

4. DFS 기반 실행과 조기 종료

행동 트리의 DFS 기반 실행이 일반적인 DFS와 구별되는 핵심적인 특성은 조기 종료(short-circuit) 규칙의 존재이다. 조기 종료란, 제어 흐름 노드가 특정 자식의 반환 상태를 수신한 후 나머지 자식의 탐색을 생략하고 즉시 자신의 반환 상태를 결정하는 것을 의미한다.

Sequence 노드의 경우, 임의의 자식이 Failure를 반환하면 후속 자식에 대한 탐색을 즉시 중단하고 Failure를 반환한다. Fallback 노드의 경우, 임의의 자식이 Success를 반환하면 후속 자식에 대한 탐색을 즉시 중단하고 Success를 반환한다. 이 규칙은 프로그래밍 언어에서 논리 연산자의 단락 평가(short-circuit evaluation)와 구조적으로 유사하다. Sequence 노드는 논리곱(AND) 연산의 단락 평가에, Fallback 노드는 논리합(OR) 연산의 단락 평가에 대응된다 (Colledanchise & Ögren, 2018).

조기 종료에 의해 방문되지 않은 노드는 Idle 상태를 유지하며, 해당 tick의 실행 추적에 포함되지 않는다. 이로 인해 동일한 트리 구조에서도 환경 조건에 따라 tick마다 방문되는 노드의 집합이 달라질 수 있다.

5. DFS 기반 실행의 예제

다음의 행동 트리를 고려한다.

Root
 └─ Fallback [F1]
     ├─ Sequence [S1]
     │   ├─ Condition [C1]
     │   └─ Action [A1]
     └─ Sequence [S2]
         ├─ Condition [C2]
         └─ Action [A2]

DFS 기반 실행에서 tick의 방문 순서는 다음과 같다.

  1. Root를 방문하고, 자식 F1에 tick을 전달한다.
  2. F1을 방문하고, 첫 번째 자식 S1에 tick을 전달한다 (깊이 우선).
  3. S1을 방문하고, 첫 번째 자식 C1에 tick을 전달한다 (깊이 우선).
  4. C1은 리프 노드이므로 실행 후 반환 상태를 산출한다.

C1이 Success를 반환하는 경우: S1은 다음 자식 A1에 tick을 전달한다. A1이 Success를 반환하면 S1도 Success를 반환하고, F1은 조기 종료하여 S2를 방문하지 않는다.

DFS 방문 순서: Root \rightarrow F1 \rightarrow S1 \rightarrow C1 \rightarrow A1

C1이 Failure를 반환하는 경우: S1은 조기 종료하여 A1을 방문하지 않고 Failure를 반환한다. F1은 다음 자식 S2에 tick을 전달하고, S2의 자식인 C2, A2가 순차적으로 방문된다.

DFS 방문 순서: Root \rightarrow F1 \rightarrow S1 \rightarrow C1 \rightarrow S2 \rightarrow C2 \rightarrow A2

이 예제는 동일한 트리 구조에서 환경 조건에 따라 DFS의 탐색 경로가 동적으로 변화함을 보여준다.

6. DFS 기반 실행의 시간 복잡도

단일 tick에서 행동 트리의 DFS 기반 실행의 시간 복잡도는 트리의 노드 수 n에 대해 O(n)이다. 이는 최악의 경우 모든 노드가 한 번씩 방문되는 상황에 해당한다. 그러나 조기 종료 규칙에 의해 실제 방문되는 노드의 수 m은 일반적으로 m \leq n을 만족하므로, 평균적인 시간 복잡도는 O(n)보다 작다.

공간 복잡도는 재귀 호출 스택의 깊이에 의해 결정되며, 트리의 높이 h에 대해 O(h)이다. 균형 잡힌 행동 트리에서 h = O(\log n)이므로, 공간 복잡도는 O(\log n)이 된다. 그러나 행동 트리의 설계에서 트리의 높이는 일반적으로 작은 상수 범위에 머무르므로, 실무적으로 공간 복잡도가 문제가 되는 경우는 드물다.

7. DFS 기반 실행과 BFS 기반 실행의 비교

행동 트리의 실행 방식으로 너비 우선 탐색(Breadth-First Search, BFS)이 아닌 DFS가 채택된 것은 행동 트리의 의미론적(semantic) 요구사항에 기인한다. BFS는 동일 깊이의 모든 노드를 방문한 후 다음 깊이로 진행하므로, 제어 흐름 노드가 자식의 반환 상태를 수신하기 전에 다른 분기의 노드를 방문하게 된다. 이는 행동 트리의 핵심 원리인 “자식의 반환 상태에 따른 조건부 실행“과 양립할 수 없다.

DFS 기반 실행에서는 자식 노드의 반환 상태가 부모 노드에 즉시 전달되므로, 제어 흐름 노드가 각 자식의 결과를 순차적으로 평가하고 후속 실행을 결정할 수 있다. 이 특성은 Sequence 노드의 순차적 실행, Fallback 노드의 대안 탐색, 데코레이터 노드의 결과 변환 등 행동 트리의 모든 제어 흐름 메커니즘의 기반이 된다 (Colledanchise & Ögren, 2018).

8. DFS 기반 실행의 결정론적 특성

DFS 기반 실행은 행동 트리에 결정론적(deterministic) 실행 순서를 부여한다. 동일한 트리 구조와 동일한 환경 상태가 주어지면, DFS는 항상 동일한 순서로 노드를 방문하고 동일한 실행 추적을 생성한다. 이 결정론적 특성은 다음과 같은 이점을 제공한다.

첫째, 재현 가능성(reproducibility)이 보장된다. 동일한 입력 조건에서 행동 트리가 항상 동일한 행동을 산출하므로, 디버깅과 테스트가 용이하다.

둘째, 예측 가능성(predictability)이 확보된다. 트리 구조를 정적으로 분석하여 특정 환경 조건에서 어떤 노드가 실행되는지를 사전에 예측할 수 있다.

셋째, 우선순위의 명시적 표현이 가능하다. 왼쪽에서 오른쪽으로의 DFS 방문 순서는 자식 노드의 상대적 우선순위를 트리 구조에 내재적으로 인코딩한다. 설계자는 높은 우선순위의 행동을 왼쪽에 배치함으로써 실행 우선순위를 직관적으로 제어할 수 있다.

참고 문헌

  • Colledanchise, M. & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.