1293.4 Tick과 이벤트 기반 실행의 비교

1. 두 실행 패러다임의 개요

행동 트리의 실행 모델을 논의할 때, 두 가지 근본적으로 상이한 패러다임이 존재한다. 하나는 tick 기반 실행(tick-based execution)이며, 다른 하나는 이벤트 기반 실행(event-driven execution)이다. tick 기반 실행에서는 외부의 주기적 신호(tick)가 트리의 평가를 촉발하는 반면, 이벤트 기반 실행에서는 환경이나 내부 상태의 변화가 이벤트로 발행되어 해당 이벤트를 구독하는 노드의 실행을 촉발한다. 행동 트리의 표준적 실행 모델은 tick 기반이나, 두 모델의 특성을 이해하는 것은 시스템 설계에서 근거 있는 선택을 가능하게 한다 (Colledanchise & Ögren, 2018).

2. Tick 기반 실행 모델의 특성

tick 기반 실행 모델에서 행동 트리의 평가는 외부 타이머에 의해 주기적으로 촉발된다. 매 tick마다 루트 노드에서 시작하여 트리 전체를 깊이 우선 순서로 순회하며, 각 노드는 tick을 수신하면 자신의 로직을 실행하고 상태를 반환한다.

이 모델의 핵심 특성은 다음과 같다.

폴링 방식(Polling): 환경 상태의 변화를 매 tick마다 능동적으로 확인한다. 환경이 이벤트를 발행하지 않더라도 조건 노드가 주기적으로 상태를 점검한다.
전체 트리 순회: 매 tick에서 루트 노드로부터 트리를 순회하므로, 트리의 상위 구조부터 하위 노드까지 체계적으로 평가된다.
균일한 갱신 주기: 모든 노드가 동일한 tick 주기에 의해 평가 기회를 부여받으므로, 반응성이 시간적으로 균일하다.
결정론적 순서: 노드의 평가 순서가 트리 구조에 의해 고정되므로, 실행의 재현성이 보장된다.

3. 이벤트 기반 실행 모델의 특성

이벤트 기반 실행 모델에서는 환경 상태의 변화나 내부 조건의 충족이 이벤트(event)로 발행되고, 해당 이벤트에 관심을 등록한 노드만이 실행된다. 이벤트가 발생하지 않으면 노드는 실행되지 않으며, 시스템은 유휴(idle) 상태를 유지한다.

이 모델의 핵심 특성은 다음과 같다.

반응 방식(Reactive): 이벤트 발생 시에만 관련 노드가 실행되므로, 변화가 없는 동안 불필요한 계산이 발생하지 않는다.
선택적 실행: 이벤트와 관련된 노드만 실행되므로, 트리 전체를 순회할 필요가 없다.
비균일한 실행 시점: 이벤트 발생 시점에 의존하므로, 노드의 실행 시점이 불규칙적이다.
이벤트 도착 순서 의존: 복수의 이벤트가 동시에 발생할 경우 처리 순서가 이벤트 큐(event queue)의 구현에 의존하며, 결정론성의 보장이 어려울 수 있다.

4. 비교 분석

4.1 반응성(Reactivity)

tick 기반 모델의 반응 지연(reaction latency)은 최대 한 tick 주기 $T$ 이다. 환경 변화가 두 tick 사이에 발생하면 다음 tick까지 감지되지 않는다. 반면, 이벤트 기반 모델에서는 이벤트가 발행되는 즉시 해당 노드가 실행될 수 있으므로, 이론적 반응 지연은 이벤트 전파 시간(event propagation time)에 한정된다.

속성	tick 기반	이벤트 기반
최대 반응 지연	$T$ (tick 주기)	이벤트 전파 시간
평균 반응 지연	$T/2$	이벤트 전파 시간
반응 지연의 예측 가능성	높음 (상한 $T$ )	이벤트 부하에 의존

4.2 계산 효율성(Computational Efficiency)

tick 기반 모델은 환경 변화의 유무에 관계없이 매 tick마다 트리를 순회하므로, 환경이 정적인 기간에도 계산 자원을 소비한다. 이벤트 기반 모델은 변화가 없으면 계산을 수행하지 않으므로, 환경 변화가 드문 경우 계산 효율성이 우수하다.

그러나 이벤트가 빈번하게 발생하는 동적 환경에서는 이벤트 기반 모델의 이벤트 라우팅(event routing)과 구독 관리(subscription management) 오버헤드가 tick 기반 순회의 오버헤드를 초과할 수 있다.

4.3 결정론성(Determinism)

