1293.3 Tick과 이산 시간 실행의 관계

1. 연속 시간과 이산 시간의 구분

물리적 세계는 연속 시간(continuous time)으로 전개된다. 그러나 디지털 컴퓨터에서 실행되는 모든 계산 시스템은 연속 시간을 직접 처리할 수 없으며, 일정한 간격으로 시간을 분할하여 이산적(discrete) 시점에서 상태를 갱신한다. 이산 시간 실행(discrete-time execution)이란, 시스템의 상태 갱신이 연속적이 아닌 이산적 시점에서만 발생하는 실행 방식을 지칭한다. 행동 트리의 tick은 이러한 이산 시간 실행의 구체적 구현이다 (Colledanchise & Ögren, 2018).

2. Tick에 의한 시간의 이산화

행동 트리에서 tick은 시간을 이산 단위로 분할하는 역할을 수행한다. tick 주기를 T라 하면, 행동 트리의 실행 시점은 \{t_0, t_0 + T, t_0 + 2T, \dots\}로 정의되는 이산 시간 집합을 형성한다. k번째 tick 시점 t_k = t_0 + kT에서 행동 트리 전체가 한 번 순회되며, 모든 노드의 상태 갱신은 이 이산 시점에서만 발생한다.

이를 수학적으로 표현하면, 행동 트리의 상태 함수 \sigma(t)는 연속 함수가 아닌 계단 함수(step function)의 형태를 취한다.

\sigma(t) = \sigma(t_k), \quad t_k \leq t < t_{k+1}

즉, 두 연속 tick 사이의 임의의 시점 t에서 행동 트리의 상태는 가장 최근 tick 시점 t_k에서 결정된 상태와 동일하다.

이산 시간 시스템으로서의 행동 트리

행동 트리는 이산 시간 동적 시스템(discrete-time dynamical system)으로 형식화할 수 있다. 트리의 내부 상태를 \sigma_k, 환경으로부터의 입력을 u_k, 트리의 출력(루트 노드의 반환 상태)을 y_k라 하면, tick에 의한 상태 갱신은 다음의 차분 방정식(difference equation)으로 표현된다.

\sigma_{k+1} = f(\sigma_k, u_k)
y_k = g(\sigma_k, u_k)

여기서 f는 상태 전이 함수, g는 출력 함수이다. 이 형식은 이산 시간 제어 이론에서 사용되는 상태 공간 표현(state-space representation)과 동일한 구조를 가진다. 이러한 형식화는 행동 트리의 안정성(stability), 도달 가능성(reachability), 안전성(safety) 등의 속성을 이산 시간 시스템 이론의 도구로 분석할 수 있는 이론적 기반을 제공한다 (Colledanchise & Ögren, 2018; Biggar et al., 2020).

샘플링 정리와의 관계

이산 시간 실행에서 핵심적 질문은 “얼마나 자주 샘플링해야 하는가“이다. 신호 처리 분야의 나이퀴스트-섀넌 샘플링 정리(Nyquist-Shannon sampling theorem)에 따르면, 주파수 f_{max}를 가진 연속 신호를 온전히 복원하려면 최소 2f_{max}의 샘플링 주파수가 필요하다 (Shannon, 1949).

행동 트리의 맥락에서 이를 유추적으로 적용하면, 환경 상태의 변화 속도에 비해 tick 주파수가 충분히 높아야 환경 변화를 놓치지 않고 감지할 수 있다. 환경의 가장 빠른 변화 주파수를 f_{env}라 하면, tick 주파수 f_{tick}은 다음 조건을 충족해야 한다.

f_{tick} \geq 2 f_{env}

이 조건이 충족되지 않으면 앨리어싱(aliasing)에 해당하는 현상이 발생하여, 행동 트리가 환경의 실제 변화를 왜곡하여 인식하거나 중요한 변화를 완전히 놓칠 수 있다.

3. Tick 주기와 시간 해상도

