大家好，我是小明，很高兴我们又见面了！今天谈的领域并非我的专业方向，但也同样有趣，初次接触时让我备受启发，因此分享给大家。和上次一样，本文的工程也为大家提供了源代码，方便交流学习。如有疑问，可以在本篇文章下留言交流。
游戏中的智能行为
游戏设计者总是努力地为游戏中的NPC赋予“智力”。而我们在设计机器人时，往往也有同样的需求：我们希望自己的机器人不仅仅是听从命令的“遥控玩具”，还能对不同的外界情形做出自己的判断与响应动作，更像一个“人”而非“机器”。
那么，要如何为机器人赋予这种智能呢？数十年来，计算机与机器人领域的研究者们各显神通。其中有两种重要方法：一种叫做有限状态机（Finite State Machine，FSM），该方法把机器人的每类响应都视作一种状态，各状态之间一旦满足规定的条件，就进行单向跳转；而我们今天要讲的方法叫做行为树（Behavior Tree， BT），是从游戏领域“借用”过来的。如果用编程思想类比，有限状态机的状态跳转，类似于早期编程中的GOTO语句，而行为树则更类似与函数调用，该方法实现起来更加简单，更有利于程序的模块化。但值得一提的是，除了直观性以外，没有证据表明BT比FSM有其它方面的优点[1]。
行为树
行为树是一种有向树，由节点和连线构成。相互连接的一对节点分别为父节点和子节点，没有子节点的节点称为叶节点。常用的非叶节点有选择节点和序列节点；常用的叶节点有条件节点和动作节点。还有并行、装饰其它类型的节点，暂时不详细介绍[2]。
选择节点（非叶）
选择节点按照自左向右的顺序计算每个子节点，一旦某个子节点返回了“成功”或“运行中”的状态，那么选择节点就会立刻将自身的状态相应地更改为“成功”或“运行中”，并不再执行后面的节点。
序列节点（非叶）
序列节点按照自左向右的顺序计算每个子节点，一旦某个子节点返回了“失败”或“运行中”的状态，那么序列节点就会立刻将自身的状态相应地更改为“失败”或“运行”中，并不再执行后面的节点。
条件节点（叶）
条件节点代表了一个判断，条件满足会返回“成功”状态；否则返回“失败”状态。
动作节点（叶）
动作节点代表了一个动作，当动作完成后会返回“成功”；当动作无法完成会返回“失败”；如果动作正在进行中，将会返回“运行中”。
仅看理论或许有点难以理解，好在Michele Colledanchise已经开发出了C++库ROS-Behavior-Tree，让我们可以在ROS中方便地实现机器人行为树。下面我们就用这个功能包，开发一个拥有智能NPC的小游戏《躲开敌方的小乌龟》，方便大家理解行为树各节点的功能逻辑。
下图中，敌方白色的小乌龟在地图中沿某条固定线路巡逻，我方用键盘控制红色小乌龟运动。当敌我距离太近时，敌方小乌龟会察觉我方存在，并展开追逐。此时我们需要移动红色小乌龟，甩开敌方一定距离后，敌方才会重新回到巡逻路线上。
下面几个图展示了敌方小乌龟的行为树，由一个选择节点guard、一个序列节点attack、一个条件节点have_enemy和两个动作节点nav_enemy、patrol构成。其中顶部guard为根节点，根节点会不停地激发其子节点。下图中，绿色代表节点状态为“成功”，红色代表节点状态为“失败”，黄色代表正在等待子节点返回状态。需要注意的是，虽然我们按顺序分析每个步骤，但并不代表必需等待一次激发走完所有步骤才会开始下一次激发。实际上，每个时刻都会从头开始一次激发，即使还有激发尚未走遍整棵树。下面我们来看看行为树是怎样运作的。
1.行为树开始，guard按从左开始的顺序，激发了自己的第一个子节点attack，而attack也按顺序激发了自己的第一个子节点have_enemy，判断周围是否有敌人。
2-1.第一种情况，我们假设小乌龟周围没有敌人，条件节点have_enemy返回了“失败”，由于attack是序列节点，当出现子节点失败后，也将自己的状态更改为“失败”；而guard节点为选择节点，当子节点失败后，继续执行下一个节点patrol，开始巡逻。
2-2.第二种情况，假设小乌龟周围存在敌人，条件节点have_enemy返回了“成功”，由于attack是序列节点，当子节点成功后，会继续执行下一个子节点nav_enemy，小乌龟开始追逐敌人，并返回“成功”（或“运行中”）；而guard节点为选择节点，当自己子节点出现“成功”时（或“运行中”），不再执行下一个节点patrol。
于是，上述判断便分别实现了“当周围没有敌人，小乌龟就保持巡逻”和“当周围有敌人，小乌龟就追逐敌人，而不再巡逻”的行为。
按照上述设计编写对应的行为树程序，其中比较重要的文件有
ROS-Behavior-Tree/behavior_tree_core/src/tree/：
guard_robot_tree.cpp定义了行为树的结构
ROS-Behavior-Tree/behavior_tree_leaves/nodes/：
action_nav_enemy.cpp动作节点——向敌人移动
action_patrol.cpp动作节点——巡逻
condition_have_enemy条件节点——判断敌人
ROS-Behavior-Tree/behavior_tree_leaves/src：
turtle_tf_broadcaster.cpp广播第一只小乌龟的tf
turtle_tf_broadcaster_2.cpp广播第二只小乌龟和巡逻点坐标的tf
将ROS-Behavior-Tree下载并放置到工作空间[3]，打开终端编译并运行：
cd ~/catkin_ws catkin_make roslaunch behavior_tree_leaves guard_robot_behavior_tree.launch一共弹出了两个界面，一个界面展示了行为树的结构：
使启动终端处于激活状态，用键盘的方向键控制己方小乌龟靠近和远离敌方小乌龟：
可以看到，行为树按照我们的预想发挥作用了！
结语
实际上，行为树可以实现的功能远不止这么简单。虽然我并非如下方向的专业人士，但也可以想象，工厂流水线对残次品和机器故障的处理，自动驾驶对复杂路况的判断，智能家居的人性化设计（据我所知已经有基于行为树的相关产品），都是一定程度上类似的智能行为。利用行为树或其思想，我们也许能够更加清晰简洁地实现需要的智能行为，为我们生活的智能化提供更加丰富的可能性！
注
[1] 在2005年游戏开发者会议关于Halo系列人工智能结构的讲座中，Damian Isla 认为行为树本质上就是分层状态机。
[2] 更多行为树在机器人中的应用研究，可参考《Behavior Trees in Robotics and AI》
项目地址
https://github.com/XM522706601/XM_Studio-guyuehome
