1293.9 Tick의 단일 실행 단위 (Atomic Step)

1. 원자적 실행의 정의

행동 트리에서 하나의 tick은 원자적 단계(atomic step)로 취급된다. 원자적 실행이란, 하나의 tick이 시작되면 완전히 완료될 때까지 중간에 중단되거나 다른 tick에 의해 선점(preemption)되지 않는 실행 단위를 의미한다. tick의 시작과 종료 사이에서 트리의 상태는 외부에서 관측 불가능한 과도 상태(transient state)에 있으며, 외부에 공개되는 상태는 오직 tick 완료 시점의 최종 상태뿐이다 (Colledanchise & Ögren, 2018).

2. 원자성의 형식적 의미

tick의 원자성(atomicity)은 다음 세 가지 속성을 의미한다.

비분할성(Indivisibility): 하나의 tick은 더 이상 분할할 수 없는 실행의 최소 단위이다. tick 내부의 개별 노드 평가는 tick이라는 하나의 단위로 묶여 외부에서 구분되지 않는다.

비선점성(Non-preemptibility): 하나의 tick이 실행 중일 때, 다른 tick이 시작될 수 없다. 현재 tick이 완료된 후에야 다음 tick이 실행될 수 있다. 이는 두 tick 사이의 상호 배제(mutual exclusion)를 보장한다.

일관성(Consistency): tick이 완료되면 트리의 상태는 일관된(consistent) 상태에 있다. tick 실행 도중의 중간 상태는 외부에 노출되지 않으므로, 외부 관찰자는 항상 일관된 상태만을 관측한다.

3. 원자적 단계의 경계

tick의 원자적 경계(atomic boundary)는 다음과 같이 정의된다.

[tick 시작 경계]
    ┌─────────────────────────────┐
    │  루트 노드 tick() 호출       │
    │  깊이 우선 순회 수행          │
    │  각 노드의 상태 갱신          │
    │  반환 상태의 상향 전달        │
    │  루트 노드의 최종 상태 결정    │
    └─────────────────────────────┘
[tick 종료 경계]

tick 시작 경계 이전과 tick 종료 경계 이후는 tick 간 간격(inter-tick interval)이며, 이 기간 동안 트리의 상태는 정지(quiescent) 상태에 있다. 새로운 센서 데이터의 수신, 외부 이벤트의 처리 등은 이 tick 간 간격에서 발생할 수 있다.

4. 트랜잭션으로서의 Tick

tick의 원자성은 데이터베이스 시스템의 트랜잭션(transaction)과 유사한 개념이다. 데이터베이스 트랜잭션이 ACID 속성(Atomicity, Consistency, Isolation, Durability)을 보장하듯이, tick은 다음과 같은 유사한 속성을 보장한다.

5. 단일 스레드 실행과 원자성

행동 트리의 표준적 구현에서 tick은 단일 스레드(single thread)에서 실행된다. 단일 스레드 실행 모델에서 원자성은 자연스럽게 보장된다. 단일 스레드는 한 번에 하나의 tick만 실행할 수 있으므로, tick 간의 상호 배제가 구조적으로 보장된다 (Faconti, 2024).

그러나 비동기 액션 노드가 별도의 스레드에서 실행되는 경우, tick의 원자성은 tick 순회 자체에 대해서만 보장된다. 비동기 액션의 실행은 tick 경계를 넘어 지속될 수 있으며, 이 경우 tick과 비동기 액션 사이의 동기화가 별도로 관리되어야 한다.

6. 노드 수준의 원자성

tick의 원자성과 구별되는 개념으로 노드 수준의 원자성이 있다. 각 노드의 tick() 함수 호출은 그 자체로 원자적이어야 한다. 즉, 노드의 tick() 함수는 호출되면 반드시 Success, Failure, 또는 Running 중 하나를 반환해야 하며, 반환 없이 무한히 차단(blocking)되어서는 안 된다.

// 올바른 노드 구현: 즉시 반환
NodeStatus CheckBattery::tick() {
    if (battery_level > threshold)
        return NodeStatus::SUCCESS;
    else
        return NodeStatus::FAILURE;
}

// 올바른 비동기 노드 구현: Running 반환
NodeStatus NavigateToGoal::tick() {
    if (goal_reached)
        return NodeStatus::SUCCESS;
    if (navigation_failed)
        return NodeStatus::FAILURE;
    return NodeStatus::RUNNING;  // 아직 진행 중
}

노드의 tick() 함수가 장시간 차단되면, 트리 전체의 tick 실행 시간이 증가하여 tick 주기를 초과할 수 있다. 이는 실시간 제약 위반으로 이어질 수 있으므로, 각 노드의 tick() 함수는 가능한 한 빠르게 반환되어야 한다.

7. 원자적 단계와 상태 일관성

tick의 원자성은 트리 상태의 일관성을 보장하는 핵심 메커니즘이다. tick 실행 도중에는 일부 노드의 상태가 갱신되고 일부는 아직 이전 상태를 유지하는 과도 상태가 존재한다. 그러나 이 과도 상태는 tick 내부에서만 존재하며, tick이 완료되면 모든 방문된 노드의 상태가 갱신된 일관된 상태가 된다.

tick 시작 전:  [S, S, R, F, S]   ← 일관된 상태
tick 실행 중:  [S, ?, ?, ?, ?]   ← 과도 상태 (외부 비공개)
tick 완료 후:  [S, F, S, F, R]   ← 일관된 상태

8. 원자적 단계 간의 상태 보존

두 연속 tick 사이에서 트리의 내부 상태는 보존(preserve)된다. 특히 Running 상태를 반환한 노드의 내부 상태는 다음 tick에서 해당 노드가 재방문될 때까지 유지된다. 이 상태 보존은 비동기 행동의 연속적 진행을 가능하게 한다.

예를 들어, 내비게이션 액션 노드가 Running을 반환한 경우, 해당 노드는 내부적으로 현재 내비게이션의 진행 상태(경로 위의 위치, 남은 거리 등)를 보존하며, 다음 tick에서 이어서 진행 상태를 확인한다.

9. 원자적 단계의 실시간 제약

실시간 시스템에서 tick의 원자적 단계는 시간적 상한(temporal upper bound)을 가져야 한다. tick의 실행 시간이 tick 주기를 초과하면 다음 tick의 시작이 지연되어 시스템의 주기성(periodicity)이 훼손된다.

tick의 최악 실행 시간(Worst-Case Execution Time, WCET)을 C_{tick}, tick 주기를 T라 하면, 실시간 스케줄링 가능성의 필요 조건은 다음과 같다.

C_{tick} \leq T

이 조건이 충족되지 않으면 tick 주기를 증가시키거나, 트리의 복잡도를 감소시켜 tick의 실행 시간을 단축해야 한다.

참고 문헌

• 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/