1291.32 행동 트리의 개념적 정의

1291.32 행동 트리의 개념적 정의

1. 행동 트리의 비형식적 정의

행동 트리(Behavior Tree, BT)는 자율 에이전트의 행동 전환 논리를 방향 비순환 트리(directed acyclic tree) 구조로 조직화한 행동 제어 기법이다. BT에서 에이전트의 행동은 트리의 리프 노드(leaf node)에 캡슐화되며, 행동의 선택·순서·조건은 내부 노드(internal node)의 제어 논리에 의하여 결정된다. 트리의 루트(root)에서 리프(leaf)를 향한 하향식 주기적 탐색(periodic top-down traversal)에 의하여, 에이전트는 현재 환경 상태에 가장 적합한 행동을 매 실행 주기(tick)마다 반응적으로 선택·실행한다.

BT의 개념적 핵심은 다음의 세 가지 원리로 요약된다:

  1. 트리 구조에 의한 행동 조직: 행동과 행동 선택 논리가 트리 자료 구조에 의하여 계층적으로 조직된다
  2. 반환 상태에 의한 제어 흐름: 각 노드의 실행 결과가 성공(Success), 실패(Failure), 진행 중(Running)의 세 가지 반환 상태(return status)로 부모 노드에 전달되며, 부모 노드는 자식의 반환 상태에 기반하여 제어 흐름을 결정한다
  3. Tick 기반 주기적 탐색: 외부에서 주기적으로 전달되는 tick 신호에 의하여 트리의 탐색이 루트에서 재시작되며, 이에 의하여 반응적 행동 전환이 구조적으로 보장된다

2. 행동 트리와 기존 기법의 개념적 구별

2.1 FSM과의 구별

유한 상태 머신(FSM)이 상태(state)와 전이(transition)의 이원적 구조에 기반하는 반면, BT는 노드(node)와 부모-자식 관계(parent-child relationship)의 이원적 구조에 기반한다. 이 구별은 행동 전환의 메커니즘에 근본적 차이를 야기한다.

FSM에서 행동 전환은 현재 상태에서 명시적으로 정의된 전이 규칙에 의하여 발생한다. 전환의 가능 여부와 목적지가 현재 상태에 의존하므로, 전환 논리가 상태별로 분산되어 정의된다.

BT에서 행동 전환은 트리 탐색의 결과로 암묵적으로 발생한다. tick이 루트에서 개시되면, 노드의 제어 논리와 조건 평가에 따라 탐색 경로가 결정되고, 최종적으로 도달한 리프 노드의 행동이 실행된다. 전환 규칙의 명시적 정의가 불필요하며, 행동 전환은 트리 구조와 조건 노드의 평가에 의하여 자동으로 결정된다.

2.2 의사 결정 트리와의 구별

의사 결정 트리(Decision Tree)는 조건 평가에 기반하여 최종 행동을 선택하는 분류(classification) 구조이다. 의사 결정 트리와 BT는 모두 트리 구조를 활용하나, 다음의 차이가 존재한다.

의사 결정 트리에서 각 탐색은 루트에서 단일 리프까지의 경로를 결정하며, 리프에 도달하면 해당 행동이 즉시 결정된다. 노드는 조건(내부)과 행동(리프)의 두 종류만 존재하며, 노드 실행의 시간적 지속성(temporal duration)이 고려되지 않는다.

BT에서 리프 노드의 행동은 시간적 지속성을 가지며, Running 반환 상태에 의하여 행동의 진행 중 상태가 표현된다. 또한 BT의 내부 노드는 Sequence, Fallback, Parallel 등 다양한 제어 흐름 의미론(control flow semantics)을 가지며, 단순한 조건 분기를 넘어서는 복합적 행동 조합을 표현할 수 있다.

2.3 계층적 과제 네트워크(HTN)와의 구별

HTN은 추상적 과제를 구체적 행동으로 분해하는 계획(planning) 기법으로서, BT와 구조적 유사성을 공유한다. 그러나 HTN은 목표 상태에 도달하기 위한 행동 시퀀스를 탐색 시간에 자동으로 생성하는 반면, BT는 사전 정의된 트리 구조를 주기적으로 탐색하여 행동을 선택한다. HTN이 계획 수립(plan generation)에 중점을 두는 반면, BT는 계획 실행(plan execution)과 반응적 전환에 중점을 둔다.

3. BT의 구성 요소에 대한 개념적 정의

3.1 노드(Node)

BT의 기본 구성 단위로서, 하나의 논리적 기능 단위를 캡슐화한다. 모든 노드는 tick을 수신하면 자신의 논리를 실행하고, 세 가지 반환 상태(Success, Failure, Running) 중 하나를 부모 노드에 반환한다. 이 일관된 인터페이스가 BT의 모든 노드에 적용됨으로써, 노드 간의 교체와 조합이 인터페이스 호환성을 보장하면서 가능하다.

3.2 내부 노드(Internal Node)와 리프 노드(Leaf Node)

