1291.28 행동 트리의 기원과 역사적 배경

1. 행동 트리 개념의 형성적 기원

행동 트리(Behavior Tree, BT)는 특정 시점에 단일 발명자에 의하여 완성된 기법이 아니라, 게임 인공지능(Game AI) 산업에서 복수의 개발자와 연구자가 유한 상태 머신(FSM)의 구조적 한계에 대하여 독립적으로 시도한 해결 방안들이 수렴적으로 결합된 결과이다. 행동 트리의 핵심 설계 원리—트리 구조에 의한 행동의 계층적 조직, 주기적 탐색(tick)에 의한 반응적 실행, 노드 단위의 모듈적 행동 정의—는 2000년대 초중반에 걸쳐 점진적으로 형성되었다.

2. 이론적 선행 기반

2.1 계층적 과제 분해와 의사 결정 트리

행동 트리의 구조적 기원은 인공지능 분야의 고전적 기법인 의사 결정 트리(Decision Tree)와 계층적 과제 네트워크(Hierarchical Task Network, HTN)에서 부분적으로 추적할 수 있다. 의사 결정 트리는 조건 평가에 기반한 이진 분기를 통하여 최종 행동을 선택하는 구조로서, BT의 조건 노드(condition node)와 제어 흐름의 하향식 탐색(top-down traversal)에 영향을 미친 것으로 간주된다.

HTN은 Sacerdoti(1974)에 의하여 제안된 계획 기법으로서, 추상적 과제를 하위 과제로 반복적으로 분해하는 계층적 구조를 가진다. BT의 서브트리(subtree) 기반 구조적 분해는 HTN의 과제 분해 원리와 구조적 유사성을 보인다. 다만, HTN이 목표 상태에 도달하기 위한 행동 순서의 탐색(planning)에 중점을 두는 반면, BT는 사전 정의된 행동 구조의 반복적 탐색(traversal)에 의한 반응적 실행에 중점을 둔다는 점에서 본질적 차이가 존재한다.

2.2 포괄 아키텍처 (Subsumption Architecture)

Brooks(1986)가 제안한 포괄 아키텍처(Subsumption Architecture)는 행동 기반 로봇공학(behavior-based robotics)의 기초를 형성한 기법으로서, 복수의 행동 층(behavior layer)이 우선순위에 따라 하위 행동을 억제(subsume)하는 구조이다. BT의 Fallback 노드가 우선순위에 따라 자식 노드를 순차적으로 시도하는 동작은 포괄 아키텍처의 우선순위 기반 행동 선택과 구조적 유사성을 보인다. 그러나 포괄 아키텍처가 병렬적 행동 층 간의 억제 메커니즘에 기반하는 반면, BT는 트리의 하향식 순차 탐색에 기반한다는 점에서 실행 모델이 상이하다.

2.3 반응적 계획과 현실 기반 계획

Firby(1987)의 반응적 행동 패키지(Reactive Action Package, RAP)와 Georgeff 및 Lansky(1987)의 절차적 추론 시스템(Procedural Reasoning System, PRS)은 사전 계획된 절차를 환경 상태에 따라 반응적으로 선택·실행하는 기법이다. 이 기법들은 순수한 계획 기반 접근의 실시간 적용 한계를 인식하고, 사전 구조화된 행동 절차의 반응적 활성화를 추구한 점에서 BT의 설계 철학—사전 구조화된 행동 트리의 tick 기반 반응적 실행—과 맥락적 연관성을 가진다.

3. 게임 산업에서의 행동 트리 고안

3.1 Bungie Studios와 Halo 시리즈

행동 트리가 명시적 기법으로 최초 고안된 산업적 맥락은 Bungie Studios의 Halo 시리즈 개발 과정이다. Isla(2005)는 Game Developers Conference(GDC) 발표에서 Halo 2(2004) 개발 중 NPC 행동 제어에 사용된 대규모 FSM의 유지보수 어려움을 보고하고, 이를 해결하기 위하여 고안한 트리 기반 행동 제어 구조를 소개하였다.

Isla가 제시한 구조는 현대적 BT의 핵심 특성을 상당 부분 포함하고 있었다:

• 행동을 트리 구조로 조직하여 우선순위에 따른 행동 선택을 구현
• 노드의 성공/실패 반환값에 기반한 제어 흐름 관리
• 상위 노드에 의한 하위 행동의 구조적 관리

이 구조가 Halo 3(2007)의 NPC 행동 제어에 본격적으로 적용됨으로써, 트리 기반 행동 제어의 산업적 실용성이 대규모 상용 프로젝트에서 입증되었다.

3.2 AiGameDev.com과 기법의 체계화

Champandard(2007)는 AiGameDev.com을 통하여 게임 AI 커뮤니티에 행동 트리의 개념과 설계 원리를 체계적으로 소개하였다. Champandard의 기여는 산업 현장에서 비형식적으로 활용되던 트리 기반 행동 제어 기법에 “Behavior Tree“라는 통일된 명칭을 부여하고, 그 구성 요소—Sequence 노드, Selector(Fallback) 노드, Decorator 노드, Action 노드, Condition 노드—를 표준화된 용어와 의미론(semantics)으로 정리한 데 있다.

이 체계화는 행동 트리가 특정 스튜디오의 내부 기법에서 게임 AI 산업 전체의 공통 기법으로 확산되는 데 결정적 역할을 수행하였다. Champandard의 저술과 강연은 게임 개발자 커뮤니티에서 행동 트리에 대한 이해를 확산시키고, 다양한 상용 게임 엔진에서의 채택을 촉진하였다.

