1293.10 단일 Tick 내 완전 실행 흐름 추적

1. 완전 실행 흐름 추적의 정의

단일 Tick 내 완전 실행 흐름 추적(Complete Execution Flow Tracing within a Single Tick)이란, 루트 노드에서 Tick이 발생한 시점부터 루트 노드가 최종 반환 상태(SUCCESS, FAILURE, RUNNING)를 결정하는 시점까지의 전체 노드 방문 경로와 상태 전이 과정을 체계적으로 기록하고 분석하는 기법을 의미한다. 행동 트리(Behavior Tree)의 실행 의미론(execution semantics)을 정확히 이해하고 검증하기 위해서는, 단일 Tick이 트리 전체에 걸쳐 어떤 노드를 어떤 순서로 방문하며 각 노드가 어떤 상태를 반환하는지를 완전하게 추적할 수 있어야 한다(Colledanchise & Ogren, 2018).

완전 실행 흐름 추적은 단순한 로깅(logging)과 구별된다. 로깅이 개별 노드의 상태 변화를 독립적으로 기록하는 것이라면, 완전 실행 흐름 추적은 노드 간의 인과 관계(causal relationship)와 제어 흐름의 전파 경로를 포함하여 Tick의 전체 생명 주기를 하나의 연속적 실행 단위로 재구성하는 것이다.

2. 추적 대상 요소

단일 Tick 내에서 추적해야 하는 핵심 요소는 다음과 같다.

2.1 노드 방문 순서

Tick이 루트 노드로부터 깊이 우선(depth-first), 왼쪽에서 오른쪽(left-to-right) 순서로 전파되는 과정에서 각 노드가 방문되는 정확한 순서를 기록한다. 이 순서는 트리의 구조적 배치와 제어 노드의 유형에 따라 결정되며, 동일한 트리 구조라 하더라도 이전 Tick에서의 노드 상태에 따라 방문 경로가 달라질 수 있다.

2.2 노드별 반환 상태

각 노드가 Tick을 수신한 후 반환하는 상태(NodeStatus)를 기록한다. BehaviorTree.CPP 프레임워크에서 노드는 SUCCESS, FAILURE, RUNNING 중 하나의 상태를 반환하며, 이 반환 상태가 부모 노드의 후속 동작을 결정한다(Faconti, 2022).

2.3 제어 흐름 분기 결정

제어 노드(Sequence, Fallback, Parallel 등)가 자식 노드의 반환 상태에 기반하여 내리는 분기 결정을 기록한다. 예를 들어, Sequence 노드가 첫 번째 자식의 FAILURE 반환을 수신하여 후속 자식 노드의 Tick을 중단하고 즉시 FAILURE를 반환하는 조기 종료(short-circuit) 결정이 이에 해당한다.

2.4 Halt 이벤트 발생

Tick 실행 과정에서 부모 노드가 자식 노드에 대해 Halt를 호출하는 이벤트를 기록한다. Halt는 이전 Tick에서 RUNNING 상태에 있던 노드가 현재 Tick에서 더 이상 실행될 필요가 없을 때 발생하며, 자원 정리(resource cleanup)와 상태 초기화를 수행하는 중요한 부수 효과(side effect)를 가진다.

2.5 블랙보드 접근 기록

각 노드가 Tick 실행 중 블랙보드(Blackboard)에 대해 수행하는 읽기(read) 및 쓰기(write) 연산을 기록한다. 블랙보드는 노드 간 데이터 공유의 핵심 메커니즘이므로, 블랙보드 접근 순서는 실행 흐름의 데이터 의존성(data dependency)을 이해하는 데 필수적이다.

3. 추적 절차의 단계별 구성

단일 Tick의 완전 실행 흐름을 추적하기 위한 체계적 절차는 다음과 같이 구성된다.

3.1 단계: Tick 시작 지점 식별

루트 노드의 tick() 메서드가 호출되는 시점을 Tick의 시작으로 정의한다. 이 시점에서 Tick 카운터(tick counter)가 증가하고, 추적을 위한 새로운 실행 컨텍스트(execution context)가 생성된다. Tick 시작 시점의 타임스탬프(timestamp)를 기록하여 이후 실행 시간 분석에 활용한다.

3.2 단계: 재귀적 노드 방문 추적