tick 주기 T는 행동 트리의 시간 해상도(temporal resolution)를 결정한다. 시간 해상도란, 시스템이 구별할 수 있는 최소 시간 간격이다. tick 주기가 T이면, T보다 짧은 시간 동안 발생하고 사라지는 환경 변화는 행동 트리에 의해 감지되지 않는다.

로봇공학에서 전형적인 tick 주기는 10 ms에서 100 ms 범위이며, 이는 로봇의 제어 루프 주기와 대응된다. 예를 들어, Nav2에서 행동 트리의 기본 tick 주기는 10 ms(100 Hz)로 설정되어 있다 (Macenski et al., 2020).

4. 이산화에 따른 지연

tick 기반 이산 시간 실행은 본질적으로 지연(latency)을 수반한다. 환경 상태의 변화가 두 tick 사이에 발생하면, 해당 변화는 다음 tick에서야 비로소 감지된다. 이 지연의 최대값은 한 tick 주기 T이며, 평균 지연은 T/2이다.

\text{최대 감지 지연} = T
\text{평균 감지 지연} = \frac{T}{2}

이 지연은 시스템의 반응성에 직접적인 영향을 미친다. 안전 필수 상황에서 장애물이 감지되기까지 최대 T만큼의 지연이 발생할 수 있으므로, 안전 요구사항에 따라 tick 주기의 상한이 제약된다.

5. 디지털 제어 시스템과의 대응

행동 트리의 tick 기반 실행은 디지털 제어 시스템의 샘플링 제어(sampled-data control)와 구조적으로 대응된다.

디지털 제어 시스템에서 샘플링 주기는 제어 대상의 동적 특성에 맞추어 설계되며, 일반적으로 시스템의 가장 빠른 동적 모드(fastest dynamic mode)의 주기보다 5~10배 빠른 샘플링 주기가 권장된다 (Åström & Wittenmark, 2011). 행동 트리에서도 유사한 설계 원칙이 적용되며, tick 주기는 로봇이 반응해야 하는 가장 빠른 환경 변화에 비해 충분히 짧게 설정되어야 한다.

6. 이산 시간 실행의 장점

행동 트리의 이산 시간 실행은 다음과 같은 장점을 제공한다.

첫째, 분석 용이성(analyzability)이다. 상태 변화가 이산 시점에서만 발생하므로, 시스템의 동작을 tick 단위로 추적하고 재현할 수 있다. 이는 형식 검증(formal verification)과 디버깅을 용이하게 한다.

둘째, 결정론적 실행(deterministic execution)이다. 각 tick 내에서 노드의 방문 순서가 결정론적이므로, 동일한 초기 상태와 입력에 대해 동일한 결과가 보장된다.

셋째, 계산 자원 관리(computational resource management)이다. tick 주기가 고정되면, 각 tick 내에서 사용 가능한 계산 시간 예산(time budget)이 명확히 정의된다. 이는 실시간 시스템에서의 스케줄링과 자원 할당을 단순화한다.

7. 이산 시간 실행의 한계

이산 시간 실행은 다음과 같은 한계를 가진다.

첫째, 감지 지연이다. 앞서 기술한 바와 같이 최대 한 tick 주기만큼의 감지 지연이 불가피하다.

둘째, 불필요한 계산이다. 환경 상태가 변하지 않았더라도 매 tick마다 트리를 순회하므로, 변화가 없는 기간 동안 불필요한 계산이 수행된다. 이는 계산 자원이 제한된 임베디드 시스템에서 문제가 될 수 있다.

셋째, 주기 설정의 딜레마이다. tick 주기를 짧게 설정하면 반응성은 향상되나 계산 부하가 증가하고, 길게 설정하면 계산 부하는 감소하나 반응성이 저하된다. 이 상충 관계(trade-off)는 tick 주기 설계의 핵심 과제이다.

참고 문헌

• Åström, K. J. & Wittenmark, B. (2011). Computer-Controlled Systems: Theory and Design (3rd ed.). Dover Publications.
• 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.
• 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).
• Shannon, C. E. (1949). Communication in the Presence of Noise. Proceedings of the IRE, 37(1), 10–21.