改進的Q-Learning算法及其在路徑規劃中的應用

2021-01-21 07:51:12毛國君顧世民

太原理工大學學報 2021年1期

毛國君，顧世民

(福建工程學院機器學習與智能科學研究所，福州 350118)

人類知識的獲取是通過感知環境(Environment)并與之交互來完成的，因此所謂的智能學習就是智能體(Agent)不斷適應環境來完善自己的過程。強化學習(reinforcement learning,RL)是機器學習的方法論之一，用于描述和解決智能體在與環境的交互過程中如何學習和優化策略的問題[1]。事實上，許多應用中的環境是動態變化和不確定性的，如機器人的路徑規劃問題，智能體必須在不確定性環境中主動地對周圍環境進行探索[2-3]。在探索過程中不斷地認知環境，形成適應環境的正確行為。

強化學習不同于目前廣泛研究的監督學習(supervised learning)和無監督學習(unsupervised learning)，它的學習不是被動地從已有數據中進行歸納或提取，而是一個主動適應環境并進行自我完善的過程。強化學習是從計算機科學、數學、神經學等多個相關學科發展而來的，已經成為機器學習的主要分支之一[4-5]。由于強化學習強調在環境變化情況下智能體的主動學習，因此近年受到廣泛關注，并在機器人控制以及智能計算等領域得到應用。

基本的強化學習思想是通過智能體對當前環境狀態的感知，并對可能采取的動作(Action)獲得的回報(Reward))進行評價來完成的。圖1給出了強化學習的基本模型[6]。

圖1 強化學習的基本模型Fig.1 Reinforcement learning model

強化學習是一個“探索-利用”的迭代過程[6-7]。首先，智能體通過感知環境的當前狀態，并采取某一個動作來探索環境，探索的結果一般以某種形式的獎勵或者回報來表示。然后，對已經獲得的回報進行評價，尋找在當前狀態下的一個最優的動作加以利用。當然，“探索-利用”是一個不斷反復循環的過程，直到獲得滿意的最終策略。

不同的強化學習算法在“探索”“利用”方法及其融合機制上會有所差異。就強化學習的經典算法Q-Learning而言，在探索階段所用的方法是ε-貪心(ε-greedy)方法，即優先利用最大Q值對應的動作來向前推進探索。

傳統的Q-Learning存在探索效率低下的致命問題[8]。實際上，探索與利用是強化學習的兩個不可分割的部分，同時也是一對矛盾共同體。當智能體過多地探索環境時必然會導致效率下降，但當智能體在探索不充分情況下盲目地相信某種決策而加以利用時也會增加后續的探索代價。因此，制定一個合適的探索計劃來平衡探索和利用的代價，以便在正確決策的同時盡可能地提高收斂速度，是強化學習的一個重要任務。

本文針對傳統的Q-Learning算法收斂速度慢的問題，提出一個改進算法ε-Q-Learning.基本思想是通過動態地改變搜索因子參數來快速適應環境的變化，既可以提高探索效率，也可以避免陷入無效的局部搜索，因而提高全局優化的可能性。

1 相關工作

路徑規劃(Path planning)是機器人研究領域的一個關鍵性的工作，同時也是許多應用(如電子游戲、無人駕駛等)的基礎。1986年，Khatib第一次提出用人工勢場法(Artificial potential field method)解決了機器人躲避障礙物的問題，此后這個方法也成為許多路徑規劃研究與應用的基礎[9]。然而，隨著人工智能技術的研究進展，利用智能學習方法來解決路徑規劃問題成為新的發展趨勢，其中強化學習扮演了十分重要的角色。例如：利用BP神經網絡和Q-Learning算法，在未知環境下的自主避障問題被研究[10]；將模糊邏輯引入到強化學習中[11]；Agent的自主強化學習等[12-14]。我國學者也在機器人、無人機等強化學習模型方面開展了卓有成效的工作[15-16]。

此外，強化學習的模型或者算法基本都是基于馬爾可夫(Markov)屬性構造的[4-5]。馬爾可夫屬性是指一個系統下的狀態只與當前狀態有關，而與更早之前的狀態無關，即公式(1)：

