396.46 행동 트리의 노드 유형과 실행 흐름

1. 개요

행동 트리(Behavior Tree, BT)의 표현력과 유연성은 다양한 노드 유형의 체계적 조합과 명확하게 정의된 실행 흐름(Execution Flow)에 의해 결정된다. 본 절에서는 행동 트리를 구성하는 모든 표준 노드 유형의 형식적 의미론(Formal Semantics)을 상세히 기술하고, 틱(Tick) 전파에 기반한 실행 흐름의 동작 원리를 분석한다.

2. 제어 흐름 노드(Control Flow Nodes)

제어 흐름 노드는 자식 노드의 실행 순서, 조건, 합성 방식을 결정하는 내부 노드이다. 표준 행동 트리에서 정의되는 제어 흐름 노드의 유형은 다음과 같다.

2.1 시퀀스 노드(Sequence Node, →)

시퀀스 노드는 자식 노드를 왼쪽에서 오른쪽으로 순차 실행하며, 모든 자식이 성공하여야 전체가 성공하는 “논리적 AND” 의미론을 갖는다.

실행 알고리즘:

function tick(Sequence):
    for i = 1 to N:
        status = tick(child[i])
        if status == RUNNING:
            return RUNNING
        if status == FAILURE:
            return FAILURE
    return SUCCESS

형식적 정의:

$\text{Seq}(c_1, \ldots, c_N) = \begin{cases} \text{FAILURE} & \text{if } \exists i \leq N : r_i = \text{FAILURE} \wedge \forall j < i : r_j = \text{SUCCESS} \\ \text{RUNNING} & \text{if } \exists i \leq N : r_i = \text{RUNNING} \wedge \forall j < i : r_j = \text{SUCCESS} \\ \text{SUCCESS} & \text{if } \forall i \leq N : r_i = \text{SUCCESS} \end{cases}$

여기서 $r_i$ 는 자식 노드 $c_i$ 의 반환 상태이다.

2.2 메모리 시퀀스(Sequence with Memory, →*)

표준 시퀀스 노드는 매 틱마다 첫 번째 자식부터 재평가한다. 메모리 시퀀스는 이전 틱에서 SUCCESS를 반환한 자식 노드를 건너뛰고, RUNNING을 반환한 자식부터 실행을 재개한다.

$\text{SeqMem}(c_1, \ldots, c_N) : \text{resume from } c_k \text{ where } c_{k-1} = \text{SUCCESS at previous tick}$

메모리 시퀀스는 이미 성공한 행동을 반복 실행하지 않아 계산 효율성을 향상시키지만, 환경 변화에 대한 반응성이 저하될 수 있다.

2.3 반응적 시퀀스(Reactive Sequence)

반응적 시퀀스는 매 틱마다 조건 노드를 재평가하면서도, RUNNING 상태인 행동 노드의 실행을 지속한다. 이를 통해 조건 변화에 대한 반응성과 행동의 지속성을 동시에 확보한다.

2.4 폴백 노드(Fallback Node, ?)

폴백 노드(또는 셀렉터 노드, Selector Node)는 자식 노드를 왼쪽에서 오른쪽으로 순차 실행하며, 하나의 자식이라도 성공하면 전체가 성공하는 “논리적 OR” 의미론을 갖는다.

실행 알고리즘:

function tick(Fallback):
    for i = 1 to N:
        status = tick(child[i])
        if status == RUNNING:
            return RUNNING
        if status == SUCCESS:
            return SUCCESS
    return FAILURE

형식적 정의:

$\text{Fal}(c_1, \ldots, c_N) = \begin{cases} \text{SUCCESS} & \text{if } \exists i \leq N : r_i = \text{SUCCESS} \wedge \forall j < i : r_j = \text{FAILURE} \\ \text{RUNNING} & \text{if } \exists i \leq N : r_i = \text{RUNNING} \wedge \forall j < i : r_j = \text{FAILURE} \\ \text{FAILURE} & \text{if } \forall i \leq N : r_i = \text{FAILURE} \end{cases}$

폴백 노드는 대안적 전략의 우선순위별 시도에 활용된다. 첫 번째 자식이 실패하면 두 번째 자식을 시도하고, 이것도 실패하면 세 번째를 시도하는 방식이다.

2.5 메모리 폴백(Fallback with Memory, ?*)

메모리 시퀀스와 유사하게, 메모리 폴백은 이전 틱에서 FAILURE를 반환한 자식을 건너뛰고 RUNNING을 반환한 자식부터 재개한다.

2.6 병렬 노드(Parallel Node, ⇒)

병렬 노드는 모든 자식 노드에 동시에 틱을 전달한다. 성공 정책(Success Policy)과 실패 정책(Failure Policy)에 따라 반환 상태가 결정된다.

