And Brain said,
Behavior Tree, 뿌리에서 잎까지. 피어나는 판단의 미학 - Beyond Behavior 본문
Behavior Tree, 뿌리에서 잎까지. - 피어나는 판단의 미학
개요
설계 원칙과 분석
Beyond Behavior
본론
Behavior Tree(BT)는 독특한 자신만의 구조를 통해 명료함과 확장성을 품고, 판단의 미학을 피워내는 구조입니다. 루트에서 잎으로 이어지는 가지는 행동의 흐름을 형성하며, 각각의 노드는 독립적이지만 조화롭게 움직입니다.
Behavior Tree의 기본 구조
BT는 크게 루트(Root), 브랜치(Branch), 리프(Leaf)라는 세 가지 주요 구성 요소로 나뉘며, 추가적으로 데이터 허브 역할을 할 BlackBoard로 구성됩니다.
루트 노드는 트리의 최상단에 위치하며, 트리 실행의 시작점입니다. 하나의 트리는 언제나 하나의 루트 노드를 가져야하며, 그 역할은 트리를 탐색하고 실행 결과를 반환하는 역할을 합니다.
브랜치 노드는 중간 계층의 역할을 하며, 하위 노드(Branch 또는 Leaf)의 실행을 관리합니다. 브랜치 노드는 컨트롤러(Controller) 혹은 컨트롤 플로우 노드(Control Flow, 혹은 Control)라고도 불리며, 다양한 조건과 논리를 기반으로 트리의 탐색 순서를 제어합니다.
리프 노드는 BT의 가장 하단에 위치하며, 실제로 작업을 수행하거나 상태를 확인하는 구체적인 동작을 정의합니다. 리프는 행동(Action)과 조건(Condition)으로 나뉩니다.
BlackBoard는 데이터 공유와 관리의 중심 역할을 수행합니다.
Tick
상세한 구조적 설명을 드리기에 앞서, Behavior Tree의 핵심 메커니즘인 tick()에 대해서 살펴보겠습니다. tick()은 Behavior Tree의 실행 단위로, 트리의 각 노드가 작업을 수행하도록 주기적으로 호출됩니다. 그 실행의 흐름은 루트에서 시작하여 하위 노드로 전달됩니다.
여기서 tick()의 역할은 아래와 같이 크게 세가지로 분류할 수 있습니다.
- 노드 실행: 현재 노드를 실행하고 상태를 반환합니다.
- 상태 관리: 각 노드의 실행 상태(SUCCESS, FAILURE, RUNNING, IDLE)를 업데이트합니다.
- 트리 순회: 루트 노드부터 자식 노드를 순차적으로 호출합니다.
Behavior Tree(BT)
- Root Node
모든 것의 시작점이자 단 하나밖에 존재하지 않는 루트 노드에서는 모든 자식 노드에게 tick()을 전달합니다.
class RootNode : public BT::ControlNode {
public:
BT::NodeStatus tick() override {
// 트리의 첫 번째 자식을 실행
return children_nodes_[0]->executeTick();
}
};
- Branch // Control Node
Branch 혹은 Control 노드라고도 불리는 이 노드들은 자식 노드의 실행을 관리합니다. 주요 유형에는 Sequence, Selector(혹은 Fallback), Parallel이 있습니다.
1. Sequence
Sequence 노드는 자식 노드를 순서대로 실행하며, 모든 자식이 성공해야 SUCCESS 반환합니다. 하나의 자식이라도 실패하면 즉시 FAILURE를 반환합니다.
class SequenceNode : public BT::ControlNode {
public:
BT::NodeStatus tick() override {
for (auto &child : children_nodes_) {
BT::NodeStatus status = child->executeTick();
if (status == BT::NodeStatus::FAILURE) return BT::NodeStatus::FAILURE;
if (status == BT::NodeStatus::RUNNING) return BT::NodeStatus::RUNNING;
}
return BT::NodeStatus::SUCCESS;
}
};
2. Selector(Fallback)
Selector 혹은 Fallback 노드는 자식 노드를 순서대로 실행하며, 하나라도 성공하면 SUCCESS 반환합니다. 모든 자식이 실패할 경우에만 FAILURE를 반환합니다.
class SelectorNode : public BT::ControlNode {
public:
BT::NodeStatus tick() override {
for (auto &child : children_nodes_) {
BT::NodeStatus status = child->executeTick();
if (status == BT::NodeStatus::SUCCESS) return BT::NodeStatus::SUCCESS;
if (status == BT::NodeStatus::RUNNING) return BT::NodeStatus::RUNNING;
}
return BT::NodeStatus::FAILURE;
}
};
3. Parallel
Parallel 노드는 자식 노드를 동시에 실행하여, 성공/실패 조건에 따라 상태 반환합니다.
class ParallelNode : public BT::ControlNode {
public:
ParallelNode(const std::string &name, size_t success_threshold, size_t failure_threshold)
: BT::ControlNode(name, {}),
success_threshold_(success_threshold),
failure_threshold_(failure_threshold) {}
BT::NodeStatus tick() override {
size_t success_count = 0;
size_t failure_count = 0;
for (auto &child : children_nodes_) {
// 자식 노드를 실행하고 상태 확인
BT::NodeStatus status = child->executeTick();
if (status == BT::NodeStatus::SUCCESS) {
success_count++;
} else if (status == BT::NodeStatus::FAILURE) {
failure_count++;
}
}
// 성공 기준 충족
if (success_count >= success_threshold_) {
return BT::NodeStatus::SUCCESS;
}
// 실패 기준 충족
if (failure_count >= failure_threshold_) {
return BT::NodeStatus::FAILURE;
}
// 아직 실행 중인 경우
return BT::NodeStatus::RUNNING;
}
private:
size_t success_threshold_;
size_t failure_threshold_;
};
success_threshold와 failure_threshold를 기준으로 상태를 평가합니다.
동시에 실행한다고는 했지만, 간단히 보여주기위해 순차 실행으로 보여드리는 점 양해바랍니다. 비동기와 멀티스레딩을 적절히 활용한다면 진정한 병렬처리를 구현하실 수 있습니다.
4. 추가적인 Reactive Node
BT는 그 자체로 이미 Reactive한 구조이지만, 내부적으로 순차 실행되고 상태를 기다리는 교착 상태에 빠질 수 있습니다. 이를 위해 더욱더 반응성을 향상시킨 구조로 짜기도 합니다. 이 글에서는 ReactiveSequence와 ReactiveFallback을 halt() 메소드와 함께 간단히 소개하겠습니다.
**halt()**
halt()는 노드의 실행을 중지하거나 초기 상태로 되돌리는 데 사용되는 중요한 메서드입니다. BT에서 실행 중(Running)인 자식 노드를 강제로 중지하거나, 트리가 중단되거나 다른 경로로 전환할 때 노드 상태를 정리합니다. 또한, Running 상태의 노드를 IDLE 상태로 되돌리거나, 실행 중이던 작업을 중단하여 재실행 가능하도록 만듭니다. 마지막으로 이 halt() 메소드는 자식 노드에 전파되므로 트리의 상태를 일관되게 유지되는것을 가능하게 합니다.
ReactiveSequence & ReactiveFallback
ReactiveSequence와 ReactiveFallback은 기존 Sequence와 Fallback을 더욱더 Reactive하게 사용하기 위한 노드입니다. 실시간으로 특정 조건을 평가하여 그 조건의 변화에 따라 자식 노드들의 상태관리를 하며 순서대로 실행시킵니다.
#include "behaviortree_cpp_v3/control_node.h"
class ReactiveSequence : public BT::ControlNode {
public:
ReactiveSequence(const std::string &name) : BT::ControlNode(name, {}) {}
BT::NodeStatus tick() override {
for (size_t i = 0; i < children_nodes_.size(); ++i) {
// 실행 중인 자식 노드 중단 및 초기화
if (children_nodes_[i]->status() == BT::NodeStatus::RUNNING) {
children_nodes_[i]->halt();
}
// 자식 노드 실행
BT::NodeStatus status = children_nodes_[i]->executeTick();
if (status == BT::NodeStatus::FAILURE) {
// 실패한 이후의 노드들을 중단
haltChildrenAfter(i);
return BT::NodeStatus::FAILURE;
}
if (status == BT::NodeStatus::RUNNING) {
return BT::NodeStatus::RUNNING; // 실행 중
}
}
return BT::NodeStatus::SUCCESS; // 모든 자식이 성공
}
void halt() override {
haltChildrenAfter(0); // 모든 자식 노드를 중단
setStatus(BT::NodeStatus::IDLE); // 노드 상태를 초기화
}
private:
// 특정 인덱스 이후의 모든 자식 노드를 중단
void haltChildrenAfter(size_t start_index) {
for (size_t i = start_index; i < children_nodes_.size(); ++i) {
if (children_nodes_[i]->status() == BT::NodeStatus::RUNNING) {
children_nodes_[i]->halt();
}
}
}
};
#include "behaviortree_cpp_v3/control_node.h"
class ReactiveFallback : public BT::ControlNode {
public:
ReactiveFallback(const std::string &name) : BT::ControlNode(name, {}) {}
BT::NodeStatus tick() override {
for (size_t i = 0; i < children_nodes_.size(); ++i) {
// 실행 중인 자식 노드를 중단 및 초기화
if (children_nodes_[i]->status() == BT::NodeStatus::RUNNING) {
children_nodes_[i]->halt();
}
// 자식 노드 실행
BT::NodeStatus status = children_nodes_[i]->executeTick();
if (status == BT::NodeStatus::SUCCESS) {
// 성공 후 나머지 노드를 초기화
haltChildrenAfter(i + 1);
return BT::NodeStatus::SUCCESS;
}
if (status == BT::NodeStatus::RUNNING) {
return BT::NodeStatus::RUNNING; // 실행 중
}
}
return BT::NodeStatus::FAILURE; // 모든 자식이 실패
}
void halt() override {
haltChildrenAfter(0); // 모든 자식 노드를 중단
setStatus(BT::NodeStatus::IDLE); // 상태 초기화
}
private:
// 특정 인덱스 이후의 모든 자식 노드를 중단
void haltChildrenAfter(size_t start_index) {
for (size_t i = start_index; i < children_nodes_.size(); ++i) {
if (children_nodes_[i]->status() == BT::NodeStatus::RUNNING) {
children_nodes_[i]->halt();
}
}
}
};
이제 자식 노드에서도 halt() 메소드를 구현하고 특정 조건에 따라 BT의 status를 IDLE로 바꾸도록 만들면 됩니다.
Leaf Node
Leaf Node는 Behavior Tree의 가장 하단에 위치하며, 실제 작업을 수행하거나 조건을 평가합니다. Leaf Node는 크게 두 가지로 나뉘는데, 특정 작업을 수행하는 Action Node와 특정 조건을 평가하는 Condition Node로 나뉩니다.
1. Action Node
Action Node는 트리에서 가장 많이 사용하는 노드 중 하나로, 어떠한 특정 작업을 수행하고 그 결과를 반환합니다.
#include "behaviortree_cpp_v3/leaf_node.h"
#include <iostream>
#include <thread>
class Action : public BT::LeafNode {
public:
Action(const std::string &name) : BT::LeafNode(name), is_running_(false) {}
BT::NodeStatus tick() override {
if (!is_running_) {
is_running_ = true;
std::cout << "[" << name() << "] Starting action..." << std::endl;
}
// 작업 완료 여부 확인
if (isTaskComplete()) {
is_running_ = false;
std::cout << "[" << name() << "] Action completed successfully." << std::endl;
return BT::NodeStatus::SUCCESS;
}
std::cout << "[" << name() << "] Action in progress..." << std::endl;
return BT::NodeStatus::RUNNING;
}
void halt() override {
if (is_running_) {
std::cout << "[" << name() << "] Action halted." << std::endl;
is_running_ = false;
}
setStatus(BT::NodeStatus::IDLE); // 상태 초기화
}
private:
bool is_running_;
// 작업 완료 조건 (여기서는 간단히 5번 tick 이후 성공)
bool isTaskComplete() {
static int counter = 0;
return ++counter >= 5;
}
};
2. Condition Node
Condition 노드는 특정 상황이나 조건을 평가하며, 조건의 만족 여부에 따라 SUCCESS 또는 FAILURE를 반환합니다.
#include "behaviortree_cpp_v3/leaf_node.h"
#include <iostream>
class CheckCondition : public BT::LeafNode {
public:
CheckCondition(const std::string &name) : BT::LeafNode(name) {}
BT::NodeStatus tick() override {
if (isConditionMet()) {
std::cout << "[" << name() << "] Condition met." << std::endl;
return BT::NodeStatus::SUCCESS; // 조건 만족
} else {
std::cout << "[" << name() << "] Condition not met." << std::endl;
return BT::NodeStatus::FAILURE; // 조건 불만족
}
}
void halt() override {
std::cout << "[" << name() << "] Condition node halted." << std::endl;
setStatus(BT::NodeStatus::IDLE); // 상태 초기화
}
private:
// 조건 평가 로직 (임의로 성공 여부를 무작위로 설정)
bool isConditionMet() {
return rand() % 2 == 0; // 무작위로 조건 반환
}
};
- Decorator Node
추가적으로 Decorator Node는 기존 노드들의 확장으로 특정 조건이나 행동을 기준으로 자식 노드의 실행을 제어합니다. Decorator Node는 자식 노드를 감싸는 형태로, 조건을 추가하거나 동작을 수정하는 데 사용됩니다. 여기서는 간단하게만 소개하고 넘어가겠습니다.
Decorator Node의 다양한 역할
- 조건 추가 Decorator
- 특정 조건이 만족될 때만 자식 노드를 실행.
- 실행 횟수 제한 Decorator
- 자식 노드의 실행 횟수를 제한하거나, 반복적으로 실행.
- 시간 제한 Decorator
- 일정 시간이 지나면 자식 노드 실행 중단.
- BlackBoard
BlackBoard는 Behavior Tree에서 데이터 공유 및 상태 관리를 위한 데이터 허브입니다.
#include "behaviortree_cpp_v3/blackboard.h"
#include <iostream>
#include <string>
int main() {
// BlackBoard 생성
auto blackboard = BT::Blackboard::create();
// 데이터를 저장
blackboard->set<int>("robot_speed", 5);
blackboard->set<std::string>("current_task", "Explore");
blackboard->set<bool>("obstacle_detected", false);
// 데이터를 읽기
int speed = blackboard->get<int>("robot_speed");
std::string task = blackboard->get<std::string>("current_task");
bool obstacle = blackboard->get<bool>("obstacle_detected");
std::cout << "Robot Speed: " << speed << std::endl;
std::cout << "Current Task: " << task << std::endl;
std::cout << "Obstacle Detected: " << (obstacle ? "Yes" : "No") << std::endl;
return 0;
}
Beyond Behavior
Behavior Tree는 명료하면서도 확장 가능한 설계로, 의사결정 프로세스를 구현하는 데 있어 우아한 접근 방식을 제공합니다. 루트(Root), 브랜치(Branch), 리프(Leaf)로 이루어진 구조에서부터 Reactive Node의 동적 적응성, 그리고 BlackBoard의 데이터 공유 기능에 이르기까지, Behavior Tree는 단순함과 확장성을 조화롭게 담아냅니다.
이러한 구조의 유연성은 로봇 제어, 게임 AI, 자동화 시스템 등 다양한 분야에서 두각을 나타내며, 실시간으로 변화하는 조건 속에서도 명확한 행동 흐름과 적응력을 제공합니다.
우리가 살펴본 구조와 아이디어를 활용해, 여러분만의 Behavior Tree를 설계해 보시길 바랍니다. 로봇의 내비게이션을 최적화하든, 복잡한 게임 캐릭터를 만들든, 시스템을 자동화하든, Behavior Tree의 아름다움은 여러분의 필요에 따라 끊임없이 확장될 것입니다.
자, 이제 여러분의 트리를 만들어 보세요!
Thanks for watching, Have a nice day.
'AI' 카테고리의 다른 글
| Behavior Tree, 뿌리에서 잎까지. 피어나는 판단의 미학 - 설계 원칙과 분석 (0) | 2024.12.10 |
|---|---|
| Behavior Tree, 뿌리에서 잎까지. 피어나는 판단의 미학 - 개요 (0) | 2024.12.10 |
