Behavior Tree 개요 및 사용법

Behavior Tree란?

Behavior Tree(행동 트리)는 로봇이나 AI 에이전트의 행동을 관리하고 결정하기 위한 계층적 제어 구조이다. 이 구조는 트리 형태로 구성되며, 각 노드는 조건이나 행동을 정의한다. 행동 트리는 주로 로봇의 행동 계획, 게임 AI, 자동화된 시스템 제어 등에서 사용된다.

Behavior Tree의 주요 구성 요소는 다음과 같다.

루트 노드 (Root Node): 트리의 최상위 노드로, 트리의 실행을 시작하는 지점이다.
행동 노드 (Action Node): 특정 행동을 정의하는 노드로, 예를 들어 로봇이 특정 경로를 따라 움직이는 행동을 포함할 수 있다.
조건 노드 (Condition Node): 조건을 평가하여 자식 노드의 실행 여부를 결정하는 노드이다.
제어 노드 (Control Node): 다른 노드들의 실행 순서를 제어하는 노드이다. 보통 Sequence, Selector, Parallel과 같은 노드들이 여기에 해당한다.

Sequence 노드

Sequence 노드는 자식 노드를 순차적으로 실행하며, 하나의 노드가 실패하면 즉시 실행을 중단한다. 모든 자식 노드가 성공하면 이 노드는 성공으로 간주된다.

수식으로 표현하자면, 각 노드 $N_i$ 에 대해 $N_1, N_2, ..., N_n$ 이 있을 때,

$\text{Sequence}(N_1, N_2, ..., N_n) = \begin{cases} \text{Success} & \text{if all } N_i \text{ succeed} \\ \text{Failure} & \text{if any } N_i \text{ fails} \end{cases}$

Selector 노드

Selector 노드는 자식 노드를 순차적으로 실행하지만, 하나의 노드가 성공하면 즉시 실행을 중단하고 성공으로 간주된다. 모든 자식 노드가 실패하면 이 노드는 실패로 간주된다.

이를 수식으로 표현하면:

$\text{Selector}(N_1, N_2, ..., N_n) = \begin{cases} \text{Success} & \text{if any } N_i \text{ succeeds} \\ \text{Failure} & \text{if all } N_i \text{ fail} \end{cases}$

Parallel 노드

Parallel 노드는 모든 자식 노드를 동시에 실행한다. 성공 또는 실패 조건은 설정된 성공 임계값과 실패 임계값에 따라 달라진다.

$\text{Parallel}(N_1, N_2, ..., N_n) = \begin{cases} \text{Success} & \text{if } k \text{ nodes succeed} \\ \text{Failure} & \text{if } m \text{ nodes fail} \end{cases}$

여기서 $k$ 는 성공 임계값, $m$ 은 실패 임계값이다.

행동 트리의 장점

직관적인 시각적 표현: 행동 트리는 트리 구조로 행동을 쉽게 시각화할 수 있어, 복잡한 행동 계획을 체계적으로 표현할 수 있다.
재사용 가능성: 행동 트리는 모듈화된 구조를 가지기 때문에 각 노드를 재사용하거나, 다른 트리에서 쉽게 통합할 수 있다.

행동 트리의 동작 흐름

행동 트리의 동작은 루트 노드에서 시작하여 자식 노드로 흐름을 전달한다. 노드들은 차례로 실행되며, 각 노드의 성공 또는 실패에 따라 다음 행동이 결정된다. 각 노드의 결과는 트리 전체의 상태를 결정짓는 중요한 요소이다.

graph TD; A[Root] --> B[Sequence] B --> C[Action 1] B --> D[Action 2] A --> E[Selector] E --> F[Condition 1] E --> G[Condition 2]

위의 예시에서는 Sequence 노드가 두 개의 행동(Action 1, Action 2)을 순차적으로 실행하며, Selector 노드는 두 개의 조건(Condition 1, Condition 2)을 평가하여 행동을 선택한다.

행동 트리의 주요 노드 유형

1. Action Node (행동 노드)

Action Node는 로봇이나 에이전트가 수행해야 할 실제 행동을 정의하는 노드이다. 예를 들어, 로봇이 특정 위치로 이동하거나 특정 물체를 집는 행동을 수행할 수 있다. 각 Action Node는 성공(Success) 또는 실패(Failure)로 평가된다.

