1292.100 동기적 실행 의미론

1. 동기적 실행 의미론의 정의

동기적 실행 의미론(synchronous execution semantics)이란, 행동 트리의 단일 tick 내에서 루트 노드부터 리프 노드까지의 전위 순회가 완전히 완료되고, 루트 노드의 반환 상태가 결정된 후에야 tick이 종료되는 실행 모델이다. 동기적 실행에서 tick 함수의 호출은 블로킹(blocking) 방식으로 수행되며, 호출자는 tick이 완료될 때까지 대기한다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

2. 동기적 실행의 특성

동기적 실행 의미론에서 단일 tick의 실행 흐름은 다음의 특성을 가진다.

특성	설명
원자성	단일 tick은 중단 없이 완전히 실행된다
블로킹	tick 함수는 반환 상태가 결정될 때까지 반환하지 않는다
결정론적 순서	노드의 평가 순서가 트리 구조에 의해 결정적으로 정해진다
단일 스레드	하나의 실행 스레드에서 순차적으로 수행된다

3. 동기적 tick의 실행 흐름

동기적 실행에서 단일 tick의 흐름은 다음과 같다.

function synchronous_tick(root):
    // 1. 루트 노드의 tick 함수 호출 (블로킹)
    status = root.tick()

    // root.tick() 내부에서:
    //   - 자식 노드에 대한 재귀적 tick 호출
    //   - 각 자식의 tick도 블로킹으로 완료
    //   - 조기 종료 규칙 적용
    //   - 최종 반환 상태 계산

    // 2. 루트의 반환 상태가 결정된 후 반환
    return status

구체적인 예시를 통해 동기적 실행의 흐름을 추적하면 다음과 같다.

Root
 └─ Sequence
      ├─ Condition [C1]
      ├─ Action [A1]     (동기 액션)
      └─ Action [A2]     (동기 액션)

동기적 tick 실행 추적:

tick 시작
 → Root.tick()
   → Sequence.tick()
     → C1.tick() → Success      [즉시 완료]
     → A1.tick() → Success      [블로킹, 완료까지 대기]
     → A2.tick() → Success      [블로킹, 완료까지 대기]
     ← Success
   ← Success
 ← Success
tick 종료

모든 노드의 평가가 단일 tick 내에서 순차적으로 완료된다.

4. 동기적 실행과 Running 상태

동기적 실행 의미론에서도 Running 상태는 존재한다. 동기 액션 노드가 단일 tick 내에서 작업을 완료하지 못하면 Running을 반환할 수 있으며, 이 경우 해당 tick은 Running 상태로 종료된다. 다음 tick에서 해당 노드가 다시 평가된다.

그러나 순수한 동기적 실행 모델에서는 모든 액션 노드가 단일 tick 내에서 완료되는 것을 전제로 하므로, Running 상태의 반환이 최소화된다. 이는 동기적 실행과 비동기적 실행의 근본적인 차이점이다.

5. 동기적 실행의 시간 제약

동기적 실행에서 단일 tick의 실행 시간은 트리 내 모든 평가 노드의 실행 시간의 합이다.

구성 요소	실행 시간 기여
조건 노드	일반적으로 매우 짧음 (마이크로초 단위)
동기 액션 노드	행동의 복잡도에 비례
제어 흐름 노드	자식 실행 시간의 합 (조기 종료 시 감소)
데코레이터 노드	자식 실행 시간 + 변환 오버헤드

tick의 총 실행 시간이 tick 주기보다 길어지면, 다음 tick의 시작이 지연되어 실시간 제약이 위반될 수 있다. 이는 동기적 실행 의미론의 핵심적인 제약 사항이다 (Faconti, BehaviorTree.CPP Documentation, 2024).

6. 동기적 실행의 장점과 단점

항목	장점	단점
구현 복잡도	단순, 단일 스레드로 충분	-
결정론	완전한 결정론적 실행 보장	-
디버깅	실행 순서가 명확하여 추적 용이	-
실시간성	-	tick 실행 시간이 가변적
장기 실행 행동	-	블로킹으로 인한 응답 지연
동시성	-	병렬 실행 불가

7. 동기적 실행이 적합한 경우

동기적 실행 의미론은 다음의 조건이 충족되는 경우에 적합하다.

모든 액션 노드의 실행 시간이 충분히 짧은 경우
tick 주기에 비해 트리의 전체 평가 시간이 충분히 짧은 경우
결정론적 실행의 보장이 최우선 요구 사항인 경우
다중 스레드에 의한 복잡성을 회피하고자 하는 경우

8. 동기적 실행과 조건-행동 패턴

동기적 실행 의미론에서 조건-행동(condition-action) 패턴은 자연스럽게 구현된다. 조건 노드의 평가와 액션 노드의 실행이 동일한 tick 내에서 순차적으로 수행되므로, 조건 평가 시점과 행동 실행 시점 사이에 환경 상태가 변경될 가능성이 최소화된다.

Sequence
 ├─ Condition [Is_Safe]   → 즉시 평가
 └─ Action [Move]         → 즉시 실행 (동기적)

조건 평가와 행동 실행 사이에 다른 프로세스가 개입하지 않으므로, 원자적(atomic) 조건-행동 쌍이 보장된다.

9. 로봇 공학에서의 의의

동기적 실행 의미론은 행동 트리의 가장 기본적인 실행 모델이며, 행동 트리의 형식적 분석과 검증의 기반이 된다. 로봇 시스템에서 동기적 실행은 실행 순서의 결정론적 보장과 구현의 단순성이라는 장점을 제공하나, 장기 실행 행동이나 실시간 제약이 엄격한 시스템에서는 비동기적 실행 의미론으로의 확장이 필요하다 (Colledanchise & Ögren, 2018).

참고 문헌

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/