Behavior Tree, 뿌리에서 잎까지. 피어나는 판단의 미학 - 개요

Behavior Tree, 뿌리에서 잎까지. - 피어나는 판단의 미학

개요
설계 원칙과 분석

1. Behavior Tree ?

Behavior Tree(BT)는 자율 에이전트(로봇, 게임 캐릭터 등)의 행동을 효율적이고 체계적으로 제어하기 위한 구조로, BT는 복잡한 작업을 단순한 빌딩 블록으로 나누어 모듈화하고, 환경 변화에 유연하게 대응할 수 있도록 설계되었습니다.

 

왜 Behavior Tree가 필요한가?

BT가 처음 등장한 것은 게임업계였습니다. 기존에 게임 업계는 오랜 시간 게임 AI와 NPC행동 제어에 FSM(Finite State Machines) 방식을 사용했고 이 방식은 다음과 같은 한계가 있었는데,

1. 복잡성 증가와 유지보수의 어려움

먼저 게임이 복잡해질수록 FSM의 상태(State)와 전이(Transition) 수도 기하급수적으로 증가했고, 새로운 상태를 추가할 때 기존 전이 조건을 모두 다시 점검해야 하므로 시간이 많이 소요됐으며, 한 상태에서 다른 상태로 전환할 때 단방향 제어 방식을 사용하므로 오류가 발생하기 쉬웠습니다.

 

ex) 캐릭터가 걷기, 뛰기, 공격, 방어, 죽음 등 다양한 상태를 가질 때, 상태 간 전이 규칙이 많아짐

 

2. 반응성(Reactiveness) 부족

FSM은 동적이고 실시간으로 변화하는 게임 환경에 대응하기 어려웠고, 예상치 못한 이벤트나 상태를 처리하는 데 상태 전이 규칙이 고정적이기 때문에 예외 상황에서 비효율적이었습니다.

ex) 플레이어가 예상치 못한 행동을 했을 때, FSM은 모든 상태 전이를 하나하나 검사해야 하므로 응답이 느려질 수 있음

 

3. 모듈화(Modularity) 부족

FSM은 상태와 전이가 밀접하게 연결되어 있어 코드 재사용이 어려웠습니다. 다른 캐릭터나 새로운 게임 환경에서 기존 FSM을 그대로 사용할 수 없고, 모든 상태와 전이를 새로 정의해야 했습니다.

 

 

2. Behavior Tree의 구성 요소

1. 제어 흐름 노드 (Control Flow Node)

부모 역할을 하며, 실행 순서를 제어

• Sequence (→): 왼쪽에서 오른쪽으로 자식 노드를 순회하며, 하나라도 실패하면 중단.
• Fallback (?): 왼쪽에서 오른쪽으로 자식 노드를 순회하며, 하나라도 성공하면 중단.
• Parallel (⇒): 모든 자식에게 동시에 명령을 전달하며, 성공 임계치(M)에 따라 결과를 결정.
• Decorator (♦): 자식 노드의 결과를 수정하거나 추가 조건을 적용.

 

2. 실행 노드 (Execution Node)

실제 작업이나 조건 평가를 담당

• Action: 명령을 수행하고 성공, 실패, 실행 중 상태를 반환.
• Condition: 조건을 평가하여 성공 또는 실패 상태를 반환.

 

3. Behavior Tree의 작동 방식

BT는 루트 노드에서 시작해 Tick이라는 신호를 자식 노드로 전달하며 동작

 

• Tick의 역할: 특정 주기마다 실행을 제어하고 상태를 업데이트.
• 상태 반환: Success, Failure, Running

 

자 그럼, 자율 로봇이 물체를 탐지하고, 해당 물체를 잡은 뒤, 장애물을 회피하여 목표 지점으로 이동하는 작업을 수행한다고 가정해보겠습니다.

 

작업 과정은 아래와 같을 것입니다.

1. 로봇은 물체를 탐지하고, 물체가 발견되지 않으면 계속 탐색합니다.
2. 물체를 탐지한 경우, 집는 동작을 수행합니다.
3. 물체를 집은 후, 장애물을 감지하고 회피합니다.
4. 모든 작업이 완료되면 목표 지점으로 이동합니다.

 

이 작업을 구현하기 위해 Behavior Tree를 생각해봅시다.

• ConditionNode (조건 노드)
  조건: 물체가 탐지되었는지 확인.
  
  작업: 로봇의 카메라 또는 센서를 통해 물체를 감지.
  ConditionNode("Object Detected?", isObjectDetected)는 카메라 데이터를 확인하여 true 또는 false를 반환.
  
  
  
• ActionNode (동작 노드)
  탐색(Search):
  작업: 로봇이 카메라와 라이다(LiDAR)를 사용해 주변 환경을 스캔.
  
  물체 집기(Grab):
  작업: 로봇 팔을 제어하여 물체를 잡음.
  
  장애물 회피(Avoid):
  작업: 로봇이 라이다 데이터를 분석하여 장애물을 우회.
  
  
  
• SequenceNode (순차 노드)
  작업 흐름:
  
  • 물체를 탐지.
  • 물체가 발견되면 집기.
  • 장애물을 감지하고 회피.

 

• FallbackNode (대체 노드)
  작업 흐름:
  
  • 물체가 발견되지 않았을 경우 탐색 작업을 수행.
  • 물체가 발견되면 탐색을 중단하고 다음 단계로 진행.

