1293.2 Tick 기반 실행 모델의 동기

1. 행동 제어 아키텍처의 실행 모델 요구

로봇 행동 제어 아키텍처는 실행 모델(execution model)을 필요로 한다. 실행 모델이란, 시스템의 각 구성 요소가 언제, 어떤 순서로, 어떤 조건하에서 실행되는지를 규정하는 체계이다. 행동 트리(Behavior Tree)가 tick 기반 실행 모델을 채택한 데에는 기존 행동 제어 패러다임의 한계를 극복하려는 명확한 동기가 존재한다.

2. 기존 실행 모델의 한계

2.1 유한 상태 머신의 이벤트 구동 모델

유한 상태 머신(Finite State Machine, FSM)은 이벤트 구동(event-driven) 실행 모델을 사용한다. 상태 전이(state transition)는 외부 이벤트의 발생에 의해 촉발되며, 이벤트가 없으면 현재 상태가 유지된다. 이 모델은 다음과 같은 문제를 내포한다.

첫째, 반응성의 비균일성(non-uniform reactivity)이다. FSM에서 환경 변화에 대한 반응은 현재 상태에 정의된 전이 규칙에 의존한다. 특정 상태에서 특정 이벤트에 대한 전이가 정의되어 있지 않으면, 해당 이벤트는 무시된다. 이로 인해 시스템의 반응성이 현재 상태에 따라 비균일하게 달라진다 (Colledanchise & Ögren, 2018).

둘째, 전이 폭발(transition explosion) 문제이다. 상태 수가 증가함에 따라 가능한 전이의 수는 O(n^2)으로 증가하며, 모든 상태에서 중요한 이벤트에 반응하려면 다수의 중복 전이를 정의해야 한다. 이는 설계의 복잡성을 급격히 증가시킨다.

2.2 서브섬션 아키텍처의 연속 실행 모델

Brooks(1986)의 서브섬션 아키텍처(subsumption architecture)는 각 행동 계층이 연속적으로 실행되며, 상위 계층이 하위 계층의 출력을 억제(suppress)하는 방식을 사용한다. 이 모델은 모든 계층이 항상 실행되므로 계산 자원의 비효율적 사용을 초래하며, 행동 간의 우선순위 관계가 고정적이어서 유연한 의사 결정 구조를 표현하기 어렵다 (Arkin, 1998).

3. Tick 기반 실행 모델의 설계 동기

3.1 주기적 환경 감시의 필요성

로봇은 동적 환경(dynamic environment)에서 운용되므로, 환경 상태를 주기적으로 감시하여 적절한 행동을 선택해야 한다. tick 기반 실행 모델은 매 tick마다 트리의 루트에서부터 순회를 수행함으로써, 환경 변화를 일정한 주기로 감지하고 행동 결정을 갱신할 수 있게 한다. 이는 이벤트의 발생에 수동적으로 의존하는 이벤트 구동 모델과 구별되는 능동적 감시(active monitoring) 방식이다 (Colledanchise & Ögren, 2018).

3.2 결정론적 실행 순서의 보장

tick 기반 모델에서 노드의 실행 순서는 트리의 구조에 의해 결정론적(deterministic)으로 결정된다. 매 tick마다 동일한 깊이 우선, 왼쪽에서 오른쪽 순서로 노드가 방문되므로, 동일한 환경 상태가 주어지면 동일한 실행 경로와 결과가 산출된다. 이러한 결정론적 실행은 시스템의 예측 가능성(predictability)과 검증 가능성(verifiability)을 보장하며, 이는 안전 필수 로봇 시스템(safety-critical robotic system)에서 필수적인 속성이다 (Biggar et al., 2020).

3.3 균일한 반응성의 확보

tick 기반 모델에서 반응형 제어 노드(reactive control node)는 매 tick마다 조건 자식을 재평가한다. 이는 트리의 어떤 위치에서든, 어떤 실행 상태에서든, 환경 변화에 대한 반응이 균일한 주기로 이루어짐을 의미한다. FSM에서 특정 상태에서만 특정 이벤트에 반응할 수 있었던 한계가 tick 기반 모델에서는 구조적으로 해소된다.

