1292.25 Tick의 주기적 실행

1292.25 Tick의 주기적 실행

1. 주기적 실행의 기본 원리

행동 트리(Behavior Tree)의 표준 실행 모델에서 tick은 일정한 시간 간격(period)으로 반복 발생한다. 행동 트리 \mathcal{T}의 tick 주기를 \Delta_t라 하면, 실행 엔진은 \Delta_t 간격으로 루트 노드에 tick을 전달하며, 이 과정이 트리의 실행이 종료될 때까지 반복된다. 이 주기적 실행 모델은 Colledanchise와 Ogren(2018)의 형식적 정의에서 행동 트리의 기본 구성 요소 중 하나로 명시되어 있다 (Colledanchise & Ogren, Behavior Trees in Robotics and AI, 2018).

시각 t_0에서 행동 트리의 실행이 시작되면, k번째 tick은 시각 t_k = t_0 + k \cdot \Delta_t에서 발생한다. 이상적인 조건에서 tick의 발생 시각은 등간격(equidistant)이며, 이는 행동 트리의 시간적 행동이 균일한 샘플링 주기를 따르는 이산 시간 시스템(discrete-time system)으로 모델링될 수 있음을 의미한다.

2. 주기적 실행의 구현

2.1 실행 루프의 구조

행동 트리의 주기적 실행은 실행 루프(execution loop)를 통해 구현된다. BehaviorTree.CPP 라이브러리에서는 Tree::tickWhileRunning() 또는 Tree::tickOnce() 함수를 통해 실행 루프를 구성한다. tickWhileRunning()은 루트 노드가 Running을 반환하는 동안 지정된 주기로 tick을 반복 전달하며, 루트 노드가 Success 또는 Failure를 반환하면 루프를 종료한다 (Faconti, BehaviorTree.CPP Documentation, 2024).

실행 루프의 일반적 구조는 다음과 같다.

  1. 현재 시각을 기록한다.
  2. 루트 노드에 tick을 전달한다.
  3. 반환 상태를 확인한다. Success 또는 Failure이면 루프를 종료한다.
  4. tick 실행에 소요된 시간을 계산한다.
  5. \Delta_t에서 소요 시간을 감산한 만큼 대기(sleep)한다.
  6. 단계 1로 돌아간다.

2.2 수면 기반 주기 유지

tick 주기의 유지는 일반적으로 운영체제의 수면(sleep) 메커니즘을 통해 이루어진다. tick 실행이 완료된 후, 다음 tick까지의 잔여 시간만큼 스레드가 수면 상태에 들어간다. 이 방식은 구현이 단순하지만, 운영체제의 스케줄링 지연(scheduling latency)에 의해 실제 tick 주기가 설정된 주기로부터 미세하게 편차를 보일 수 있다.

실시간(real-time) 운영체제에서는 고정밀 타이머(high-resolution timer)와 실시간 스케줄링 정책을 활용하여 tick 주기의 정밀도를 향상시킬 수 있다. ROS2 환경에서는 rclcpp::WallTimer나 rclcpp::Rate를 활용하여 주기적 tick 실행을 구현한다.

3. 주기적 실행과 제어 이론의 관계

3.1 샘플링 주기와의 대응

행동 트리의 tick 주기 \Delta_t는 디지털 제어 이론(digital control theory)에서의 샘플링 주기(sampling period) T_s와 직접적으로 대응한다. 디지털 제어에서 연속 시간 시스템을 이산 시간으로 변환할 때 샘플링 주기가 시스템의 성능과 안정성에 영향을 미치는 것과 마찬가지로, 행동 트리에서 tick 주기는 로봇의 반응성과 행동 품질에 영향을 미친다.

나이퀴스트-샤논 샘플링 정리(Nyquist-Shannon sampling theorem)에 따르면, 연속 신호를 정확히 복원하기 위해서는 샘플링 주파수가 신호의 최대 주파수의 2배 이상이어야 한다. 이 원리를 행동 트리에 적용하면, 환경 변화의 최대 빈도에 비해 tick 빈도가 충분히 높아야 환경 변화를 적시에 감지하고 대응할 수 있다 (Colledanchise & Ogren, 2018).

3.2 제어 루프와의 통합

로봇 시스템에서 행동 트리의 tick 주기는 하위 수준의 제어 루프 주기와 상이한 시간 스케일(time scale)에서 동작하는 경우가 일반적이다. 모터 제어나 자세 제어 등의 저수준 제어 루프는 수백 Hz에서 수 kHz의 주기로 동작하는 반면, 행동 트리는 일반적으로 10~100 Hz 수준의 주기로 동작한다.