루트 노드로부터 시작하여 각 노드의 tick() 호출이 재귀적으로 발생하는 과정을 추적한다. 제어 노드의 경우, 자식 노드에 대한 Tick 전파 규칙에 따라 방문 대상 자식이 결정되며, 이 결정 과정 자체도 추적 대상에 포함된다.

구체적으로, 제어 노드가 자식 노드를 방문할 때마다 다음 정보를 기록한다.

• 부모 노드의 식별자와 유형
• 방문 대상 자식 노드의 식별자와 인덱스
• 방문 사유(순차 진행, 재평가, 재진입 등)

3.3 단계: 리프 노드 실행 결과 수집

리프 노드(액션 노드 또는 조건 노드)에 도달하면 해당 노드의 tick() 메서드가 실행되고 반환 상태가 결정된다. 동기 노드는 tick() 호출 내에서 즉시 SUCCESS 또는 FAILURE를 반환하고, 비동기 노드는 RUNNING을 반환하거나 이전 실행의 완료 여부를 확인하여 최종 상태를 반환한다.

3.4 단계: 반환 상태의 상향 전파 추적

리프 노드의 반환 상태가 부모 노드로 전파되는 과정을 추적한다. 부모 노드는 자식의 반환 상태를 수신한 후 자신의 제어 정책(control policy)에 따라 후속 자식의 Tick 여부를 결정하거나 자신의 반환 상태를 결정한다. 이 상향 전파 과정은 리프 노드로부터 루트 노드까지 역방향으로 진행되며, 각 단계에서의 결정 논리가 기록된다.

3.5 단계: Tick 종료 및 최종 상태 기록

루트 노드가 최종 반환 상태를 결정하면 해당 Tick이 완료된다. Tick 종료 시점의 타임스탬프를 기록하고, 전체 실행 경로를 요약하여 추적 기록을 완성한다.

4. 실행 흐름 추적의 형식적 표현

단일 Tick의 실행 흐름은 노드 방문의 순서열(sequence)로 형식적으로 표현할 수 있다. 각 방문 이벤트는 다음의 튜플(tuple)로 기술된다.

e_i = (t_i, n_i, d_i, s_i)

여기서 t_i는 이벤트 발생 시각, n_i는 방문된 노드의 식별자, d_i는 방문 깊이(depth), s_i는 해당 노드의 반환 상태를 나타낸다. 단일 Tick의 완전 실행 흐름은 이러한 이벤트들의 순서열 T = \langle e_1, e_2, \ldots, e_k \rangle로 정의되며, e_1은 루트 노드의 Tick 수신, e_k는 루트 노드의 최종 상태 반환에 해당한다.

이 형식적 표현을 통해 두 Tick 간의 실행 흐름을 비교하거나, 예상 실행 경로와 실제 실행 경로 간의 차이를 분석하는 것이 가능해진다.

5. 구체적 추적 예시

다음과 같은 행동 트리 구조를 가정하여 단일 Tick 내 실행 흐름을 추적한다.

Root (Sequence)
├── Condition_A
├── Action_B
└── Action_C

이 트리에서 Condition_A는 동기 조건 노드, Action_B는 비동기 액션 노드, Action_C는 동기 액션 노드이다. 이전 Tick에서 Action_B가 RUNNING을 반환한 상태에서 새로운 Tick이 발생하는 경우를 추적한다.

위 추적에서 Sequence 노드는 자식 노드를 왼쪽에서 오른쪽으로 순차적으로 방문하며, 각 자식이 SUCCESS를 반환할 때마다 다음 자식으로 진행한다. 만약 Condition_A가 FAILURE를 반환하였다면, Sequence 노드는 즉시 FAILURE를 반환하고, Action_B에 대해 Halt를 호출하여 이전 Tick에서의 RUNNING 상태를 정리하였을 것이다.

6. WithMemory 모드에서의 실행 흐름 차이

Sequence 노드가 WithMemory 속성을 가지는 경우, 이전 Tick에서 SUCCESS를 반환한 자식 노드는 현재 Tick에서 다시 Tick되지 않는다. 앞선 예시에서 Action_B가 RUNNING을 반환한 이전 Tick 이후의 추적은 다음과 같이 달라진다.

