1292.22 Tick 메커니즘의 기본 개념

1292.22 Tick 메커니즘의 기본 개념

1. Tick의 개념적 기원

행동 트리(Behavior Tree)에서 Tick은 트리의 실행을 구동하는 기본적 신호(signal)이다. Tick의 개념은 게임 엔진(game engine)의 프레임 갱신(frame update) 메커니즘에서 유래하였으며, 행동 트리가 비디오 게임의 인공지능 시스템에서 처음 체계적으로 활용되면서 이 개념이 채택되었다. Isla(2005)가 Halo 2의 인공지능 아키텍처에서 행동 트리를 적용한 이래, Tick 기반의 주기적 실행 모델은 행동 트리의 표준적 실행 메커니즘으로 정착하였다 (Isla, “Handling Complexity in the Halo 2 AI”, GDC 2005).

Colledanchise와 Ogren(2018)의 형식적 정의에서 Tick은 행동 트리의 루트 노드(Root Node)에 전달되어 트리 전체의 실행을 유발하는 활성화 신호로 정의된다 (Colledanchise & Ogren, Behavior Trees in Robotics and AI, 2018).

2. Tick의 기본 정의

Tick은 행동 트리의 실행 엔진(execution engine)이 루트 노드에 전달하는 단위 실행 요청이다. 하나의 tick이 발생하면 루트 노드로부터 시작하여 트리의 노드들이 순차적으로 실행되며, 각 노드는 tick을 수신한 후 Success, Failure, Running 중 하나의 상태를 반환한다.

Tick은 다음과 같은 본질적 속성을 갖는다.

2.1 원자성 (Atomicity)

하나의 tick은 원자적(atomic) 실행 단위이다. tick이 시작되면 트리의 순회와 노드 실행이 완료되어 루트 노드가 반환 상태를 수신할 때까지 중단되지 않는다. 이 원자성은 tick 실행 중에 트리의 구조나 블랙보드(Blackboard)의 값이 외부에서 변경되지 않는다는 전제하에 성립하며, 행동 트리의 결정론적 실행을 보장하는 기반이 된다.

2.2 이산성 (Discreteness)

Tick은 연속적(continuous)이 아니라 이산적(discrete)이다. 행동 트리의 실행은 연속적인 시간 흐름이 아니라 이산적인 tick의 연속으로 진행된다. 각 tick 사이에는 행동 트리가 실행되지 않는 유휴 기간(idle period)이 존재하며, 이 기간 동안 센서 데이터의 갱신, 하드웨어 상태의 변화, 외부 이벤트의 발생 등이 이루어진다.

2.3 주기성 (Periodicity)

Tick은 일반적으로 일정한 주기(period)로 반복 발생한다. 행동 트리의 실행 엔진은 설정된 주기에 따라 주기적으로 tick을 생성하고 루트 노드에 전달한다. 이 주기적 실행은 로봇 제어 시스템의 제어 루프(control loop)와 유사한 구조를 갖는다.

3. Tick의 동작 메커니즘

3.1 Tick의 하향 전파

Tick은 트리의 루트 노드에서 시작하여 하위 노드 방향으로 전파(propagation)된다. 루트 노드가 tick을 수신하면, 루트 노드는 자신의 유일한 자식 노드에게 tick을 전달한다. 제어 흐름 노드(Control Flow Node)는 자신의 제어 정책에 따라 특정 자식 노드에게 선택적으로 tick을 전달한다.

이 하향 전파 과정에서 모든 노드가 tick을 수신하는 것은 아니다. 제어 흐름 노드의 조기 종료(short-circuit) 규칙에 의해 일부 노드는 tick을 수신하지 못할 수 있다. 예를 들어, Sequence 노드에서 첫 번째 자식이 Failure를 반환하면 두 번째 이후의 자식은 tick을 수신하지 않는다.

3.2 반환 상태의 상향 전파

Tick의 하향 전파와 대응하여, 노드의 반환 상태(Return Status)는 상향으로 전파된다. 리프 노드(Leaf Node)가 tick을 수신하여 실행을 완료하면 반환 상태를 부모 노드에게 보고하고, 부모 노드는 자식의 반환 상태를 기반으로 자신의 반환 상태를 결정하여 다시 상위 노드에게 보고한다. 이 과정은 루트 노드에 도달할 때까지 계속된다.

루트 노드가 최종적으로 수신하는 반환 상태는 해당 tick의 전체적인 실행 결과를 나타낸다. Success는 트리가 표현하는 행동이 성공적으로 완료되었음을, Failure는 실패하였음을, Running은 아직 진행 중임을 의미한다.

