陈妙云，王 雷，丁治强

(中国科学技术大学信息科技学院，安徽 合肥 230031)

1 引言

多智能体仿真是当前仿真的主流研究方法，应用在军事，交通，社会安全娱乐游戏等广泛领域[1]。在多智能体仿真的过程中，智能体需要对不同场景下的不同事件进行决策，能否合理决策是判断仿真成功与否的重要依据。基于有限状态机的决策模型具有决策过程较为僵化的缺点[2]，而模糊状态机[3]的优点在于随机性较好，但是其场景适应性差。行为树决策模型是当前智能体研究中重要的行为模型，广泛应用于仿真领域[4]。其优点在于提供了丰富的流程控制方法，可以更加直观的看到状态的改变，还具有扩展性好，易于编辑的特点。但目前基于行为树决策模型的多智能体仿真研究还有如下不足：

● 行为树的设计需要对不同的状态进行判断[5]，涉及到大量的条件节点。当人物的行为逻辑较为复杂时，行为树会非常庞大，需要进行大量的调试工作，极大的加大了开发难度；

● 需要对单个物体或人物的行为树进行设计，大大降低了开发效率；

● 不合理的行为树设计会导致仿真时出现异常。

本文通过引入Q-Learning算法来解决行为树的上述不足。Q-Learning具有优秀的自学习和自适应能力[6]，可以用于实现行为树的自动化设计。但是传统的ε贪心Q-learning[7]为了避免陷入局部最优的陷阱，需要对次优的动作进行探索，随着智能体学习经验的不断增加会产生大量的无效计算，存在难以收敛的问题。

基于以上问题，本文提出了一种新的人群仿真多智能体决策模型，该模型对传统的ε贪心Q-learning算法进行了改进，并引入了行为树，使得模型能够对行为树节点进行自动重排，实现自动化调试。

2 多步Q-Learning

传统ε贪心Q-Learning算法[8]是一种单步时序差分算法，在估计状态动作价值时只考虑下一步的信息，而忽略了未来决策对当前的影响，因此具有低预见性的缺点。Q(λ)学习算法[9]是一种新的强化学习算法，它在估计状态动作价值时考虑了将来的所有状态奖励，极大的提高了算法的预见能力。但当状态-动作空间规模较大时，该算法的计算复杂度过高。基于该缺点，Nachum[10]提出了一种多步Q-Learning算法，它在更新Q值时考虑了将来n步的信息，极大的降低了算法的计算复杂度，加快收敛；同时又增强了智能体的预见能力，使其决策更加合理。

其算法描述如算法1所示：

输入:初始 Q表,S[m],A[m],E[m],E'[m]输出:收敛的Q值表For each episodet=1, 初始化 siFor each step of episode采取动作at, 得到收益rt,st→st+1;et'=rt+γ·Vt(st+1)-Qt(st,at)et=rt+γ·Vt(st+1)-Vt(st)Update Array S,A,E,E' if(t

在算法1中，输入数组的长度用m来表示，m个步骤的状态、动作、e和e′ 分别用数组S[m]，A[m]，E[m]和E′[m]来存储。当t

3 改进的多步Q-Learning算法设计

多步Q-Learning算法的动作选择是基于ε贪心策略，会有一定的概率选择非最优动作，而这概率保持不变会使得在算法学习后期产生许多无效的计算，导致算法收敛速度变慢，性能下降。

除此之外，其值函数更新策略也会降低算法的收敛速度。当采取动作从环境中得到收益之后，算法只是对当前状态-动作对的Q值进行更新。在学习过程中，该状态动作对会重复进行更新。

针对当前多步Q-learning难以收敛的问题，本文使用模拟退火算法中的Metropolis准则改进了多步Q-learning算法的动作选择策略，使用动态规划改进了值函数的更新策略，提出了一种改进的多步Q-learning算法。

3.1 动作选择策略的设计

在传统的Q-Learning算法中使用ε贪心策略进行动作选择，会以ε的概率选择次优动作。但是当智能体学习到足够多的经验后，ε的值仍然不发生改变，导致产生许多无效的计算，降低算法的收敛速度。

基于以上分析，本算法改进了ε贪心动作选择策略，随着学习过程的不断迭代，ε值会逐渐降低。在学习初期，智能体经验不足，因此选择较大的ε值对环境进行探索。随着智能体的经验不断增加，ε值逐渐减小，智能体更趋于利用而非探索。而模拟退火算法[14]通过降温策略来改变转移概率，可以逐渐降低选择次优动作的概率。因此本文将Metropolis准则应用到动作选择策略中。

Peng[15]将Metropolis准则应用到传统的单步Q-Learning算法中，有效的平衡了探索和利用的问题。