노드는 자식 노드의 유무에 따라 내부 노드와 리프 노드로 분류된다. 내부 노드는 하나 이상의 자식 노드를 보유하며, 자식 노드에 tick을 전파하고 자식의 반환 상태에 기반하여 자신의 반환 상태를 결정하는 제어 흐름 역할을 수행한다. 리프 노드는 자식 노드를 보유하지 않으며, 에이전트의 구체적 행동(action)을 실행하거나 환경 조건(condition)을 평가하는 실행 역할을 수행한다.

3.3 제어 흐름 노드(Control Flow Node)

내부 노드 중 자식 노드의 실행 순서와 반환 상태의 조합 논리를 결정하는 노드이다. 주요 제어 흐름 노드의 유형은 다음과 같다:

  • Sequence 노드: 자식 노드를 좌측에서 우측으로 순차 실행하며, 모든 자식이 Success를 반환하면 Success를, 하나라도 Failure를 반환하면 즉시 Failure를 반환한다. 논리곱(AND)에 대응한다.
  • Fallback 노드(Selector): 자식 노드를 좌측에서 우측으로 순차 시도하며, 하나라도 Success를 반환하면 즉시 Success를, 모든 자식이 Failure를 반환하면 Failure를 반환한다. 논리합(OR)에 대응한다.
  • Parallel 노드: 복수의 자식 노드를 동시에 실행하며, 성공/실패 정책(success/failure policy)에 따라 반환 상태를 결정한다.

3.4 실행 노드(Execution Node)

리프 노드에 해당하며, 다음의 두 유형으로 분류된다:

  • 액션 노드(Action Node): 에이전트의 구체적 행동(예: 이동, 사격, 물체 파지)을 실행한다. 행동이 즉시 완료되면 Success 또는 Failure를 반환하고, 완료에 시간이 소요되면 Running을 반환한다.
  • 조건 노드(Condition Node): 환경 또는 에이전트의 상태를 평가한다(예: 목표가 가시 범위 내에 있는가? 배터리 잔량이 충분한가?). 조건이 참이면 Success를, 거짓이면 Failure를 반환하며, Running은 반환하지 않는 것이 일반적이다.

3.5 데코레이터 노드(Decorator Node)

단일 자식 노드를 보유하는 특수한 내부 노드로서, 자식의 반환 상태를 변형하거나 자식의 실행에 부가적 논리를 적용한다. 예를 들어, Inverter 데코레이터는 자식의 Success를 Failure로, Failure를 Success로 변환하며, Repeat 데코레이터는 자식을 지정된 횟수만큼 반복 실행한다.

4. 행동 트리의 실행 의미론(Execution Semantics)

BT의 실행은 외부에서 전달되는 tick 신호에 의하여 구동된다. 매 tick이 루트 노드에 도달하면, 루트는 자식에게 tick을 전파하고, 자식은 자신의 논리를 실행하거나 하위 자식에게 tick을 재전파한다. 이 과정이 트리의 구조에 따라 재귀적으로 진행되며, 최종적으로 실행된 리프 노드의 반환 상태가 상향 전파(bottom-up propagation)되어 루트에 도달한다.

이 실행 모델의 핵심 특성은 매 tick마다 루트에서 탐색이 재시작된다는 것이다. 이에 의하여, 이전 tick에서 낮은 우선순위의 행동을 실행 중이었더라도, 새로운 tick에서 높은 우선순위의 조건이 충족되면 현재 행동이 중단되고 높은 우선순위의 행동이 즉시 실행된다. 이 메커니즘이 BT의 반응성(reactivity)을 구조적으로 보장하며, FSM에서 모든 상태에 전역 전이를 일일이 정의하여야 하는 부담을 제거한다.

5. 행동 트리의 질적 속성

BT의 개념적 정의로부터 도출되는 핵심 질적 속성(quality attribute)은 다음과 같다.

모듈성(Modularity). 각 서브트리가 자체 완결적(self-contained) 행동 모듈로서 기능하며, 트리의 다른 부분에 대한 의존 없이 독립적으로 설계·검증·재사용될 수 있다.

반응성(Reactivity). tick 기반 주기적 탐색에 의하여, 환경 변화에 대한 즉각적 행동 전환이 구조적으로 보장된다.

확장성(Scalability). 새로운 행동의 추가가 트리의 적절한 위치에 노드 또는 서브트리를 삽입하는 것으로 충분하며, 기존 트리에 대한 비국소적 수정이 불필요하다.

가독성(Readability). 트리 구조가 행동의 우선순위와 논리적 관계를 시각적으로 명료하게 표현하며, 좌측에서 우측으로의 우선순위 순서가 직관적으로 파악 가능하다.

선언적 표현(Declarative Representation). BT는 에이전트가 “무엇을(what)” 하여야 하는지를 트리 구조로 선언적으로 기술하며, 행동 간 전환이 “어떻게(how)” 발생하는지는 제어 흐름 노드의 의미론에 의하여 자동으로 결정된다.

6. 참고 문헌

  • 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.
  • Millington, I., & Funge, J. (2009). Artificial Intelligence for Games (2nd ed.). Morgan Kaufmann.
  • Champandard, A. J. (2007). “Understanding Behavior Trees.” AiGameDev.com.

v0.2.0