tick 기반 모델에서 노드의 평가 순서는 트리 구조에 의해 완전히 결정된다. 동일한 트리 상태와 환경 입력이 주어지면, 동일한 실행 경로와 결과가 보장된다. 이는 형식 검증(formal verification)과 테스트에 유리하다 (Biggar et al., 2020).

이벤트 기반 모델에서는 복수의 이벤트가 동시에 발생하거나 이벤트 처리 도중 새로운 이벤트가 도착하는 경우, 실행 순서가 이벤트 큐의 구현 세부사항에 의존하게 된다. 이로 인해 결정론적 실행을 보장하기 위한 추가적인 동기화 메커니즘이 필요하다.

4.4 구현 복잡성(Implementation Complexity)

tick 기반 모델의 구현은 상대적으로 단순하다. 타이머가 주기적으로 루트 노드의 tick() 함수를 호출하면 되며, 이벤트 발행, 구독, 라우팅 등의 인프라가 필요하지 않다.

이벤트 기반 모델의 구현은 이벤트 발행자(publisher)와 구독자(subscriber) 간의 매핑, 이벤트 큐 관리, 이벤트 우선순위 처리, 이벤트 전파 규칙 등의 추가 인프라를 요구한다. 또한, 이벤트 기반 모델에서 행동 트리의 계층적 제어 흐름(hierarchical control flow)을 올바르게 유지하기 위해서는 이벤트가 트리 구조를 존중하는 방식으로 전파되어야 하며, 이는 설계의 복잡성을 증가시킨다.

4.5 디버깅 용이성(Debuggability)

tick 기반 모델은 디버깅에 유리하다. 매 tick의 시작과 종료가 명확한 경계를 형성하므로, 특정 tick에서의 트리 상태를 스냅샷으로 캡처하고 단계별 실행(single-step execution)이 가능하다. 또한, tick 단위의 실행 로그는 시간 순서가 명확하여 문제 추적이 용이하다.

이벤트 기반 모델에서는 이벤트의 비동기적 발생과 처리가 실행 흐름을 비선형적으로 만들어, 문제의 원인을 추적하는 것이 상대적으로 어렵다.

5. 하이브리드 접근법

실무에서는 tick 기반과 이벤트 기반의 장점을 결합한 하이브리드 접근법이 사용되기도 한다. 대표적인 방식은 다음과 같다.

첫째, 이벤트 트리거 tick(event-triggered tick) 방식이다. 기본적으로 tick 기반 모델을 유지하되, 중요한 이벤트가 발생하면 정규 tick 주기를 기다리지 않고 즉시 추가 tick을 실행한다. 이 방식은 tick 기반 모델의 결정론성과 이벤트 기반 모델의 빠른 반응성을 모두 확보할 수 있다.

둘째, 조건부 순회(conditional traversal) 방식이다. 매 tick에서 트리 전체를 순회하는 대신, 이전 tick 이후 변화가 발생한 영역만을 선택적으로 순회한다. 이는 tick 기반 모델의 구조를 유지하면서 계산 효율성을 개선한다.

BehaviorTree.CPP 라이브러리에서는 기본적으로 tick 기반 모델을 사용하되, 반응형 노드(ReactiveSequence, ReactiveFallback)를 통해 매 tick에서 조건을 재평가하는 반응적 행동을 지원한다. 이는 tick 기반 프레임워크 내에서 이벤트 기반 모델의 반응성을 부분적으로 구현한 것이다 (Faconti, 2024).

6. 행동 트리에서 Tick 기반 모델이 표준인 이유

행동 트리 문헌과 주요 구현체에서 tick 기반 모델이 표준적 실행 모델로 채택된 것은 다음의 종합적 이유에 기인한다.

구현의 단순성: 단일 루프와 재귀 호출로 전체 실행 모델이 구현된다.
분석의 용이성: 이산 시간 시스템으로서의 형식적 분석이 가능하다.
결정론적 보장: 형식 검증과 안전성 분석의 전제 조건을 충족한다.
제어 루프와의 자연스러운 통합: 로봇의 주기적 제어 루프와 tick 주기가 자연스럽게 대응된다.
Running 상태 처리의 일관성: 비동기 행동의 진행 상태를 매 tick에서 균일하게 폴링할 수 있다.

이러한 이유로 Colledanchise & Ögren(2018)의 표준 정의, BehaviorTree.CPP(Faconti, 2024), 그리고 Nav2(Macenski et al., 2020) 등 주요 행동 트리 프레임워크는 모두 tick 기반 실행 모델을 채택하고 있다.

참고 문헌

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), 2341–2348.
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/
Macenski, S., Martín, F., White, R., & Clavero, J. G. (2020). The Marathon 2: A Navigation System. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).