이러한 다중 시간 스케일(multi-rate) 구조에서 행동 트리는 상위 수준의 의사 결정을 담당하고, 저수준 제어기는 행동 트리가 결정한 목표를 실현하는 역할을 담당한다. 행동 트리의 tick 주기가 저수준 제어 주기보다 낮은 것은, 상위 수준의 의사 결정이 하위 수준의 실행보다 낮은 빈도로 이루어져도 충분하다는 계층적 제어(hierarchical control) 원리에 기반한다.

4. Tick 초과 시간의 처리

4.1 Tick 실행 시간이 주기를 초과하는 경우

실제 시스템에서는 tick 실행에 소요되는 시간이 설정된 tick 주기 \Delta_t를 초과할 수 있다. 이는 트리의 규모가 크거나, 노드의 동기적 연산이 예상보다 오래 걸리거나, 시스템의 계산 자원이 부족한 경우에 발생한다.

tick 실행 시간이 주기를 초과하면 다음 tick의 시작이 지연되며, 이는 행동 트리의 실질적 tick 빈도(effective tick rate)가 설정된 빈도보다 낮아지는 결과를 초래한다. 이 상황은 다음과 같은 방식으로 처리될 수 있다.

  1. 지연 허용(Tolerate delay): 초과 시간을 허용하고, 다음 tick을 즉시 시작한다. 이 경우 tick 간격이 불규칙해지지만, tick이 누락되지는 않는다.
  2. Tick 건너뛰기(Skip tick): 초과 시간 동안 발생했어야 할 tick을 건너뛰고, 다음 정규 tick 시점에서 실행을 재개한다. 이 방식은 tick 주기의 규칙성을 유지하지만, 일부 tick이 누락된다.
  3. 경고 발생(Raise warning): 초과 시간이 발생하면 경고를 기록하고 시스템 운영자에게 통보한다. 이는 시스템의 실시간 제약 위반을 감시하는 데 활용된다.

4.2 최악 실행 시간의 분석

실시간 시스템에서 행동 트리를 운용하기 위해서는 단일 tick의 최악 실행 시간(Worst-Case Execution Time, WCET)을 분석하여야 한다. WCET는 트리의 모든 노드가 실행되는 최악의 경로(worst-case path)에서의 총 실행 시간으로 추정된다.

WCET = \sum_{i=1}^{n} wcet(N_i) \cdot p(N_i)

여기서 wcet(N_i)는 노드 N_i의 최악 실행 시간이고, p(N_i)는 최악 경로에서 해당 노드가 실행되는 확률(0 또는 1)이다. WCET가 \Delta_t보다 작아야 tick 주기가 안정적으로 유지된다.

주기적 실행의 대안적 모델

이벤트 주도 실행

주기적 실행의 대안으로 이벤트 주도(event-driven) 실행 모델이 존재한다. 이 모델에서는 tick이 고정된 주기로 발생하는 것이 아니라, 블랙보드의 값 변경, 외부 이벤트 수신, 조건 변화 등의 사건에 의해 촉발된다. 이벤트 주도 모델은 환경 변화가 없는 동안의 불필요한 계산을 제거하여 에너지 효율과 계산 자원 활용을 최적화할 수 있다.

그러나 이벤트 주도 모델은 이벤트의 발생을 감지하기 위한 별도의 메커니즘이 필요하며, 다수의 이벤트가 동시에 발생하는 경우의 처리 순서를 정의하여야 한다는 복잡성이 추가된다.

적응적 주기 실행

적응적(adaptive) 주기 실행 모델에서는 tick 주기가 시스템의 상태에 따라 동적으로 조절된다. 로봇이 고속으로 이동하거나 장애물이 밀집한 환경에서는 tick 빈도를 높여 반응성을 향상시키고, 정지 상태이거나 변화가 적은 환경에서는 tick 빈도를 낮추어 계산 자원을 절약한다. 이 모델은 고정 주기 모델과 이벤트 주도 모델의 절충적 접근이라 할 수 있다.

주기적 실행과 행동 트리의 반응성

Tick의 주기적 실행은 행동 트리의 반응성(reactivity)과 직접적으로 연관된다. 환경에서 발생한 변화는 해당 변화 이후의 첫 번째 tick에서 감지된다. 따라서 최악의 경우 환경 변화에 대한 반응 지연은 하나의 tick 주기 \Delta_t에 해당한다.

반응형 노드(ReactiveSequence, ReactiveFallback)는 매 tick마다 조건을 재평가하므로, tick 주기가 곧 조건 재평가 주기이다. tick 주기가 충분히 짧으면 환경 변화에 대한 즉각적 대응이 가능하며, 이는 동적 환경에서 로봇의 안전하고 적응적인 행동을 보장하는 핵심 메커니즘이다 (Colledanchise & Ogren, 2018).

참고 문헌

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