로봇이 좌표 $\mathbf{p}_\text{goal}$ 에 도달하는 행동을 정의할 때:

$\mathbf{p}_\text{current} = \mathbf{f}(t)$

여기서 $\mathbf{p}_\text{current}$ 는 시간 $t$ 에서의 로봇의 현재 위치, $\mathbf{p}_\text{goal}$ 은 목표 위치이다. Action Node는 다음과 같은 평가를 수행할 수 있다.

$\text{Action Node} = \begin{cases} \text{Success} & \text{if } \|\mathbf{p}_\text{current} - \mathbf{p}_\text{goal}\| \leq \epsilon \\ \text{Failure} & \text{otherwise} \end{cases}$

여기서 $\epsilon$ 은 허용 오차이다.

2. Condition Node (조건 노드)

Condition Node는 특정 조건을 평가하여 자식 노드의 실행 여부를 결정한다. 조건이 참일 경우 자식 노드가 실행되며, 거짓일 경우 해당 노드는 실패로 간주된다. 예를 들어, 로봇의 배터리 잔량이 일정 수준 이상인지 확인하는 조건 노드가 있을 수 있다.

배터리 잔량이 최소 요구치 이상인지 확인하는 조건 노드는 다음과 같이 표현할 수 있다.

$\text{Condition Node} = \begin{cases} \text{Success} & \text{if } \mathbf{b}_\text{current} \geq \mathbf{b}_\text{min} \\ \text{Failure} & \text{otherwise} \end{cases}$

여기서 $\mathbf{b}_\text{current}$ 는 현재 배터리 잔량, $\mathbf{b}_\text{min}$ 은 최소 요구 배터리 잔량이다.

3. Decorator Node (데코레이터 노드)

Decorator Node는 자식 노드의 결과를 변형하거나 특정 조건에 따라 반복 실행할 수 있도록 하는 노드이다. 예를 들어, 자식 노드의 실패를 성공으로 변환하거나, 자식 노드가 특정 횟수만큼 실행되도록 제어할 수 있다.

특정 조건을 만족할 때까지 행동을 반복하는 경우:

$\text{Repeat}(N, k) = \begin{cases} \text{Success} & \text{if } N \text{ succeeds in } k \text{ iterations} \\ \text{Failure} & \text{if } N \text{ fails in } k \text{ iterations} \end{cases}$

여기서 $N$ 은 자식 노드, $k$ 는 반복 횟수이다.

행동 트리의 설계 패턴

Behavior Tree는 다양한 설계 패턴을 적용할 수 있다. 그 중 대표적인 패턴은 Sequence 패턴과 Selector 패턴이다. 이 패턴들은 로봇의 행동을 더욱 체계적으로 관리하는 데 도움이 된다.

1. Sequence 패턴

Sequence 패턴은 여러 행동을 차례로 실행하고, 그 중 하나라도 실패하면 나머지 행동을 실행하지 않는다. 이 패턴은 로봇이 특정 작업을 완료할 때까지 여러 단계의 행동을 순차적으로 수행해야 하는 경우에 적합한다.

예시: 로봇이 물체를 집고 이동하는 작업을 순차적으로 수행해야 하는 경우

$\text{Sequence}(\text{Pick}, \text{Move})$

만약 Pick 동작이 실패하면 Move는 실행되지 않는다.

2. Selector 패턴

Selector 패턴은 여러 행동 중 하나라도 성공하면 나머지 행동을 실행하지 않는다. 이 패턴은 여러 대안 중 하나의 행동만 성공하면 충분한 경우에 적합한다.

예시: 로봇이 경로를 우회할 수 있는 여러 대안을 두고 그 중 하나를 선택하는 경우

$\text{Selector}(\text{Path A}, \text{Path B}, \text{Path C})$

Path A가 성공하면 다른 경로는 평가되지 않는다.

행동 트리의 실행 주기

행동 트리는 각 노드를 일정 주기마다 실행할 수 있다. 이를 통해 로봇의 행동을 실시간으로 업데이트하거나 상황에 맞는 행동을 취할 수 있다. 보통 Behavior Tree는 다음과 같은 방식으로 동작한다.