성공 정책 $M$ -of- $N$ :

$\text{Par}_M(c_1, \ldots, c_N) = \begin{cases} \text{SUCCESS} & \text{if } S \geq M \\ \text{FAILURE} & \text{if } F > N - M \\ \text{RUNNING} & \text{otherwise} \end{cases}$

여기서 $S = |\{i : r_i = \text{SUCCESS}\}|$ , $F = |\{i : r_i = \text{FAILURE}\}|$ 이다.

병렬 노드의 대표적 활용 사례는 다음과 같다.

성공 정책	의미	활용 사례
1-of-N	하나만 성공하면 전체 성공	다중 전략 중 최초 성공 선택
N-of-N	모두 성공하여야 전체 성공	동시 수행 과업의 완료 확인
M-of-N	M개 이상 성공하면 전체 성공	과반수 합의 기반 행동

3. 데코레이터 노드(Decorator Nodes)

데코레이터 노드는 단일 자식 노드를 갖는 특수 제어 노드로, 자식 노드의 반환 상태를 수정하거나 실행 조건을 부가한다.

3.1 반전자(Inverter, ¬)

반전자는 자식 노드의 SUCCESS와 FAILURE를 뒤집는다. RUNNING은 변경하지 않는다.

$\text{Inv}(c) = \begin{cases} \text{SUCCESS} & \text{if } r_c = \text{FAILURE} \\ \text{FAILURE} & \text{if } r_c = \text{SUCCESS} \\ \text{RUNNING} & \text{if } r_c = \text{RUNNING} \end{cases}$

3.2 반복자(Repeat, ↻)

반복자는 자식 노드를 지정된 횟수만큼 또는 특정 조건이 충족될 때까지 반복 실행한다.

$\text{Repeat}_n(c) : \text{execute } c \text{ up to } n \text{ times, until FAILURE}$

3.3 재시도(Retry)

재시도 데코레이터는 자식 노드가 FAILURE를 반환할 때 지정된 횟수만큼 재시도한다.

$\text{Retry}_n(c) : \text{execute } c \text{ up to } n \text{ times, until SUCCESS}$

3.4 강제 성공(ForceSuccess)

자식 노드의 반환 상태에 관계없이 항상 SUCCESS를 반환한다. RUNNING은 그대로 전달한다.

$\text{ForceSuccess}(c) = \begin{cases} \text{SUCCESS} & \text{if } r_c \in \{\text{SUCCESS}, \text{FAILURE}\} \\ \text{RUNNING} & \text{if } r_c = \text{RUNNING} \end{cases}$

3.5 강제 실패(ForceFailure)

자식 노드의 반환 상태에 관계없이 항상 FAILURE를 반환한다.

3.6 타임아웃(Timeout)

자식 노드의 실행 시간이 지정된 시간 $T$ 를 초과하면 FAILURE를 반환하고 자식을 중단한다.

$\text{Timeout}_T(c) = \begin{cases} r_c & \text{if } t_{\text{elapsed}} < T \\ \text{FAILURE} & \text{if } t_{\text{elapsed}} \geq T \end{cases}$

4. 실행 노드(Execution Nodes)

4.1 행동 노드(Action Node)

행동 노드는 로봇의 물리적 행동을 실행하는 단말 노드이다.

동기 행동 노드(Synchronous Action): 틱이 전달되면 즉시 실행을 완료하고 SUCCESS 또는 FAILURE를 반환한다. 계산 비용이 작은 연산에 적합하다.

$\text{SyncAction}.\text{tick}() \rightarrow \text{Status} \in \{\text{SUCCESS}, \text{FAILURE}\}$

비동기 행동 노드(Asynchronous Action): 실행이 진행 중일 때 RUNNING을 반환하며, 향후 틱에서 완료 여부를 다시 확인한다. 네비게이션, 조작 등 장기 실행 행동에 사용된다.

$\text{AsyncAction}.\text{tick}() \rightarrow \text{Status} \in \{\text{SUCCESS}, \text{FAILURE}, \text{RUNNING}\}$

비동기 행동 노드는 다음의 생명 주기를 갖는다.

$\text{IDLE} \xrightarrow{\text{first tick}} \text{RUNNING} \xrightarrow{\text{completion}} \text{SUCCESS} \text{ or } \text{FAILURE}$

4.2 조건 노드(Condition Node)

조건 노드는 환경 상태나 시스템 변수를 평가하는 단말 노드이다. 항상 즉시 결과를 반환하며 RUNNING 상태를 갖지 않는다.

$\text{Condition}.\text{tick}() \rightarrow \text{Status} \in \{\text{SUCCESS}, \text{FAILURE}\}$

조건 노드의 전형적 활용 예시는 다음과 같다.

