1291.85 행동 트리의 자동 생성 연구
1. 개요
행동 트리(Behavior Tree, BT)의 자동 생성(automatic synthesis) 연구는 수작업 설계의 한계를 극복하고, 형식 명세(formal specification)나 임무 기술(task description)로부터 행동 트리를 자동으로 구성하는 방법론을 개발하는 학술 분야이다. 자동 생성 연구는 크게 형식 합성(formal synthesis), 계획 기반 생성(planning-based generation), 진화적 탐색(evolutionary search)의 세 가지 주요 접근법으로 분류된다. 본 절에서는 각 접근법의 이론적 기초와 주요 연구 성과를 기술한다.
2. 수작업 설계의 한계와 자동 생성의 필요성
행동 트리의 수작업 설계는 다음과 같은 근본적 한계를 가진다. 첫째, 복잡한 임무에 대해 올바르고 완전한 행동 트리를 설계하는 것은 설계자의 전문 지식과 경험에 크게 의존하며, 설계 오류를 원천적으로 방지하기 어렵다. 둘째, 임무 요구 사항이 변경될 때마다 행동 트리를 수동으로 수정해야 하므로, 적응성과 유지보수성이 낮다. 셋째, 대규모 행동 트리의 수동 설계는 시간과 비용이 과도하게 소요된다.
이러한 한계를 극복하기 위해, 고수준 임무 명세로부터 행동 트리를 자동으로 생성하는 연구가 활발히 진행되어 왔다.
3. 형식 합성 기반 접근법
3.1 Correct-by-Construction 합성
Colledanchise, Murray, Ögren(2017)은 Synthesis of Correct-by-Construction Behavior Trees에서 선형 시제 논리(Linear Temporal Logic, LTL) 명세로부터 구조적으로 올바른(correct-by-construction) 행동 트리를 자동 합성하는 알고리즘을 제안하였다.
이 접근법의 핵심 개념은 다음과 같다. 사용자가 임무 요구 사항을 LTL 공식 \varphi로 명세하면, 합성 알고리즘이 \varphi를 만족하는 행동 트리 \mathcal{T}를 자동으로 구성한다. 합성 과정은 다음의 단계로 진행된다:
- 명세 분해(Specification Decomposition): LTL 공식 \varphi를 하위 목표(sub-goal)로 분해한다.
- 노드 매핑(Node Mapping): 각 하위 목표를 행동 트리의 조건 노드 또는 행동 노드에 매핑한다.
- 구조 합성(Structure Synthesis): 제어 흐름 노드(Sequence, Fallback)를 삽입하여 하위 목표 간의 논리적 관계를 트리 구조로 표현한다.
- 정확성 검증(Correctness Verification): 합성된 행동 트리 \mathcal{T}가 원래 명세 \varphi를 만족함을 형식적으로 검증한다.
이 방법의 핵심 장점은 합성 결과물의 정확성이 구성적으로 보장(correct-by-construction)된다는 점이다. 즉, 합성 알고리즘의 정확성이 증명되어 있으므로, 합성 결과물에 대한 별도의 검증이 불필요하다.
3.2 반응형 합성
반응형 합성(reactive synthesis)은 환경의 동적 변화에 대응하는 행동 전략을 자동으로 생성하는 접근법이다. 이 방법에서는 임무 명세가 환경의 가정(environment assumption)과 시스템의 보증(system guarantee)으로 구성된 가정-보증(assume-guarantee) 쌍으로 표현된다:
\varphi = \varphi_{\text{env}} \rightarrow \varphi_{\text{sys}}
반응형 합성 알고리즘은 환경이 \varphi_{\text{env}}를 만족하는 모든 가능한 행동에 대해 시스템이 \varphi_{\text{sys}}를 만족하는 행동 전략을 생성하며, 이를 행동 트리 구조로 인코딩한다.
4. 계획 기반 생성 접근법
4.1 태스크 플래닝과의 결합
태스크 플래닝(task planning) 알고리즘과 행동 트리를 결합하는 접근법에서는, PDDL(Planning Domain Definition Language) 등의 계획 언어로 기술된 도메인과 문제 정의로부터 행동 트리를 자동으로 생성한다.
Rovida, Crosby, Holz, Polydoros, Großmann, Petrick, Krüger(2017)은 SkiROS—A Skill-Based Robot Control Platform on Top of ROS에서 스킬(skill) 기반 로봇 제어 플랫폼에서 태스크 플래너의 계획 출력을 행동 트리로 변환하는 프레임워크를 제안하였다. 태스크 플래너가 생성한 행동 시퀀스는 Sequence 노드의 자식으로 배치되며, 각 행동의 사전 조건은 조건 노드로 표현된다.
4.2 계층적 계획과의 통합
계층적 태스크 네트워크(Hierarchical Task Network, HTN) 계획과 행동 트리의 결합도 주요한 연구 방향이다. HTN 계획에서 태스크의 계층적 분해(hierarchical decomposition) 구조는 행동 트리의 서브트리 계층 구조와 자연스럽게 대응한다. 상위 태스크의 분해 규칙은 행동 트리의 제어 흐름 노드로, 원시 태스크(primitive task)는 행동 노드로 변환된다.
5. 진화적 탐색 기반 접근법
5.1 유전 프로그래밍
Scheide, Best, Hollinger(2021)은 유전 프로그래밍(Genetic Programming, GP) 기법을 활용하여 행동 트리를 진화적으로 탐색하고 최적화하는 방법론을 제시하였다. 유전 프로그래밍에서 행동 트리는 개체(individual)로 표현되며, 다음의 진화 연산자(evolutionary operator)를 통해 세대를 거쳐 최적화된다:
- 선택(Selection): 적합도 함수(fitness function)에 기반하여 우수한 행동 트리를 선택한다.
- 교차(Crossover): 두 행동 트리의 서브트리를 교환하여 새로운 행동 트리를 생성한다.
- 돌연변이(Mutation): 행동 트리의 노드를 무작위로 추가, 삭제, 또는 변경한다.
적합도 함수는 임무 수행 성공률, 실행 시간, 에너지 소비, 안전성 등 다수의 목적 함수를 동시에 고려하는 다목적 최적화(multi-objective optimization) 형태로 정의된다:
f(\mathcal{T}) = w_1 \cdot f_{\text{success}}(\mathcal{T}) + w_2 \cdot f_{\text{time}}(\mathcal{T}) + w_3 \cdot f_{\text{safety}}(\mathcal{T})
여기서 w_i는 각 목적 함수의 가중치이다.
5.2 시뮬레이션 기반 평가
진화적 탐색에서 각 후보 행동 트리의 적합도 평가는 시뮬레이션 환경에서 수행된다. 후보 행동 트리를 시뮬레이션 환경에 배포하고, 다수의 시나리오에 대해 실행하여 성능 지표를 수집한다. 이 과정에서 Gazebo, Webots 등의 로봇 시뮬레이터가 활용된다.
6. 접근법 간 비교
Iovino, Scukins, Styrud, Ögren, Smith(2022)는 A Survey of Behavior Trees in Robotics and AI에서 행동 트리 자동 생성 접근법들을 체계적으로 비교하였다. 각 접근법의 주요 특성은 다음과 같이 비교된다:
| 접근법 | 정확성 보장 | 확장성 | 적응성 | 사전 지식 요구 |
|---|---|---|---|---|
| 형식 합성 | 구성적 보장 | 낮음 (상태 공간 제약) | 낮음 | LTL 명세 |
| 계획 기반 | 계획 알고리즘에 의존 | 중간 | 중간 | 도메인 모델 |
| 진화적 탐색 | 통계적 보장 | 높음 | 높음 | 적합도 함수 |
형식 합성은 정확성이 수학적으로 보장되나 대규모 시스템에 대한 확장성이 제한적이며, 진화적 탐색은 확장성과 적응성이 우수하나 정확성은 통계적으로만 보장된다. 계획 기반 접근법은 두 극단 사이의 절충점을 제공한다.
7. 자동 생성 연구의 과제와 전망
행동 트리 자동 생성 연구는 다음과 같은 과제를 안고 있다:
- 확장성: 형식 합성의 상태 공간 폭발 문제를 해결하기 위한 추상화(abstraction) 기법과 합성적 분해(compositional decomposition) 방법의 발전이 요구된다.
- 실세계 적용성: 시뮬레이션 환경에서 생성된 행동 트리가 실세계에서도 동일한 성능을 보장하는 시뮬레이션-실세계 전이(sim-to-real transfer) 문제의 해결이 필요하다.
- 인간 이해 가능성: 자동 생성된 행동 트리가 인간 개발자에게 이해 가능하고 유지보수 가능한 형태를 갖추도록 하는 연구가 필요하다.
- 온라인 적응: 사전에 생성된 행동 트리를 실행 중에 환경 변화에 따라 실시간으로 재합성하는 온라인 합성(online synthesis) 기법의 발전이 요구된다.
참고 문헌
- Colledanchise, M., Murray, R. M., & Ögren, P. (2017). Synthesis of Correct-by-Construction Behavior Trees. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
- Iovino, M., Scukins, E., Styrud, J., Ögren, P., & Smith, C. (2022). A Survey of Behavior Trees in Robotics and AI. Robotics and Autonomous Systems, 154, 104096.
- Rovida, F., Crosby, M., Holz, D., Polydoros, A., Großmann, B., Petrick, R., & Krüger, V. (2017). SkiROS—A Skill-Based Robot Control Platform on Top of ROS. Springer Tracts in Advanced Robotics.
- Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
버전: 2026-04-01