本文采用模拟退火动作算法来改进多步Q-learning算法中的动作选择策略，动作选择概率如式(3)所示：

p(ap→ar)=

(3)

式中，ar和ap分别表示随机选择策略和贪婪选择策略对应的动作，当Q(s，ar)≤Q(s，ap)时，选择ar动作进行探索，通过探索非最优动作提升算法的性能，当Q(s，ar)>Q(s，ap)时，以exp[(Q(s，ap)-Q(s，ar))/T]的概率探索非最优动作，T是温度控制参数，即T值较大时，探索的概率会比较大，当T值趋向于0时，不在探索非最优动作。T值的选取借鉴了模拟退火算法中的温度降温策略，其公式如(4)所示

T(N)=T0exp(-AN1/M)

(4)

T0，N，A，M分别表示初始的温度，算法迭代的次数，指定的常数和待反演参数的个数。上式也可表示为：

T(N)=T0aN1/M

(5)

其中α∈(0.7，1)，1/M通常取为1或0.5。在算法的起始阶段，T一般取较大的值，依据式(3)可得p(ap=ar)较大，此时选择随机动作的概率较大。随着不断迭代，依据式(4)T值会逐渐降低，即会进行降温处理，使得p(ap=ar)变小，则选择非最优动作的概率变小，有利于在Q-Learning算法的后期更倾向于选择最优动作，随着迭代的进行，模型不断逼近收敛状态，T值也逐渐接近0。此时模型的动作选择策略退化为贪心策略，即不再进行探索，每次动作选择只选最优动作。通过上述分析可以看到，使用模拟退火动作选择策略可以较好的实现ε值的自适应变化，加速了Q-Learning算法的收敛。

基于Metropolis准则的动作选择策略流程图如图1所示。

图1 基于Metropolis准则的动作选择流程

3.2 值函数更新策略

在多步Q-Learning算法的学习过程中，智能体根据自身状态以及动作选择策略选择动作，并加以执行，从环境中得到收益。但是每一步只能在Q值表中更新当前状态-动作对的Q值。当Q值表没有收敛到最优时，每个状态下同一个动作会反复执行，这也造成了多步Q-learning算法的难以收敛。Shilova[16]等提出了逆序的思想对传统的单步Q-learning算法进行了改进，可以加快收敛。原因在于对学习到的状态动作对进行逆序更新避免了相同状态动作对的重复执行。智能体根据自身状态选择动作加以执行并从环境中得到收益，更新Q值。动态规划也是基于逆序的思想，本文中用动态规划来对Q值进行更新。

本文算法使用邻接链表来存储到达不同状态前的状态动作对，以达到降低时间复杂度的效果。当智能体采取动作进入到下一状态后，邻接链表进行相应的更新，比如智能体经过(s1，a1)， (s2，a2)之后到达状态s3，那么此时在邻接链表中s3对应的就是{(s1，a1)， (s2，a2)}。同时对邻接链表的状态进行逆序更新。更新步骤如图2所示。智能体根据当前状态选择动作并执行从环境中得到奖励后，根据Q值更新公式更新当前状态动作对的Q值，判断当前状态动作对的Q值是否为该状态下所有动作的最大Q值，如果是，就对邻接表中当前状态下的状态动作集的Q值进行逆序更新。

图2 动态规划逆序更新Q值

3.3 改进的多步Q-Learning算法

本算法将Metropolis准则和动态规划分别应用到动作选择策略和值更新策略中，提出了改进的多步Q-Learning算法。本算法在每一episode的开始时初始化参数和Q值表，建立邻接链表。在每一step中，智能体根据当前状态 st和基于Metropolis准则的动作选择策略选择动作at并且执行，从环境中得到相应的奖励r，转移到st+1状态，然后根据基于动态规划思想的值更新策略对Q值表以及邻接链表进行更新。当到达终止状态时结束当前episode的学习。重新开始下一episode的学习。

本算法流程如图3所示。

图3 改进的多步Q-Learning算法

其中存储状态，动作，e和e′的四个数组分别是S[k]，A[k]，E[k]和E′[k]

4 人群仿真系统设计与实现

4.1 模型概述

本系统模型描述如下：

Step1：初始化行为树，动作空间，状态空间，状态转移表，奖励表和Q值表。

Step2：应用上述介绍的改进的多步Q-learning算法学习得到最终收敛的Q值表。然后根据不同的动作将收敛的Q值表划分成不同的状态允许子表，如图4所示。

Step3：将得到的不同动作的状态允许子表替换行为树的条件节点，并输出不同动作下获得的最大Q值；

Step4：根据不同动作节点得到的最大Q值对行为树进行重排；