WithMemory 모드에서는 Condition_A에 대한 재평가가 생략되므로, 방문 노드 수가 감소하고 Tick 실행 시간이 단축된다. 그러나 조건이 변화하였을 때 이를 감지하지 못하는 위험이 존재하므로, 설계 시 트레이드오프(trade-off)를 고려해야 한다.

7. Reactive 모드에서의 실행 흐름 차이

ReactiveSequence 노드를 사용하는 경우, 모든 자식 노드가 매 Tick마다 처음부터 재평가된다. 이전 Tick에서 Action_B가 RUNNING을 반환한 상태에서의 추적은 다음과 같다.

ReactiveSequence에서는 Action_B가 여전히 RUNNING을 반환하므로 Action_C에 대한 Tick 전파가 발생하지 않는다. 또한 매 Tick마다 Condition_A가 재평가되므로, 조건 변화에 대한 즉각적인 반응이 가능하다. 만약 Condition_A가 FAILURE를 반환하면, Action_B에 대해 Halt가 호출되어 진행 중이던 비동기 작업이 중단된다.

8. 실행 흐름 추적의 구현 기법

8.1 콜백 기반 추적

BehaviorTree.CPP 프레임워크는 TreeObserver 인터페이스를 제공하여 노드의 상태 변화를 관찰할 수 있다. TreeObserver를 상속받아 구현한 관찰자 객체를 트리에 등록하면, 각 노드의 Tick 전후에 콜백(callback)이 호출되어 방문 순서와 반환 상태를 자동으로 수집할 수 있다.

class ExecutionFlowTracer : public BT::TreeObserver {
    void onNodeTicked(const BT::TreeNode& node, 
                      BT::NodeStatus prev_status,
                      BT::NodeStatus new_status) override {
        trace_log_.emplace_back(
            std::chrono::steady_clock::now(),
            node.name(),
            node.UID(),
            prev_status,
            new_status
        );
    }
};

8.2 로그 구조화

추적 기록은 구조화된 형식으로 저장하여 사후 분석(post-mortem analysis)에 활용한다. 각 Tick의 실행 흐름을 독립적인 단위로 구분하고, Tick 번호, 시작 시각, 종료 시각, 방문 노드 수, 최종 반환 상태 등의 메타데이터를 포함시킨다. JSON 또는 프로토콜 버퍼(Protocol Buffers) 형식이 일반적으로 사용된다.

8.3 시각적 추적 도구

Groot2와 같은 행동 트리 시각화 도구는 단일 Tick의 실행 흐름을 그래픽으로 표현하는 기능을 제공한다. 트리의 각 노드에 현재 상태에 대응하는 색상을 부여하고, Tick 전파 경로를 애니메이션으로 재현함으로써 복잡한 트리 구조에서의 실행 흐름을 직관적으로 이해할 수 있도록 지원한다(Faconti, 2022).

9. 실행 흐름 추적의 활용

9.1 행동 트리 검증

설계된 행동 트리가 의도한 대로 동작하는지를 검증하기 위해 실행 흐름 추적을 활용한다. 특정 입력 조건에서 예상되는 노드 방문 순서와 반환 상태를 사전에 정의하고, 실제 추적 결과와 비교하여 불일치를 탐지한다. 이는 단위 테스트(unit test)의 형태로 자동화할 수 있다.

9.2 성능 병목 분석

단일 Tick 내에서 각 노드의 실행 시간을 측정하여 성능 병목(performance bottleneck)을 식별한다. 특정 노드가 과도한 실행 시간을 소비하는 경우, 해당 노드의 구현을 최적화하거나 트리 구조를 재설계하여 해당 노드의 불필요한 Tick을 방지하는 방안을 마련한다.

9.3 비결정적 동작 진단

비동기 노드의 실행 결과나 외부 센서 데이터의 변화로 인해 동일한 트리 구조에서도 Tick마다 상이한 실행 경로가 나타날 수 있다. 실행 흐름 추적을 통해 비결정적(nondeterministic) 동작의 원인을 식별하고, 재현 가능한 테스트 환경을 구성하는 데 활용한다.

참고 문헌

• Colledanchise, M., & Ogren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
• Faconti, D. (2022). BehaviorTree.CPP documentation and API reference. https://www.behaviortree.dev/