397.65 행동 트리(Behavior Tree) 기반 임무 계획과의 통합

1. 개요

**행동 트리(Behavior Tree, BT)**는 자율 에이전트의 행동을 계층적·모듈적으로 구성하는 제어 아키텍처로서, 게임 인공지능에서 유래하여 로봇 공학 분야에서 광범위하게 채택되고 있다(Colledanchise & Ögren, 2018). 행동 트리는 유한 상태 기계(Finite State Machine, FSM)에 비해 모듈성(modularity), 반응성(reactivity), 확장성(scalability)이 뛰어나며, 복잡한 임무 수행 로직을 직관적으로 구조화할 수 있다.

임무 계획(mission planning)과 행동 트리의 통합은, 고수준 임무 계획기가 생성한 추상적 계획을 로봇이 실시간으로 실행 가능한 행동 시퀀스로 변환하는 연결 계층(interface layer)을 제공한다. 본 절에서는 행동 트리의 기본 구조, 임무 계획과의 통합 아키텍처, 자동 행동 트리 생성 기법을 다룬다.

2. 행동 트리의 기본 구조

2.1 노드 유형

행동 트리는 방향 비순환 트리(rooted tree)로 구성되며, 각 노드는 틱(tick) 신호를 수신하여 성공(Success), 실패(Failure), 실행 중(Running) 중 하나의 상태를 부모 노드에 반환한다.

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

• 시퀀스(Sequence, →): 자식 노드를 좌에서 우로 순차 실행하며, 모든 자식이 성공하면 성공, 하나라도 실패하면 즉시 실패를 반환한다.
• 폴백(Fallback, ?): 자식 노드를 좌에서 우로 순차 실행하며, 하나라도 성공하면 즉시 성공, 모든 자식이 실패하면 실패를 반환한다. 셀렉터(Selector)라고도 한다.
• 병렬(Parallel, ⇉): 모든 자식 노드를 동시에 실행하며, 성공/실패 판정 정책(M개 이상 성공 시 성공 등)에 따라 결과를 반환한다.

실행 노드(Execution Node):

• 액션(Action): 로봇의 구체적 행동(이동, 집기, 통신 등)을 실행한다.
• 조건(Condition): 환경 상태나 로봇 상태를 확인하여 성공 또는 실패를 반환한다. 상태를 변경하지 않는다.

데코레이터(Decorator): 단일 자식을 가지며, 자식의 결과를 변형한다. 대표적으로 반전(Inverter), 반복(Repeat), 타임아웃(Timeout) 등이 있다.

2.2 형식적 의미론

행동 트리의 실행 의미론은 함수적으로 정의할 수 있다. 각 노드 N의 실행 함수 f_N: \mathcal{S} \rightarrow \mathcal{S} \times \{\text{S}, \text{F}, \text{R}\}는 현재 상태 s \in \mathcal{S}를 입력으로 받아 갱신된 상태와 반환값을 출력한다.

시퀀스 노드의 의미론:

