1291.33 행동 트리의 수학적 정의

1. 행동 트리의 형식적 정의의 필요성

행동 트리(Behavior Tree, BT)가 게임 산업에서 실용적 기법으로 발전한 이후, 로봇공학 등 안전 임계(safety-critical) 분야로의 적용을 위해서는 엄밀한 수학적 정의에 기반한 형식적 분석이 필수적이다. Colledanchise와 Ögren(2017, 2018)은 BT에 대한 최초의 체계적 수학적 정의를 제시하였으며, 이 정의는 BT의 형식적 분석, 안전성 검증, 표현력 비교의 이론적 기초를 형성한다.

2. 반환 상태 집합의 정의

BT의 모든 노드는 실행 결과로서 다음의 세 가지 반환 상태 중 하나를 반환한다:

$\mathcal{R} = \{\text{Success}, \text{Failure}, \text{Running}\}$

$\text{Success}$ ( $\mathcal{S}$ ): 노드의 실행이 성공적으로 완료되었음을 나타낸다.
$\text{Failure}$ ( $\mathcal{F}$ ): 노드의 실행이 실패하였음을 나타낸다.
$\text{Running}$ ( $\mathcal{R}_u$ ): 노드의 실행이 아직 진행 중이며, 완료를 위하여 후속 tick이 필요함을 나타낸다.

3. 행동 트리의 재귀적 정의

Colledanchise와 Ögren(2018)에 따르면, 행동 트리 $T$ 는 다음과 같이 재귀적으로 정의된다:

정의 1 (행동 트리). 행동 트리는 다음의 4-튜플로 정의되는 유향 근트리(directed rooted tree)이다:

$T = \{f_T, r_T, \Delta t, T_1, T_2, \ldots, T_N\}$

여기서:

$f_T : \mathcal{R}^N \rightarrow \mathcal{R}$ 는 노드 $T$ 의 tick 함수로서, 자식 노드의 반환 상태 벡터를 입력으로 받아 자신의 반환 상태를 출력한다.
$r_T \in \mathcal{R}$ 는 노드 $T$ 의 현재 반환 상태이다.
$\Delta t$ 는 tick 주기이다.
$T_1, T_2, \ldots, T_N$ 은 $T$ 의 자식 행동 트리(서브트리)이며, $N \geq 0$ 이다.

$N = 0$ 인 경우 $T$ 는 리프 노드(leaf node)에 해당하며, $N \geq 1$ 인 경우 내부 노드(internal node)에 해당한다.

4. 제어 흐름 노드의 형식적 정의

4.1 Sequence 노드

정의 2 (Sequence). Sequence 노드 $T_{\text{Seq}}$ 는 자식 노드 $T_1, T_2, \ldots, T_N$ 을 좌측에서 우측으로 순차적으로 tick하며, 다음의 tick 함수 $f_{\text{Seq}}$ 를 가진다:

$r_{T_{\text{Seq}}} = f_{\text{Seq}}(r_{T_1}, r_{T_2}, \ldots, r_{T_N})$

tick 함수의 의미론은 다음과 같다:

자식 $T_i$ 를 $i = 1$ 부터 순차적으로 tick한다.
$r_{T_i} = \text{Success}$ 이면, 다음 자식 $T_{i+1}$ 을 tick한다.
$r_{T_i} = \text{Failure}$ 이면, 잔여 자식을 tick하지 않고 $r_{T_{\text{Seq}}} = \text{Failure}$ 를 반환한다.
$r_{T_i} = \text{Running}$ 이면, 잔여 자식을 tick하지 않고 $r_{T_{\text{Seq}}} = \text{Running}$ 을 반환한다.
모든 자식이 $\text{Success}$ 를 반환하면, $r_{T_{\text{Seq}}} = \text{Success}$ 를 반환한다.

Sequence의 의미론은 논리곱(logical AND)의 단락 평가(short-circuit evaluation)와 대응한다.

4.2 Fallback 노드

정의 3 (Fallback). Fallback 노드(Selector 노드라고도 칭함) $T_{\text{Fb}}$ 는 자식 노드 $T_1, T_2, \ldots, T_N$ 을 좌측에서 우측으로 순차적으로 tick하며, 다음의 tick 함수 $f_{\text{Fb}}$ 를 가진다:

$r_{T_{\text{Fb}}} = f_{\text{Fb}}(r_{T_1}, r_{T_2}, \ldots, r_{T_N})$

tick 함수의 의미론은 다음과 같다:

