2728 字
14 分钟
行为树BehaviourTree

环境配置#

基本概念#

概述#

行为树(Behavior Tree, BT)是一种用于构建自主代理(例如机器人或电脑游戏中非玩家控制的角色)决策过程的形式化图形建模语言。与有限状态机不同,行为树是控制“任务”执行流程的分层节点树

它的主要特点和用途包括:

  • 图形化建模:行为树使用图形符号来表示不同的任务和决策流程,使得复杂的逻辑易于理解和维护。
  • 分层结构:行为树采用分层设计,可以将复杂的决策过程分解成多个层级,每个层级处理特定的任务或决策。
  • 灵活性和可扩展性:通过组合不同的节点,可以轻松地修改或扩展行为树,以适应新的需求或环境变化。
  • 广泛的应用领域:最初应用于视频游戏中的NPC控制,现在也被广泛应用于机器人技术、自动化系统等领域。

基本组成#

下图展现了一个基本的行为树结构:

行为树由节点(Node)构成,节点主要有两种类型:控制结点(Control node)和执行节点(Execution node)。其中,控制节点又分为四种,分别为顺序节点(Sequence),选择节点(Fallback or Selector),并行节点(Parallel)和装饰节点(Decorator);执行节点分为两种,分别为条件节点(Condition)和动作节点(Action)。

控制节点#

控制节点(Control node)是行为树的内部结点,它们定义了遍历其子结点的方式。控制结点的子节点可以是执行结点,也可以是控制结点。顺序(Sequence),选择(Fallback),并行(Parallel)这3种类型的控制结点可以有任意数量的子结点(1-N),而装饰(Decorator)结点只能有一个子结点,表示对子结点的行为进行修饰。

  • 顺序节点(Sequence):按照顺序依次执行其子结点,直到某个子结点返回失败或成功,或者所有子结点都返回成功。
  • 选择节点(Fallback or Selector):按照顺序依次执行其子结点,直到某个子结点返回成功,或者所有子结点都返回失败。
  • 并行节点(Parallel):并行节点将“并行”执行其所有子节点。 之所以打上引号,是因为这不是真正的并行;在每次每个子节点都会按顺序单独进行。 当至少有M个子节点(在1到N之间)执行成功时,并行节点会返回成功;当所有子节点都执行失败时,并行节点会返回失败。
  • 修饰节点(Decorator):装饰节点用自定义策略修改单个子节点。 装饰器有自己的一套规则来改变“被装饰节点”的状态。 例如,“反转 “装饰器会将 “成功 “改为 “失败”,反之亦然。常见的修饰有:反转(Invert),重复(Repeat/Retry)等。

执行节点#

