行为树技术的研究进展与应用

2020-04-02刘瑞峰王家胜张灏龙田梦凡

计算机与现代化 2020年2期

刘瑞峰，王家胜，张灏龙，田梦凡

(中国航天系统科学与工程研究院，北京 100048)

0 引言

当前,世界正处于智能革命的前夜，人类社会正从“互联网+”时代迈入“智能+”时代。近年来，在大数据、新型算法和超级计算的推动下，人工智能正在改变乃至颠覆所触及的每一个行业，军事发展亦不例外，科学、高效地进行作战规划对未来信息化战争至关重要。作战仿真具有试验安全、灵活、高效、鲁棒、经济的特点，被广泛应用于装备作战效能和作战规律的研究，用于支撑改进装备性能，以及部队作战指挥能力的提高。该领域的基础是武器装备模型，通过作战试验数据的分析，构建贴近实战的作战环境，设计作战想定，同时，以行为树技术为工具，进行行为模型设计，可以提高作战仿真的专业性、实时性、精确性。

行为树(Behavior Tree， BT)是一种形式化的建模语言，主要用于系统和软件工程，其概念最初由Dromey提出[1]，并于2001年首次发表。

在行为树领域的发展初期，常常使用“遗传软件工程(Genetic Software Engineering)”或“遗传设计(Genetic Design)”等描述行为树的实际应用。目前，由于行为树具有简单、灵活和模块化等优势，被广泛用于交互式应用软件中的智能交互对象NPC(Non-player Character)的行为决策。此外，行为树具有较好的随机性、扩展性、可复用性，可以构建复杂的执行逻辑[2]，且能有效解决决策逻辑在设计与扩展中改动成本较大的问题。同时，通过行为树与智能算法理论的结合，提出新的融合点，应用于智能体的行为决策，从根本上提高了决策水平，也大幅提高了决策精度。因此，行为树技术的研究与发展具有重大意义。

1 行为树的基本原理

行为树是一个包含逻辑节点和行为节点的倒挂型树结构[3]，它用模块化的方式描述了一组有限任务之间的切换，本质是一段逻辑代码[4]，可以通过行为树编辑器转换为各种编程语言代码。

1.1 行为树的组成

2007年行为树在Next-Gen AI[5]中以一种计划执行的数学模型被再次提出。行为树通过透明的逻辑封装来提高状态的模块化，从而独立化状态。其简图如图1(a)所示，它通过节点描述行为逻辑，其中，父节点(Root)是AI逻辑执行的起点，只接受选择节点和序列节点，当对行为树初始化或执行过程中无法找到有效的动作节点时，执行指针会回到父节点。其他节点按照结构可以分为：组合节点(Combination Node)、修饰节点(Decorator Node)、叶节点(Leaf Node)。如图1(b)所示为行为树的节点分类图，分类下的节点主要有：顺序节点、随机节点、并行节点、选择节点、修饰节点、条件节点、行为节点。

(a) 行为树简图

(b) 节点分类

1.2 组合节点

1)选择节点(Select)。

选择节点从左到右遍历，在遍历过程中依次执行所有子节点，当子节点执行结果返回值为Fail时，则可继续执行后续子节点，直到有一个子节点返回Success或者Running，则停止执行后续子节点，并向父节点返回当前子节点执行结果，否则向父节点返回Fail。当子节点返回值为Running时，停止执行所有后续节点，同时，向父节点返回Running，并保存返回Running值的节点。在执行新一轮迭代时，则置该节点为初始节点，重新开始执行。

2)顺序节点(Sequence)。

遍历方式为从左到右依次执行所有子节点，只要子节点执行结果为Success，就继续执行后续子节点，直到有一个子节点返回Fail或者Running，则停止执行后续子节点，并向父节点返回当前子节点执行结果，只有所有子节点返回值都为Success的情况下，父节点的返回值置为Success。

3)并行节点(Parallel)。

