1292.103 행동 트리의 결정론적 실행 보장
1. 결정론적 실행의 정의
행동 트리의 결정론적 실행(deterministic execution)이란, 동일한 트리 구조와 동일한 환경 상태가 주어졌을 때, tick에 의한 노드의 평가 순서와 반환 상태가 항상 동일하게 재현되는 성질이다. 결정론적 실행이 보장되면, 행동 트리의 동작은 트리의 구조와 환경의 상태만으로 완전히 예측할 수 있다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).
2. 결정론의 형식적 조건
행동 트리 T의 실행이 결정론적이려면 다음의 조건이 충족되어야 한다.
- 순서 결정성: 모든 제어 흐름 노드에서 자식의 평가 순서가 고정되어 있다
- 상태 결정성: 동일한 입력에 대해 각 노드가 항상 동일한 상태를 반환한다
- 전파 결정성: tick의 전파 규칙이 모호함 없이 정의되어 있다
- 종료 결정성: 각 tick이 유한한 시간 내에 종료된다
이 네 가지 조건이 충족되면, 트리의 실행은 결정론적 함수 f: S \rightarrow R로 표현된다. 여기서 S는 환경 상태, R은 반환 상태이다.
3. 결정론을 보장하는 구조적 메커니즘
3.1 고정된 평가 순서
행동 트리의 제어 흐름 노드는 자식을 항상 왼쪽에서 오른쪽 순서로 평가한다. 이 고정된 순서는 트리의 구조에 의해 결정되며, 런타임에 변경되지 않는다. 이는 동일한 환경 상태에서 동일한 노드가 항상 동일한 순서로 평가됨을 보장한다.
3.2 전위 순회 기반 실행
tick의 전파는 전위 순회(pre-order traversal)를 따르므로, 노드의 방문 순서가 트리의 구조에 의해 유일하게 결정된다. 전위 순회는 결정론적 알고리즘이므로, 동일한 트리 구조에 대해 항상 동일한 방문 순서를 생성한다.
3.3 조기 종료 규칙의 결정성
조기 종료(short-circuit) 규칙은 자식의 반환 상태에 기반하여 결정론적으로 적용된다. Sequence 노드에서 Failure가 발생하면 항상 즉시 Failure를 반환하고, Fallback 노드에서 Success가 발생하면 항상 즉시 Success를 반환한다. 이 규칙에는 모호함이 없다.
| 메커니즘 | 결정론 기여 |
|---|---|
| 왼쪽-오른쪽 순서 | 평가 순서의 유일성 보장 |
| 전위 순회 | 방문 순서의 재현성 보장 |
| 조기 종료 규칙 | 분기 결정의 유일성 보장 |
| 상태 전이 규칙 | 노드 상태 변화의 예측 가능성 보장 |
4. 결정론을 위협하는 요인
4.1 비결정론적 노드
외부 센서 입력에 의존하는 조건 노드나, 확률적 행동을 수행하는 액션 노드는 동일한 tick에서도 다른 결과를 반환할 수 있다. 이러한 비결정론은 환경의 비결정성에서 기인하며, 트리 구조의 비결정성은 아니다.
4.2 동시성에 의한 비결정론
다중 스레드로 구현된 비동기 액션 노드에서 스레드 스케줄링에 의한 실행 순서의 변동이 발생할 수 있다. 이는 구현 수준의 비결정론이며, 논리적 수준에서는 행동 트리의 실행 의미론이 결정론을 유지한다.
4.3 블랙보드 경쟁 조건
다수의 노드가 동일한 블랙보드 키에 동시에 접근하는 경우, 읽기-쓰기 순서에 따라 결과가 달라질 수 있다. 단일 스레드 실행에서는 전위 순회 순서에 의해 이 문제가 해결되나, 다중 스레드 실행에서는 동기화 메커니즘이 필요하다 (Faconti, BehaviorTree.CPP Documentation, 2024).
| 위협 요인 | 원인 | 해결 방안 |
|---|---|---|
| 센서 입력 변동 | 환경의 비결정성 | 트리 구조의 결정론과 분리 |
| 스레드 스케줄링 | 운영체제의 비결정성 | 논리적 순서의 결정론적 정의 |
| 블랙보드 경쟁 | 동시 접근 | 포트 시스템에 의한 접근 제어 |
5. 결정론적 실행과 재현 가능성
결정론적 실행은 재현 가능성(reproducibility)의 전제 조건이다. 행동 트리의 실행이 결정론적이면, 동일한 입력 시퀀스에 대해 동일한 실행 결과를 재현할 수 있으며, 이는 다음의 활동을 가능하게 한다.
| 활동 | 결정론의 역할 |
|---|---|
| 디버깅 | 오류 발생 조건을 정확히 재현 |
| 테스트 | 테스트 결과의 반복 가능성 보장 |
| 형식적 검증 | 트리의 속성을 수학적으로 증명 |
| 시뮬레이션 | 실제 환경 없이 동작을 예측 |
| 인증 | 안전성의 증명 가능성 제공 |
6. 결정론적 실행의 보장 전략
- 단일 스레드 실행: tick의 전체 과정을 단일 스레드에서 수행하여 동시성 비결정론을 제거한다
- 포트 기반 데이터 흐름: 블랙보드 접근을 포트 시스템으로 제한하여 경쟁 조건을 방지한다
- 결정론적 노드 설계: 각 노드가 동일한 입력에 대해 동일한 출력을 반환하도록 설계한다
- 환경 추상화: 환경의 비결정성을 트리 구조의 결정론과 명확히 분리한다
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/