이를 간단하게 코드로 구현한다면 아래와 같은 느낌일 것입니다.

#include <iostream>
#include <vector>
#include <string>
#include <functional>

// Node 상태 정의
enum class NodeStatus {
    SUCCESS,
    FAILURE,
    RUNNING
};

// 추상 노드 클래스
class Node {
public:
    virtual ~Node() = default;
    virtual NodeStatus tick() = 0; // 모든 노드는 tick 메서드를 가져야 함
};

// Action 노드 클래스
class ActionNode : public Node {
private:
    std::string name;
    std::function<NodeStatus()> action;

public:
    ActionNode(const std::string& name, std::function<NodeStatus()> action)
        : name(name), action(action) {}

    NodeStatus tick() override {
        std::cout << "[Action: " << name << "] ";
        return action();
    }
};

// Condition 노드 클래스
class ConditionNode : public Node {
private:
    std::string name;
    std::function<bool()> condition;

public:
    ConditionNode(const std::string& name, std::function<bool()> condition)
        : name(name), condition(condition) {}

    NodeStatus tick() override {
        std::cout << "[Condition: " << name << "] ";
        return condition() ? NodeStatus::SUCCESS : NodeStatus::FAILURE;
    }
};

// Sequence 노드 클래스
class SequenceNode : public Node {
private:
    std::vector<Node*> children;
    size_t currentChild = 0;

public:
    void addChild(Node* child) {
        children.push_back(child);
    }

    NodeStatus tick() override {
        while (currentChild < children.size()) {
            NodeStatus status = children[currentChild]->tick();
            if (status == NodeStatus::RUNNING) {
                return NodeStatus::RUNNING;
            } else if (status == NodeStatus::FAILURE) {
                std::cout << "[Sequence] Failure at child " << currentChild << "\n";
                currentChild = 0; // Reset for future execution
                return NodeStatus::FAILURE;
            }
            currentChild++;
        }
        std::cout << "[Sequence] All children succeeded.\n";
        currentChild = 0; // Reset for future execution
        return NodeStatus::SUCCESS;
    }
};

// Fallback 노드 클래스
class FallbackNode : public Node {
private:
    std::vector<Node*> children;

public:
    void addChild(Node* child) {
        children.push_back(child);
    }

    NodeStatus tick() override {
        for (Node* child : children) {
            NodeStatus status = child->tick();
            if (status == NodeStatus::SUCCESS) {
                std::cout << "[Fallback] Success from child.\n";
                return NodeStatus::SUCCESS;
            } else if (status == NodeStatus::RUNNING) {
                return NodeStatus::RUNNING;
            }
        }
        std::cout << "[Fallback] All children failed.\n";
        return NodeStatus::FAILURE;
    }
};

// 메인 함수
int main() {
    // 상태 변수 정의
    bool objectDetected = false;

    // 동작 정의
    auto searchForObject = []() {
        std::cout << "Searching for object...\n";
        return NodeStatus::RUNNING;
    };

    auto grabObject = []() {
        std::cout << "Grabbing object...\n";
        return NodeStatus::SUCCESS;
    };

    auto isObjectDetected = [&objectDetected]() {
        return objectDetected;
    };

    auto avoidObstacle = []() {
        std::cout << "Avoiding obstacle...\n";
        return NodeStatus::SUCCESS;
    };

    auto moveToTarget = []() {
        std::cout << "Moving to target location...\n";
        return NodeStatus::SUCCESS;
    };

    // BT 구성
    SequenceNode root;
    FallbackNode searchAndRetrieve;
    ActionNode moveToTargetAction("Move to Target Location", moveToTarget);
    ConditionNode objectCheck("Object Detected?", isObjectDetected);
    ActionNode searchAction("Search for Object", searchForObject);
    ActionNode grabAction("Grab Object", grabObject);
    ActionNode avoidObstacleAction("Avoid Obstacle", avoidObstacle);

    // 트리 구조 생성
    searchAndRetrieve.addChild(&objectCheck);
    searchAndRetrieve.addChild(&searchAction);
    root.addChild(&searchAndRetrieve);
    root.addChild(&grabAction);
    root.addChild(&avoidObstacleAction);
    root.addChild(&moveToTargetAction);

    // 트리 실행
    std::cout << "=== Behavior Tree Start ===\n";
    while (root.tick() == NodeStatus::RUNNING) {
        std::cout << "---- Tick ----\n";
        objectDetected = true; // 시뮬레이션: 물체를 발견했다고 가정
    }
    std::cout << "=== Behavior Tree Complete ===\n";

    return 0;
}

 

 

이 BT 구조는 아래와 같습니다.

Root (Sequence)
  ├── Fallback (SearchAndRetrieve)
  │     ├── Condition (ObjectCheck): "Object Detected?"
  │     └── Action (SearchAction): "Search for Object"
  ├── Action (GrabAction): "Grab Object"
  ├── Action (AvoidObstacleAction): "Avoid Obstacle"
  └── Action (MoveToTargetAction): "Move to Target Location"

 

 

Behavior Tree의 활용 사례는 무궁무진합니다. 이 단순하지만 강력한 제어 구조는, 복잡한 시스템의 행동을 설계하고 관리하기 위한 탁월한 설계입니다.

 

다음 장에서는 Behavior Tree 설계 원칙에 대해 다루어보겠습니다.