1292.2 방향 비순환 그래프로서의 행동 트리

1. 방향 비순환 그래프의 정의

방향 비순환 그래프(directed acyclic graph, DAG)는 방향 그래프(directed graph)의 일종으로, 그래프 내에 방향 순환(directed cycle)이 존재하지 않는 구조를 의미한다. 형식적으로 DAG G는 다음과 같이 정의한다.

G = (V, E), \quad E \subseteq V \times V

여기서 V는 정점(vertex)의 유한 집합이며, E는 방향 간선(directed edge)의 집합이다. DAG의 핵심 제약은 임의의 정점 v \in V에서 출발하여 방향 간선을 따라 이동할 때, 다시 v로 되돌아오는 경로가 존재하지 않는다는 것이다. 즉, 다음 조건이 성립한다.

\nexists \, v \in V : v \rightsquigarrow v

여기서 v \rightsquigarrow v는 v에서 v로의 방향 경로(directed path)의 존재를 나타낸다.

2. 트리와 DAG의 관계

트리 자료 구조는 DAG의 특수한 형태이다. 모든 트리는 DAG이지만, 모든 DAG가 트리는 아니다. 양자의 구조적 차이는 다음과 같이 정리할 수 있다.

트리에서는 각 노드가 정확히 하나의 부모를 가지므로 루트로부터 임의의 노드까지의 경로가 유일하다. 반면 DAG에서는 하나의 노드가 둘 이상의 부모를 가질 수 있으므로, 루트로부터 특정 노드까지 복수의 경로가 존재할 수 있다.

3. 행동 트리의 DAG 관점

행동 트리는 기본적으로 순서 트리(ordered tree)로 정의되지만, 실질적 구현 및 운용 과정에서 DAG의 특성을 일부 수용한다. 이러한 확장이 필요한 주요 동기는 다음과 같다.

3.1 서브트리 재사용과 노드 공유

실제 로봇 시스템에서는 동일한 행동 패턴이 트리의 서로 다른 위치에서 반복적으로 요구되는 경우가 빈번하다. 예를 들어, “배터리 잔량 확인” 조건 노드는 트리의 여러 분기에서 사용될 수 있다. 순수한 트리 구조에서는 동일한 서브트리를 매번 복제(duplication)하여 배치해야 하므로 메모리 비효율과 유지보수의 어려움이 발생한다. DAG 구조를 허용하면 하나의 서브트리 정의를 여러 부모 노드가 참조할 수 있으므로, 구조적 중복을 제거할 수 있다.

3.2 논리적 DAG와 물리적 트리의 구분

행동 트리 프레임워크에서는 논리적 수준(logical level)과 물리적 수준(physical level)을 구분하여 DAG 특성을 수용한다. 논리적 수준에서 행동 트리의 설계자는 서브트리를 참조(reference) 방식으로 공유하여 DAG 위상(topology)을 구성할 수 있다. 그러나 물리적 수준에서는 실행 시점에 각 참조가 독립적인 인스턴스로 확장(instantiation)되어, 실제 실행 구조는 트리의 형태를 유지한다. 이 이중 구조를 형식적으로 표현하면 다음과 같다.

G_{\text{logical}} = (V_L, E_L) \quad \text{(DAG)}

T_{\text{physical}} = (V_P, E_P) \quad \text{(Tree)}, \quad \lvert V_P \rvert \geq \lvert V_L \rvert

논리적 DAG G_{\text{logical}}에서 공유된 노드는 물리적 트리 T_{\text{physical}}에서 복수의 독립 인스턴스로 전개되므로, \lvert V_P \rvert \geq \lvert V_L \rvert가 성립한다.

4. DAG 위상에서의 실행 의미론

행동 트리가 DAG 위상을 논리적으로 허용하더라도, 실행 의미론(execution semantics)은 트리 순회 기반의 결정론적 실행을 유지해야 한다. 이를 보장하기 위해 다음의 원칙이 적용된다.

4.1 인스턴스 격리 원칙