在并行节点中，共有N个子节点，且每次均需执行所有节点，当某一节点返回值为Fail，或所有返回值为Success时，则向父节点返回Fail或Success，同时，将其他所有节点的状态置为终止。与选择节点和顺序节点不同的是，并行节点不需要记录返回值为Running的节点，每次执行都会从左向右依次执行所有子节点。

4)随机节点(Random)。

随机执行所有子节点，当一个节点返回值为Success或Running时，则停止执行后续所有子节点，并向父节点返回当前子节点执行结果。

1.3 修饰节点

修饰节点(Decorator)只能有一个节点，修饰节点循环执行其子节点，控制循环终止的方式有：设置最大执行次数、设置计时器、设置过滤条件等。首先，将预期结果置为某一定值，其次，循环执行所有子节点，直到存在节点的返回值和预置的结果值相同，则停止执行，并向父节点返回预置值，否则返回Running。

1.4 叶节点

1)条件节点(Condition)。

与编程语言中的if-else结构相对应，用于判断当前环境状态是否满足设置的逻辑条件，若条件测试结果为True，向父节点返回Success，否则返回Fail。

2)行为节点(Action)。

用来执行节点关联的特定动作，并根据动作执行状态向父节点返回执行结果。

行为树的执行通过周期性的帧循环的更新来驱动，且每棵行为树表示一个AI逻辑，执行AI逻辑的时候，需要从根节点出发，采用深度优先的执行顺序，遍历每个节点。遍历过程中，由组合节点和修饰节点决定下一个执行节点，通过动作节点作出行为决策，执行定义好的动作，当叶子节点执行完毕以后，会将执行结果反馈给父节点。

2 发展现状

当前，行为树的研究主要有实现方式和设计应用2个方面。

行为树实现方案主要有2种：

1)Daniel Kollmann在2008年发布的开源项目“Brainiac Designer”，提供了行为树编辑器的基本实现方案。Brainiac Designer具有默认的基础节点，支持通过插件的形式自定义节点类型与参数，支持导出行为树和保存行为结构为XML文件[6]。

2)腾讯计算机系统有限公司(Tencent)在2016年发布的开源项目“Behaviac”。Behaviac是基于行为树的游戏AI开发框架组件，其支持行为树(BT)、状态机(FSM)、层次任务网络(HTN)等多种范式，其在标准行为树的基础上扩展了一些常见的逻辑节点，如循环节点、时间节点和帧数节点等，使得游戏设计师可以更细致地控制智能体的行为逻辑。

行为树的设计应用集中在对行为树学习机制的改进，主要涉及游戏、仿真决策系统、机器人、评估决策系统等领域。

2.1 仿真决策系统

随着智能信息化的不断普及以及军事科学技术近年来的飞速发展，系统仿真以及诸多仿真模拟平台已成为研究复杂系统工作的一种必要的方法。通过仿真对问题进行分析和研究，能够高效地优化和改善系统，同时可以取得较高的经济效益。行为树作为一种人工智能技术，在仿真系统中通常用于行为或流程逻辑建模。

董倩等人[7]将空中作战行为分为使命、任务和行为3个层次，并自顶向下分析作战行为，将行为执行过程的指挥决策分为2类，一类为模型内部自主决策规则，另一类为模型外部决策规则。模型内部自主决策规则通过装备建模实现，模型外部决策规则通过Lua语言和构建空中决策仿真行为树实现，并借助仿真推演系统OCEAN进行案例演示，结果证明行为树实现的空中作战决策不仅可以完成相关侦察巡逻任务，同时还可以进行压制敌防空和打击等任务，具有较好的自主决策能力。

王在刚等人[8]分析了潜艇CGF建模特点和要求，指出建立潜艇CGF模型的过程，就是依据一定的行为分解原则，构造潜艇CGF的行为树，从而产生出一系列的、可直接执行的、并能够组合实施的动作。

随着计算机处理能力的大大提高，三维仿真等技术均已发展到了相对较高的水平。郝运[9]研究了原型系统中有外部干预条件下智能体进行决策的问题，以行为树为驱动,使智能体能够进行相对合理的决策。利用多种算法处理智能体与人、环境间的交互行为，使智能体能够进行相对合理的决策,并能持续性的反馈,进行上下文相关的再决策,从而实现智能体的自治。

