1291.34 행동 트리의 기본 구조 개요
1. 행동 트리의 구조적 개관
행동 트리(Behavior Tree, BT)는 유향 근트리(directed rooted tree) 자료 구조에 기반한 행동 제어 기법으로서, 트리를 구성하는 노드의 유형과 그 상호 관계에 의하여 에이전트의 행동 논리가 정의된다. BT의 기본 구조는 세 가지 핵심 요소—노드(node), 노드 간 부모-자식 관계(parent-child relationship), 반환 상태(return status)—로 구성되며, 이 세 요소의 조합에 의하여 복잡한 행동 논리가 간결하고 모듈적으로 표현된다.
2. 트리 구조의 구성 원리
2.1 루트 노드(Root Node)
BT의 최상위에 위치하는 유일한 노드로서, 부모 노드를 갖지 않는다. 외부에서 전달되는 tick 신호는 루트 노드를 통하여 트리 내부로 진입하며, 루트 노드의 반환 상태가 BT 전체의 실행 결과를 대표한다. 루트 노드의 반환 상태가 Success이면 BT가 표현하는 임무가 성공적으로 수행된 것이고, Failure이면 임무 수행이 실패한 것이며, Running이면 임무가 아직 진행 중인 것이다.
2.2 내부 노드(Internal Node)
하나 이상의 자식 노드를 보유하는 노드로서, 자식 노드에 tick을 전파하고 자식의 반환 상태에 기반하여 자신의 반환 상태를 결정하는 제어 흐름(control flow) 역할을 수행한다. 내부 노드는 다시 **제어 흐름 노드(control flow node)**와 **데코레이터 노드(decorator node)**로 세분된다.
제어 흐름 노드는 복수의 자식 노드(N \geq 2)를 보유하며, 자식의 실행 순서와 반환 상태의 조합 방식을 결정한다. 주요 유형은 다음과 같다:
| 노드 유형 | 기호 | 자식 실행 방식 | 반환 상태 결정 규칙 |
|---|---|---|---|
| Sequence | \rightarrow | 좌측에서 우측으로 순차 실행 | 모든 자식 Success → Success; 하나라도 Failure → Failure |
| Fallback | ? | 좌측에서 우측으로 순차 시도 | 하나라도 Success → Success; 모든 자식 Failure → Failure |
| Parallel | \rightrightarrows | 모든 자식 동시 실행 | 성공/실패 정책(policy)에 따라 결정 |
데코레이터 노드는 정확히 하나의 자식 노드(N = 1)를 보유하며, 자식의 실행 조건 변경, 반환 상태 변형, 반복 실행 등 단항(unary) 변환을 수행한다.
2.3 리프 노드(Leaf Node)
자식 노드를 갖지 않는 최말단 노드(N = 0)로서, 에이전트의 구체적 행동을 실행하거나 환경 조건을 평가하는 실행(execution) 역할을 수행한다. 리프 노드는 **액션 노드(action node)**와 **조건 노드(condition node)**로 분류된다.
액션 노드는 에이전트의 물리적 행동(이동, 파지, 사격 등)을 실행하며, 행동의 성공/실패/진행 중 여부를 반환한다. 조건 노드는 환경 또는 에이전트의 상태를 평가(배터리 잔량 확인, 목표 가시성 판별 등)하며, 평가 결과에 따라 Success 또는 Failure를 반환한다.
3. 노드 분류 체계의 정리
BT의 노드 분류 체계를 계층적으로 정리하면 다음과 같다:
노드(Node)
├── 내부 노드(Internal Node)
│ ├── 제어 흐름 노드(Control Flow Node)
│ │ ├── Sequence
│ │ ├── Fallback (Selector)
│ │ └── Parallel
│ └── 데코레이터 노드(Decorator Node)
│ ├── Inverter
│ ├── Repeat
│ ├── Retry
│ ├── ForceSuccess
│ └── ForceFailure
└── 리프 노드(Leaf Node)
├── 액션 노드(Action Node)
└── 조건 노드(Condition Node)
4. 반환 상태 체계
모든 노드는 tick을 수신하면 자신의 논리를 실행한 후, 다음의 세 가지 반환 상태 중 정확히 하나를 부모 노드에 반환한다:
- Success: 노드의 목적이 달성되었음을 나타낸다.
- Failure: 노드의 목적이 달성되지 않았음을 나타낸다.
- Running: 노드의 실행이 진행 중이며, 완료를 위하여 후속 tick이 필요함을 나타낸다.
이 삼원 반환 상태 체계(ternary return status system)는 BT의 모든 노드에 보편적으로 적용되는 일관된 인터페이스이다. 제어 흐름 노드는 자식의 반환 상태를 입력으로 받아 자신의 반환 상태를 결정하며, 이 과정이 트리를 따라 하향(자식으로의 tick 전파)과 상향(반환 상태의 전달)으로 재귀적으로 진행된다.
5. Tick에 의한 실행 흐름
5.1 Tick의 정의와 역할
tick은 외부 시계(external clock)로부터 일정 주기 \Delta t마다 루트 노드에 전달되는 실행 신호이다. 로봇공학에서 tick 주기는 일반적으로 제어 루프의 주기와 동기화되며, 10~100Hz(10~100ms) 범위가 일반적이다.
5.2 실행 흐름의 하향 전파
tick이 루트 노드에 도달하면, 루트 노드는 자신의 의미론에 따라 하나 이상의 자식 노드에 tick을 전파한다. 자식 노드는 다시 자신의 의미론에 따라 하위 자식에게 tick을 전파하며, 이 과정이 리프 노드에 도달할 때까지 재귀적으로 진행된다. 리프 노드에서 실제 행동 실행 또는 조건 평가가 수행된다.
5.3 반환 상태의 상향 전파
리프 노드의 실행이 완료되면, 실행 결과가 반환 상태로 부모 노드에 전달된다. 부모 노드는 수신한 자식의 반환 상태에 기반하여 자신의 반환 상태를 결정하고, 이를 다시 상위 부모에게 전달한다. 이 상향 전파가 루트 노드에 도달하면, 해당 tick의 실행이 완료된다.
5.4 루트에서의 재시작
매 tick마다 탐색이 루트 노드에서부터 새로 시작된다는 점이 BT의 반응성(reactivity)을 구조적으로 보장하는 핵심 메커니즘이다. 이전 tick에서 특정 행동이 Running 상태로 진행 중이었더라도, 새로운 tick에서 루트부터 탐색이 재개되므로, 우선순위가 높은 조건이 새로 충족되면 현재 행동이 중단되고 우선순위가 높은 행동으로 즉시 전환된다.
6. 구조적 아이디어의 핵심: 제어와 실행의 분리
BT의 기본 구조에서 가장 중요한 설계 원리는 제어 논리와 실행 논리의 분리이다. 내부 노드는 “어떤 순서로, 어떤 조건 하에 행동을 선택할 것인가“의 제어 논리만을 담당하며, 리프 노드는 “실제로 무엇을 할 것인가“의 실행 논리만을 담당한다. 이 분리에 의하여:
- 실행 노드(액션, 조건)는 제어 구조에 대한 의존 없이 독립적으로 구현·테스트될 수 있다.
- 제어 구조(Sequence, Fallback 등)는 실행 노드의 구체적 내용에 대한 의존 없이 행동 조합 논리를 정의할 수 있다.
- 동일 실행 노드가 상이한 제어 구조 내에서 재사용될 수 있다.
이 분리 원칙은 소프트웨어 공학의 관심사 분리(separation of concerns) 원칙과 전략 패턴(strategy pattern)에 부합하며, FSM에서 상태 내부에 행동 논리와 전이 논리가 혼재되는 문제를 구조적으로 해소한다.
7. BT 구조의 시각적 표현 관례
BT의 시각적 표현에서 다음의 표기 관례가 광범위하게 사용된다:
| 노드 유형 | 시각적 기호 | 표기 |
|---|---|---|
| Sequence | 오른쪽 화살표가 포함된 상자 | \rightarrow |
| Fallback | 물음표가 포함된 상자 | ? |
| Parallel | 이중 화살표가 포함된 상자 | \rightrightarrows |
| Action | 직사각형 상자 | 행동 명칭 기입 |
| Condition | 타원(ellipse) | 조건 명칭 기입 |
| Decorator | 마름모(rhombus) | 데코레이터 명칭 기입 |
이 표기 관례는 Colledanchise와 Ögren(2018)에 의하여 표준화되었으며, BehaviorTree.CPP의 Groot 에디터, Unreal Engine의 BT 에디터 등 주요 구현에서 유사한 시각적 표현이 사용된다.
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., & Colledanchise, M. (2022). BehaviorTree.CPP Documentation. https://www.behaviortree.dev
v0.2.0