공유된 서브트리의 각 인스턴스는 독립적인 실행 상태(execution state)를 유지한다. 한 인스턴스에서의 상태 변화가 다른 인스턴스에 영향을 미치지 않으며, 이를 통해 DAG 구조에서 발생할 수 있는 상태 간섭(state interference) 문제를 방지한다. 노드 n이 DAG에서 두 부모 p_1과 p_2에 의해 공유될 때, 실행 시에는 다음과 같이 분리된다.

n \rightarrow \{n_{p_1}, n_{p_2}\}, \quad \text{state}(n_{p_1}) \perp \text{state}(n_{p_2})

여기서 \perp는 상태의 독립성을 나타낸다.

4.2 비순환 제약의 유지

DAG의 핵심 제약인 비순환성은 행동 트리에서 반드시 유지되어야 한다. 순환이 존재할 경우 Tick 신호의 전파가 무한 루프에 빠질 수 있으며, 이는 실시간 로봇 시스템에서 치명적인 오류를 야기한다. 따라서 행동 트리 프레임워크는 트리 구성 시점에 위상 정렬(topological sorting)을 통해 순환 존재 여부를 검증한다. DAG G = (V, E)에 대한 위상 정렬이 존재하기 위한 필요충분조건은 G가 비순환임이며, 이는 다음과 같이 표현된다.

\exists \, \sigma: V \rightarrow \{1, 2, \ldots, \lvert V \rvert\} \quad \text{s.t.} \quad (u, v) \in E \Rightarrow \sigma(u) < \sigma(v)

5. DAG 관점의 구조적 분석

행동 트리를 DAG로 해석하면 다음과 같은 구조적 분석이 가능하다.

5.1 노드 진입 차수와 역할 분류

DAG에서 각 노드의 진입 차수(in-degree)는 해당 노드가 참조되는 횟수를 나타낸다.

• 진입 차수 0: 루트 노드에 해당하며, 트리 전체에서 유일하게 존재한다.
• 진입 차수 1: 단일 부모에 의해 참조되는 노드로, 순수 트리 구조를 따른다.
• 진입 차수 2 이상: 복수의 부모에 의해 공유되는 노드로, DAG 고유의 특성이 나타나는 지점이다.

5.2 노드 진출 차수와 노드 유형

DAG에서 각 노드의 진출 차수(out-degree)는 해당 노드의 자식 수를 나타내며, 행동 트리의 노드 유형과 직접 관련된다.

• 진출 차수 0: 리프 노드로서 액션 노드 또는 조건 노드에 해당한다.
• 진출 차수 1: 데코레이터 노드에 해당하며, 정확히 하나의 자식 노드를 가진다.
• 진출 차수 2 이상: 제어 흐름 노드(Sequence, Fallback, Parallel 등)에 해당한다.

6. 행동 트리에서 순수 DAG 구조의 한계

행동 트리를 순수한 DAG로 구현할 경우 다음과 같은 문제가 발생할 수 있다.

첫째, 노드 공유 시 각 인스턴스의 실행 상태를 독립적으로 관리해야 하므로, 상태 관리의 복잡성이 증가한다. 특히 Running 상태를 반환하는 비동기 액션 노드가 공유될 경우, 동일 노드의 서로 다른 실행 맥락(execution context)을 구분하는 메커니즘이 필수적이다.

둘째, Tick 신호의 전파 경로가 복수로 존재할 수 있으므로, 동일 노드가 하나의 Tick 주기 내에서 중복 실행(double execution)될 위험이 있다. 이를 방지하기 위해 각 Tick 주기에 대한 실행 표식(execution mark)을 도입하거나, 물리적 트리로의 전개를 통해 중복 실행을 원천적으로 차단해야 한다.

이러한 이유로 대부분의 행동 트리 프레임워크는 논리적으로는 DAG 기반의 서브트리 재사용을 허용하되, 실행 시에는 트리 구조로 전개하여 결정론적 실행 의미론을 보존하는 혼합 접근법(hybrid approach)을 채택한다.

7. 참고 문헌

• Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
• Bang-Jensen, J., & Gutin, G. Z. (2009). Digraphs: Theory, Algorithms and Applications (2nd ed.). Springer.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Iovino, M., Scukins, E., Styrud, J., Ögren, P., & Smith, C. (2022). A Survey of Behavior Trees in Robotics and AI. Robotics and Autonomous Systems, 154, 104096.

본 절은 Version 1로 작성되었다.