一種改進型Q學習算法及其在行為樹中的應用

涂 浩 劉洪星

(武漢理工大學計算機科學與技術學院 湖北 武漢 430063)

一種改進型Q學習算法及其在行為樹中的應用

涂 浩 劉洪星

(武漢理工大學計算機科學與技術學院 湖北 武漢 430063)

游戲中的非玩家角色(NPC)通過學習獲得智能，因此學習算法的設計是一個關鍵問題。提出一種改進型Q學習算法(SA-QL)，它以模擬退火算法為基礎，在狀態空間、探索策略、報酬函數等方面改進了Q學習算法的不足。將該算法運用到行為樹的設計中，使NPC能在游戲過程中實時學習，調整行為樹中邏輯行為的最佳執行點，從而產生合適的行為響應。實驗結果表明，SA-QL算法比傳統Q學習算法效率更高，控制NPC的效果更好。

游戲人工智能 行為決策 Q學習 行為樹

0 引 言

行為樹由于其簡單、靈活和模塊化等優勢，被廣泛用于設計游戲中非玩家角色(NPC)的行為決策。然而，對于大多數行為樹的設計，所有任務的控制細節通常都是手動編碼的，因此開發過程往往花費大量的時間和精力。不好的行為樹設計可能導致NPC行為異常，從而破壞玩家的體驗。在行為樹的設計過程中，需要根據NPC與游戲世界的反饋信號不斷調整其結構，從而使NPC更好地適應環境。Q學習算法具有良好的在線自適應和對非線性系統的學習能力，采用試錯的方式與環境進行交互，根據環境對動作的評價性反饋信號改進行動方案以適應環境。將Q學習算法運用于NPC的行為樹設計是一種可行的方法。然而在具有大規模狀態空間或連續狀態空間的游戲任務中，該方法也面臨著一些問題，其中之一就是在動作選擇時的“探索和利用”問題：如果僅根據當前狀態動作值選擇最優動作，則容易陷入局部最優，而無法得到最優解；如果為了跳出局部最優而選擇非最優的動作，獲取更多的知識，又往往會降低了算法的性能。

目前將Q學習算法應用于游戲人工智能領域的研究還較少。Florez-Puga等[1]將案例推理應用到行為樹中，使得NPC可以從知識庫中動態獲取行為。Ibrahim Mahmoud[2]將HTN應用于NPC的行為決策中，得到了較好的效果。但是這些方法往往過度依賴于經驗數據，需要手動生成經驗記錄。為了減少對于經驗數據的依賴，讓NPC的行為更加智能，關鍵是賦予其學習能力，調節自身動作以更好地適應環境。針對以上問題，本文提出了一種改進型Q學習算法，它是基于模擬退火算法的Q學習算法SA-QL(Simulated Annealing-Q-Learning)，從狀態空間、探索策略、報酬函數等方面改進Q學習算法，利用模擬退火算法中的Metropolis準則控制NPC在學習進程中適當地減少探索次數。然后將SA-QL算法運用到行為樹的設計，最后通過實驗進一步對學習結果進行分析并優化行為樹。實驗結果表明：該方法可以提高Q學習算法的收斂速度，幫助游戲設計者減少在行為樹設計中耗費的精力，實現自動化行為樹設計，并使NPC在游戲過程中實時學習，更好地適應環境，提高了NPC的智能。

1 相關研究

1.1 行為樹

行為樹是由行為節點組成的樹狀結構。行為樹處理周圍游戲世界變化的任務是由條件節點來完成的，這相當于每次遍歷行為樹時，條件節點都向周圍世界發出某種“詢問”，以這種方式來監視游戲世界發生的事情。行為樹中的每個節點表示一個行為，節點是有層次的，子節點由其父節點來控制，從而決定接下來做什么，父節點的類型決定了某種高級控制策略。節點不需要維護向其他節點的轉換，節點的模塊化被大大增強了。在大型的游戲邏輯設計當中，如果需要為多個NPC設計不同的行為樹，可能這些NPC的行為樹在某個子樹處相同。為了避免重復的工作，可以復用這些子樹，在行為樹的某些位置增加單個行為節點或行為子樹。行為樹的選擇器中包含隨機選擇節點和概率選擇節點，若能合理地安排節點的權值，便能較好地實現合理的隨機性[3-5]。模塊化、可復用性、并發等特點使得行為樹有效地降低了NPC行為設計的復雜性。

雖然已被大量的游戲和項目使用，行為樹仍具有以下不足之處：1) 必須在每個行為節點處手動編碼，隨著游戲規模增大，行為樹變得很復雜，并且調試比較困難；2) 缺乏學習機制，無法實現自動行為樹設計。由于以上原因使得行為樹的設計不夠高效。

