1291.43 행동 트리의 Tick 기반 실행 모델 개요

1. Tick의 정의와 역할

행동 트리(Behavior Tree, BT)는 자율적으로 실행을 개시하지 않는다. 행동 트리의 실행은 반드시 외부로부터 인가되는 이산적 신호(discrete signal)인 Tick에 의하여 구동된다. Tick은 행동 트리의 루트 노드에 전달되어 트리 순회(tree traversal)를 촉발하며, 이 순회 과정에서 각 노드의 평가 및 실행이 이루어진다.

형식적으로, 행동 트리 \mathcal{T}의 실행은 이산 시간 축 상의 Tick 시퀀스 \{\tau_0, \tau_1, \tau_2, \ldots\}에 의하여 구동되는 이산 시간 시스템(discrete-time system)으로 모형화된다. 시각 t_k에서 Tick \tau_k가 인가되면, 행동 트리는 환경의 현재 상태를 참조하여 노드를 순회하고, 적절한 행동을 실행하거나 조건을 평가한 후, 반환 상태(return status)를 루트 노드까지 상향 전파한다. Tick은 행동 트리의 단일 실행 주기(execution cycle)를 정의하는 기본 단위이며, 이 주기에 기반하여 로봇 시스템의 의사 결정과 행동 선택이 반복적으로 이루어진다.

Tick 기반 실행 모델의 근본적 설계 동기는, 로봇 시스템에서 요구되는 주기적 환경 인식과 반응적 행동 전환을 자연스럽게 구현하기 위함이다. 로봇은 지속적으로 변화하는 환경 속에서 동작하므로, 매 Tick마다 트리를 재순회함으로써 환경 변화에 대한 즉각적 반응이 가능해진다.

2. Tick 기반 실행 루프의 구조

2.1 기본 실행 루프

Tick 기반 실행 모델은 외부 실행 엔진(execution engine)과 행동 트리 사이의 상호작용으로 구성되며, 다음과 같은 반복 루프(loop)를 따른다.

1. 외부 실행 엔진이 사전에 결정된 Tick 주기 \Delta t에 따라 루트 노드에 Tick 신호를 인가한다.
2. 루트 노드는 수신한 Tick을 자신의 자식 노드에 전달한다.
3. Tick은 제어 흐름 노드(control flow node)의 실행 규칙에 따라 트리를 하향 순회(top-down traversal)한다.
4. 리프 노드(leaf node)에 도달하면, 해당 노드가 행동을 실행(액션 노드)하거나 조건을 평가(조건 노드)한다.
5. 리프 노드의 반환 상태(Success, Failure, Running)가 부모 노드로 상향 전파(bottom-up propagation)된다.
6. 부모 노드는 수신한 반환 상태와 자신의 제어 규칙에 따라 추가 자식 노드에 Tick을 전파하거나, 자신의 반환 상태를 결정하여 상위 노드에 보고한다.
7. 루트 노드의 최종 반환 상태가 외부 실행 엔진에 보고되고, 다음 Tick 시점까지 대기한다.

이 루프의 의사 코드(pseudocode)는 다음과 같이 표현된다.

while mission_active:
    wait_until(next_tick_time)
    status = root_node.tick()
    if status == SUCCESS:
        handle_mission_success()
    elif status == FAILURE:
        handle_mission_failure()
    # status == RUNNING이면 다음 Tick에서 계속

2.2 실행 엔진의 역할

외부 실행 엔진은 행동 트리의 Tick 주기를 관리하고, Tick 인가와 반환 상태 수신을 반복하는 상위 계층의 실행 관리자이다. ROS2 환경에서는 일반적으로 타이머 콜백(timer callback)을 통하여 Tick 주기를 제어한다. BehaviorTree.CPP 라이브러리의 Tree::tickWhileRunning() 함수는 이러한 실행 루프를 캡슐화하여, Running 상태가 반환되는 동안 지정된 주기로 Tick을 반복 인가하고, Success 또는 Failure가 반환되면 루프를 종료한다.