자식 $T_i$ 를 $i = 1$ 부터 순차적으로 tick한다.
$r_{T_i} = \text{Failure}$ 이면, 다음 자식 $T_{i+1}$ 을 tick한다.
$r_{T_i} = \text{Success}$ 이면, 잔여 자식을 tick하지 않고 $r_{T_{\text{Fb}}} = \text{Success}$ 를 반환한다.
$r_{T_i} = \text{Running}$ 이면, 잔여 자식을 tick하지 않고 $r_{T_{\text{Fb}}} = \text{Running}$ 을 반환한다.
모든 자식이 $\text{Failure}$ 를 반환하면, $r_{T_{\text{Fb}}} = \text{Failure}$ 를 반환한다.

Fallback의 의미론은 논리합(logical OR)의 단락 평가와 대응한다.

4.3 Parallel 노드

정의 4 (Parallel). Parallel 노드 $T_{\text{Par}}$ 는 모든 자식 노드 $T_1, T_2, \ldots, T_N$ 을 동시에 tick하며, 성공 임계값(success threshold) $M$ 에 기반하여 반환 상태를 결정한다. $1 \leq M \leq N$ 이며:

$M$ 개 이상의 자식이 $\text{Success}$ 를 반환하면, $r_{T_{\text{Par}}} = \text{Success}$ 를 반환한다.
$N - M + 1$ 개 이상의 자식이 $\text{Failure}$ 를 반환하면, $r_{T_{\text{Par}}} = \text{Failure}$ 를 반환한다.
그 외의 경우, $r_{T_{\text{Par}}} = \text{Running}$ 을 반환한다.

5. 실행 노드의 형식적 정의

5.1 액션 노드

정의 5 (Action). 액션 노드 $T_{\text{Act}}$ 는 자식 노드를 갖지 않는 리프 노드( $N = 0$ )로서, tick을 수신하면 에이전트의 행동을 실행하고 $\mathcal{R}$ 중 하나를 반환한다. tick 함수는 환경 상태 $\mathbf{x} \in \mathcal{X}$ 에 의존한다:

$r_{T_{\text{Act}}} = f_{\text{Act}}(\mathbf{x})$

여기서 $\mathcal{X}$ 는 환경 상태 공간이다. 행동의 부수 효과(side effect)로서 환경 상태가 $\mathbf{x}$ 에서 $\mathbf{x}'$ 으로 변경될 수 있다.

5.2 조건 노드

정의 6 (Condition). 조건 노드 $T_{\text{Cond}}$ 는 자식 노드를 갖지 않는 리프 노드( $N = 0$ )로서, 환경 상태에 대한 술어(predicate) $p : \mathcal{X} \rightarrow \{\text{true}, \text{false}\}$ 를 평가한다:

$r_{T_{\text{Cond}}} = \begin{cases} \text{Success} & \text{if } p(\mathbf{x}) = \text{true} \\ \text{Failure} & \text{if } p(\mathbf{x}) = \text{false} \end{cases}$

조건 노드는 환경 상태를 변경하지 않으며, $\text{Running}$ 을 반환하지 않는다.

6. 데코레이터 노드의 형식적 정의

정의 7 (Decorator). 데코레이터 노드 $T_{\text{Dec}}$ 는 정확히 하나의 자식 $T_1$ 을 보유하며( $N = 1$ ), 자식의 반환 상태를 변형하는 단항 함수 $\delta : \mathcal{R} \rightarrow \mathcal{R}$ 를 적용한다:

$r_{T_{\text{Dec}}} = \delta(r_{T_1})$

대표적 데코레이터의 형식적 정의는 다음과 같다:

Inverter(반전):

$\delta_{\text{Inv}}(r) = \begin{cases} \text{Failure} & \text{if } r = \text{Success} \\ \text{Success} & \text{if } r = \text{Failure} \\ \text{Running} & \text{if } r = \text{Running} \end{cases}$

ForceSuccess(강제 성공):

$\delta_{\text{FS}}(r) = \begin{cases} \text{Success} & \text{if } r = \text{Success} \lor r = \text{Failure} \\ \text{Running} & \text{if } r = \text{Running} \end{cases}$

7. 행동 트리의 실행 의미론

7.1 Tick 함수의 재귀적 실행

BT의 실행은 외부 시계(external clock)로부터 주기 $\Delta t$ 마다 전달되는 tick 신호에 의하여 구동된다. 시각 $t_k = k \cdot \Delta t$ 에서 루트 노드 $T_{\text{root}}$ 에 tick이 전달되면, $T_{\text{root}}$ 의 tick 함수 $f_{T_{\text{root}}}$ 가 실행된다. $f_{T_{\text{root}}}$ 는 자신의 의미론에 따라 자식 노드에 tick을 전파하며, 이 과정이 트리의 깊이에 따라 재귀적으로 진행된다.

