1295.2 Parallel 노드의 동시 실행 모델
1. 동시 실행 모델의 개요
Parallel 노드의 동시 실행 모델(concurrent execution model)은 행동 트리 프레임워크에서 복수의 자식 노드가 동일한 틱(tick) 주기 내에서 모두 실행 기회를 갖는 방식을 형식적으로 규정한다. 이 모델은 운영체제의 프로세스 스케줄링이나 멀티스레드 프로그래밍과는 근본적으로 상이한 실행 패러다임을 따르며, 행동 트리의 결정론적(deterministic) 특성을 유지하면서도 동시적 행동 표현을 가능하게 한다(Colledanchise & Ögren, 2018).
2. 인터리빙 실행 모델
Parallel 노드의 동시 실행은 인터리빙(interleaving) 실행 모델에 기반한다. 인터리빙 실행이란, 복수의 실행 단위가 물리적으로 동시에 수행되는 것이 아니라, 단일 실행 흐름 내에서 각 실행 단위에 교대로 실행 기회를 부여하는 방식을 의미한다.
Parallel 노드 P가 N개의 자식 C_1, C_2, \ldots, C_N을 보유하는 경우, 단일 틱 주기에서의 실행 순서는 다음과 같이 결정론적으로 고정된다.
\text{tick}(P) \rightarrow \text{tick}(C_1) \rightarrow \text{tick}(C_2) \rightarrow \cdots \rightarrow \text{tick}(C_N) \rightarrow \text{aggregate}
여기서 \text{aggregate}는 모든 자식의 반환 상태를 수집하여 Parallel 노드의 최종 상태를 결정하는 단계이다. 각 자식은 이전 자식의 틱이 완전히 종료된 후에 틱을 수신하므로, 실행 순서에 따른 암묵적 의존성이 존재할 수 있다.
3. 협력적 동시성
Parallel 노드의 실행 모델은 선점형 동시성(preemptive concurrency)이 아닌 협력적 동시성(cooperative concurrency)을 따른다. 협력적 동시성에서는 각 실행 단위가 자발적으로 제어권을 양보하며, 외부에 의한 강제적 실행 중단이 발생하지 않는다.
행동 트리에서 이 원리가 적용되는 방식은 다음과 같다.
- 각 자식 노드는 틱을 수신하면 자신의 로직을 실행한다.
- 실행이 완료되면 SUCCESS, FAILURE, 또는 RUNNING 상태를 반환하고 제어권을 Parallel 노드에 양보한다.
- Parallel 노드는 다음 자식에 틱을 전달한다.
- 모든 자식이 상태를 반환하면 정책에 따라 최종 상태를 결정한다.
이 모델에서 각 자식 노드의 tick() 호출은 비차단(non-blocking)적이어야 한다. 즉, 자식 노드가 장시간 실행을 요구하는 경우 RUNNING을 반환하고 즉시 제어권을 반환해야 한다. 자식 노드가 tick() 내부에서 차단(blocking) 연산을 수행하면 후속 자식 노드의 틱이 지연되어 전체 행동 트리의 반응성이 저하된다.
4. 시간 모델과 틱 주기
Parallel 노드의 동시 실행 모델은 이산 시간(discrete time) 모델에 기반한다. 행동 트리는 연속적으로 실행되는 것이 아니라 주기적인 틱에 의해 구동되며, 각 틱은 논리적으로 단일 시점(instant)에 해당한다.
틱 주기를 \Delta t라 하면, 시각 t_k = k \cdot \Delta t에서 Parallel 노드의 모든 자식이 동일 시점의 상태 정보를 기반으로 판단을 수행하는 것이 이상적이다. 그러나 실제 구현에서는 C_1의 틱 실행이 C_2보다 먼저 완료되므로, C_1의 결과가 블랙보드를 통해 C_2에 영향을 미칠 수 있다. 이러한 암묵적 순서 의존성은 설계 시 주의가 필요하다.
t_k: \quad \underbrace{C_1 \rightarrow C_2 \rightarrow \cdots \rightarrow C_N}_{\text{단일 틱 주기 내 순차 실행}} \quad \rightarrow \quad t_{k+1}: \quad C_1 \rightarrow C_2 \rightarrow \cdots \rightarrow C_N
위 다이어그램은 연속된 두 틱 주기에서의 실행 흐름을 보여준다. 각 틱 주기 내에서 자식들은 순차적으로 실행되지만, 틱 주기 간에는 모든 자식이 동등하게 진행 기회를 가지므로 논리적 동시성이 성립한다.
5. 코루틴 유사 패턴
Parallel 노드의 동시 실행 모델은 프로그래밍 언어의 코루틴(coroutine) 패턴과 구조적 유사성을 갖는다. 코루틴은 실행을 중단(suspend)하고 나중에 재개(resume)할 수 있는 일반화된 서브루틴으로, 협력적 멀티태스킹의 기본 단위이다.
| 특성 | 코루틴 | Parallel 노드 자식 |
|---|---|---|
| 실행 중단 메커니즘 | yield 문 | RUNNING 반환 |
| 실행 재개 메커니즘 | 스케줄러 호출 | 다음 틱에서 재틱 |
| 상태 보존 | 지역 변수 유지 | 노드 내부 상태 유지 |
| 동시성 유형 | 협력적 | 협력적 |
| 종료 시점 | return 문 | SUCCESS 또는 FAILURE 반환 |
행동 트리의 자식 노드가 RUNNING을 반환하는 것은 코루틴이 yield를 호출하여 실행을 일시 중단하는 것과 동치이다. Parallel 노드는 스케줄러의 역할을 수행하여 매 틱마다 모든 자식에 재개 기회를 부여한다. 이 관점에서 Parallel 노드는 라운드 로빈(round-robin) 스케줄링을 수행하는 협력적 멀티태스킹 스케줄러로 해석할 수 있다.
6. 실행 모델의 형식적 성질
Parallel 노드의 인터리빙 실행 모델은 다음의 형식적 성질을 보장한다.
6.1 결정론성
동일한 입력 상태에서 동일한 순서의 자식 노드 배치는 항상 동일한 실행 결과를 산출한다. 이는 자식의 실행 순서가 정의 순서에 의해 결정론적으로 고정되기 때문이다. 멀티스레드 병렬 실행에서 발생하는 비결정론적(non-deterministic) 경합 조건(race condition)이 원천적으로 배제된다.
6.2 공정성
매 틱마다 모든 자식이 실행 기회를 가지므로, 특정 자식이 기아(starvation) 상태에 빠지지 않는다. 이는 Sequence나 Fallback 노드와의 핵심적 차이이다. Sequence에서는 첫 번째 자식이 RUNNING을 반환하면 후속 자식이 틱을 수신하지 못하지만, Parallel에서는 모든 자식이 매 틱마다 틱을 수신한다.
6.3 진행 보장
각 자식 노드가 유한 시간 내에 SUCCESS 또는 FAILURE를 반환한다면, Parallel 노드 역시 유한 시간 내에 최종 상태를 결정할 수 있다. 자식 노드가 무한히 RUNNING을 반환하는 경우, Parallel 노드도 무한히 RUNNING을 반환하게 되므로, 개별 자식의 종료 보장이 전체 Parallel 노드의 종료 보장에 대한 전제 조건이 된다.
7. 다른 동시성 모델과의 비교
| 동시성 모델 | 실행 방식 | 결정론성 | 경합 조건 가능성 | 적용 분야 |
|---|---|---|---|---|
| 멀티스레드 병렬 | 물리적 동시 실행 | 비결정론적 | 있음 | 범용 컴퓨팅 |
| 이벤트 루프 | 단일 스레드, 이벤트 구동 | 결정론적 | 없음 | I/O 집약적 시스템 |
| 코루틴 | 단일 스레드, 협력적 | 결정론적 | 없음 | 비동기 프로그래밍 |
| 행동 트리 Parallel | 단일 스레드, 틱 구동 | 결정론적 | 없음 | 로봇 행동 제어 |
행동 트리의 Parallel 실행 모델은 이벤트 루프 및 코루틴 모델과 유사한 단일 스레드 동시성 패러다임에 속하며, 멀티스레드 병렬 모델과는 근본적으로 구분된다. 로봇 행동 제어에서 결정론적 실행이 중시되는 이유는, 행동의 재현성(reproducibility)과 안전성 검증이 비결정론적 시스템에서는 극히 어렵기 때문이다.
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., & contributors. (2024). BehaviorTree.CPP Documentation. https://www.behaviortree.dev/
Version: 1.0-2026.04.03