BehaviorTree之概念讲解（一）

什么是BehaviorTree

行为树，顾名思义，就是一个以树为底层结构的，决定行为走向的一个工具。行为树一开始多用于游戏行业，但是随着机器人行业的发展，越来越多的机器人框架（如navigation2，pr2_robot）开始使用行为树来决定机器人的动作走向。没有行为树之前，这种动作/状态之间的切换大多使用的是FSM（有限状态机）。FSM在状态多起来的时候，很容易发生混乱，在做动作的时候还要兼顾状态的切换，增加程序员的心智负担。行为树在这种场景下应运而生！

行为树与状态机的差异

状态机

状态机的本质，就是维护了多个不同的状态，每个状态之间可以互相切换，状态本身可以做动作，可以做条件，也可以在做动作的过程中判断条件，改变状态。状态机最大的好处就是自由，状态的切换可以在动作中，也可以在外部切换，内部只做动作。

行为树

节点1就是树的root节点，外部每tick一次，就可以从root节点开始，依次遍历。行为树解决了状态机，状态一多层次就会不清晰，不好维护的痛点。行为树把动作和执行动作的逻辑本身隔离开来，让动作模块可以更加关注动作本身，不用分心考虑状态切换的问题。

行为树节点简介

行为树是一种有向树，由节点和连线构成。相互连接的一对节点分别为父节点和子节点，没有子节点的节点称为叶节点。常用的非叶节点有选择节点和序列节点；常用的叶节点有条件节点和动作节点。

选择节点（非叶）

选择节点按照自左向右的顺序计算每个子节点，一旦某个子节点返回了“成功”或“运行中”的状态，那么选择节点就会立刻将自身的状态相应地更改为“成功”或“运行中”，并不再执行后面的节点。

序列节点（非叶）

序列节点按照自左向右的顺序计算每个子节点，一旦某个子节点返回了“失败”或“运行中”的状态，那么序列节点就会立刻将自身的状态相应地更改为“失败”或“运行”中，并不再执行后面的节点。

装饰器节点（非叶）

InverterNode

• 勾选孩子一次，如果孩子失败则返回 SUCCESS 或如果孩子成功则返回 FAILURE。
  如果子节点返回 RUNNING，则此节点也返回 RUNNING。

ForceSuccessNode

• 如果子节点返回 RUNNING，则此节点也返回 RUNNING。
  否则，它总是返回 SUCCESS。

ForceFailureNode

• 如果子节点返回 RUNNING，则此节点也返回 RUNNING。
  否则，它总是返回 FAILURE。

RepeatNode

• 最多勾选孩子 N 次，其中 N 作为输入端口传递，只要孩子返回 SUCCESS。
  如果子进程返回 FAILURE，则中断循环，在这种情况下，也返回 FAILURE。
  如果子节点返回 RUNNING，则此节点也返回 RUNNING。

RetryNode

• 最多勾选孩子 N 次，其中 N 作为输入端口传递，只要孩子返回 FAILURE。
  如果子进程返回 SUCCESS，则中断循环，在这种情况下，也返回 SUCCESS。
  如果子节点返回 RUNNING，则此节点也返回 RUNNING。

条件节点（叶节点）

条件节点，就是根据条件，返回SUCCESS或者FAILURE，结合非叶节点可以有效的打断树的运行，适合在逻辑复杂的场景下使用。

动作节点（叶节点）

动作节点，就是最终做动作的节点，具体的业务动作处理就在这里面做， 动作节点也分为同步节点和异步节点，异步节点又分为开线程做异步和通过协程实现异步。

大概节点类型及作用如下：

通过C语言实现简易行为树

先要确定数据结构，去以一个适当的方式排列节点。在选取一个适当的方式遍历整棵树。我选择的是孩子兄弟树，原因是它既有行为树本身的层次结构，又兼顾了二叉树的遍历方式，非常符合目前的需求。

孩子兄弟树

即每个节点都只能有一个孩子，但可以有多个兄弟。
数据结构如下：

typedef bool (*NodeCallBack)(void);

typedef struct BTNode
{
	    const char* id;
	    NodeCallBack node_callback;
	    struct BTNode *firstchild,*rightsib;

} BTNode;

typedef struct BTTree
{
	    int leaf_len;            // 叶子结点个数(执行动作的节点)
	    int node_len;            // 树的节点树(不算头节点)
	    BTNode *root;            // 指向头节点的
    
} BTTree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

遍历方式

孩子兄弟树的一个优点，就是可以通过二叉树的前序遍历，实现树从左到右的完全遍历。代码形式也非常简单。

/* 
 * describe  : 前序便利
 * parameter : bt_node 指向根节点的指针
 *             id 查找到的节点ID
 *             pre_node 指向当前找到的节点
 * return    : 指向id符合的节点的指针
 */
static void ErgodicTree(BTNode* bt_node)
{
	  do {
	
		       if(bt_node == NULL) break;
		       if(GetEndLoopTarget()) break;
		       if(bt_node->node_callback != NULL) bt_node->node_callback();
		
		       ErgodicTree(bt_node->firstchild); 
		       ErgodicTree(bt_node->rightsib);
	
	   } while(0);
}

// describe  : 前序遍历，执行所有叶子结点的函数指针指向
// parameter : tree 树的地址
// return    : None
void DisBehaviorTree(const BTTree* tree)
{
	   if(tree == NULL)
	   {
		       DEBUG("DisBehaviorTree error ");
		       return;
	   }
	   
	   SetEndLoopTarget(false);
	   
	   ErgodicTree(tree->root);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

用法展示