1292.84 행동 트리의 실행 순서 보장
1. 실행 순서 보장의 정의
행동 트리의 실행 순서 보장(execution order guarantee)이란, tick이 전파될 때 노드가 평가되는 순서가 행동 트리의 구조에 의해 결정론적으로 정해지며, 동일한 트리 구조와 동일한 환경 상태에서 항상 동일한 순서로 노드가 실행됨을 보장하는 특성이다. 이 결정론적 실행 순서는 행동 트리의 정확성 검증과 동작 예측의 기반이 된다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).
2. 실행 순서의 결정 규칙
행동 트리의 실행 순서는 다음의 두 가지 규칙에 의해 결정된다.
2.1 왼쪽에서 오른쪽 순서
동일한 부모 노드의 자식들은 왼쪽(첫 번째)에서 오른쪽(마지막) 순서로 평가된다. 이 순서는 자식의 배치 순서에 의해 결정되며, 모든 제어 흐름 노드에서 동일하게 적용된다.
2.2 깊이 우선 순서
tick은 깊이 우선 탐색(DFS) 방식으로 전파된다. 상위 노드가 자식 노드에 tick을 전달하면, 자식 노드의 서브트리가 완전히 평가된 후에 다음 형제 노드로 진행한다.
3. 제어 흐름 노드별 실행 순서
| 제어 흐름 노드 | 실행 순서 | 조기 종료 |
|---|---|---|
| Sequence | 왼쪽부터 순차, Failure 시 종료 | 자식 Failure |
| Fallback | 왼쪽부터 순차, Success 시 종료 | 자식 Success |
| Parallel | 왼쪽부터 순차 (모든 자식 실행) | 임계값 도달 |
| ReactiveSequence | 왼쪽부터 순차, 매 tick 재시작 | 자식 Failure |
| ReactiveFallback | 왼쪽부터 순차, 매 tick 재시작 | 자식 Success/Running |
4. 실행 순서와 우선순위
왼쪽에 배치된 자식이 오른쪽에 배치된 자식보다 높은 우선순위를 가진다. 이 우선순위는 Fallback 노드에서의 대안 선택, ReactiveSequence에서의 조건 검사 등에서 의미를 가진다.
Fallback
├─ Action [A1: 최우선 대안] ← 최고 우선순위
├─ Action [A2: 차선 대안]
└─ Action [A3: 최후 대안] ← 최저 우선순위
5. 단일 스레드 실행 모델
행동 트리의 tick 전파는 단일 스레드에서 수행된다. 이 단일 스레드 모델에 의해, 두 개의 노드가 동시에 tick을 수신하는 상황이 발생하지 않으며, 실행 순서가 엄격하게 보장된다. Parallel 노드의 자식도 단일 스레드에서 순차적으로 tick을 수신하며, 물리적 병렬 실행이 아닌 논리적 병렬 실행이다 (Faconti, BehaviorTree.CPP Documentation, 2024).
6. 실행 순서 보장의 의의
실행 순서의 결정론적 보장은 다음의 이점을 제공한다.
- 예측 가능성: 동일한 조건에서 동일한 동작이 재현된다
- 디버깅 용이성: 실행 경로를 추적하고 문제를 진단할 수 있다
- 정적 분석: 트리 구조만으로 실행 순서를 분석할 수 있다
- 안전성 검증: 안전 조건 검사가 행동 실행 전에 수행됨을 보장할 수 있다
7. 로봇 공학에서의 의의
실행 순서 보장은 안전이 중요한 로봇 시스템에서 필수적이다. 안전 조건 검사가 행동 실행 전에 항상 수행되고, 우선순위가 높은 대안이 항상 먼저 평가되며, 동일한 상황에서 동일한 행동이 선택됨을 보장한다 (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/