Nav2(Navigation2)에서는 BtActionServer가 실행 엔진의 역할을 수행하며, ROS2 액션 서버의 피드백 주기에 맞추어 행동 트리에 Tick을 인가한다.

3. Tick의 전파 메커니즘

3.1 깊이 우선 순회

Tick은 루트 노드로부터 깊이 우선 탐색(Depth-First Search, DFS) 방식으로 트리를 순회한다. 동일 계층의 자식 노드 사이에서는 좌측 우선(left-to-right) 순서가 적용된다. 이 순회 순서는 행동 트리의 노드 배치에 의미적 우선순위를 부여하며, 좌측에 배치된 행동일수록 높은 우선순위를 갖는다.

3.2 단축 평가에 의한 선택적 순회

행동 트리의 제어 흐름 노드는 단축 평가(short-circuit evaluation) 규칙을 적용함으로써, 불필요한 노드의 방문을 회피한다. 이로 인하여 하나의 Tick 주기에서 실제로 방문되는 노드의 수는 트리 전체 노드 수보다 일반적으로 적다.

Sequence 노드의 단축 평가: Sequence 노드 S가 자식 \{c_1, c_2, \ldots, c_n\}을 가질 때, 자식 노드를 좌측부터 순차적으로 Tick하되, 어떤 자식 c_i가 Failure를 반환하면 c_{i+1}, \ldots, c_n에는 Tick을 전달하지 않고 S 자체가 Failure를 반환한다.

\text{tick}(S) = \begin{cases} \text{Failure} & \exists\, i : \text{tick}(c_i) = \text{Failure} \\ \text{Running} & \exists\, i : \text{tick}(c_i) = \text{Running} \wedge \forall\, j < i : \text{tick}(c_j) = \text{Success} \\ \text{Success} & \forall\, i : \text{tick}(c_i) = \text{Success} \end{cases}

Fallback 노드의 단축 평가: Fallback 노드 F는 Sequence와 대칭적으로 동작한다. 어떤 자식 c_i가 Success를 반환하면 나머지 자식에는 Tick이 전달되지 않고 F는 Success를 반환한다.

\text{tick}(F) = \begin{cases} \text{Success} & \exists\, i : \text{tick}(c_i) = \text{Success} \\ \text{Running} & \exists\, i : \text{tick}(c_i) = \text{Running} \wedge \forall\, j < i : \text{tick}(c_j) = \text{Failure} \\ \text{Failure} & \forall\, i : \text{tick}(c_i) = \text{Failure} \end{cases}

이러한 단축 평가 메커니즘은 부울 논리(Boolean logic)의 단축 평가와 구조적으로 동일하며, Sequence는 논리곱(AND), Fallback은 논리합(OR)에 대응한다.

4. Tick 주기와 실시간 제약

4.1 Tick 주기의 설정

Tick 주기(tick period) \Delta t는 연속적인 두 Tick \tau_k와 \tau_{k+1} 사이의 시간 간격이다. Tick 주기는 로봇 시스템의 제어 루프 주기, 센서 갱신 주기, 그리고 의사 결정의 시간적 해상도(temporal resolution)에 따라 결정된다.

Nav2에서는 기본 Tick 주기를 약 10 ms(100 Hz)로 설정하며, 이는 DWB(Dynamic Window Based) 로컬 플래너의 제어 갱신 주기에 부합한다. BehaviorTree.CPP에서는 tickWhileRunning() 함수의 sleep_time 매개변수를 통하여 Tick 주기를 명시적으로 지정할 수 있다.

4.2 실시간성 보장 조건

Tick 기반 실행 모델에서 실시간성(real-time performance)을 보장하기 위한 필수 조건은, 단일 Tick 순회에 소요되는 시간 t_{\text{tick}}이 Tick 주기 \Delta t를 초과하지 않아야 한다는 것이다.