1.2 Q學習算法

Watkins提出的Q學習算法用于解決不確定環境下的學習問題，通過學習選擇能達到目標的最優動作。Q學習的模型如圖1所示。

圖1 Q學習模型圖

定義Q(s,a)為Agent在狀態s下執行動作a所返回強化信號的累計值函數。Agent通過觀察環境得到狀態s，Agent按策略π選擇動作a并執行，在下一時刻，Agent 收到環境反饋的強化信號(報酬值)并作用于Q(s,a)，更新策略π并達到新狀態。當滿足一定條件，Q(s,a)值會收斂到某一確定值。在做決策時只需要比較s下執行每個動作的Q值，即可明確s下的最優策略，無需考慮s的后續狀態[6-7]。Q(s,a)值定義如下：

Q(s,a)=(1-α)Q(s,a)+α[r+γQ(s′)]

(1)

式中：r為狀態s下執行a動作得到的瞬時報酬值；γ為折扣因子；α表示學習率，Q(s′)為s后續狀態下的最大Q值。

在學習過程中，Agent采用試探的方式與環境交互，得到最優的控制策略。為了避免其動作選擇時的“探索和利用”問題，通常給每個動作設定固定的執行概率，并按照概率對當前非最優動作進行探索，用貪心策略和隨機探索策略相結合的方式分配探索和利用的時間。常用的方法是ε-貪心策略。ε-貪心策略設定具有最高Q值函數的動作被選中的概率為ε，如果該動作沒有被選擇，則從所有動作中隨機地選擇一個動作執行。這種方法在學習開始階段主動探索非最優動作，能避免“局部最優”的問題，取得一定的效果。隨著學習的不斷深入，Agent所取得的知識趨于精確，應減少對非最優動作的探索，此時ε-貪心策略仍以不變的概率探索非最優動作，會造成不必要的探索，影響Q學習算法的收斂速度。

2 SA-QL算法

為了減少在學習知識趨于精確之后的探索次數，本文將模擬退火算法應用于Q學習的動作選擇策略中，提出了SA-QL算法。模擬退火算法可以保證在追求全局最優解的同時，避免陷入局部最優[8]。該算法主要根據Metropolis準則對應的轉移概率來決定是否接受從解到新解的局部變化。由于模擬退火算法不完全拒絕惡化解，使得它可以跳出局部最優解，避免陷入局部搜索。隨著學習的深入，通過調整溫度等參數的變化來自動減少Q學習中的探索次數，可有效平衡“探索-利用”問題。SA-QL算法描述如下：

輸入：動作集合A(s)，<狀態-動作>的值函數Q(s,a)；初始溫度temperature；學習率α，報酬函數r，折扣因子γ。

輸出：優化的<狀態-動作>的值函數Q(s,a)。

處理過程：

1．選擇待訓練的狀態s，當+前動作為ap；

3．執行下一步動作，更新Q(s,a)和狀態動作:

Q(s,a)=(1-α)Q(s,a)+α[r+γQ(s′)];s=s′;ap=ar

4．若s不是終止狀態，則轉至第2步；

5．若Q(s,a)收斂，算法結束;否則，依等比降溫策略重新計算temperature，轉至第2步。

該算法改善了基于ε-貪心算法的Q學習算法中由于ε固定不變帶來的收斂速度慢問題，在學習過程中，隨著溫度的降低，Agent探索次數將隨之減少，最終幾乎不存在探索，從而提高了算法的性能。

3 基于SA-QL算法的行為樹

在行為樹的設計中應用SA-QL算法，將經SA-QL算法優化的<狀態-動作>的值函數Q(s,a)運用到行為樹的設計中，可在構建行為樹時，減少剛開始時需要設計的節點，特別是條件節點，并能調整邏輯行為的最佳執行點，從而對整個行為樹進行重排和優化。

SA-QL算法應用在在行為樹構建的預處理階段。首先分析行為樹并找到最深的順序節點，這些節點將作為學習中的動作，在Q值表中建立對應的Q值。為了支持在線學習，將生成的Q值表根據動作劃分為相應的Q值子表。子表根據Q值從大到小進行排序，進而得到Q條件節點(動作的狀態允許列表)代替之前的條件節點。如圖2所示。后續學習過程將根據報酬更新Q值，然后采用相應的動作選擇策略。隨著學習的深入，將Q條件節點中的狀態過濾，只剩下部分高Q值的對應狀態。

圖2 將Q值信息整合到行為樹中