7.2 상태 공간 표현

시각 $t_k$ 에서 BT의 상태는 모든 노드의 반환 상태 벡터로 표현된다:

$\mathbf{r}(t_k) = (r_{T_1}(t_k), r_{T_2}(t_k), \ldots, r_{T_M}(t_k))$

여기서 $M$ 은 BT를 구성하는 전체 노드의 수이다. 환경 상태 $\mathbf{x}(t_k)$ 와 결합하여, BT의 전체 동적 시스템은 다음과 같이 표현된다:

$(\mathbf{r}(t_{k+1}), \mathbf{x}(t_{k+1})) = G(\mathbf{r}(t_k), \mathbf{x}(t_k))$

여기서 $G$ 는 BT의 tick 실행과 환경의 동역학을 결합한 전역 갱신 함수이다. 이 표현에 의하여, BT의 동작이 이산 시간 동적 시스템(discrete-time dynamical system)으로 형식화되며, 안정성 분석, 수렴성 분석 등 제어 이론의 분석 도구를 BT에 적용할 수 있는 이론적 기반이 마련된다.

8. 강건성의 형식적 정의

Colledanchise와 Ögren(2018)은 BT의 강건성(robustness)을 형식적으로 정의하였다. BT $T$ 가 환경 상태 공간 $\mathcal{X}$ 의 영역 $\mathcal{X}_S \subset \mathcal{X}$ 에 대하여 **안전(safe)**하다는 것은, 임의의 초기 상태 $\mathbf{x}(t_0) \in \mathcal{X}_S$ 에 대하여 모든 후속 시각 $t_k > t_0$ 에서 $\mathbf{x}(t_k) \in \mathcal{X}_S$ 가 보장되는 것으로 정의된다.

BT $T$ 가 목표 영역 $\mathcal{X}_G \subset \mathcal{X}$ 에 대하여 **유한 시간 성공적(finite-time successful)**이라는 것은, 유한 시각 $t_K$ 가 존재하여 $r_{T_{\text{root}}}(t_K) = \text{Success}$ 이고 $\mathbf{x}(t_K) \in \mathcal{X}_G$ 가 되는 것으로 정의된다.

9. 행동 트리의 합성 기반 구성

BT의 수학적 정의는 합성(composition) 연산의 형식화를 가능하게 한다. 두 행동 트리 $T_A$ 와 $T_B$ 에 대하여:

Sequence 합성: $T_{\text{Seq}}(T_A, T_B)$ 는 “ $T_A$ 를 수행하고, 성공하면 $T_B$ 를 수행하라“를 표현한다.
Fallback 합성: $T_{\text{Fb}}(T_A, T_B)$ 는 “ $T_A$ 를 시도하고, 실패하면 $T_B$ 를 시도하라“를 표현한다.

이 합성 연산에 의하여 BT는 닫힘 속성(closure property)을 만족한다. 즉, 두 BT의 합성 결과 역시 유효한 BT이며, 이 속성이 BT의 모듈적 구축과 계층적 분해를 수학적으로 보장한다.

10. 수학적 정의의 학술적 의의

BT의 수학적 정의는 다음의 학술적 기여를 제공한다.

첫째, BT의 동작을 수학적으로 엄밀하게 기술함으로써, BT의 속성에 대한 형식적 증명(formal proof)이 가능해진다. 안전성, 활성성(liveness), 교착 부재(deadlock-freedom) 등 시스템 속성의 형식적 검증이 수학적 정의에 기반하여 수행될 수 있다.

둘째, BT를 이산 시간 동적 시스템으로 형식화함으로써, 제어 이론의 안정성 분석 도구(리아푸노프 함수, 수렴 증명 등)를 BT의 행동 분석에 적용할 수 있는 이론적 상호 연결이 확립된다.

셋째, BT와 FSM, HTN, 포괄 아키텍처 등 기존 행동 제어 기법의 표현력을 수학적으로 엄밀하게 비교할 수 있는 공통 형식 체계가 제공된다.

11. 참고 문헌

Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
Colledanchise, M., & Ögren, P. (2017). “How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees.” IEEE Transactions on Robotics, 33(2), 372–389.
Biggar, O., Zamani, M., & Shames, I. (2020). “A Framework for Formal Verification of Behavior Trees with Linear Temporal Logic.” IEEE Robotics and Automation Letters, 5(2), 2435–2442.
Sprague, C. I., Ögren, P., & Colledanchise, M. (2018). “Adding Memory to Behavior Trees.” arXiv preprint arXiv:1809.07874.

v0.2.0