t_{\text{tick}} < \Delta t

이 조건이 위반되면 Tick 요청이 누적(backlog)되어 행동 트리의 반응 지연(response latency)이 증가하거나, 환경 변화에 대한 시의적절한 대응이 불가능해진다. 최악의 경우, Tick 처리가 무한정 지연되어 시스템의 안전 임계 요건(safety-critical requirements)을 위반할 수 있다.

이 조건을 충족하기 위하여, 행동 트리 설계 시 다음 사항을 고려하여야 한다.

• 트리의 최대 깊이(depth)와 폭(breadth)을 제한하여 순회 경로의 길이를 제어한다.
• 각 노드의 tick() 함수가 비차단(non-blocking) 방식으로 구현되어야 한다.
• 장시간 소요되는 연산은 별도의 비동기 프로세스로 위임하고, 노드는 해당 프로세스의 완료 여부만을 확인하여 Running 또는 종결 상태를 반환한다.

5. Tick과 노드 상태의 생명 주기

5.1 노드의 상태 전이 모델

각 노드는 Tick의 수신과 처리에 따라 다음과 같은 상태 전이(state transition)를 경험한다.

\text{IDLE} \xrightarrow{\text{최초 Tick 수신}} \text{RUNNING} \xrightarrow{\text{후속 Tick}} \text{RUNNING} \xrightarrow{\text{완료}} \text{SUCCESS 또는 FAILURE} \xrightarrow{\text{halt 호출}} \text{IDLE}

• IDLE: 노드가 아직 Tick을 수신하지 않았거나, 이전 실행이 완료된 후 halt() 호출에 의하여 초기화된 상태이다.
• RUNNING: 노드가 행동을 개시하였으나 아직 완료되지 않은 상태이다. 이 상태에서는 후속 Tick을 수신할 때마다 진행 상태를 확인하여 완료 여부를 판단한다.
• SUCCESS/FAILURE: 노드의 행동이 성공적으로 완료되었거나 실패하여 종결된 상태이다.

BehaviorTree.CPP 4.x에서는 노드의 생명 주기 관리를 위하여 onStart(), onRunning(), onHalted() 콜백 함수를 제공한다. onStart()는 IDLE 상태에서 최초 Tick 수신 시 호출되며, onRunning()은 RUNNING 상태에서 후속 Tick 수신 시 호출된다. 노드가 외부에 의하여 중단될 때는 onHalted()가 호출되어 자원 해제(resource cleanup)를 수행한다.

5.2 Halt 메커니즘

Tick 기반 실행 모델에서 halt는 Running 상태의 노드를 강제로 IDLE 상태로 복귀시키는 메커니즘이다. 제어 흐름 노드가 단축 평가에 의하여 특정 자식 노드에 더 이상 Tick을 전달하지 않을 때, 해당 자식 노드가 Running 상태였다면 halt가 호출된다.

예를 들어, Fallback 노드의 첫 번째 자식이 이전 Tick에서 Running을 반환하였으나, 현재 Tick에서 Success로 종결된 경우, 이전에 Running 상태였던 두 번째 자식 노드가 있다면 해당 노드에 halt가 인가된다. 이 메커니즘은 불필요하게 지속되는 비동기 행동의 정리를 보장하며, 시스템 자원의 누수(resource leak)를 방지한다.

5.3 동일 Tick 내의 다중 노드 실행

하나의 Tick에서 복수의 노드가 순차적으로 실행될 수 있다. Sequence 노드 아래에 즉시 완료되는 조건 노드와 액션 노드가 연속으로 배치된 경우, 단일 Tick 내에서 여러 노드의 실행과 반환이 연쇄적(cascading)으로 발생한다. 이는 Tick이 단순한 시간 분할(time slicing)이 아니라, **논리적 실행 단위(logical execution unit)**임을 의미한다.

6. Tick 기반 모델과 이벤트 기반 모델의 비교