3.4 비동기 행동의 자연스러운 수용

로봇의 행동은 대부분 비동기적(asynchronous)이다. 예를 들어, 목표 지점으로의 내비게이션은 수 초에서 수 분이 소요된다. tick 기반 모델에서 비동기 행동 노드는 Running 상태를 반환하여 행동이 아직 진행 중임을 보고하고, 후속 tick에서 진행 상태를 재확인받는다. 이 폴링(polling) 방식은 비동기 행동의 진행 상태 추적과 중단(halt)을 단순하고 통일된 메커니즘으로 처리할 수 있게 한다 (Faconti, 2024).

3.5 모듈성과 재사용성의 촉진

tick 기반 모델에서 각 노드는 tick() 함수라는 단일 인터페이스만을 구현하면 된다. 노드의 실행은 오직 tick 수신에 의해서만 촉발되며, 노드는 자신의 부모나 형제 노드의 구체적인 유형을 알 필요가 없다. 이러한 균일한 인터페이스는 노드의 독립적 개발, 테스트, 재사용을 촉진하며, 행동 트리의 모듈적 구성(modular composition)을 가능하게 한다 (Colledanchise & Ögren, 2018).

4. 제어 이론적 관점에서의 동기

제어 이론의 관점에서 tick 기반 실행 모델은 이산 시간 샘플링 제어(discrete-time sampled control)와 유사하다. 연속 시간 시스템을 이산 시간 간격으로 샘플링하여 제어하는 디지털 제어 시스템과 마찬가지로, tick 기반 행동 트리는 연속적인 환경 상태를 tick 주기마다 샘플링하여 행동 결정을 내린다.

이산 시간 제어 이론에서 샘플링 주기 T_s가 시스템의 동적 특성에 비해 충분히 작으면 연속 시간 제어와 유사한 성능을 달성할 수 있듯이, tick 주기가 환경 변화 속도에 비해 충분히 빠르면 tick 기반 행동 트리도 환경 변화에 적시에 반응할 수 있다. 이러한 이론적 유사성은 tick 기반 모델의 안정성 분석에 이산 시간 제어 이론의 도구를 적용할 수 있는 근거를 제공한다 (Colledanchise & Ögren, 2018).

5. 게임 AI에서의 기원

tick 기반 실행 모델의 기원은 게임 인공지능(game AI) 분야에 있다. 게임 엔진의 메인 루프(main loop)는 매 프레임(frame)마다 게임 세계의 상태를 갱신하며, 이 프레임 갱신 주기가 곧 tick이다. Isla(2005)가 Halo 2의 게임 AI에 행동 트리를 도입하였을 때, 게임 엔진의 프레임 갱신 주기에 맞추어 행동 트리를 tick하는 방식이 자연스럽게 채택되었다. 이 설계 선택은 이후 로봇공학으로 행동 트리가 전이되면서 그대로 계승되었으며, 로봇의 제어 루프(control loop)가 게임 엔진의 메인 루프와 구조적으로 유사하다는 점에서 합리적인 계승이었다 (Millington & Funge, 2009).

6. 대안적 실행 모델과의 비교

tick 기반 모델이 유일한 선택지는 아니다. 이벤트 기반(event-driven) 모델이나 하이브리드(hybrid) 모델도 가능하다. 그러나 tick 기반 모델이 행동 트리의 표준적 실행 모델로 자리 잡은 것은 다음의 이유에 기인한다.

tick 기반 모델은 구현의 단순성, 분석의 용이성, 반응성의 균일성이라는 조합에서 다른 모델보다 우위를 점하며, 이것이 행동 트리에서 tick 기반 실행 모델이 채택된 핵심 동기이다.

참고 문헌

• Arkin, R. C. (1998). Behavior-Based Robotics. MIT Press.
• 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.
• Brooks, R. A. (1986). A Robust Layered Control System for a Mobile Robot. IEEE Journal on Robotics and Automation, 2(1), 14–23.
• 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/
• Isla, D. (2005). Handling Complexity in the Halo 2 AI. Proceedings of the Game Developers Conference (GDC).
• Millington, I. & Funge, J. (2009). Artificial Intelligence for Games (2nd ed.). Morgan Kaufmann.