P(st+1|st,st-1…s1)=P(st+1|st) .

(1)

基本的馬爾可夫決策(MDP)[4]模型由一個四元組來刻畫：

其中，S表示環境中的所有狀態集合；A表示是作用于環境的所有可能動作集合；P表示狀態之間的轉移概率；R表示采取某一動作到達下一狀態后的回報。

基于MDP模型，目前的強化學習算法主要是圍繞著回報的評價機制、狀態與動作的影響估算等方面進行研究和實踐，因而出現了不同的解決模型，也在算法的可用性等方面進行有效探索[17-18]。

目前的典型強化學習算法大致有3種，分別為Q-Learning算法、Sarsa算法和TD算法[4,16-17]。分析這些典型算法的理論基礎，基本上是由2個實體和4個評價機制組成的。當然在不同的強化學習算法中可能依賴的評價機制或者函數有所側重。

實體主要有環境和智能體。

1) 環境是學習的對象。一般而言，在一個確定時刻，一個環境一定有一個確定的狀態(State)，但是當智能體在該環境中活動后，其狀態就會發生改變。因此智能體必須對其活動結果(下一個狀態)有一個估算，并借此形成下一步的決策。

2) 智能體則是學習者。一般而言，智能體是通過采取動作(Action)來適應環境的。就是說，智能體需要通過不斷地嘗試某狀態下可能動作的效果，來認知環境并采取恰當的動作來繼續探索。

評價機制包括4個基本方面。

1.1 策略π

在強化學習過程中，智能體在某個狀態采取什么樣的動作到下一個狀態是由策略控制的。簡單地說，策略就是從狀態到動作的映射。特別地，當環境存在障礙或者陷阱時，策略就必須保證下個動作不能碰到障礙或者掉入陷阱。策略的好壞決定了智能體行動的好壞，進而決定了整個算法的學習質量。

1.2 回報R(s)

回報R(s)是智能體處在狀態s下可能形成正確決策的可能性：可能性大則回報值就大，反之亦然。強化學習的任務就是不斷地探索來改變狀態，達到尋優目的。因此，一個狀態s的回報是在不斷地探索中加以完善的。

給定一個探索的時間序列<1,2,…,t,t+1,…>,設當前時間為t，根據馬爾可夫屬性，則R(s)的理論值就是：

Rt(s)←f(Rt(s),Rt+1(s),…) .

(2)

其中，Rt(s)為狀態s在t時刻的回報，f則代表對向前探索的回報值的綜合評價函數。

基于回報估計是強化學習的理論基礎，也是構建強化學習算法的基本依據。當然，不同的算法在實現路徑上會有不同，在回報值的計算及其評價函數的設計上會有所區別[19]。

從公式(2)可以看出，一個狀態s的理論回報值的計算是一個反復探索直到穩定的過程。特別地，當環境的狀態空間很大或者情況復雜的情況下，這種探索可能耗時很長、甚至是無限的。因此，實際的算法經常使用的是有限T步的探索策略。此外，在回報值的綜合評價函數方面，最常用的方法是“折扣累計回報”，即給定探索的步數T>0和折扣因子γ∈[0,1]，基于有限折扣累計回報策略，t時刻的狀態回報值計算如下：

R(s)←Rt(s)+γ×Rt+1(s)+…+γT×Rt+T(s) .

(3)

1.3 狀態值函數V(s)

如上所述，環境的變化在強化學習中表現為狀態的更新。值函數將理論上的回報值轉化成可以計算的V值、并通過反復迭代來實現強化學習的目標。基于V值學習的模型和算法已經成為強化學習的一個重要方法。

給定一個時間t和當前狀態st，值函數方法是一個“前探+回推”的過程。基于有限折扣累計回報策略，下面的公式(4)給出了對應值函數的計算方法：

(4)

