1292.86 깊이 우선 실행 순서
1. 깊이 우선 실행 순서의 정의
깊이 우선 실행 순서(depth-first execution order)란, 행동 트리에서 tick이 전파될 때 자식 노드의 서브트리를 완전히 평가한 후에 다음 형제 노드로 진행하는 실행 방식이다. 이 순서는 깊이 우선 탐색(Depth-First Search, DFS) 알고리즘의 순회 방식과 동일하며, 행동 트리의 실행이 트리 구조의 전위 순회(pre-order traversal)를 따름을 의미한다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).
2. DFS 기반 실행의 메커니즘
tick이 제어 흐름 노드에 도달하면, 해당 노드는 첫 번째 자식에 tick을 전달한다. 첫 번째 자식이 제어 흐름 노드인 경우, 해당 자식의 서브트리가 완전히 평가될 때까지 두 번째 자식에는 tick이 전달되지 않는다.
Sequence [S1]
├─ Sequence [S2]
│ ├─ Action [A1]
│ └─ Action [A2]
└─ Action [A3]
이 트리에서 tick의 전파 순서는 S1 → S2 → A1 → A2 → A3이다. S2의 서브트리(A1, A2)가 완전히 평가된 후에야 A3에 tick이 전달된다.
3. 전위 순회와의 대응
행동 트리의 DFS 기반 실행은 전위 순회에 대응한다. 전위 순회에서 노드의 방문 순서는 부모 → 왼쪽 자식의 서브트리 → 오른쪽 자식의 서브트리이다. 행동 트리의 tick 전파도 동일한 순서를 따른다.
단, 행동 트리에서는 조기 종료에 의해 모든 노드가 방문되지 않을 수 있다. Sequence 노드에서 자식이 Failure를 반환하면 이후의 자식은 방문되지 않으며, 이는 일반적인 DFS 순회와의 차이이다 (Faconti, BehaviorTree.CPP Documentation, 2024).
4. 너비 우선 실행과의 비교
| 속성 | 깊이 우선 (DFS) | 너비 우선 (BFS) |
|---|---|---|
| 서브트리 완결 | 한 서브트리를 완전히 평가 후 다음으로 | 같은 깊이의 노드를 먼저 평가 |
| 행동 트리 채택 | 채택됨 | 미채택 |
| 실행 예측성 | 높음 | 상대적으로 낮음 |
| 조기 종료 적합성 | 적합 | 부적합 |
행동 트리가 BFS가 아닌 DFS를 채택하는 이유는, DFS가 서브트리 단위의 의미론적 완결성을 보장하고, 조기 종료와 자연스럽게 결합되기 때문이다.
5. DFS 순서의 실행 흐름 예제
Fallback [F1]
├─ Sequence [S1]
│ ├─ Condition [C1]
│ └─ Action [A1]
└─ Action [A2]
| 단계 | 방문 노드 | 동작 |
|---|---|---|
| 1 | F1 | 첫 번째 자식 S1에 tick 전달 |
| 2 | S1 | 첫 번째 자식 C1에 tick 전달 |
| 3 | C1 | 조건 평가, Success 반환 |
| 4 | S1 | 두 번째 자식 A1에 tick 전달 |
| 5 | A1 | 행동 실행, Running 반환 |
| 6 | S1 | Running 반환 |
| 7 | F1 | Running 반환 (A2 미방문) |
S1의 서브트리가 Running을 반환하므로, A2는 이 tick에서 방문되지 않는다 (Colledanchise & Ögren, 2018).
6. 로봇 공학에서의 의의
DFS 기반 실행 순서는 행동의 논리적 그룹화와 일치한다. 하나의 Sequence 서브트리가 하나의 완결된 행동 시퀀스를 나타내며, 이 서브트리가 완전히 평가된 후에 다른 행동으로 전환된다. 이 특성은 행동 트리의 모듈적 설계를 지원한다 (Faconti, 2024).
참고 문헌
- 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/