Step5：输出重排后的Q-learning行为树。

步骤1是初始化行为树，其中动作节点代表智能体可以采取的动作，条件节点对智能体所处状态进行判断。状态空间，动作空间，状态转移表和奖励表都是人为给定的。

系统输入是一棵普通的行为树，输出是自动重排后的Q-Learning行为树。该系统首先应用上述介绍的改进的多步Q-learning算法得到最终收敛的Q值表。然后对初始行为树进行dfs搜索找到所有的动作集合，根据动作集合的动作将Q值表分割成不同的状态Q值集合，并将其替换掉行为树中的条件节点，并将最大的Q值填入动作节点对应的顺序节点中。从而行为树在选择动作的时候就不需要进行复杂的条件判断，只需判断当前状态是否存在动作节点对应的状态允许列表中即可，如果存在，就采取该动作。改造的Q-Learning行为树如图4所示。得到了含有Q值和状态允许列表的行为树后，根据动作节点对应的状态集合中的最大Q值对行为树进行重排序，得到的行为树即为系统输出。

以下内容将对step2，3，4分别进行具体描述。

4.2 行为树改造

应用本文提出的改进的多步Q-learning算法学习到收敛的Q值表之后，根据不同的动作将得到的Q值表分割成状态-Q值集合，对每一个集合中的状态根据Q值从大到小排序，根据实验情况保留一定比例的高Q值状态，命名为状态允许列表，用得到的不同动作对应的状态允许列表替换行为树中的条件节点，如图4所示。

图4 将Q值信息整合到行为树

4.3 选取最大Q值

状态允许列表中去掉Q值小于0的状态，并保留一定比例的高Q值状态。

算法2是选取最大Q值的伪代码：

输入:动作集合A,状态集合S,Q值表输出:输出动作-最大Q值for each a in Afor each s in Sq=Q.getQ(s,a)if q > 0 act_states[a].insert(s)sort(act_states[a]) in reverse orderact_states.remove[size*(1-x):]res[a]=act_states[0]

4.4 行为树拓扑重排序

得到含有Q值的行为树后，根据Q值大小对行为树进行重排序。Q行为树中节点的Q值自上而下自左而右依次减小，如算法3所示。

算法3是行为树重排的伪代码

输入:初始Q-tree输出:已重排Q-treefor each node in bottom layerif node.value > fa_node.value swap(node, fa_node) down(node)sort(node.childs)

图5为具体的重排过程。行为树对应节点的Q值从上往下，从左往右依次减少。重排后得到决策更加合理的行为树

图5 根据Q 值重排行为树

5 实验设计与仿真分析

本文将改进的多步Q-Learning算法命名为DP-SAMQ(Dynamic Programming Simulated Annealing Multi-step Q-learning)算法。本文的实验环境基于手动搭建的人群仿真场景，场景中部署了一定的监控设备。

在Unity 3D中仿照真实人物构造了相应的3d模型，并导入相应的运动动画，使其显示更加逼真。

5.1 实验设计

实验的场景基于城市中的一座广场，其中重要人物正在视察，安保人员的任务是保护重要人物的安全，嫌疑人的任务是找到攻击重要人物。

本实验选择基于模拟退火的单步Q-Learning算法(SAMQ)以及采用ε贪心策略的(GQ)算法与本文的DP-SAMQ算法进行对比实验。实验中的参数设置如下：折扣因子γ设置为0.9，权重参数λ设置为0.85，学习率α设置为0.4，初始温度T0设置为500。

Q-Learning算法涉及智能体的状态，动作，状态转移，奖励，之后Q-Learning算法才能开始具体的学习。所以接下来将详细介绍嫌疑人和安保人员的状态空间，动作空间，状态转移和奖励的设计。

5.1.1 状态空间

安保人员的状态空间：(生命值lv，与嫌疑人距离dis_em， 与同伴距离dis_pt， 是否被攻击hited)

生命值lv(0-1000)：高(500-1000)，中 (200-500)，低(0-200)，死亡(0)；

是否被攻击(hited)：T/F；

与嫌疑人距离(dis_em)：近(0-50)，中 (50-100)，远(>100)；

与同伴距离(dis_pt)：近(0-50)，中(50-100)，远(>100)；

为了避免维数灾难，对距离和健康值进行了离散化，模糊化处理。

危险分子的状态空间： (生命值lv，发现重要人物fl， 被安保人员发现fd，发现安保人员fp，与安保人员距离dis_pl)。

生命值lv(0-1000)：高(500-1000)，中 (200-500)，低(0-200)，死亡(0)；

发现重要人物(fl)： T/F;

是否被安保人员发现(fd)： T/F;

发现安保人员(fp)： T/F；