空战行为决策的智能性是学术界关注的重要问题之一。方君等人[10]提出一种基于Q-学习和行为树的CGF空战行为决策方法。通过构建CGF空战行为树模型，实现CGF智能行为；通过在行为树上的Q-学习，使CGF具有不断进化的能力。通过其仿真结果可看出，该算法在与传统算法对抗中，性能优势明显，且该算法学习能力较强。

针对行为树上的Q-学习算法，涂浩等人[11]提出了改进Q-学习的算法，通过使用模拟退火算法，在状态空间、探索策略、报酬函数等方面改进了Q-学习算法的不足，调整了行为树中逻辑行为的最佳执行点,从而产生合适的行为响应。

针对复杂武器装备部件繁多、维修过程复杂导致虚拟维修系统开发周期长的问题,徐文胜等人[12]运用行为树设计模式进行了系统分析、设计和开发，并通过某武器装备行军拉紧器的虚拟维修案例进行了应用验证，结果表明基于行为树模型的设计方法具有良好的扩展性和模型描述清晰度,为各种装备虚拟维修训练系统的仿真决策等提供了参考和借鉴。

通过行为树在仿真决策系统的技术与应用研究，推动了仿真决策体系的构建以及不断优化，提高了决策系统的可用性，解决了依托于知识以及经验建模的局限性。

2.2 游戏

行为树通过透明的逻辑封装来提高状态的模块化，因此重用性高，扩展性良好[13]。除此之外，行为树是面向目标的，每棵行为树与较高层次的任务相联系，且可以与自身相连接。因此可以通过构建小型逻辑子树，然后组合较为复杂的行为逻辑。正因为这些特点，它为大型游戏开发中对游戏角色的逻辑控制提出了新思路，例如，使用行为树的理论作为人工智能控制器的工具[14-16]。比如它最早出现在微软发布的《光晕 2(Halo2)》[17]中，当打击不同种类的团队时，将会展现出不同的符合情节的团队行为。之后Ubisoft Reflections发布的《狂飙：旧金山(Driver:San Francisco)》[18]中也应用了行为树。此外，应用行为树的游戏还包括生命模拟游戏《孢子》和游戏《孤岛危机》[19]。目前，腾讯公司主要利用Behaviac组件对游戏中的NPC、关卡、玩家Avatar等游戏场景进行开发，应用案例有王者荣耀、全民突击、QQ飞车等。

为了提高游戏中画面的质量以及集合建模的真实性与完整性，何汶俊[20]在现有的行为树模型基础之上，通过算法改进，设计了基于Saras算法的行为树模型。该模型用于优化行为树的创建，通过使用一般行为树与使用Saras算法的行为树之间进行比较可发现，使用Sarsa算法的行为树的个体，最终存活率远高于使用一般行为树的个体，游戏AI使用行为树技术进行设计，保证了游戏的稳定性，同时又满足了游戏的扩展性。

为了解决决策逻辑的复杂化背景下行为树的可读性和决策精度的优化问题，蔡礼权[21]通过使用前提节点代替条件节点的条件判断，以及使用模糊逻辑表述模糊的前提条件，可以计算和分析节点的执行期望，提高行为树的决策精度。在实验分析与游戏测试后发现，改进的行为树在提高游戏中智能体的智能水平方面具有较好的表现。将此方法应用到ARPG游戏的AI系统，验证了该行为树在决策逻辑设计中的有效性，改进行为树可以为游戏设计者提供更多的技术选择。

行为树的概念为游戏角色的控制提供了新思路，因为可以先构建任务较小的子行为树，将复杂的逻辑分解开，然后通过子行为树的组合实现对整个游戏角色的控制。且其对于复杂人工智能的扩展性好、重用性高的优点，大大减少了程序开发人员的工作量，提高了开发效率。

2.3 机器人

控制系统和伺服系统是决定机器人性能的重要因素，也是机器人发展的瓶颈之一。因此利用各种AI技术对控制系统的智能化升级一直是学术界研究热点。