4. 게임 엔진에서의 제도적 채택

4.1 Unreal Engine의 BT 내장

Epic Games의 Unreal Engine은 4.x 버전부터 행동 트리를 내장 AI 시스템으로 채택하였다. Unreal Engine의 BT 구현은 시각적 편집기(visual editor)를 통하여 비프로그래머 인력이 행동 트리를 직접 설계·수정할 수 있는 인터페이스를 제공하며, 블랙보드(Blackboard) 데이터 구조를 통한 노드 간 데이터 공유 메커니즘을 표준화하였다. 세계 최대 규모의 상용 게임 엔진이 BT를 공식 AI 기법으로 채택한 것은 BT의 산업 표준화에 있어 이정표적 사건이다.

4.2 Unity 생태계에서의 확산

Unity 엔진에서는 엔진 내장 형태가 아닌 서드파티 에셋(third-party asset) 형태로 다수의 BT 프레임워크가 제공되었다. Behavior Designer, NodeCanvas 등의 에셋이 Unity Asset Store를 통하여 광범위하게 배포되었으며, 이들은 Unreal Engine의 BT 구현과 유사한 시각적 편집 인터페이스와 블랙보드 시스템을 제공하였다.

5. 학술 연구에서의 행동 트리 형식화

5.1 산업에서 학술로의 역방향 기술 이전

행동 트리는 산업 현장에서 실용적 필요에 의하여 고안된 후, 학술 분야로 역방향(industry-to-academia)으로 이전된 특수한 사례이다. 대부분의 소프트웨어 공학적 기법과 행동 제어 기법이 학술 연구에서 산업으로 이전되는 통상적 경로와 반대의 방향을 따른 것이다.

5.2 Colledanchise와 Ögren의 형식적 분석

Colledanchise와 Ögren(2014, 2017, 2018)은 행동 트리에 대한 최초의 체계적 형식적(formal) 분석을 수행하였다. 이들은 BT를 수학적으로 엄밀하게 정의하고, BT의 안전성(safety)과 활성성(liveness) 속성을 형식적으로 분석하며, BT와 FSM의 표현력(expressiveness)을 비교하는 연구를 수행하였다. 2018년에 출판된 저서 Behavior Trees in Robotics and AI: An Introduction은 행동 트리의 형식적 기초와 로봇공학 적용을 체계화한 최초의 학술 서적으로서, 로봇공학 분야에서 BT 연구의 기준 문헌이 되었다.

5.3 로봇공학으로의 이전

Marzinotto 등(2014)은 BT를 로봇 매니퓰레이션 작업에 적용하는 연구를 발표하여, BT가 게임 환경을 넘어 물리적 로봇 시스템에서도 효과적으로 작동함을 입증하였다. 이후 ROS2의 Nav2(Navigation2) 프레임워크가 행동 트리를 공식 행동 제어 기법으로 채택함으로써, 로봇공학 생태계에서의 BT 확산이 가속화되었다.

6. 행동 트리 발전의 연대기적 정리

7. 행동 트리 기원의 학술적 의의

행동 트리의 기원사는 다음의 학술적 시사점을 제공한다.

첫째, 행동 트리는 복수 선행 기법의 설계 원리가 산업적 필요에 의하여 수렴적으로 통합된 결과이며, 단일 이론에서 연역적으로 도출된 기법이 아니다. 이는 공학적 기법의 발전이 반드시 이론 선행-적용 후행의 선형적 경로를 따르지 않음을 보여준다.

둘째, 행동 트리의 산업에서 학술로의 역방향 이전은 실용적 검증이 형식적 분석에 선행할 수 있으며, 형식적 분석이 사후적으로 기법의 이론적 기초를 공고히 하는 역할을 수행할 수 있음을 보여준다.

셋째, 게임 AI와 로봇공학이 공유하는 행동 제어 문제—동적 환경에서의 에이전트 의사 결정, 실시간 반응성, 모듈적 행동 구성—의 구조적 유사성이 기술 이전의 이론적 기반이 되었으며, 이는 분야 간 기술 이전의 잠재적 가능성을 시사한다.

8. 참고 문헌

• Isla, D. (2005). “Handling Complexity in the Halo 2 AI.” Proceedings of the Game Developers Conference (GDC).
• Champandard, A. J. (2007). “Understanding Behavior Trees.” AiGameDev.com.
• 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.
• Marzinotto, A., Colledanchise, M., Smith, C., & Ögren, P. (2014). “Towards a Unified Behavior Trees Framework for Robot Control.” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 5420–5427.
• Brooks, R. A. (1986). “A Robust Layered Control System for a Mobile Robot.” IEEE Journal on Robotics and Automation, 2(1), 14–23.
• Sacerdoti, E. D. (1974). “Planning in a Hierarchy of Abstraction Spaces.” Artificial Intelligence, 5(2), 115–135.
• Firby, R. J. (1987). “An Investigation into Reactive Planning in Complex Domains.” Proceedings of the AAAI Conference on Artificial Intelligence, 202–206.
• Georgeff, M. P., & Lansky, A. L. (1987). “Reactive Reasoning and Planning.” Proceedings of the AAAI Conference on Artificial Intelligence, 677–682.

v0.2.0