在行為樹的學習過程中還要用到Q條件節點中的最大Q值。如圖3所示，以最大的Q值替換其父節點的Q值，并且重排行為樹，使節點的子樹從左至右按照子樹的Q值從大到小排列。重排行為樹使得行為節點之間的執行順序更加合理，便于找到邏輯行為的最佳執行點。

按照上述方式遞歸至根節點，完成重排行為樹。這里不必像一般行為樹編輯器一樣手動地去修改節點，SA-QL算法學習過程中會自動重排行為樹，重排后的行為樹的執行與原行為樹的執行類似。只是在執行到Q條件節點的時候，需要在該動作節點的狀態允許列表查找當前狀態，如果列表中存在對應狀態則執行后續子節點，否則返回失敗狀態。

4 實驗與結果分析

4.1 實驗過程

實驗平臺采用一款跨平臺的專業游戲引擎Unity。在一個簡單地圖中進行五對五的NPC對戰實驗。 NPC的初始位置是隨機分布在地圖中，以一方NPC全部被消滅或執行超時作為實驗結束標志。為了比較兩種算法的收斂速度，在實驗過程中分別采用傳統Q學習算法(以ε-貪心算法作為動作選擇策略)和SA-QL算法重排NPC的行為樹。NPC的初始行為樹如圖4所示。

4.2 狀態和動作

在理論上，Q學習以所有狀態完全收斂，獲得全狀態空間的最優策略為學習目標。Q學習狀態收斂所需的探索次數隨狀態空間和動作空間的增加呈指數增長。在實際控制中，Q學習不可能遍歷系統所有狀態，因為對連續的環境變量的遍歷，會造成“維數災難”的問題。

實驗對狀態空間和動作空間進行泛化，通過一定程度地犧牲控制精度來提高算法收斂速度。利用合適的知識表示設計狀態聚類或狀態空間離散化的方法，對環境因素進行模糊化和離散化處理，并通過建立Q值函數，狀態-動作模型實現狀態空間和動作空間的泛化，減少Q學習所需探索和學習的狀態空間，從而加快學習過程的收斂速度。

在根據經驗數據初始化Q值表時，考慮了以下幾點規則：

1) 行為節點允許的狀態對應的Q值必須大于0；

2) 同一行為節點允許的狀態數目不易過多；

3) 盡量減小同一動作的允許狀態的Q值的差距。

NPC的狀態空間主要由血量HP，離最近加血處的距離Db，離最近敵人的距離De，是否正在被攻擊IsAttacked四個方面環境因素構成。相應環境因素經模糊化和離散化處理后如下：

? 血量HP：(none，low，medium，high)；

? 離最近加血處的距離Db：(none，near，medium，far)；

? 離最近敵人的距離De：(none，near，medium，far)；

? 是否正在被攻擊IsAttacked：(yes，no)。

血量中的none表示Agent已被消滅，距離為none表示沒有察覺或距離過遠。

NPC的主要行為定義如下：

? 尋覓加血：尋找并移至加血處，獲取加血效果；

? 群聚：朝著隊友聚集的方向移動；

? 尋找敵人：如果沒有找到敵人的位置，就調整方向以找到敵人的位置；

? 交戰：與敵人交戰；

? 漫步：在地圖上一定范圍隨機移動；

? 逃跑：朝著一個遠離敵人的方向逃跑。

4.3 報酬函數

Q學習狀態收斂所需的探索次數與該狀態報酬值距離收斂報酬值的步長呈指數關系。為了加快算法的收斂速度，實驗減小動作的報酬函數邊界，報酬信號將結合先驗知識和學習更新過程中的效果，以加權的方式綜合報酬函數。

為了讓NPC的行為選擇符合人類認知的行為邏輯，在設計報酬函數時，狀態離目標狀態越近，執行動作到達該狀態的報酬值越高。表1是根據先驗知識制定<狀態-動作>報酬函數表。記NPC在狀態s下執行動作a的報酬值為R1(s,a),未出現的情況默認報酬函數值為0。表1中符號定義為：L=low；M= medium；H=high；N=near；F=far。同時，報酬函數結合學習過程中的報酬R2(NPC血量增加，獎勵；NPC血量減少，懲罰；NPC消滅敵人，獎勵；NPC被消滅，懲罰)。

表1 先驗知識<狀態-動作>報酬函數表

綜合考慮以上信息，以加權的方法得到報酬函數：R=ω1·R1+ω2·R2，其中:ω1、ω2為對應的加權系數，均大于或等于0且兩者之和為1。

4.4 實驗結果分析