행동 트리의 실행 구동 방식은 크게 Tick 기반(polling) 모델과 이벤트 기반(event-driven) 모델로 구분된다.

Tick 기반 모델의 핵심 장점은 **시간적 예측 가능성(temporal predictability)**이다. 매 Tick마다 트리를 재순회하므로, 행동 트리의 반응 지연이 최대 하나의 Tick 주기 \Delta t로 상한(upper bound)이 제한된다. 이 특성은 실시간 시스템(real-time system)에서의 안전성 분석과 최악 실행 시간(Worst-Case Execution Time, WCET) 분석에 유리하다.

반면, Tick 기반 모델의 단점은 환경에 변화가 없는 경우에도 매 주기마다 트리 순회가 수행되어 연산 자원이 불필요하게 소모된다는 점이다. 이를 완화하기 위하여, 최근의 행동 트리 프레임워크에서는 **반응형 노드(reactive node)**와 이벤트 트리거의 결합을 통한 하이브리드 실행 모델을 도입하고 있다.

BehaviorTree.CPP 4.x에서는 Tick 기반 모델을 기본 실행 모드로 채택하되, TreeObserver와 TreeExecutionServer 등의 기능을 통하여 이벤트 기반 트리거를 보조적으로 지원한다. 이를 통하여 특정 조건이 변경되었을 때만 Tick을 인가하는 부분적 이벤트 구동 방식을 구현할 수 있다.

7. Tick 기반 실행의 시간 복잡도

7.1 최악 시간 복잡도

행동 트리의 단일 Tick 순회에 대한 최악 시간 복잡도(worst-case time complexity)는 O(n)이다. 여기서 n은 트리 내 전체 노드의 수이다. 이는 모든 리프 노드가 Success를 반환하는 Sequence 트리처럼, 단축 평가에 의한 조기 종료가 발생하지 않아 전체 노드를 방문하는 경우에 해당한다.

7.2 평균 및 최선 시간 복잡도

단축 평가와 Running 상태의 메모리 메커니즘에 의하여, 실제 방문 노드 수는 일반적으로 n보다 상당히 적다.

• 단축 평가 효과: Fallback 노드에서 첫 번째 자식이 Success를 반환하면 나머지 자식을 방문하지 않으므로, 트리의 좌측 편향(left-biased) 구조에서 방문 노드 수가 대폭 감소한다.
• 메모리 메커니즘 효과: Running 상태를 기억하는 제어 노드(예: SequenceWithMemory)를 사용하면, 이전 Tick에서 Success를 반환한 자식 노드를 재방문하지 않고 Running 상태의 노드부터 순회를 재개한다. 이 경우 방문 노드 수가 트리의 높이 h에 비례하여 O(h)로 감소할 수 있다.

O(h) \leq t_{\text{visit}} \leq O(n), \quad h = \text{트리 높이}

7.3 공간 복잡도

Tick 기반 실행 모델의 공간 복잡도는 O(n)이다. 각 노드가 자신의 현재 상태(IDLE, RUNNING, SUCCESS, FAILURE)를 저장하여야 하며, 호출 스택(call stack)의 깊이는 트리의 높이 h에 비례하므로 O(h)의 추가 공간이 필요하다.

8. 참고 문헌

• Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
• Colledanchise, M., & Ögren, P. (2017). “How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees.” IEEE Transactions on Robotics, 33(2), 372–389.
• Faconti, D. (2022). BehaviorTree.CPP 4.x Documentation. https://www.behaviortree.dev/
• Marzinotto, A., Colledanchise, M., Smith, C., & Ögren, P. (2014). “Towards a Unified Behavior Trees Framework for Robot Control.” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 5420–5427.
• Iovino, M., Scukins, E., Styrud, J., Ögren, P., & Smith, C. (2022). “A Survey of Behavior Trees in Robotics and AI.” Robotics and Autonomous Systems, 154, 104096.
• 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), 2718–2725.
• 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.

버전: 2026-03-31