其中：π是學習的策略；R(st)是t時刻的回報(也被稱為t時刻的即時回報)；P(s1,s2)為狀態s1可能轉移到狀態s2的概率；γ∈[0,1]是折扣因子，而且整個后面一項是前探T步的V值函數的綜合評估，即相對于即時回報R(st)而言，這部分是t后可能的回報(強化學習中也被稱為未來回報)，它需要通過V值的迭代計算來完成。

1.4 動作值函數Q(s,a)

在強化學習中，狀態的轉移是通過執行動作來完成的。一個狀態下實施了某種動作就到達一個新狀態。這在機器人系統或者棋牌對弈系統中得到充分體現。例如，在圍棋對弈系統中，每落一個棋子就意味著棋局(狀態)發生改變，但是這種改變需要持續進行評價。同樣，在機器人路線規劃中，機器人每前進一步意味著新的狀態產生，但是這并不意味著接近目標點，所以每個動作引發的狀態更新都需要進行評價并累計到之前的獎勵回報中。

假設一個環境用狀態集S和動作集A來描述。給定t時刻的當前狀態s∈S，動作a∈A是s狀態下可以執行的一個候選動作，則π策略下的關于狀態s和動作集a的回報可以用動作值函數來估計。公式(5)給出了對應的表達公式:

(5)

其中：R(st)和γ分別是t時刻的立即回報和折扣因子；A(*)是狀態*可能采取的下動作集合，整個的后面一項就是t時刻的未來Q值的累計估計。

除了經典的上述3種算法外，還有在此3種算法基礎上大量改進的強化學習算法，比如在Q-Learning中加入多個智能體，將TD與神經網絡相結合以及將啟發函數與Sarsa相結合等等，這些算法都在實驗中表現出了優異的成績。

2 Q-Learning算法分析

2.1 基本原理

Q-Learning是強化學習三種最流行的算法之一，是基于Q值迭代的無模型算法。如前所述，給定某一時刻的狀態si和準備采取的動作ai，Q(si,ai)就是在該時刻的狀態si下采取動作ai獲得回報的估計值。理論上講，當探索了一個給定時刻的狀態si和所有可能動作A(si)后，就可以根據環境的反饋回報信息選取一個最優動作進入下一次狀態si+1；如此反復直到終點或者人為終止，一次迭代過程結束。當然，一個狀態的Q值也是隨著探索的不斷推進在不斷更新中，直到所有狀態的Q值相對穩定為止。

Q-Learning算法的特點是根據潛在的狀態與動作來構建一張二維表(被稱為Q-table)來存儲Q值，然后通過查表方式獲得Q值來尋找最優的動作。該方法具有簡單直接的特點，在環境大小適中的應用場景中(如簡單棋牌對弈等)，已經證明非常有效。

Q-table的數據結構簡單易用，表1給出了一個4個狀態、2個動作的結構示意。

表1 Q-Table結構示意Table 1 Q-Table schematic

基于Q-table，Q-Learning算法主要使用公式(6)來更新Q值：

Q(s,a)←Q(s,a)+α×((R(s′)+γ×maxa′∈A(s′)
{Q(s′,a′)-Q(s,a)}) .

(6)

其中：s和s′分別是當前狀態和下個狀態，a則是使s到s′的有效動作，而A(s′)則是下狀態s′可能采取的候選動作；α∈[0,1]被稱為為學習率，用于調節學習過程中的可能誤差；γ為折扣因子。

依據公式(6)，Q-Learning算法在一個特定狀態下將貪婪地對所有可能的路徑進行探索，每前進一步都是在尋找當前狀態下的局部最優解。

為了準確刻畫改進的算法，本文采用的主要符號及其意義見表2.

表2 符號表Table 2 Symbols in this paper

算法1給出了Q-Learning算法的偽碼描述。

Input: learning rate α, discount factor γ, greedy factor ε, reward matrix R(|S|,|A|), maximum forward steps maxStep, maximum number of Q-table modifications maxIter.Output: Q-table Q(|S|,|A|).Process:Initialize Q-table;所有Q(s,a)元素為0iter←0;Reapeat //循環更新Q表 s←start; 開始狀態為start step←0; Repeat// 循環找終點terminal: For(each action a∈A(s)) call ε-greedy obtain a'∈A(s);//用貪婪策略前探 Q(s,a)←Q(s,a)+α*(R(s)+γ*(Q(s(a),a')-Q(s,a))); s←s(a'); step++; Until (step>=maxStep) or (s=terminal) iter←iter++;Until (iter>=maxIter) or (Q-table no again change)Return Q-Table.

值得注意地是，考慮到現有Q-Learning算法的描述大多過于簡單[4,8]，不利于讀者閱讀和本文后面算法的介紹。算法1把整個Q-Learning的主要步驟整合到一起，對細節進行了更詳細描述。

簡單地講，Q-Learning算法除了必要的初始化外，主要是一個雙層循環：

1) 在內層循環里要完成一次從起點到終點狀態的探索，并對探索過的路徑的Q值進行更新。它的理想出口是每次探索都能到達終點。這種(內循環)正常出口只意味著找到一條可行的路徑來完成從起點到終點的工作，但它不一定是最優的，因此還需要通過Q-Table的迭代來尋優。當然，當內循環人為終止(超過步驟閾值)時，就說明本次探索失敗，需要重新開始探索。此外，在一個狀態下尋找下動作采用的是ε-greedy策略。