Abiyev等人[22]为了提高决策模块的灵活性，采用了模糊逻辑与行为树相结合的方法。提出了基于行为树的决策机制和模糊避障算法，并用于四轮驱动足球机器人的控制。通过实验验证了该算法能在较短的时间内有效地找到新的决策，并在避障过程中缩短了路径长度。

刘潇龙[23]构建了基于行为树的分层行为模型，把传统的行为分为动作、行为、行为树3个层次，来解决机器人行为之间组合不灵活的问题，并通过给行为树添加动态调度节点，赋予其进行非逻辑组合行为的能力。之后设计了一种基于视觉反馈的行为树动作控制算法，利用视觉传感器实时地采集环境信息，对目标进行定位，根据目标位置和机器人自身状态给出动作决策，实现移动机器人从检测到目标后向目标靠近的自主导航以及铲运过程。

传统行为模型的研究重点是行为的选择和决策，其实现过程可以概括为状态输入到行为动作的映射，难以精确表达多层次复杂行为。通过行为树技术进行行为建模可以通过行为的层次划分，按照层级高低和行为复杂程度由低到高、由简到繁进行模型的建立，能有效提高行为决策精度，降低模型的复杂度。

2.4 评估决策系统

评估决策系统是指通过判断某事物的价值、正确性、可行性及可取性的过程，对所需事件进行分析以及综合评价。评估系统在生产生活中被广泛应用，不同的评估系统可以按照需求对目标的某种特性做出分析比较，以支撑用户决策。行为树具有扩展性好、逻辑层次性强的特点，可以有效支撑评估模型的建立与软件开发。

Subagyo等人[24]扩展了行为树的定义，提出了一种新的选择节点，即情绪选择节点。不同于普通行为树按照优先级从高到低的排序选择节点，情绪选择子节点按照情绪权重的大小升序排列，当子节点返回成功时，则停止执行其他子节点。通过构建包含火灾发生时人通常具有的各种情绪的情绪行为树，应用于NPC的行为选择控制。通过实验，证明了情绪在火灾疏散过程中对不同行为的选择有重要的影响。该方法可以帮助专家评估情绪对撤离行为的影响，并针对性地研究火灾撤离方案。

付钰等人[25]以攻击行为树为模型，利用博弈论描述具体的攻防事件场景，分析了不同层面攻击行为的逻辑关系，构建了完整的网络攻防行为树模型。并从攻防行为、网络检测设备、网络防御措施3个方面，扩展了基本攻防行为树，从而提出网络目标攻击成功率算法，从攻防行为概率的角度分析了网络安全态势，来为网络管理者与运营者提供科学的决策依据。

熊海军等人[26]对行为树模型进行了概率扩展并建立了保护系统行为树模型。之后将构建的行为树模型按照文献[27]所述的转化步骤转换为满足PAT语法格式的CSP模型，并给出了行为及系统可靠度计算方法。最后利用过程分析工具对生成的CSP模型进行仿真，分析了系统可靠度随时间的变化规律以及系统的薄弱环节和冗余结构。

除了以上4个方面的应用之外，解方等人[28]通过定义从行为树到UML状态机的转换规则，并利用Eclipse模型框架实现了自然语言需求到统一建模语言的转换，促进了从需求验证到模型驱动软件开发方法的转变。

此外，在评估决策系统中，涉及内部人员监管时，谭良等人[29]提出了一种基于用户行为树的用户行为监管模型。该模型主要采用基于行为树的不良行为过滤算法，通过此算法，可以有效防止合法用户的“开域授权”行为，保证用户行为的可信性。由仿真结果可以看出，基于过滤算法的用户行为监管模型是传统访问控制理论的有益补充，解决了用户监管传统“关口控制”的诸多局限性。

行为树在评估决策系统中的应用可以充分将影响评估决策的因素与评估过程相联系，降低人为因素对于评估过程的干预与影响，提高评估决策的可信度。

3 技术对比