조건 노드	설명	반환 조건
IsBatteryOK	배터리 잔량 확인	$E_{\text{battery}} \geq E_{\text{min}}$
IsPathClear	경로 장애물 유무	$d_{\text{obstacle}} \geq d_{\text{safe}}$
IsGoalReached	목표 도달 여부	$\lVert p_{\text{robot}} - p_{\text{goal}} \rVert \leq \epsilon$
IsCommActive	통신 상태 확인	$\text{link\_quality} \geq q_{\text{min}}$

5. 실행 흐름 분석

5.1 틱 전파 과정

행동 트리의 실행은 루트 노드에서 시작되는 틱의 전파 과정으로 설명된다. 매 틱 주기마다 다음의 과정이 수행된다.

루트 노드에 틱이 전달된다.
루트 노드는 자신의 유형에 따라 자식 노드에 틱을 전파한다.
각 자식 노드는 반환 상태를 부모 노드에 반환한다.
부모 노드는 자식 노드의 반환 상태에 기반하여 자신의 반환 상태를 결정한다.
이 과정이 루트 노드까지 역전파되어 전체 트리의 실행 상태가 결정된다.

5.2 실행 예시: 순찰 로봇

순찰 로봇의 행동 트리를 다음과 같이 구성한다.

        [?] Root Fallback
       /              \
   [→] NormalPatrol    [→] Emergency
   / | \                / \
  C1  A1  A2          C3  A3

$C_1$ : BatteryOK 조건
$A_1$ : NavigateToWaypoint 행동
$A_2$ : ScanArea 행동
$C_3$ : EmergencyDetected 조건
$A_3$ : ReturnToBase 행동

틱 1: $C_1$ → SUCCESS, $A_1$ → RUNNING (이동 중)

NormalPatrol → RUNNING
Root → RUNNING

틱 2: $C_1$ → SUCCESS, $A_1$ → SUCCESS (도착), $A_2$ → RUNNING (스캔 중)

NormalPatrol → RUNNING
Root → RUNNING

틱 3: $C_1$ → FAILURE (배터리 부족)

NormalPatrol → FAILURE
$C_3$ → SUCCESS (비상 감지), $A_3$ → RUNNING
Emergency → RUNNING
Root → RUNNING

이 예시는 조건 변화에 따라 실행 경로가 자동으로 전환되는 행동 트리의 반응성을 보여준다.

5.3 행동 중단(Halting) 메커니즘

행동 트리에서 RUNNING 상태인 행동 노드가 더 이상 틱을 받지 않게 될 때, 해당 노드의 halt() 함수가 호출된다. 이는 안전한 행동 중단을 보장한다.

$\text{if } r_i^{t-1} = \text{RUNNING} \wedge \text{not ticked at } t : \text{halt}(c_i)$

halt 메커니즘은 다음의 정리 작업을 수행한다.

실행 중인 비동기 작업의 취소
할당된 자원의 해제
관련 하드웨어의 안전 상태 전환

6. 노드 유형별 특성 요약

노드 유형	범주	자식 수	RUNNING 반환	주요 역할
Sequence	제어	1~N	가능	순차 실행 (AND)
Fallback	제어	1~N	가능	대안 시도 (OR)
Parallel	제어	1~N	가능	동시 실행
Inverter	데코레이터	1	가능	결과 반전
Repeat	데코레이터	1	가능	반복 실행
Retry	데코레이터	1	가능	실패 시 재시도
Timeout	데코레이터	1	가능	시간 제한
Action	실행	0	가능	행동 수행
Condition	실행	0	불가	조건 평가

7. 요약

행동 트리의 노드는 제어 흐름(시퀀스, 폴백, 병렬), 데코레이터(반전자, 반복자, 타임아웃 등), 실행(행동, 조건)의 세 범주로 분류된다. 틱 기반의 주기적 평가는 트리의 깊이 우선 순회를 통해 이루어지며, 각 노드의 3-값 반환 상태(SUCCESS, FAILURE, RUNNING)가 부모 노드로 역전파되어 전체 트리의 실행 상태를 결정한다. 메모리 변형과 반응적 변형은 반응성과 효율성 사이의 균형을 조절하며, halt 메커니즘은 행동 전환 시의 안전성을 보장한다.

8. 참고 문헌

Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC 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.
Marzinotto, A., Colledanchise, M., Smith, C., & Ögren, P. (2014). “Towards a Unified Behavior Trees Framework for Robot Control.” Proceedings of IEEE International Conference on Robotics and Automation (ICRA), pp. 5420–5427.
Ghzouli, R., Berger, T., Johnsen, E. B., Wasowski, A., & Dragule, S. (2020). “Behavior Trees in Action: A Study of Robotics Applications.” Proceedings of ACM/IEEE International Conference on Model Driven Engineering Languages and Systems (MODELS), pp. 196–207.

v0.1