Tick (틱): 각 행동 트리는 일정 시간마다 "틱"을 받는다. 틱은 트리의 루트에서 시작하여 하위 노드로 전파된다. 각 노드는 틱을 받으면 자신의 상태를 평가하고, 자식 노드로 틱을 전파할지 여부를 결정한다.
노드 상태: 각 노드는 세 가지 상태 중 하나를 반환한다.
Success: 노드의 행동이 성공적으로 완료되었음을 의미한다.
Failure: 노드의 행동이 실패했음을 의미한다.
Running: 노드의 행동이 아직 완료되지 않았음을 나타내며, 더 많은 틱이 필요하다.

틱의 전파 방식

틱은 트리의 루트 노드에서부터 아래로 전파된다. 각 노드는 자신의 상태를 보고한 후 자식 노드로 틱을 전달할지 여부를 결정한다.

graph TD; A[Root] --> B[Sequence] B --> C[Action 1] B --> D[Action 2] B --> E[Action 3]

위의 트리에서는 루트에서 Sequence 노드로 틱이 전파되며, Action 1, Action 2, Action 3이 차례대로 틱을 받는다. Action 1이 실패하면 Action 2와 Action 3은 실행되지 않는다.

상태 전이

노드의 상태는 다음과 같이 전이된다.

Success: 노드가 성공적으로 행동을 완료하면 자식 노드로 틱을 더 이상 전달하지 않는다.
Failure: 노드가 실패하면 부모 노드로 실패 상태가 반환되고, 트리의 상위 구조에서 다른 대안을 실행할 수 있다.
Running: 노드가 실행 중일 때는 틱이 계속 전파되며, 노드가 완료될 때까지 자식 노드로 틱을 전달한다.

상태 전이 수식

각 노드 $N_i$ 의 상태 $S(N_i)$ 는 Success, Failure, Running 중 하나이다. 이 상태 전이는 다음과 같은 수식으로 표현될 수 있다.

$S(N_i) = \begin{cases} \text{Success} & \text{if the action completes successfully} \\ \text{Failure} & \text{if the action fails} \\ \text{Running} & \text{if the action is still running} \end{cases}$

행동 트리의 실시간 응용

Behavior Tree는 실시간 시스템에서 매우 유용하게 사용된다. 각 행동을 유연하게 처리할 수 있고, 상태 변화를 즉각적으로 반영할 수 있기 때문이다. 특히 로봇이 다양한 환경에서 적응적으로 행동해야 할 때, 행동 트리를 활용하여 다양한 상황에 맞는 결정을 내릴 수 있다.

예시: 장애물 회피

로봇이 장애물을 탐지하고 회피하는 예제를 살펴봅시다. 이때, 행동 트리는 다음과 같은 구조로 구성될 수 있다.

graph TD; A[Root] --> B[Sequence] B --> C[Check Obstacle] B --> D[Avoid Obstacle] B --> E[Move Forward]

Check Obstacle 노드가 장애물이 있는지 확인한다.
장애물이 있을 경우 Avoid Obstacle 노드가 실행되어 로봇이 회피 행동을 취한다.
장애물이 없을 경우 Move Forward 노드가 실행되어 로봇이 계속 전진한다.

QoS(품질 서비스)와 행동 트리의 연동

ROS2의 QoS(품질 서비스) 정책은 행동 트리에서 각 노드의 행동이 네트워크 상에서 안정적으로 수행될 수 있도록 보장한다. 예를 들어, 메시지가 손실되지 않도록 QoS 설정을 통해 안정성을 높일 수 있다.

QoS 정책을 행동 트리와 연동할 때 중요한 요소는 다음과 같다.

신뢰성: 메시지가 중요한 경우, 신뢰성 있는 전송을 보장하는 정책을 사용해야 한다.
내구성: 로봇이 잠시 네트워크에서 분리되더라도 메시지가 손실되지 않도록 내구성 있는 QoS 설정을 해야 한다.

graph TD; A[Root] --> B[QoS 설정] B --> C[Reliable] B --> D[Best-effort] A --> E[행동 트리 실행]

위 트리에서 QoS 설정 노드는 Reliable 또는 Best-effort로 메시지 전송 방식을 설정하고, 이후 행동 트리의 노드들이 실행된다.