目前，常用的决策方法主要分为3类：基于概率论的决策方法、基于学习的决策方法和基于规则的决策方法。而基于规则的决策方法包括模糊逻辑、有限状态机、层次有限状态机和行为树。与模糊逻辑相比，有限状态机、层次有限状态机和行为树与人的直觉思维相近，层次性更强、决策精度更高，因此应用更加广泛。

3.1 有限状态机

有限状态机(Finite State Machine， FSM)是一种封装了有限的状态和状态之间的转换的数学模型。反映了从系统开始到现在的输入变化。有限状态机的实现包含了动作(Action)、状态(State)、转移(Transition)以及状态机(State Machine)等4个部分。动作指在给定时刻要进行的活动的描述。状态指智能体的某种形态，包含在当前形态下可能会拥有不同的行为和属性，转移表示状态变更，并且必须满足确使转移发生的条件，状态机负责检查转换条件以及确定智能体的当前状态。有限状态机有着简单的优势，采用状态机来实现AI更符合思维的朴素表达。对于一些决策逻辑简单的AI，用状态机更加便捷，但是面对一些复杂的AI逻辑时，随着状态的增多，状态机的迁移表呈现指数式膨胀，这种膨胀直接导致维护成本的急剧增加。同时有限状态机会变得错综复杂，难以构建出一个清晰易扩展的模型。有限状态机简图如图2所示

图2 有限状态机简图

3.2 分层有限状态机

分层有限状态机(Hierarchical Finite State Machine， HFSM)是有限状态机在层次结构上的扩展。它将众多的状态按照类型或者逻辑定义为不同的层次，在一定程度上限制了状态机的转移。不同层次之间的状态转移是相互独立的，且通过分层可以降低跳转链接数，因此一定程度上降低了状态机的复杂度。但是其状态和数据并没有明确的分离，这使得分层有限状态机同样不能描述多个状态的智能体。分层有限状态机简图如图3所示。

图3 分层有限状态机简图

3.3 行为树

行为树是有限状态机和层次有限状态机的改进，它将状态高度模块化，减少了状态转移条件，使状态变成一个行为，从而使模型设计更加容易。行为树把每种情况都抽象成了某个类型的节点，开发者只需要按照规范把各种节点组合连接，并且一个复杂的行为可以通过多个子树连接而成。因此行为树更加具有面向对象的特征，行为模块间的藕合度相对较低，许多通用的子模块在新建行为树时可以被重用以减少工作量。且其建模与实现过程分离，便于设计与开发。但是当决策逻辑复杂时，行为树的组织结构会迅速扩张，这会造成行为树的可读性降低。

以坦克作战时的攻击、躲避、巡逻、调整方向、退出战场5个行为为研究对象，构建FSM、HFSM、BT这3种技术方法下行为之间的关系图，如图4～图6所示。

图4 FSM行为关系图

图5 HFSM行为关系图

图6 BT行为关系图

有限状态机中每个状态之间的变化都需要条件或者事件的触发来形成。层次有限状态机将行为进行了分类，外部状态之间的变化不需要考虑内部状态之间的变化，内部状态之间的变化不需要考虑外部状态的变化。行为树则通过条件节点、顺序节点等来实现状态之间的转变。

综上所述，有限状态机、层次有限状态机和行为树的特点对比如表1所示。

表1 FSM、HFSM和BT对比

属性特点FSMHFSMBT层次性低中高维护性难难易代码耦合度高高低扩展性弱中强复用性差差优决策逻辑和数据未分离未分离分离

4 行为树未来发展趋势

目前，行为树已在诸多领域都得到了应用，但学习能力不足、可读性差、决策精度有限，阻碍了行为树的发展。因而，优化学习能力、提高可读性以及决策精度成为了未来研究的重点。

4.1 机器学习与行为树的结合

