行为树（人工智能、机器人和控制）

行为树是计算机科学、机器人学、控制系统和视频游戏中使用的计划执行的数学模型。它们以模块化的方式描述有限的任务集之间的切换。它们的优势在于能够创建由简单任务组成的非常复杂的任务，而不用担心简单任务是如何实现的。行为树与分层状态机有一些相似之处，关键是行为的主要构件是一个任务而不是一个状态。行为树的易懂性使得它不容易出错，在游戏开发者社区非常流行。行为树已经被证明可以概括其他几种控制架构。

行为树起源于计算机游戏行业，是模拟非玩家角色（NPC）行为的有力工具。它们已被广泛用于高知名度的视频游戏，如《光环》、《生化危机》和《孢子》。最近的工作提出将行为树作为无人机、复杂机器人、机器人操纵和多机器人系统的多任务控制框架。行为树现在已经达到了成熟的程度，可以在游戏AI教科书以及Unity（游戏引擎）和虚幻引擎等通用游戏环境中得到处理（见以下链接）。行为树因其开发范式而变得流行：只需对NPC的动作进行编程，然后设计一个树状结构（通常是通过拖放），其叶子节点是动作，其内部节点决定NPC的决策，就能够创建一个复杂的行为。行为树在视觉上很直观，易于设计、测试和调试，并且比其他行为创建方法提供更多的模块化、可扩展性和可重用性。多年来，行为树的各种实现方式在效率和功能方面不断改进，以满足行业的需求，直到它们演变成事件驱动的行为树。事件驱动行为树通过改变行为树内部处理执行的方式，以及引入一种能够对事件做出反应并中止运行节点的新型节点，解决了经典行为树的一些可扩展性问题。现在，事件驱动的行为树的概念已经成为一种标准，并被用于大多数的实现中，尽管为了简单起见，它们仍然被称为行为树。

行为树用图形表示为一棵有向树，其中的节点被分为根、控制流节点或执行节点（任务）。对于每一对连接的节点，传出的节点被称为父节点，传入的节点被称为子节点。根没有父母，只有一个孩子，控制流节点有一个父母，至少有一个孩子，而执行节点有一个父母，没有孩子。从图形上看，控制流节点的子节点被放在它的下面，从左到右排序。行为树的执行从根开始，根以一定的频率向它的子节点发送tick。Tick是一个允许执行子节点的启用信号。当行为树中的一个节点被允许执行时，如果它的执行还没有结束，它就会向父节点返回运行状态；如果它已经达到了目标，就会返回成功；否则就会返回失败。

一个控制流节点用于控制它所组成的子任务。一个控制流节点可以是一个选择器（回退）节点或一个序列节点。它们依次运行其每个子任务。当一个子任务完成并返回其状态（成功或失败），控制流节点决定是否执行下一个子任务。

回避节点用于寻找和执行xxx个不失败的子任务。当它的一个子任务返回成功或运行时，回避节点将立即返回，状态代码为成功或运行（见图一和下面的伪代码）。子节点按重要性从左到右依次打钩。在伪代码中，后退构成的算法是。

序列节点用于寻找和执行xxx个尚未成功的孩子。当它的一个子节点返回失败或运行时，一个序列节点将立即返回，状态代码为失败或运行（见图二和下面的伪代码）。子节点按顺序打钩，从左到右。在伪代码中，序列构成的算法是。