与安保人员距离(dis_pl)：近(0-50)，中(50-100)，远(>100)；

5.1.2 行为空间

安保人员的行为空间：(追击/pa，逃跑/ma，巡视/sa，寻找伙伴/fc，寻找嫌疑人/fe)。

危险分子的行为空间：(自首/sr，逃跑/ma，攻击重要人物/al，寻找重要人物/fl，攻击安保人员/ap)

5.1.3 动作选择策略

采用如上介绍的基于Metropolis准则的动作选择策略。

5.1.4 奖励表

表1 安保人员的奖励表

表2 危险分子的奖励表

除表1中给出的状态-动作对有奖励值之外，其它状态-动作对奖励值均设置为0。

5.1.5 行为树

图6 安保人员初始行为树

图7 嫌疑人初始行为树

图8 基于DP-SAMQ的行为树模型得到的安保人员的行为树

图9 基于DP-SAMQ的行为树模型得到的嫌疑人行为树

本实验中安保人员和嫌疑人的行为树设计如上。重排后行为树由多棵子树组成，从上到下从左到右Q值逐渐降低，输入状态，输出具有最大Q值的动作。嫌疑人初始行为树中存在的不合理地方在于当危险分子的健康值小于200且与安保人员的距离大于100时，应该优先逃跑而不是继续攻击安保人员。经过DP-SAMQ算法重排后的嫌疑人行为树则有较好的表现。

接下来的实验需要找到改进后多步Q-learning的最优n值。本文接下来的实验分成两组。第一组是测试不同n值下算法的收敛速度，找到最佳n值，第二组验证应用了本文算法的行为树的合理性。

5.2 n值的确定

从算法1中可以看出该算法的时间复杂度为O(Episode_num*step_num)。

n值决定了智能体的预见能力，n值越大，预见能力越高，但是计算复杂度同时也加大，n值越小，虽然计算复杂度降低，但是预见能力也越低。因此需要权衡n的取值。

实验过程中采取了不同的n值进行实验，分别取了n=10，20，..，100，在实验中发现当n>20的时候，算法的收敛速度明显下降，因此本文只给出n为10，20时算法的收敛曲线。每次实验运行1000个Episode。横坐标为episode_num/40，纵坐标为40个episode的steps_num的平均值。

图10 不同n值下DP-SAMQ算法的收敛曲线

从图中可以看出，当n=10的时候，算法收敛速度更快，最终steps_num收敛为17，而n=20时，steps_num最终收敛为28。因此n值最终取10。

5.3 实验一

下图是GQ/SAQ与本文算法(DPSAMQ)的对比效果图，纵坐标为log(steps_num)，表示最终算法收敛时的步骤数。横坐标为实验的次数，总共是100次实验。

图11 GQ/SAQ/DPSAMQ对比实验

从图中可看出本文DP-SAMQ算法收敛所需迭代次数相较GQ和SAQ算法有非常明显的下降，算法性能显著提高。

5.4 实验二

从图12/13的对比可看出，基于本文算法(DP-SAMQ)训练出来的嫌疑人在面临安保人员攻击时更倾向于逃跑，这是符合嫌疑人的行为逻辑的。而且行为树在选择动作时是基于dfs算法搜索的，从上到下从左到右的动作优先级逐渐降低，因此当嫌疑人被安保人员发现时优先选择逃跑而不是主动攻击。

初始行为树仿真结果如图12所示。

图12 初始行为树仿真结果

可以发现实验中嫌疑人被安保人员发现时选择进一步接近并攻击安保人员。

基于DP-SAMQ算法学习得到的行为树仿真结果如图13所示。

图13 基于DP-SAMQ的行为树模型仿真结果

从图中可看出，当嫌疑人被安保人员发现时，优先选择逃跑。从以上对比实验可看出，基于DP-SAMQ训练得到的行为树决策模型更加合理，证明了该算法的合理性

6 结语

针对目前传统的单步Q-learning算法预见性低，难以收敛以及Q(λ)算法计算复杂度过大等缺点，本文引入了模拟退火算法中Metropolis准则对多步Q-learning算法中的动作选择策略进行改进，使得算法能够随着学习过程自适应改变次优动作的选择概率。并且本文还引入了动态规划来改进了Q值函数的更新策略，极大地加快了算法的收敛；并且本文还针对目前基于行为树的智能体决策模型存在人工开发效率低的缺点，将改进的多步Q-leaning算法应用到行为树决策模型中，实现了行为树的自动化设计和优化；通过实验也证明了本文算法(DP-SAMQ)的合理性与有效性。但是本文实验仍是基于单智能体，现实生活中更多是多智能体场景，因此在进一步的工作中会考虑引入多智能体。