1292.104 행동 트리 구조와 동작 원리의 요약
1. 행동 트리의 구조적 기반
행동 트리(behavior tree)는 방향 비순환 그래프(DAG)의 특수한 형태인 루트 트리(rooted tree)로 정의된다. 트리는 하나의 루트 노드에서 시작하여, 내부 노드(제어 흐름 노드, 데코레이터 노드)와 리프 노드(액션 노드, 조건 노드)의 계층적 구조로 구성된다. 수학적으로 행동 트리 T는 노드 집합 N, 간선 집합 E, 루트 노드 r의 튜플 T = (N, E, r)로 형식화된다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).
2. 노드 유형의 분류
행동 트리의 노드는 기능에 따라 다음과 같이 분류된다.
| 노드 분류 | 노드 유형 | 위치 | 역할 |
|---|---|---|---|
| 루트 노드 | Root | 최상위 | tick의 시작점, 단일 자식 제약 |
| 제어 흐름 노드 | Sequence, Fallback, Parallel, Reactive 변형 | 내부 | 자식 실행 순서와 조건부 전파 |
| 데코레이터 노드 | Inverter, ForceSuccess, Repeat 등 | 내부 | 단일 자식의 반환 상태 변환 |
| 액션 노드 | 동기/비동기 액션 | 리프 | 환경에 대한 행동 수행 |
| 조건 노드 | 조건 | 리프 | 환경 상태의 즉각적 판별 |
3. 노드 반환 상태
각 노드는 tick을 수신하면 다음의 상태 중 하나를 반환한다.
| 반환 상태 | 의미 |
|---|---|
| Success | 노드의 작업이 성공적으로 완료됨 |
| Failure | 노드의 작업이 실패함 |
| Running | 노드의 작업이 진행 중이며 다음 tick에서 계속됨 |
| Idle | 노드가 아직 tick을 수신하지 않은 초기 상태 |
| Skipped | 제어 흐름에 의해 노드가 평가되지 않음 |
4. Tick 메커니즘
tick은 행동 트리의 실행을 구동하는 신호이다. 루트 노드에서 생성된 tick은 전위 순회(pre-order traversal) 순서에 따라 트리를 순회하며, 각 노드의 실행을 촉발한다. tick의 전파는 제어 흐름 노드의 의미론에 의해 조건부로 수행되며, 조기 종료 규칙에 의해 불필요한 노드의 평가가 생략된다.
5. 제어 흐름 노드의 동작 원리
제어 흐름 노드는 자식 노드에 대한 tick의 전파 방식을 결정한다.
| 제어 흐름 노드 | 의미론 | 조기 종료 조건 | 최종 반환 조건 |
|---|---|---|---|
| Sequence | 논리 AND | 자식 Failure → Failure | 모든 자식 Success → Success |
| Fallback | 논리 OR | 자식 Success → Success | 모든 자식 Failure → Failure |
| Parallel | 동시 실행 | 임계값 도달 시 | 성공/실패 임계값 정책 |
| ReactiveSequence | 반응형 AND | 자식 Failure → Failure | 매 tick 첫 자식부터 재평가 |
| ReactiveFallback | 반응형 OR | 자식 Success → Success | 매 tick 첫 자식부터 재평가 |
6. 노드 생명주기와 Halt 메커니즘
각 노드는 Idle, Running, Success, Failure의 상태 전이로 구성되는 생명주기를 가진다. onStart, onRunning, onHalted 콜백에 의해 노드의 초기화, 실행 지속, 중단 시 자원 정리가 수행된다. Halt 요청은 부모에서 자식으로 재귀적으로 전파되며, Running 상태의 모든 하위 노드가 안전하게 중단된다.
7. 메모리 모델
행동 트리의 메모리 모델은 노드 상태 메모리와 블랙보드로 구성된다. 노드 상태 메모리는 각 노드의 내부 상태를 유지하며, 블랙보드는 노드 간 데이터 공유를 위한 키-값 저장소이다. 블랙보드에 대한 접근은 포트 시스템(입력 포트, 출력 포트)에 의해 명시적으로 관리된다 (Faconti, BehaviorTree.CPP Documentation, 2024).
8. 실행 순서 보장
행동 트리는 왼쪽에서 오른쪽, 깊이 우선의 고정된 실행 순서를 보장한다. 트리에서 왼쪽에 배치된 노드가 오른쪽 노드보다 높은 우선순위를 가지며, 이 순서는 전위 순회에 의해 결정론적으로 구현된다.
9. 정적 분석
행동 트리는 실행 전에 정적 분석을 통해 구조적 정확성을 검증할 수 있다. 도달 가능성 분석은 모든 노드가 실행 경로상에서 도달 가능한지를 판정하고, 데드 노드 검출은 도달 불가능한 노드를 식별한다. 구조적 일관성 검증은 자식 수 제약, 포트 연결, 타입 일치 등의 형식적 제약 조건을 검사한다.
10. 실행 의미론의 분류
| 실행 의미론 | 특성 | 적용 영역 |
|---|---|---|
| 동기적 실행 | 단일 tick 내 완전 평가, 블로킹 | 단순 조건, 즉각 응답 시스템 |
| 비동기적 실행 | Running 상태로 다중 tick 실행 | 장기 실행 행동, 로봇 제어 |
| 이벤트 주도 실행 | 이벤트 발생 시에만 tick | 자원 제한 시스템, 반응형 시스템 |
11. 결정론적 실행
행동 트리의 실행은 결정론적이다. 고정된 평가 순서, 전위 순회 기반 실행, 명확한 조기 종료 규칙에 의해, 동일한 트리 구조와 동일한 환경 상태에서 항상 동일한 실행 결과가 보장된다. 이 결정론적 특성은 행동 트리의 검증, 디버깅, 안전성 분석의 근간이다.
12. 로봇 공학에서의 의의
행동 트리는 모듈성, 반응성, 결정론적 실행, 정적 분석 가능성이라는 구조적 장점에 의해 로봇 행동 제어의 표준적 프레임워크로 자리잡았다. 트리의 계층적 구조는 복잡한 행동의 체계적 분해와 조합을 지원하고, tick 메커니즘에 의한 주기적 재평가는 환경 변화에 대한 반응성을 보장한다. 조기 종료 규칙에 의한 안전 조건의 구조적 보장과, 결정론적 실행에 의한 예측 가능성은 안전 필수 로봇 시스템의 핵심 요구 사항을 충족한다 (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/