克服行为树设计中的陷阱
9.1 Introduction
大概所有游戏行业的从业人员都知道行为树，除非你从不关心技术(Isla 2005, Champandard and Dunstan 2012). 行为树是一种基于任务层次图来控制npc行为的体系结构，其中每个任务要么是一个原子，一个智能体可以直接执行的简单行为，要么是一个由任意复杂度的低级行为树执行的行为的组合。由于行为树提供了比层次有限状态机（HFSM）等替代方案更简洁清晰的行为分解，并且有大量成功使用的经验报告，行为树的使用让大团队能处理更复杂的智能体行为，不仅在游戏行业中，在机器人领域也是如此。但是在实现中有一些关键的技术难点，这些关键点要嘛让架构更困难，要嘛让实现更灵活、易于扩展和易于重用。
我好不容易才发现这些关键点。在命运的驱使下，我已经实现了五次行为树，包括Lisp中的三个与行为树架构相似的系统，这这三个系统后来用于Halo2的AI系统中。并且最近为谷歌的机器人项目提供了两个基于C++的行为树方案实现。
在这个过程中，我学到了一些在创建行为树时不应该做的事情，包括不必要地倍增核心原语（core primitives），发明了一个完整的控制编程语言，并在将所有通信通过“适当的”渠道（如黑板）进行路由时，我提出了一些具体的建议，如何创建一个避免这些陷阱的系统，尤其是在许可或互操作性问题阻碍了您在现有商业或开源解决方案的基础上构建时。
9.2 What Makes Behavior Trees Work
像行为树这样的想法早在Halo出现之前就已经存在了。将行为分解分层为任务最先是由RAPs (Firby 1987)开创的：高级RAPs被分解成低级RAPs，最终在最底层的叶子节点中用来直接控制真实或模拟的机器人 (Bonasso et al. 1997).
行为到任务的分层分解是由反应性动作包（rap）开创的（Firby 1987）：高级rap被分解成低级rap，最终在叶技能中达到最低点，这些技能用于直接控制真实和模拟机器人（Bonasso et al。1997年）。我的TaskStorm架构更接近现代行为树，将层次化的任务装饰位置（hierarchical task decomposition）直接集成到封装智能体状态的黑板系统中，使得认知操作能够在行为过程中相互分割 (Francis 2000)。
尽管这些系统在功能上类似于行为树，但Damian Isla补充的关键点侧重软件设计方面，重点在于简化生成行为树所需的代码(Isla 2005).
Isla认为，有四个关键特性使Halo2的AI及其后续产品得以大规模开发：可定制性、明确性、可编辑性和可变性。
可定制性，行为被分解成更小的组件，这些组件可以单独更改或参数化；
明确性，智能体所做的事情可以表示为不同的行为节点，整个行为可以表示为一个图；
可编辑性，行为的彻底分解使得用现版本替换节点（旧版本）变得容易；
可变性，控制算法本身被表示为节点；
根据我的经验，在实现过程中很容易失去方向，导致偏离最初的功能设计，并在这个过程中忽略这个关键点。一个在功能上将行为分解为由复合行为树组成的原子行为的系统，其行为可能类似于行为树，但如果行为过于紧密，它将不可定制或可编辑，如果节点太过臃肿，它也不会是明确的或可变的。更糟糕的是，实施这些特性的设计模式可能成为比疾病更糟糕的治疗方法，使整个系统更难维护。尽管其中一些问题是不可避免的，但如果我们对如何设计行为树非常小心，其他陷阱也很容易避免。
9.3 Pitfalls in Behavior Tree Design
行为树作为一个决策组件运行在一个更大的结构（游戏引擎、机器人操作系统或认知架构）中，它很容易设计出满足父系统所有需求的东西。但是，当软件各组件有明确定义的职责范围和明确区分的关注点时，会工作得更好。与此同时，反常的是，你的行为树做的越多效率反而更低。其中三个陷阱是：
将过多不同功能的类添加进行为树的决策体系中。
在不需要时提前加入其它编程语言。
强迫所有的通信都必须通过黑板系统（作为准则之一），而不是按需实现。
如果你在一个大项目中，并且对你需要的东西有一个明确的规范（或经验），（2）和（3）可能不适用于你；但如果你在一个较小的项目中，更简单的结构可能适合你。
9.3.1 Pitfall #1: Creating Too Many Organizing Classes
Occam的Razor被简化为“保持简单，傻瓜化”，但最初的表述更像是“如无必要，勿增实体”——这更符合行为树架构的一个陷阱：为系统需要做的每一种事情创建一个单独的架构类别。这使得开发所需的特性变得更加困难。
例如，除了执行动作的元行为和编排动作的复合行为外，角色可能需要一些低级“技能”来直接操纵动画系统，或机器人控制器，或管理游戏引擎或机器人操作系统提供的资源的高级“模块”。但是，为每一个模块（即行为、组合、技能和模块的根类）单独构建体系结构类别可能是错误的。行为树已经提供了低层和高层结构，并且随着外部内存存储的增加，它们的决策能力是图灵完备的。那么，为什么不使用行为呢？
如前所述，许多类似行为树的史前系统在技能、任务、任务网络或模块等概念之间进行了区分，并创建了实现这些概念的类或模块。这种方法完成了任务，也许在Lisp hacking时期是一种好方法，但是这种通过增加实体来实现功能的方法，在以更少的类来实现快速迭代重构的现代C++开发中会引入更多的陷阱。
例如，我们为Google一个内部机器人项目开发的行为树有两个模块，一是通过上下文模块与机器人操作系统交流，一是组成行为树的任务模块，它通过隐藏底层通信协议的称为AgentHandles的thin wrappers直接与智能体通信。
但是随着系统体系结构的发展，每一个简单的重构都会影响到这两个模块，而会影响到其他系统的（如Blackboard）更复杂的新功能需要考虑到两者不同的特性，为兼容做额外的开发。
我们只使用tasks来避免创建太多抽象类。可以将所有能在行为树中完成的事都看成是在创建新的任务。执行元行为？任务。将多个动作分组？另一种任务。访问系统资源？任务。运行整个行为树脚本？另一种任务。我们最终采纳了一句口头禅：“这是任务，一路向下。”
当我们把这个行为树移植到一个新的机器人平台上时，一切都变成了一项任务。好吧，从技术上讲，不是所有来自机器人操作系统的资源都是由ExecutionContext统一提供的，但是所有负责行为模块的类，比如旧的AgentHandles和脚本都被实现为一个任务的子任务SchedulableTask，如表9.1所示；这个类为给定特定ExecutionContext的单个决策步骤提供接口。
将所有这些不同的类型强制到一个模型中并没有伤害我们；相反，结果是我们的新行为树变成了一个具有单一责任决策的系统，其API只有两个外部联系点：顶部提供ExecutionContext或底部叶任务中的自定义代码。这种更简单的设计使我们能够在几个星期内构建出功能，而旧系统已经花了我们几个月的时间。
9.3.2 Pitfall #2: Implementing a Language Too Soon
行为树是一个决策系统，这意味着构成树的行为节点需要两个独立的属性：一个节点既需要运行行为的能力，也需要决定是否运行行为的能力。这就提出了行为树系统本身是否应该实现条件语言的问题。
你可以只做一点工作就能完成大部分的事情；甚至非常简单的决策结构都是图灵完备的：实际上，您可以使用NANDs或NORs执行任何计算。
因此，可以用很少的节点类型实现复杂的控制行为。测试可以通过简单的成功或失败的元操作来实现；if–thens可以由组合实现，比如执行第一个非失败操作的Selectors，代码块可以由执行所有未失败操作的Sequences或Parallel nodes来实现，Parallel nodes允许同时执行多个操作（Champandard和Dunstan 2012）。
使用非常简单的组件（Tinkertoy style）实现复杂的行为会导致很多boilerplate，因此很容易添加更多的控件结构。封装其他任务的Decorator task允许创建反转失败重要性的Not；序列的子类可以创建一个And task，该任务只有在其所有任务都成功的情况下才能成功，依此类推。很快，您会发现自己正在开发一种完整的编程语言，它使您能够简洁地表示字符逻辑。
对于一个“陷阱”部分，我并不建议您不要实现一个完整的编程语言（这对于一个双重否定是怎样的）；如果您的行为树会大量应用，您可能确实想要实现一种语言。但是我用两种不同的方式实现了这类语言：从上到下从语言关注点出发，从下到上，基于对问题域的理解从下往上驱动，后者是一种更有效的策略。
有大量可供选择的语言结构----Not, And, Or, If-Then-Else, Cond, Loop, For, While, Repeat-Until, Progn, Parallel, Any, All, Try-Catch-Except----当你学习你最喜欢的编程语言（可能不是C++）时，你看你会对其中的一个或多个情有独钟。大多数这些构造的逻辑都非常清晰，因此很容易为任何可能的需要构建一个大型库。
问题是，这些逻辑中的大部分可以通过标准行为树节点来更好的实现----Actions、Decorator、Sequence、Parallels和Selector。（你可以试着在Selector和Cond之间找一找区别）最好的情况是，最终得到一个具有非标准名称的节点。更糟糕的情况是编写不需要的功能。实际的最坏情况时，最终你在多个相似的节点之间实现了重复的逻辑，这些节点虽然是被需要的，但随着API的扩展，变得非常难以维护。
一个更好的方法是从行为树节点的标准集合开始----Actions, Decorators, Sequences, Parallels, and Selectors，并尽可能将它们应用到您的问题域中。如果你要自己实现它们，那每个行为树对于任务执行、失败和成功以及逻辑测试的含义都会略有不同。一旦你理解了你的问题域需要什么样的模式，你就可以通过特化现有的结构来扩展你的语言。这将减少无意义的重复，得到更易于维护的代码，和一个由对游戏有用的内容驱动的构造库。
对于object containment这样的结构特性，这一点很容易看到；例如，如果Schedulable Task有GetChildren和AddChild来管理其子级（children），在没有子级的原子叶子任务和有子级的组合任务中，应该用不同的方式来重写这些子级。对于我们用例中的几乎所有不同类型的容器，一个高级类，如清单9.2所示的ContainerTask足以处理所有这些实现细节。
这是一个简单的类设计，所以我假设您在执行这个类或它的对应的AtomicTask的实现时没有任何困难。实际上，我们拥有的每一个组合任务都继承自ContainerTask；我们与此模式的唯一不同之处是某些类型的队列不是从向量继承的。
但我们在行为领域有更好的复用机会。我们不应该简单地分别实现每个任务的Step成员函数，而是应该分解Step成员函数，并通过类的受保护接口将stepping API的内部公开给子类，如清单9.3所示。
使用这些受保护的成员函数，Step成员函数在SchedulableTask中以一种看起来几乎微不足道的方式实现。但是，通过在树的顶部定义这个（和类似的成员函数），我们定义了任务的执行模型，所以我们真正需要了解的是任务与规范的区别。我们已经展示的ContainerTask只包含任务；它没有执行语义。但是在树的下一级出现了类似ParallelTask或SequenceTask之类的任务，它们确实覆盖了这些受保护的方法，如清单9.4所示。
一个实际的SequenceTask的核心可以相当简单，在它的PerformAction成员函数中进行编码。但是我们做的不仅仅是实现这个成员函数；我们还在受保护的API中暴露了它的一些内部特性，包括HandleChildFailure和AdvanceToNextChild。
我们选择通过查看我们的机器人应用程序的实际决策用例来做到这一点，我们希望在不使实际的SequenceTask非常复杂的情况下，对任务如何响应各种环境进行更细粒度的控制。例如，我们需要一个TryTask，它按序列测试子任务，但如果子任务失败，它本身不会失败。通过在受保护的API中公开AdvanceToNextChild和HandleChildFailure，我们能够用（本质上）半页代码编写一个TryTask，如清单9.5所示。
我们需要重写的唯一成员函数是HandleChildFailure，重写本身非常简单。这使得开发和测试这个类变得很容易；我们可以依赖父类的控制和stepping逻辑，并将测试重点放在HandleChildFailure及其对子级失败的影响上。
此设计基于具有可重写成员函数的类层次结构分解行为树。在C++中，这可能比手工编写的代码更为有效。Game AI Pro 第一卷中关于 Behavior Tree Starter Kit 的章节描述了一系列这样的权衡和考虑，你可以参考并深入考虑（Champandard和Dunstan 2012）。
对于我们的用例，这种明确的行为分解适用于其顶层决策周期不超过30赫兹的机器人。这可能不一定适用于需要优化每个周期的游戏，但我们能够在一台不太结实的计算机上运行一个行为树步骤，以获得6000万赫兹的简单基准。因此，您可能需要从一个简洁的分支开始，这个分支易扩展，且后续易于优化并将其当做基准、分析和游戏所需的一切。
9.3.3 Pitfall #3: Routing Everything through the Blackboard
以前，类似BT的系统被设计成将认知任务分解成一个个功能块(Francis 2000)，因此，系统所做的思考可以与系统的内存检索过程混合在一起；为了使内存检索工作正常，系统操作的几乎所有数据都需要暴露在系统的黑板上。
因此系统所做的思想可以与系统的记忆检索过程交织在一起；为了使记忆检索起作用，系统操纵的几乎所有数据都需要暴露在系统的黑板上。一种机器人控制系统，其中多个独立进程进行通信，如ROS(ROS.org 2016)，也有类似的约束，谷歌的机器人行为树的第一个版本支持系统黑板和行为树之间的紧密交互。虽然不是系统的必需部分，但这使我们能够同时指定行为树及其数据。
类似的问题也存在于需要感官模型的游戏中，比如潜行游戏（以及许多其他现代射击游戏），但是，将整个行为树逻辑与黑板的逻辑联系得太紧密可能是一个错误，在原型设计过程中，将简单任务依赖于黑板进行通信，这可能是一个错误。
将所有任务通过黑板系统或感官管理器来实现，同时还要随着系统变得复杂庞大的时候还能顺畅的运行，这可能比使用编程语言自带的特性来进行通信要复杂得多，而且往往不太可靠，除非你们精通c++模板并用它创建了一个类型安全的黑办系统（如果是，这将更强大）。
在原型设计阶段，以这种方式“正确”地做事情实际上会干扰到行为树的设计空间的探索和完善它们的逻辑。在我们的第一个行为树中，黑板和行为树被设计在一起，相互补充。不幸的是，这意味着一个应用程序接口的改变会影响到另一个，特别是任务的层次结构如何引用黑板的层次结构，反之亦然。至少在两个不同的情况下，较低级别的API更改会导致一个月或更长的时间来重新连接任务和黑板，以便所有数据都可以用于正确的任务。
另一种方法是将行为树与黑板强解耦。相同的行为树逻辑应该与复杂的层次黑板一起工作，具有丰富的知识表示或具有简单的C++简单的旧数据结构（POD），或者甚至没有显式黑板，并建立协作任务之间的临时通信。使用ad-hoc communication可以使构建完整的数据驱动的行为树变得更加困难，但是对于许多问题，这已经足够了。例如，一个机器学习系统成功地学习了比人类行为树更好的控制，而无人机则使用了一个只包含少量值的C++ POD作为黑板。
当我们为一个新的机器人平台重新实现我们的行为树时，我们暂时放弃了黑板，取而代之的是ad-hoc communication，这有两个好处。
可以在更高层次上测试和完善黑板的逻辑；
当我们决定放弃一个低级API时，只需要更改两个叶子节点上的任务。
我们在新的行为树中仍然有一个旧黑板的用例，但把关注点从旧黑板上清晰地分离出来意味着我们有一个可靠的、经过良好测试的行为树，它可以与各种通信机制一起工作。
我不能用简单的代码就清楚地告诉你这两种方法之间的区别（旧的黑板上代码很庞杂，新的通信机制是它们的用例所特有的），但如果你的行为树架构合理，你可以在以下两个场景使用相同的核心决策逻辑：
玩具级Demo：其“黑板”是一个C++的POD，其决策是由C++ LAMBDAS完成的。
一个完整的系统：它有一个分布式黑板和一个完全由数据驱动的行为树条件系统。
9.4 Conclusion
我设计过很多行为树系统和类行为树系统，实现过程中遇到过许多陷阱。但我在上面概述的模式很简单：首先弄清楚你的需求是什么，在没确定好需求前不要急着动手，精炼设计直到可以用最简单的方式来表达足够复杂的功能。这种方法可以应用于任何地方，当您这样做时，它可以从根本上改善您的开发体验。
测试驱动开发和持续集成以及重构工具会让这一过程变得简单（sed, awk, 和 shell脚本工具也会帮上大用处），但我想说的是行为树可能会十分复杂，其结构却非常规则，因此非常重要的一点是要重点关注可能导致重复性工作的地方，并通过类层次结构来解决这一问题。
我们第一次尝试创建行为树时产生了太多的概念、太多重复的代码和太多的样板文件。通过减少实体的数量，考虑相关领域的需求，并将复杂性关联到精心选择的超类和支持文件中，我们从根本上减少了必须维护的重复代码的数量，乃至一页就能放下。
当你做到了这一点，并且你可以对你的系统进行基准测试以证明它仍然是有效的，那么你就完成了构建行为树的工作。
References
Bonasso, R. P., Firby, R. J., Gat, E., Kortenkamp, D., Miller, D. P., and Slack, M. G.
1997. Experiences with an architecture for intelligent, reactive agents. Journal of
Experimental & Theoretical Artificial Intelligence 9(2–3):237–256.
Champandard, A., and Dunstan, P. 2012. The behavior tree starter kit. In Game AI Pro, ed.
S. Rabin. Boca Raton, FL: CRC Press, pp. 73–95.
Firby, R. J. 1987. An investigation into reactive planning in complex domains. AAAI
87:202–206.
文章来源：http://www.gameaipro.com/
如侵犯版权，请联系译者删除。
读者若需要转载，请注明出处。
若有错误，欢迎指正。
