1292.27 단일 Tick 실행 흐름의 추적
1. 단일 Tick 실행 흐름의 정의
행동 트리(Behavior Tree)에서 단일 tick 실행 흐름(single tick execution flow)이란, 실행 엔진이 루트 노드에 하나의 tick 신호를 전달한 시점부터 루트 노드가 최종 반환 상태(terminal return status)를 산출하여 실행 엔진에 보고하는 시점까지의 완전한 실행 과정을 의미한다. 이 과정에서 tick 신호는 트리의 상위 노드로부터 하위 노드로 하향 전파(top-down propagation)되며, 각 노드의 반환 상태는 하위 노드로부터 상위 노드로 상향 전파(bottom-up propagation)된다. 이 두 방향의 전파가 재귀적으로 결합되어 단일 tick의 실행 흐름을 구성한다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).
단일 tick 실행 흐름의 추적(tracing)이란, 하나의 tick 동안 방문된 모든 노드의 순서, 각 노드에서 수행된 연산, 각 노드가 반환한 상태를 시간 순서에 따라 기록하고 분석하는 과정을 가리킨다. 이 추적은 행동 트리의 동작을 이해하고 검증하며 디버깅하는 데 핵심적인 기법이다.
2. 실행 추적의 형식적 정의
단일 tick k에 대한 실행 추적(execution trace) \tau_k는 방문된 노드와 그 반환 상태의 순서쌍(ordered pair)으로 구성된 유한 순서열(finite sequence)로 정의된다.
\tau_k = \langle (N_1, s_1), (N_2, s_2), \ldots, (N_m, s_m) \rangle
여기서 N_i는 i번째로 tick을 수신하여 실행된 노드이며, s_i \in \{Success, Failure, Running\}는 해당 노드가 반환한 상태이다. m은 해당 tick에서 실제로 실행된 노드의 총 수를 나타낸다. 제어 흐름 노드의 조기 종료(short-circuit) 규칙에 의해 tick을 수신하지 못한 노드는 실행 추적에 포함되지 않으며, 해당 노드는 Idle 상태를 유지한다 (Colledanchise & Ögren, 2018).
실행 추적의 순서는 깊이 우선 탐색(Depth-First Search, DFS) 순서를 따른다. 루트 노드로부터 시작하여 각 제어 흐름 노드가 자식 노드를 왼쪽에서 오른쪽으로 순차적으로 방문하며, 자식 노드의 반환 상태에 따라 후속 자식의 방문 여부가 결정된다.
실행 흐름 추적의 구성 요소
Tick의 하향 전파
tick 신호의 하향 전파는 다음의 규칙을 따른다.
- 실행 엔진이 루트 노드의
tick()메서드를 호출한다. - 루트 노드는 자신의 유일한 자식 노드에 tick을 전달한다.
- 제어 흐름 노드는 자신의 정책(policy)에 따라 자식 노드에 순차적으로 또는 동시에 tick을 전달한다.
- 실행 노드(리프 노드)는 tick을 수신하면 자신의 작업을 수행하고 반환 상태를 산출한다.
반환 상태의 상향 전파
반환 상태의 상향 전파는 다음의 규칙을 따른다.
- 실행 노드가 반환 상태를 자신의 부모 노드에 보고한다.
- 제어 흐름 노드는 자식 노드의 반환 상태를 수신하고, 자신의 정책에 따라 후속 자식의 실행 여부를 결정하거나 자신의 반환 상태를 결정한다.
- 제어 흐름 노드가 자신의 반환 상태를 결정하면, 이를 다시 자신의 부모 노드에 보고한다.
- 이 과정이 루트 노드에 도달할 때까지 반복된다.
노드 콜백의 호출 순서
tick을 수신한 각 노드에서는 해당 노드의 현재 상태에 따라 적절한 콜백 함수가 호출된다. 노드가 Idle 상태에서 처음 tick을 수신하면 onStart() 콜백이 호출되고, 이전 tick에서 Running 상태를 반환하여 현재 Running 상태에 있는 노드가 다시 tick을 수신하면 onRunning() 콜백이 호출된다. 이 콜백 호출 순서는 실행 추적의 세부 수준에서 기록될 수 있으며, 노드의 내부 상태 전이를 추적하는 데 활용된다 (Faconti, BehaviorTree.CPP Documentation, 2024).
예제 트리를 통한 실행 흐름 추적
예제 트리 구조
다음과 같은 행동 트리를 가정하여 실행 흐름을 단계별로 추적한다. 이 트리는 로봇이 장애물 회피 후 목표 지점으로 이동하는 행동을 모델링한 것이다.
Root
└─ Sequence [S1]
├─ Condition [C1: 경로 유효성 확인]
├─ Action [A1: 경로 추종]
└─ Action [A2: 목표 도달 보고]
사례 1: 모든 자식 노드가 Success를 반환하는 경우
| 단계 | 실행 주체 | 동작 | 반환 상태 |
|---|---|---|---|
| 1 | 실행 엔진 | Root에 tick 전달 | — |
| 2 | Root | 자식 S1에 tick 전달 | — |
| 3 | S1 | 첫 번째 자식 C1에 tick 전달 | — |
| 4 | C1 | 경로 유효성 확인 수행 | Success |
| 5 | S1 | C1이 Success이므로 다음 자식 A1에 tick 전달 | — |
| 6 | A1 | 경로 추종 완료 | Success |
| 7 | S1 | A1이 Success이므로 다음 자식 A2에 tick 전달 | — |
| 8 | A2 | 목표 도달 보고 완료 | Success |
| 9 | S1 | 모든 자식이 Success이므로 반환 | Success |
| 10 | Root | S1의 반환 상태를 실행 엔진에 보고 | Success |
이 경우의 실행 추적은 다음과 같다.
\tau_k = \langle (C1, S), (A1, S), (A2, S) \rangle
S1의 최종 반환 상태는 Success이며, 트리의 모든 리프 노드가 방문되었다.
2.1 사례 2: 조건 노드가 Failure를 반환하는 경우
| 단계 | 실행 주체 | 동작 | 반환 상태 |
|---|---|---|---|
| 1 | 실행 엔진 | Root에 tick 전달 | — |
| 2 | Root | 자식 S1에 tick 전달 | — |
| 3 | S1 | 첫 번째 자식 C1에 tick 전달 | — |
| 4 | C1 | 경로가 유효하지 않음을 확인 | Failure |
| 5 | S1 | C1이 Failure이므로 즉시 반환 | Failure |
| 6 | Root | S1의 반환 상태를 실행 엔진에 보고 | Failure |
이 경우의 실행 추적은 다음과 같다.
\tau_k = \langle (C1, F) \rangle
Sequence 노드의 조기 종료 규칙에 의해 A1과 A2에는 tick이 전달되지 않았으며, 두 노드는 Idle 상태를 유지한다. 이 사례는 조기 종료가 실행 추적의 길이를 단축시키는 전형적인 예를 보여준다.
사례 3: 액션 노드가 Running을 반환하는 경우
| 단계 | 실행 주체 | 동작 | 반환 상태 |
|---|---|---|---|
| 1 | 실행 엔진 | Root에 tick 전달 | — |
| 2 | Root | 자식 S1에 tick 전달 | — |
| 3 | S1 | 첫 번째 자식 C1에 tick 전달 | — |
| 4 | C1 | 경로 유효성 확인 수행 | Success |
| 5 | S1 | C1이 Success이므로 다음 자식 A1에 tick 전달 | — |
| 6 | A1 | 경로 추종이 진행 중 | Running |
| 7 | S1 | A1이 Running이므로 현재 자식 인덱스를 기억하고 반환 | Running |
| 8 | Root | S1의 반환 상태를 실행 엔진에 보고 | Running |
이 경우의 실행 추적은 다음과 같다.
\tau_k = \langle (C1, S), (A1, R) \rangle
A2에는 tick이 전달되지 않았으며 Idle 상태를 유지한다. Running 상태의 반환은 S1이 다음 tick에서 실행을 재개할 자식 노드의 인덱스를 내부적으로 기억하도록 한다.
2.2 사례 3의 후속 Tick에서의 실행 흐름
일반 Sequence 노드(비반응형)에서는 이전 tick에서 Running을 반환한 자식 노드의 인덱스를 기억하며, 후속 tick에서는 해당 자식부터 실행을 재개한다.
\tau_{k+1} = \langle (A1, S), (A2, S) \rangle
후속 tick에서 A1이 Success를 반환하면 S1은 다음 자식인 A2로 진행하며, C1에는 tick이 재전달되지 않는다. 이는 일반 Sequence 노드가 이전에 Success를 반환한 자식 노드를 재평가하지 않는 특성을 반영한다.
복합 트리 구조에서의 실행 흐름 추적
Fallback 노드를 포함한 복합 구조
Root
└─ Fallback [F1]
├─ Sequence [S1]
│ ├─ Condition [C1: 근거리 장애물 감지]
│ └─ Action [A1: 긴급 정지]
└─ Action [A2: 정상 주행 계속]
C1이 Success를 반환하는 경우: 근거리 장애물이 감지되어 C1이 Success를 반환하면, S1은 A1에 tick을 전달한다. A1이 Success를 반환하면 S1도 Success를 반환하고, F1은 첫 번째 자식이 Success를 반환하였으므로 즉시 Success를 반환한다. A2에는 tick이 전달되지 않는다.
\tau_k = \langle (C1, S), (A1, S) \rangle \quad \rightarrow \quad F1: Success
C1이 Failure를 반환하는 경우: 근거리 장애물이 감지되지 않아 C1이 Failure를 반환하면, S1은 즉시 Failure를 반환한다. F1은 첫 번째 자식이 Failure를 반환하였으므로 다음 자식인 A2에 tick을 전달한다. A2가 Success를 반환하면 F1도 Success를 반환한다.
\tau_k = \langle (C1, F), (A2, S) \rangle \quad \rightarrow \quad F1: Success
이 두 사례의 비교는 동일한 트리 구조에서 환경 조건의 변화가 실행 흐름의 경로를 어떻게 분기시키는지를 명확히 보여준다.
중첩된 제어 흐름 노드에서의 추적
행동 트리의 깊이가 증가하면 실행 흐름의 추적이 더욱 복잡해진다. 다음과 같은 3단계 중첩 구조를 고려한다.
Root
└─ Fallback [F1]
├─ Sequence [S1]
│ ├─ Condition [C1]
│ └─ Sequence [S2]
│ ├─ Action [A1]
│ └─ Action [A2]
└─ Action [A3]
C1이 Success, A1이 Running을 반환하는 경우의 실행 추적은 다음과 같다.
\tau_k = \langle (C1, S), (A1, R) \rangle
이 경우 S2는 Running을 반환하고, S1도 Running을 반환하며, F1도 Running을 반환한다. Running 상태는 중첩된 제어 흐름 노드를 통해 루트까지 상향 전파된다. A2와 A3에는 tick이 전달되지 않는다.
3. 실행 추적의 기록과 분석
3.1 로그 기반 추적
BehaviorTree.CPP 라이브러리는 각 tick의 실행 추적을 구조화된 로그(structured log)로 기록하는 기능을 제공한다. 이 로그에는 각 노드의 고유 식별자(UID), 호출된 콜백 유형(onStart 또는 onRunning), 반환 상태, 타임스탬프가 포함된다. 기록된 로그는 사후 분석(post-mortem analysis)에 활용되며, 로봇이 예상과 다른 행동을 수행한 시점의 원인을 규명하는 데 핵심적인 역할을 한다 (Faconti, 2024).
3.2 시각적 추적
Groot 도구는 행동 트리의 실행 흐름을 실시간으로 시각화한다. 각 노드는 현재 반환 상태에 따라 색상으로 구분되며, tick이 전파되는 경로가 시각적으로 강조된다. 일반적으로 Idle 상태는 회색, Running 상태는 황색, Success 상태는 녹색, Failure 상태는 적색으로 표현된다. 시각적 추적은 실행 추적의 이해를 직관적으로 보조하며, 특히 복잡한 트리 구조에서 실행 흐름의 분기 패턴을 파악하는 데 유용하다.
3.3 비교 분석
연속적인 두 tick의 실행 추적 \tau_k와 \tau_{k+1}을 비교하면, 환경 조건의 변화에 의해 어떤 실행 경로의 전환이 발생하였는지를 파악할 수 있다. 예를 들어, \tau_k에서 Fallback의 첫 번째 분기가 실행되었으나 \tau_{k+1}에서 두 번째 분기가 실행되었다면, 두 tick 사이에 첫 번째 분기의 선행 조건이 변화하였음을 추론할 수 있다. 이러한 비교 분석은 행동 트리의 적응적 행동(adaptive behavior) 메커니즘을 이해하고 검증하는 데 활용된다 (Colledanchise & Ögren, 2018).
4. 실행 흐름 추적의 실무적 활용
4.1 디버깅
로봇이 예상과 다른 행동을 수행할 때, 해당 시점의 실행 추적을 분석하면 문제의 원인을 체계적으로 규명할 수 있다. 어떤 조건 노드가 예상과 다른 반환 상태를 산출하였는지, 어떤 제어 흐름 노드에서 의도하지 않은 분기가 발생하였는지, 어떤 액션 노드가 예상보다 오래 Running 상태를 유지하였는지를 실행 추적으로부터 정확히 식별할 수 있다.
4.2 성능 프로파일링
실행 추적에 각 노드의 실행 소요 시간을 함께 기록하면, 단일 tick의 총 실행 시간에 대한 각 노드의 기여도를 산출할 수 있다. 이를 통해 tick 주기 내에 실행이 완료되지 못하는 병목 노드(bottleneck node)를 식별하고, 해당 노드의 최적화 또는 비동기화 필요성을 판단할 수 있다.
4.3 행동 검증
실행 추적을 사전에 정의된 기대 추적(expected trace)과 비교하여, 행동 트리의 실제 동작이 설계 사양에 부합하는지를 자동화된 방식으로 검증할 수 있다. 단위 테스트에서 특정 환경 조건을 설정한 후 실행 추적이 기대 추적과 일치하는지 확인하는 방법은 행동 트리의 정확성을 보장하는 체계적인 검증 기법이다.
참고 문헌
- 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/