[FSM vs Behavior Tree] Part.3 - Behavior Tree 의 개념

Behavior Tree 의 개념

 

행동 트리

 

행동트리는 FSM 에서처럼 상태들끼리 의존하는 문제를 해소할 수 있습니다. Tree 구조에서 알 수 있듯, 상태 개념없이 특정 행동에 대한 노드단위 개념을 사용합니다. 이 구조를 쓰는 핵심 목적은 루트노드로부터 DFS (깊이탐색)을 하여 실행 가능한 행동을 찾고, 최종적으로 찾은 행동에 대해 동작(Action)을 수행하기 위함입니다. 

매번 DFS 를 수행해야하기 때문에, 성능면에서는 실행시간도 FSM 보다 길고, 노드단위 탐색이다 보니 캐시 미스가 잦아서 좋지 않습니다. 

 

노드의 종류는 크게 다음 세가지가 있습니다.

 

Root : 최상단 노드

Control flow : 하위 트리의 반환 종류에 따라 DFS의 흐름을 제어하기위한 노드

Execution : 최하위 노드(Leaf).  Action을 수행하기위한 노드. 

 

각 노드는 DFS 시 탐색 결과를 부모 노드로 반환합니다. 

반환 종류는 다음 세가지가 있습니다.

Success : Execution 노드의 Action 성공.

Failure : Execution 노드의 Action 실패.

Running : Execution 노드의 Action 실행 중, 반환 시 다음 Tick 에서 Execution 노드 액션 계속 실행.

(* Tick : Behavior Tree 의 탐색 단위)

 

 

그리고 특정 노드의 하위 트리를 Branch 라고 합니다.

다음 기본 컨셉에서 깊이 1 의 Controlflow 의 Branch 는 Execution, Control flow - Execution, Execution 세가지가 있고 각각이 탐색 순위 대상입니다.

Behavior tree 의 기본 컨셉

 

위 기본컨셉에서, Control flow 노드는 흐름 분기를 위해 다양한 종류의 노드들이 존재합니다.

우선 간단하게 Selector, Sequence 두가지로 예를 들자면 

 

Selector : 자식 노드들 중에서 단 하나가 성공할때 까지 탐색하기위한 노드.

 

자식노드들에 대해 DFS 를 차례대로 수행합니다.

DFS 탐색시 Execution(Leaf) 노드까지 도달했을 때 해당 노드가 -

 1. Success 반환시 : 탐색을 종료하고 Selector 노드가 Success 를 반환

 2. Failure 반환시 : 다음 우선순위 자식노드 탐색 시작

 3. Running 반환시 : 탐색을 종료하고 Selector 노드가 Running 을 반환

 

Sequence : 모든 자식 노드들을 연속적으로 탐색하기 위한 노드. 

 

자식노드들에 대해 DFS 를 차례대로 수행합니다. 

DFS 탐색시 Execution(Leaf) 노드까지 도달했을 때 해당 노드가 -

 1. Success 반환시 : 다음 우선순위 자식노드 탐색 시작

 2. Failure 반환시 : 탐색을 종료하고 Sequence 노드가 Failure 를 반환

 3. Running 반환시 : 탐색을 종료하고 Sequence 노드가 Running 을 반환

 

 

그래서 다음 예시를 보면, 

처음에 Selector 노드이므로 아래 세가지 Branch 들을 우선순위에 따라 탐색하면서 가장 먼저 Success 가 반환 되었을 때 탐색을 종료하고 Success 를 반환 할 것입니다.

(예시에서 우선순위는 왼쪽에서 오른쪽으로 진행됩니다.)

 

1. ② 에서 Execution 노드 실행에 실패했으므로 그다음 Branch 의 시작노드인 Sequence 노드를 탐색합니다.

Sequence 노드는 자식 노드들을 우선순위에 따라 모두 탐색하려 할것입니다. 

 

2. ④ 에서 Sequence의 자식노드가 Success 를 반환했지만 ⑤ 에서 자식노드가 Failure 을 반환했으므로, 해당 시퀀스는 실패한 것이고 Sequence는 Failure 를 Selector 에게 반환합니다.

 

3. Selector 는 Failure 반환을 받아 다음 Branch 인 Execution 노드를 탐색합니다. 

 

4. Execution 노드에서 Success 가 반환되었으므로 Selector 는 탐색을 종료하고 Root 노드에 Success 를 반환하고 Root 노드가 Success 를 그대로 반환하면서 이 트리의 탐색이 종료되었습니다.

Behavior Tree 탐색 예시

Behavior Tree 는 실행가능한 Action을 찾아서 수행하기에 적합한 구조이고 , 그래서 AI 구현에 주로 사용됩니다. 

위에서는 단순한 예시를 위해 우선순위가 무조건 왼쪽에서 오른쪽이지만 ,

무작위 우선순위 선정이나 우선순위에 대한 특별한 알고리즘을 적용할 수 있고, 때로는 우선순위 상관없이 병렬로 탐색을 하는 등의 복합 노드를 구성할 수 있으며, Composite 패턴으로 복합 노드 동작을 하나의 노드로 취급할 수 있게 한다고 해서 이런 타입의 노드들을 Composite 노드라고 합니다. 쉽게 말하자면 자식노드를 하나이상 가질 수 있는 행동노드입니다.  위 예시에서 Selector 는 세개의 자식, Sequece는 두개의 자식을 각각 가지고있는것 처럼요. 모두 Composite 라는 행동노드를 추상화 해두고 상속받아서 Tick() 마다 호출할 함수만 다르게 구현해 놓았을 뿐입니다.

 

자식노드를 탐색하기위한 조건이 필요할 때에는 if문 같은 개념을 적용할 수 있는데, 이런 노드들을 Condition 노드 라고합니다. 

 

경우에 따라 자식 행동노드의 반환값에 부가적인 처리를 해 줄 수도 있는데, 이것들을 명령을 꾸며준다고 해서 Decorator 노드 라고 합니다. Decorator 노드는 Execution 의 반환을 받았을때 특정 조건에 따라 Execution의 반환값은 보류하고 Running 을 반환하여 반복문처럼 Action 을 반복 할 수 있게 하는 기능, 반환값을 반전시키는 기능, 반환값을 강제하는 (Execution 결과 무시하고 Failure / Success / Running 반환) 기능 등 원래의 트리구조에 덧붙인 기능들을 수행하는 노드 종류입니다.