重排后的行為樹如圖5所示。可以看出重排后的行為樹與初始行為樹的不同，學習的結果傾向于游蕩和群聚對NPC生存下來的目標作用較小。另一個變化是攻擊行為子樹被賦予更高的優先級，撤退的優先級高于攻擊，說明NPC更傾向于被動攻擊。下面從對戰結果中驗證重排后行為樹的合理性。

圖5 重排后的行為樹

圖6顯示了實驗結果，每組實驗進行5次對戰，記錄以下結果：生存下來的NPC數量、生存下來NPC的血量，實驗得分由二者綜合所得。根據實驗結果可知，SA-QL算法的收斂速度明顯比傳統Q學習算法快。Q學習本身強調采用試錯的方式與環境進行交互，根據環境對動作的評價性反饋信號改進行動方案以適應環境。SA-QL算法可以在與環境的不斷交互中更新狀態動作值函數，改進動作選擇策略，隨著學習的不斷深入，該方法能有效地減少探索次數，加快學習的收斂速度。從實驗結果中還可以看出行為樹重排之后的合理性，將SA-QL算法應用于NPC的行為樹設計中可實現行為樹的自動重排，調整其邏輯行為的最佳執行點，使得NPC的行為更加智能、擬人化，這對于游戲中的NPC行為設計有一定的實用價值。

圖6 兩種算法的實驗得分

5 結 語

本文研究了游戲人工智能中NPC的行為決策問題，以模擬退火算法為基礎，提出了一種改進型Q學習算法，并將其應用到行為樹的構建當中。實驗結果表明，該方法在行為樹的設計上為游戲設計者帶來諸多方便，能幫助確定NPC邏輯行為的最佳執行點，提高Q學習算法的收斂速度，實現自動化的行為樹設計，讓NPC表現得更加智能。為了進一步優化Q學習算法在行為樹中的效果，在結合模擬退火算法和Q學習算法的過程中，如何選擇合理的降溫策略以及Q學習算法的值函數，是下一步的研究方向。

[1] Puga G F,Gómez-Martín M A,Díaz-Agudo B,et al.Dynamic Expansion of Behaviour Trees[C]//Artificial Intelligence and Interactive Digital Entertainment Conference,October 22-24,2008,Stanford,California,USA.2008.

[2] Mahmoud I M,Li L,Wloka D,et al.Believable NPCs in serious games:HTN planning approach based on visual perception[C]//Computational Intelligence and Games.IEEE,2014:1-8.

[3] Kyaw A S,Peters C,Swe T N.Unity 4.x Game AI Programming[M].Packt Publishing,2013.

[4] Robertson G,Watson I.Building behavior trees from observations in real-time strategy games[C]//International Symposium on Innovations in Intelligent Systems and Applications.IEEE,2015:1-7.

[5] Dey R,Child C.QL-BT:Enhancing behaviour tree design and implementation with Q-learning[C]//Computational Intelligence in Games.IEEE,2013:1-8.

[6] 姜文軍.網絡游戲中人工智能的研究及應用[D].上海交通大學,2013.

[7] Nicolau M,Perez-Liebana D,O’Neill M,et al.Evolutionary Behavior Tree Approaches for Navigating Platform Games[J].IEEE Transactions on Computational Intelligence & Ai in Games,2016,9(3):227-238.

[8] 李炎武,陳渝,曾慶維.基于強化學習的非玩家角色行為改進[J].四川大學學報(自然科學版),2014,51(5):915-920.

ANIMPROVEDQ-LEARNINGALGORITHMANDITSAPPLICATIONINBEHAVIORTREE

Tu Hao Liu Hongxing

(CollegeofComputerScienceandTechnology,WuhanUniversityofTechnology,Wuhan430063,Hubei,China)

The non-player character (NPC) in a game gains intelligence by learning, so the design of the learning algorithm becomes the key issue. In this paper, an improved Q-learning algorithm (SA-QL) was proposed. Based on simulated annealing algorithm, the Q-learning algorithm was improved in the aspects of state space, exploration strategy and reward function. Then the algorithm was applied to the design of behaviour tree, so that the NPC could learn and adjust the best execution point of the logical behaviour in the process of the game in real time, and produced the appropriate behavior response. Experimental results showed that the SA-QL algorithm was more efficient than the traditional Q-learning algorithm, and had better control effect on NPC.

Game AI Behaviour decision Q-learning Behaviour tree

2016-12-06。國家自然科學基金項目(61472294)；中央高校基本科研業務費基金項目(15521004)。涂浩，碩士，主研領域：機器學習，信息系統集成。劉洪星，教授。

TP3

A

10.3969/j.issn.1000-386x.2017.12.045