f_{\text{Seq}}(s) = \begin{cases} (s', \text{F}) & \text{if } f_{c_1}(s) = (s', \text{F}) \\ f_{\text{Seq}'}(s') & \text{if } f_{c_1}(s) = (s', \text{S}) \\ (s', \text{R}) & \text{if } f_{c_1}(s) = (s', \text{R}) \end{cases}

여기서 c_1은 첫 번째 자식, \text{Seq}'는 나머지 자식으로 구성된 시퀀스이다.

3. 임무 계획과 행동 트리의 통합 아키텍처

3.1 계층적 통합 구조

임무 계획기와 행동 트리의 통합은 일반적으로 세 계층 아키텍처를 따른다.

심의 계층에서 생성된 임무 계획 \pi = (\tau_1, \tau_2, \ldots, \tau_k)는 중간 계층에서 행동 트리로 변환되어 반응 계층에서 실행된다.

3.2 계획-실행 루프

통합 시스템의 핵심은 계획(plan)과 실행(execution)의 지속적 상호작용이다.

1. 계획 단계: 임무 계획기가 현재 세계 상태(world state)와 목표 상태(goal state)를 기반으로 행동 시퀀스를 생성한다.
2. 변환 단계: 행동 시퀀스를 행동 트리 구조로 변환한다.
3. 실행 단계: 행동 트리 엔진이 트리를 틱하면서 로봇 행동을 제어한다.
4. 모니터링 단계: 실행 결과를 모니터링하고, 계획 전제의 위반이 감지되면 재계획(replanning)을 발동한다.

이 루프는 환경 변화에 대한 반응성을 제공하며, 행동 트리의 고유한 반응적 특성과 결합하여 강건한 임무 수행을 가능하게 한다.

4. 자동 행동 트리 생성

4.1 PDDL 계획 기반 BT 생성

PDDL 기반 임무 계획기가 생성한 행동 시퀀스를 행동 트리로 자동 변환하는 체계적 방법론이 발전하였다(Colledanchise et al., 2019).

기본 변환 규칙은 다음과 같다.

순차 계획의 변환: 계획 \pi = (a_1, a_2, \ldots, a_k)는 시퀀스 노드로 직접 변환된다.

Sequence
├── Action(a₁)
├── Action(a₂)
├── ...
└── Action(aₖ)

조건 전제의 변환: 각 액션 a_i의 전제 조건(precondition) \text{pre}(a_i)은 조건 노드로 추가된다.

Sequence
├── Condition(pre(a₁))
├── Action(a₁)
├── Condition(pre(a₂))
├── Action(a₂)
├── ...

폴백을 통한 강건성 확보: 전제 조건이 만족되지 않을 때 대안 행동을 시도하도록 폴백 구조를 삽입한다.

Sequence
├── Fallback
│   ├── Condition(pre(a₁))
│   └── RecoverAction(a₁)
├── Action(a₁)
├── ...

4.2 후방 연쇄(Backward Chaining) 기반 BT 확장

Colledanchise & Ögren(2017)이 제안한 후방 연쇄 알고리즘은 목표 조건으로부터 역방향으로 행동 트리를 점진적으로 구축한다.

알고리즘: BackwardChainingBTExpansion

입력: 목표 조건 G, 액션 라이브러리 A
출력: 행동 트리 T

1.  T ← Fallback(Condition(G))
2.  while T가 실행 시 목표 미달성 do:
      미충족 조건 c ← T의 실패 원인 식별
      적합 액션 a ← {a ∈ A | c ∈ post(a)} 에서 선택
      서브트리 S ← Sequence(Condition(pre(a)), Action(a))
      T의 해당 폴백 노드에 S 추가
3.  return T

이 방법은 필요한 액션만을 점진적으로 추가하므로, 최소한의 행동 트리를 생성하며, 계획과 실행을 통합적으로 수행할 수 있다.

4.3 HTN 기반 BT 생성

계층적 작업 네트워크(HTN)의 과업 분해 구조는 행동 트리의 계층적 구조와 자연스럽게 대응된다.

HTN의 과업 분해를 행동 트리로 변환하면, HTN의 계획 능력과 BT의 반응적 실행 능력을 결합할 수 있다.

5. 반응적 재계획과 행동 트리의 결합

5.1 실행 중 재계획 트리거

행동 트리의 실행 과정에서 다음 상황이 감지되면 재계획이 트리거된다.

• 전제 조건 위반: 현재 실행할 액션의 전제 조건이 더 이상 만족되지 않는 경우
• 액션 실패: 액션 실행이 실패를 반환한 경우
• 새로운 목표 추가: 상위 시스템으로부터 새로운 임무 목표가 전달된 경우
• 환경 변화 감지: 센서에 의해 중대한 환경 변화가 관측된 경우

5.2 부분 재계획(Partial Replanning)

전체 행동 트리를 재생성하는 대신, 실패한 서브트리만을 대상으로 재계획을 수행하여 계산 비용을 절감한다. 실패가 발생한 서브트리의 루트 노드에서 후방 연쇄를 재적용하여, 변경된 환경에 적합한 새로운 서브트리를 생성하고 기존 트리에 삽입한다.

T' = T[\text{subtree}(N_{\text{fail}}) \leftarrow \text{Replan}(N_{\text{fail}}, s_{\text{current}})]

이 방법은 트리의 나머지 부분을 보존하므로, 안정적인 행동 연속성을 유지할 수 있다.

6. 행동 트리의 형식적 검증

6.1 안전성과 활동성 검증

행동 트리 기반 임무 실행의 형식적 검증은 다음 속성을 검사한다.

안전성(Safety): “위험한 상태에 진입하지 않는다.” 이는 행동 트리의 모든 실행 경로에서 안전하지 않은 액션-조건 조합이 발생하지 않는 것을 확인하는 것이다.

\forall s \in \mathcal{S}_{\text{reachable}}: s \notin \mathcal{S}_{\text{unsafe}}

활동성(Liveness): “목표 상태에 결국 도달한다.” 행동 트리의 반복적 틱이 무한 루프에 빠지지 않고 목표를 달성함을 보장한다.

\forall s_0 \in \mathcal{S}_{\text{init}}: \exists k, \text{tick}^k(T, s_0) \text{ yields Success}

6.2 모델 검사(Model Checking) 기반 검증

행동 트리를 시간적 구조(Kripke structure)로 번역하여 모델 검사기(NuSMV, SPIN 등)를 통해 시간 논리(LTL, CTL) 명세에 대한 적합성을 자동 검증할 수 있다(Biggar et al., 2020). 이를 통해 임무 계획기가 생성한 행동 트리가 원래의 임무 명세를 올바르게 구현하는지 형식적으로 확인한다.

7. 구현 프레임워크

7.1 BehaviorTree.CPP

BehaviorTree.CPP는 C++로 구현된 오픈 소스 행동 트리 라이브러리로서, ROS2 생태계에서 광범위하게 사용된다. 이 라이브러리는 다음 기능을 제공한다.

• XML 또는 프로그래매틱 방식의 트리 정의
• 런타임 트리 교체 및 서브트리 삽입
• 블랙보드(Blackboard) 기반 노드 간 데이터 공유
• 로깅 및 시각화 도구

7.2 py_trees

py_trees는 Python 기반 행동 트리 라이브러리로서, 빠른 프로토타이핑과 연구 목적에 적합하다. 데코레이터 패턴, 블랙보드, 시각화 기능을 제공하며, ROS2와의 통합을 지원한다.

8. 참고 문헌

• Biggar, O., Zamani, M., & Shames, I. (2020). “A Framework for Formal Verification of Behavior Trees with Linear Temporal Logic.” IEEE Robotics and Automation Letters, 5(2), 2341–2348.
• 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.
• Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
• Colledanchise, M., Parasuraman, R., & Ögren, P. (2019). “Learning of Behavior Trees for Autonomous Agents.” IEEE Transactions on Games, 11(2), 183–189.
• 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.