2) 外循環的正常結束條件是Q-table不再變化。這意味著經過多次迭代后，已經產生了從起點到終點狀態的穩定情況，因而達到了優化的目標，最后的答案也就是從起點到終點的“最大Q值”形成的路徑。當然，當外循環觸動“意外的結束條件”時，就說明循環探索已經達到極限，沒有必要繼續下去了。

2.2 改進Q-Learning算法

強化學習和監督學習、半監督學習等其他學習方法不同，它需要不斷探索環境并獲得反饋。目前最常用的探索策略有兩個：貪婪策略和Boltzmann策略[4-5]。

一般地講，Boltzmann基本上是隨機選擇策略，缺乏探索的目的性，效率很難保證，特別是在復雜情況下很難完成。相對來說，貪婪策略增加了探索的目的性，但是很容易陷入局部優化，甚至經常“碰壁”而被迫終止。目前的算法也都致力于解決該問題，但是仍然存在很大的改進空間。

本文引入動態搜索因子ε，嘗試改進Q-Learning算法。算法2給出了改進Q-Learning算法ε-Q-Learning的偽碼描述。

Input: learning rate α, discount factor γ, basic greedy factor ε, greed incremental θ, reward matrix R(|S|,|A|), maxi-mum forward steps maxStep, maximum number of Q-table modifications maxIter.Output: The optimal path P.Process:Initialize Q-table;所有Q(s,a)元素為0iter←0;Reapeat //循環更新Q表 s←start; 開始狀態為start step←0; Repeat// 循環找終點terminal: For(each action a∈A(s)) IF rand()<ε Then a'← a random forward action from s Else call ε-greedy get a'∈A(s);//用貪婪策略前探 Q(s,a)←Q(s,a)+α*(R(s)+γ*(Q(s(a),a')-Q(s,a)) End Do s←s(a'); step++;Until (step>=maxStep) or (s=terminal)iter←iter++;If (step>=maxStep) Then □←□+θElse Then □←□-θ;Until (iter>=maxIter) or (Q-table no again change);For (s=start To terminal) Do a←argmax{Q(s,a)|a∈A(s)} P←P+;Return P.

ε-Q-Learning主要改變是根據環境的反饋來動態調整貪婪因子ε.正如算法2中間描述那樣，ε-greedy策略是通過條件rand()<ε來決定是隨機選擇還是選擇最大Q值的下動作。很顯然，ε越大則隨機搜索下動作的概率就會增大，這在一定程度上避免陷入局部優化。

算法2引入動態的貪婪因子ε.簡單地說，在算法2中，假如在一次從起點到終點的探索失敗，則通過增大ε來使下一次探索的隨機性增大，以免陷入之前的局部優化困境。反之，則通過減少ε來增加目的性。當然，算法2中的基礎貪婪因子ε和增幅θ是一個經驗值，也需要根據應用中環境的不斷變化進行嘗試實驗來確定。