虽然行为树已被大量使用，但是由于缺乏学习机制，造成了无法动态的适应决策环境。然而，手动调整行为树通常需要耗费巨大的精力和时间，且不能保证结构的最优化，设计欠佳的行为树，可能导致决策行为的异常或错误，因此需要使用强化学习提高行为树的动态适应性。强化学习(Reinforcement learning)又称增强学习，是机器学习的分支，其具有较好的自适应和学习能力，其把学习看作试探评价的过程，通过与环境交互获得的奖赏来指导行动并选择策略以适应环境，被广泛应用于系统控制[30]。目前行为树与机器学习的结合主要表现为基于Q-learning算法的行为树模型的建立。首先构建基于Q-learning算法的行为树初始化模型，之后对奖励函数进行更新，使Q值表收敛，最后根据Q值表更新行为树节点的Q值，直到行为树节点不再更新为止，完成模型建立。在此基础上，如何进一步改进Q-learning算法或使用更强大的机器学习算法，设计更合理的奖励函数，加速算法收敛至最优值将是未来的研究方向。

4.2 专家系统与行为树的结合

专家系统是一种智能计算机程序系统，其内部含有丰富的特定领域专家水平的知识与经验，构成了经验库，使得人们能够利用专家的知识和解决问题的方法处理各个领域的问题，来弥补纯机器系统的不足。通过专家系统与行为树的结合，又解决了专家系统中有容易产生“局部最优”的弊端。行为树逻辑表达主要通过节点的组合来完成，但是随着决策逻辑的复杂化，行为树的组织结构会急剧扩张，造成可读性和决策经度的下降。如果将一些先验知识以专家系统的形式集成起来，利用专家系统“IF—Then”的产生规则与行为树的条件节点相结合，可以有效降低行为树的复杂度和决策精度。利用专家系统庞大的知识库，基于相似逻辑的不同应用领域的行为树可以实现模块复用，使得行为树的扩展性进一步提高。

4.3 行为树技术应用前景

4.3.1 交互式软件平台

交互式软件平台是用户与系统之间信息交换的媒介，能够实现人们物质世界和虚拟网络的融合。人机交互的过程可以分为4步：1)通过传感器与人接触获得信息，此类信息多为感知信息；2)通过建立模型对感知信息进行识别与分析；3)通过推理将分析结果上升为感性的理解；4)将理解结果通过合理方式表达出来。行为树技术可以被用来构建具体感官的行为模型，然后根据交互场景建立整体的行为分析树模型，来实现信息获取到信息表达的映射转换，成为感知层与应用层信息及行为传递的桥梁。在此基础上行为树技术可以与虚拟现实技术结合，用于单兵作战训练平台、虚拟驾驶舱、虚拟游戏平台的开发。

4.3.2 无人自主系统

智能无人自主系统是人工智能(AI)中最重要的应用之一，其能够通过先进的技术进行操作或管理而不需要人工干预的人工系统。随着AI技术的飞速发展，各种类型的智能无人自主系统也相继出现，并且对人类生活和社会产生着显著的影响。包括无人车、无人机和各种机器人，在不久的将来都可能发展成为智能无人自主系统。目前，提升智能无人系统的智能化和自主化水平是该领域的发展方向。深度学习算法、专家库与行为树的结合在提高控制系统的灵活性、准确性的同时可以有效地解决人机关系。同时行为树复用性好和可扩展性强的优点也便于无人自主系统的群体智能技术的研究。

4.3.3 作战仿真系统

计算机技术的诞生与飞速发展，推动了军事变革的不断深入，以信息化为条件的多兵种联合作战已经成为了现代战争的主要作战样式。但是实战演习和武器装备作战试验的周期长、成本高、灵活性差，不能满足部队的训练与研究。以联合作战和体系仿真为目标的虚拟作战仿真系统可以通过分布式仿真、装备建模、想定制作的方式对装备性能、作战计划、兵力运用、战法等进行研究。但是目前大部分作战仿真系统的作战流程和规则是集成封装于武器装备模型中的，想定制作以后难以对作战规则进行修改，难以实现人在回路的仿真，且作战想定死板，作战仿真数据真实度、可信度有限。如果对作战流程和规则进行逻辑分析，将作战行为过程分为物理系统建模和决策建模。利用行为树技术和智能算法构建独立的基于行为树的指挥决策模块，可以灵活实现战法的制定和决策行为控制，并能通过对行为树的修改设计来实现人在回路的仿真。