4. Tick과 제어 루프의 관계

4.1 로봇 제어 루프와의 유사성

행동 트리의 tick 메커니즘은 로봇 제어 시스템의 제어 루프(control loop)와 구조적 유사성을 갖는다. 제어 루프에서는 센서 데이터를 읽고(sense), 제어 입력을 계산하고(plan), 액추에이터에 명령을 전달하는(act) 과정이 주기적으로 반복된다. 행동 트리에서는 tick을 통해 환경 상태를 조건 노드로 평가하고(sense), 제어 흐름 노드의 논리에 의해 행동을 선택하고(plan), 액션 노드를 통해 행동을 실행하는(act) 과정이 주기적으로 반복된다.

이러한 구조적 유사성으로 인해 행동 트리는 로봇의 Sense-Plan-Act 아키텍처에 자연스럽게 통합될 수 있다 (Colledanchise & Ogren, 2018).

4.2 실시간 시스템에서의 Tick

로봇 공학에서 행동 트리의 tick은 실시간(real-time) 제약을 갖는 경우가 많다. 로봇의 안전한 동작을 위해서는 각 tick의 실행이 지정된 시간(deadline) 내에 완료되어야 하며, tick 주기의 안정적 유지가 필요하다. 이는 행동 트리의 설계에서 각 노드의 실행 시간이 예측 가능하고 제한된 범위 내에 있어야 함을 의미한다.

비동기 액션 노드가 Running을 반환하고 onRunning 콜백에서 작업 상태만 확인하는 설계 패턴은 이러한 실시간 제약을 충족시키기 위한 것이다. 실제 작업은 별도의 스레드나 프로세스에서 수행되고, tick 콜백에서는 작업의 완료 여부만 검사함으로써 tick의 실행 시간을 짧게 유지한다.

5. Tick의 실행 모델

5.1 동기적 Tick 모델

기본적인 tick 실행 모델은 동기적(synchronous) 모델이다. 이 모델에서 tick은 단일 스레드에서 실행되며, 하나의 tick이 완료된 후에야 다음 tick이 시작된다. 동기적 모델은 실행의 결정론성(determinism)을 보장하며, 동시성(concurrency) 관련 문제를 원천적으로 방지한다.

5.2 이벤트 주도 Tick 모델

전통적인 주기적 tick 외에, 이벤트 주도(event-driven) tick 모델도 존재한다. 이 모델에서는 tick이 고정된 주기로 발생하는 것이 아니라, 블랙보드의 값 변경이나 외부 이벤트의 발생에 의해 촉발된다. 이벤트 주도 모델은 환경 변화가 없는 동안의 불필요한 tick 실행을 방지하여 계산 자원을 절약할 수 있다 (Colledanchise & Ogren, 2018).

6. Tick과 행동 트리의 반응성

Tick 메커니즘은 행동 트리의 반응성(reactivity)을 결정하는 핵심 요소이다. 환경의 변화에 대한 행동 트리의 반응 지연(response latency)은 tick 주기에 의해 하한이 결정된다. 환경 변화가 tick 사이에 발생하면, 해당 변화는 다음 tick에서야 감지되고 처리된다.

tick 주기를 짧게 설정하면 반응성이 향상되지만, 각 tick에서의 계산 부하가 증가한다. 반대로 tick 주기를 길게 설정하면 계산 부하는 감소하지만 반응 지연이 증가한다. 이 절충(trade-off)은 로봇 시스템의 요구 사항에 따라 적절하게 설정되어야 한다.

7. Tick의 형식적 표현

행동 트리의 형식적 의미론에서 tick은 다음과 같이 정의된다. 행동 트리 \mathcal{T}의 루트 노드를 R이라 하면, k번째 tick의 실행은 함수 tick_k: \mathcal{T} \times E_k \rightarrow S로 표현된다. 여기서 E_k는 k번째 tick 시점의 환경 상태, S = \{Success, Failure, Running\}은 반환 상태의 집합이다.

tick_k(\mathcal{T}, E_k) = f_R(E_k)

여기서 f_R은 루트 노드의 실행 함수이며, 이 함수는 재귀적으로 자식 노드의 실행 함수를 호출하여 트리 전체를 순회한다 (Colledanchise & Ogren, 2018).

참고 문헌

  • Colledanchise, M. & Ogren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
  • Isla, D. (2005). “Handling Complexity in the Halo 2 AI”. Game Developers Conference (GDC) 2005.
  • Faconti, D. (2024). BehaviorTree.CPP Documentation. https://www.behaviortree.dev/