执行节点(execution node):行为树的叶子节点,可以是动作节点(Action)或条件节点(Condition)。

  • 动作节点(Action:执行一个动作,例如,向一个目标移动、攻击、使用物品等。
  • 条件节点(Condition):检查一个条件,例如,玩家是否在攻击范围内、是否已到达目标位置等。
节点类型子节点数量描述
顺序节点(Sequence)1-N按照顺序依次执行其子结点,全部成功或者遇到失败
选择节点(Fallback)1-N按照顺序依次执行其子结点,全部失败或者遇到成功
并行节点(Parallel)1-N并行执行其所有子节点,至少M个成功,或者执行失败
修饰节点(Decorator)1修饰单个子节点
动作节点(Action)0执行一个动作
条件节点(Condition)0检查一个条件

执行流程#

行为树按照设定的频率(一般为100-200HZ)离散地更新步骤,信号(这里称之为”tick”)在树的根节点开始被执行,然后它通过分支进行传播直到它到达一个或者多个叶子。这里的tick意味着去唤醒一个树节点的回调函数tick()。当节点被tick后,会向其父节点返回状态,如下所示:

  • 成功(Success):节点执行成功;
  • 失败(Failure):节点执行失败;
  • 运行中(Running):节点正在执行。
注意

条件节点(Condition)只能返回成功或失败,不能返回运行中。

示例#

假设现在有一个机器人需要去搜索一个物品。

若物品只在一个区域A存在,则我们可以使用一个简单的顺序节点(Sequence)来控制机器人的搜索过程,结构如下:

如上图,我们用动作节点(Action)执行到A区域的行为,然后通过条件节点判断是否找到物品。
在前往A区域时,动作节点返回运行中(Running);当到达A区域时,返回成功(Success);否则返回失败(Failure),整个顺序节点结束。
当到达A区域时,条件节点检查物品是否在A区域内,若找到则返回成功,否则返回失败。
当条件节点返回成功时,表示整个顺序节点成功执行,整个顺序节点结束,返回成功,机器人搜索结束;否则返回失败。

如果物体不只是存在区域A,而是可能在其他的区域(1-N),这样我们可以加入一个判断循环条件,每次先判断是否在区域M,如果不在,就前往区域M,然后执行搜索,结构框图如下:

在上图,引入了显式成功条件(explicit success condition),即在执行动作前总是先进行条件检测。比如,先检测机器人是否已经在A处,如果在就不执行去A处的动作,直接返回成功状态。一般使用选择节点(Fallback)和条件节点(Condition)构成。

修饰节点(Decorator)和黑板(Blackboard)#

考虑上面的行为树,我们可以发现,如果区域很多并且会动态修改,这样每次更新行为树时,都需要修改节点,非常麻烦。为了解决这个问题,我们可以使用黑板(Blackboard)来存储动态数据,并通过修饰节点(Decorator)来修改行为树。

  • 黑板(Blackboard):行为树中存储动态数据的结构,实际上只是一个公共存储区域,各个行为可以在其中读取或写入数据;
  • 装饰节点(Decorator):相较于每增加一个地点就复制一份相同的子树,我们可以使用一个特点的规则(如重复(Repeat))的修饰节点,描述这个节点的运行逻辑。

针对上面存在的问题,我们可以给行为树添加一个Repeat装饰节点和一个GetLoc的动作节点,用来在每一次迭代读取新的搜寻地址。GetLoc操作从已知位置队列中弹出一个位置,并将其作为某个参数target_location写入黑板。如果队列为空,则返回Failure;否则返回Success。然后,处理导航的下游节点可以使用此 target_location参数,该参数在每次子树重复时都会更改。如下图所示:

BehaviorTree.CPP#

参考文档:BehaviorTree Docs

BehaviorTree.CPP是一个开源的C++库,用于构建行为树。

xml脚本储存树结构#

行为树通过xml脚本构建,xml脚本的语法分为compactexplicit两种,前者结构简单,后者包含消息更多,方便软件读取。xml脚本的格式如下:

<root BTCPP_format="4" >
    <BehaviorTree ID="MainTree">
        <Sequence name="root_sequence">
            <Action ID="SaySomething"   name="action_hello" message="Hello"/>
            <Action ID="OpenGripper"    name="open_gripper"/>
            <Action ID="ApproachObject" name="approach_object"/>
            <Action ID="CloseGripper"   name="close_gripper"/>
        </Sequence>
    </BehaviorTree>
</root>
  • BTCPP_format是必须的,它表示当前xml脚本的版本,目前支持4;
  • <BehaviorTree><Action/><Sequence/>等表示了这个节点的类型;
  • ID描述了节点的类型,这些类型为之前在程序里面注册过的,name表示节点的名字,这个名字是必须的,并且不能重复;
  • messaage用于在不同节点之间传递的消息,对因为黑板里面的数据

为了方便使用Groot软件编写,这里采用explicit语法。

子树#

我们可以将一些节点组合成一个子树,子树可以嵌套,子树也可以作为节点参数传入,以此来降低行为树的复杂度。

 <root BTCPP_format="4" >
 
     <BehaviorTree ID="MainTree">
        <Sequence>
           <Action  ID="SaySomething"  message="Hello World"/>
           <SubTree ID="GraspObject"/>
        </Sequence>
     </BehaviorTree>
     
     <BehaviorTree ID="GraspObject">
        <Sequence>
           <Action ID="OpenGripper"/>
           <Action ID="ApproachObject"/>
           <Action ID="CloseGripper"/>
        </Sequence>
     </BehaviorTree>  
 </root>

外部文件#

在一个xm文件里面。可以使用其他文件的树结构,使用标签如下:

<include path="path_to_another_xml"/>

将前面两个树结构拆分两个文件,如下所示:

<!-- file maintree.xml -->

<root BTCPP_format="4" >
     
    <include path="grasp.xml"/>
     
    <BehaviorTree ID="MainTree">
        <Sequence>
           <Action  ID="SaySomething"  message="Hello World"/>
           <SubTree ID="GraspObject"/>
        </Sequence>
    </BehaviorTree>
</root>
 <!-- file grasp.xml -->

<root BTCPP_format="4" >
    <BehaviorTree ID="GraspObject">
        <Sequence>
           <Action ID="OpenGripper"/>
           <Action ID="ApproachObject"/>
           <Action ID="CloseGripper"/>
        </Sequence>
    </BehaviorTree>  
</root>
注意

如果你想在 ROS 包中查找文件,您可以使用以下语法:

<include ros_pkg="name_package" path="path_to_file"/>

在CPP里面使用#

cmake里面需要添加:

find_package(behaviortree_cpp REQUIRED)
target_link_libraries(executable_name BT::behaviortree_cpp)

在CPP里面使用:

#include "behaviortree_cpp/bt_factory.h"

using namespace BT; // optional

库处于命名空间BT里面,为了避免污染命名空间,建议不要直接使用using namespace BT;

节点状态#

在BehaviorTree.CPP中,节点的状态通过enum class NodeStatus来表示,在头文件<behaviortree_cpp/basic_types.h>中定义,官方实现如下:

/// Enumerates the possible types of nodes
enum class NodeStatus
{
  IDLE = 0,
  RUNNING = 1,
  SUCCESS = 2,
  FAILURE = 3,
  SKIPPED = 4,
};

我们可以通过自定义函数来实现状态的返回,如下所示:

BT::NodeStatus CheckBattery()
{
  std::cout << "[ Battery: OK ]" << std::endl;
  return BT::NodeStatus::SUCCESS;
}

节点类型#

在BehaviorTree.CPP中,节点的对应关系如下:

节点类型CPP 类名
动作节点(Action)BT::SyncActionNode
条件节点(Condition)BT::ConditionNode
控制节点(Control)BT::ControlNode
修饰节点(Decorator)BT::DecoratorNode

分别在头文件<behaviortree_cpp/action_node.h><behaviortree_cpp/condition_node.h>等定义。在CPP程序里面,我们需要通过继承来实现不同的动作节点和条件节点;控制节点和修饰节点通过xml文件来配置。
之后将会具体介绍如何实现自定义节点。

如下简单展示了一个动作节点的实现:

// Example of custom SyncActionNode (synchronous action)
// without ports.
class ApproachObject : public BT::SyncActionNode
{
public:
  ApproachObject(const std::string& name) :
      SyncActionNode(name, {})
  {}

  // You must override the virtual function tick()
  BT::NodeStatus tick() override
  {
    std::cout << "ApproachObject: " << this->name() << std::endl;
    return BT::NodeStatus::SUCCESS;
  }
};

参考文章#

[1] BehaviorTree.CPP
[2] Introduction to behavior trees
[3] Behavior Trees in Robotics and AI: An Introduction