強化學習模型及其在避障中的應用

孫　魁,吳成東（.沈陽建筑大學信息學院;　.沈陽建筑大學,沈陽　006）

?

強化學習模型及其在避障中的應用

孫魁1,吳成東2
（1.沈陽建筑大學信息學院;2.沈陽建筑大學,沈陽110016）

摘 要：強化學習是機器學習的一個重要分支，其優點是不需要先驗知識，通過與環境的交互進行試錯學習。與有導師學習不同，強化學習沒有得到確定的目標值而是一個獎賞值。本文介紹了強化學習的模型和一些常用算法，并將強化學習的方法應用在避障問題上。

關鍵詞：強化學習；馬爾科夫決策；避障

1　概述

強化學習(Reinforcement Learning，RL)是近幾年來人工智能和機器學習研究的熱點。不同于監督學習，強化學習強調與環境的交互并在其中進行學習，用極大化的從環境獲得的評價性反饋信號為學習目標，所以強化學習在求解那種無法獲得教師信號的復雜優化決策問題中具有廣泛的應用[1][2]。

強化學習是機器學習的一個重要分支。強化學習通過對環境的反復試探，從中學習環境到可執行動作的最優反應式策略，以期獲得最大回報。相比于其它學習策略，強化學習的明顯優勢在于它對先驗知識的是否完備幾乎沒有要求，即使在信息完全未知的情況下，強化學習仍然具有較好的自適應性和魯棒性[3]。

傳統的強化學習方法主要針對的是離散狀態和行為空間的馬爾科夫決策過程，也就是狀態的值函數或行為的值函數采用了表格的形式來進行存儲和迭代計算。但是實際工程應用中的許多優化決策問題是具有大規?；蜻B續的狀態或行為空間的情況，所以表格型強化學習算法也同動態規劃法一樣存在維數災難。為了克服維數災難，以實現對連續性狀態或行為空間的馬爾科夫決策過程的最優值函數和最優策略的逼近，我們就必須研究強化學習的泛化問題或推廣問題，也就是利用有限的學習經驗和記憶以實現對一個大范圍空間的有效知識獲取和表示的方法。

2　強化學習模型和馬爾科夫決策過程（Markov decision process, MDPs）

2.1強化學習模型

強化學習系統的基本要素包括：狀態集合S、控制行為集合A、控制策略p、強化信號R和狀態評價函數V（s）[4]。

強化學習要研究解決的問題是：一個能夠感知外部環境的自治智能體(Agent),通過學習選擇能夠到達目標任務的最優動作，即強化學習Agent的任務就是學習從環境到動作的映射[26]。強化學習跟連接主義學習中的監督學習的區別主要表現在不存在教師信號上，強化學習中的由環境提供的強化信號是對Agent所產生動作的好壞作出一種評價(通常為標量信號)，而不是直接告訴Agent如何去產生確定性的動作。由于外部環境提供了很少的信息，Agent必須靠自身的探索進行學習，通過這種方式Agent在行動-評價的環境中獲得知識、改進行動方案以適應環境。

強化學習具有以下特征：

Agent不是靜止的、被動的等待，而是主動對環境做出試探；環境對試探動作反饋的信息是評價性的(好或者壞)；

Agent在行動-評價的環境中獲得知識，改進行動方案以適應環境，達到預期目的。

標準的Agent強化學習框架如圖1所示，Agent通過感知和動作與環境交互。在Agent 與環境每一次的交互過程中，強化學習Agent接收環境狀態的輸入s,根據內部的運算機制，輸出相應的行為動作a。環境在動作a的作用下，轉移到新的狀態s’，與此同時產生一個強化信號(立即回報)r(獎勵或懲罰)返回給Agent，Agent根據環境狀態和強化信號選擇下一個動作，選擇的原則是使Agent獲得最大的回報值。選擇的動作不僅影響立即回報值，而且影響下一時刻的狀態及最終時刻的強化值。在學習過程中，強化學習技術的基本原理是：如果系統的某個動作導致環境正的回報，那么系統以后產生這個動作的趨勢就會加強，反之系統產生這個動作的趨勢便會減弱。這和生理學中的條件反射原理是接近的。

2.2馬爾科夫決策過程（Markov decision process, MDPs）

大多數關于強化學習方法的研究都是建立在馬爾科夫決策過程理論框架之上的，盡管強化學習方法并不局限于馬爾科夫決策過程，但離散的、有限狀態的Markov決策過程框架是強化學習算法的基礎。

馬爾科夫決策過程起源于隨機優化控制，是一個離散時間的隨機過程，由六元組{S,A,D,P,r,J}來描述。六元組中，S為有限的環境狀態空間；A為有限的系統動作空間；D為初始狀態概率分布，當初始狀態是確定的，D在該初始狀態下的概率為1，當初始狀態是以相等的概率從所有狀態中選擇時，則D可以忽略；為狀態轉移概率，表在狀態s下選擇動作a后使環境狀態轉移到s’的概率；為學習系統從狀態s執行動作a轉移到狀態s’后獲得的立即回報(獎賞)，是一種“近視”的表達信號；J為決策優化目標函數。馬氏決策過程的特點是目前狀態s向下一個狀態s’轉移的概率和回報只取決于當前狀態s和選擇的動作a，而與歷史狀態無關，因此MDP的轉移概率P和立即回報r也只取決于當前狀態和選擇的動作，與歷史狀態和歷史動作無關。若轉移概率函數P(s , a , s ')和回報函數r(s , a , s ')與決策時間t無關，即不隨時間t的變化而變化，則MDP稱為平穩MDP。

2.3累積獎賞模型（3種）

MDP的決策優化目標函數J一般分為3種類型，即有限階段總回報目標、無限折扣總回報目標和平均回報目標。

有限階段總回報目標為

式中，tr為t時刻得到的立即回報；N表示智能體的生命長度，即馬爾科夫鏈的長度。在多數情況下，智能體學習的生命長度是未知的，且當N?￥時，函數可能會發散。因此，有限階段總回報目標很少考慮。

無限折扣總回報目標為

平均回報目標為

3　強化學習基本算法

強化學習主要算法有動態規劃法(Dynamic Programming, DP),蒙特卡洛法(Monte Carlo, MC)和時序差分法(Temporal Difference, TD)和Q學習（Q-learning）等。

3.1動態規劃法

動態規劃法是一種基于模型的策略尋優方法。這種方法將動態系統的狀態和值函數的概念用于定義函數方程(現在通常稱為Bellman方程)。這類通過求解Bellman方程來解決最優控制問題的方法被稱為動態規劃。

動態規劃在過去的幾十年中已經取得了極大的發展，被廣泛地認為是求解一般隨機最優控制問題的唯一切實可行的方法。但是，動態規劃存在所謂的維數災難問題，也就是說，動態規劃的計算量需求隨著狀態變量數目的增加而呈指數級增長。但是相比于其他方法，動態規劃仍然是一個非常有效且應用廣泛的方法。動態規劃與強化學習密切相關，對于馬爾科夫決策問題，前者主要解決環境的狀態轉移概率和回報函數已知的決策問題，而后者主要處理狀態轉移概率和回報函數未知的情形。

3.2蒙特卡羅法

在概率和統計理論中，蒙特卡羅（Monte carlo, MC）方法是一種用部分估計整體利用隨機數來解決問題的方法，通過統計模擬或抽樣方式以獲得問題的近似解。將MC引入強化學習中，就得到一種無模型的學習方法。此方法不需環境的先驗模型，只需要通過與環境的交互來獲得的實際或模擬樣本數據（狀態、動作、獎賞）序列，從而去發現最優策略。MC方法與策略迭代原理類似，分為MC策略評估和MC策略控制兩部分，MC方法主要用在策略評估中。

本質上講，MC方法就是基于平均化樣本回報值來求解值函數的方法，從而解決強化學習問題。為了確保良好的定義回報值，MC算法定義為完全抽樣的即所有的抽樣點必須最終終止只有當一個抽樣點結束，估計值和策略才會改變。因此該方法只適合于場景式任務，即任務存在終止狀態，任何策略都在有限步內以概率1到達終止狀態。

3.3時序差分法

1988年，Sutton等人提出了一種用于解決時間信度分配問題的方法：時間差分方法TD，而強化學習中所用的主要方法都是基于TD的。TD學習方法結合了蒙特卡羅和動態規劃兩種方法的思想，不需要系統模型，這樣能夠直接從學習者的原始經驗開始。與動態規劃方法一樣，TD方法通過預測每個動作的長期結果來給先前的動作賦予獎勵或懲罰，即依賴于后續狀態的值函數來更新先前狀態值函數，主要應用于預測問題。

3.4Q-學習

Q-學習是由Watkins提出的一種模型無關的強化學習算法。Q-學習在迭代時采用狀態-動作對的獎賞值和Q*(s,a)作為估計函數，而不是TD算法中的狀態獎賞和V（s），因此在每一次學習迭代過程中都需要考察每一個行為，可確保學習過程收斂。

Q函數定義及Q值的調整方法如下：

4　基于Q學習的避障應用

良好的學習性能使得強化學習在實際中獲得越來越廣泛的應用，應用領域有各種任務調度、機器人控制和游戲等等。本文簡單介紹基于Q學習的避障應用。

避障環境采用20X20柵格，模擬Agent從左下角出發點出發，通過基于Q學習算法的動作選擇到達目標點設定在（19，15），在過程中要避開隨機放置的障礙物，并且動作過程中不能離開柵格邊界。模型將Agent的坐標作為Q學習中的狀態參數，在每一個柵格，Agent只有上、下、左、右四個動作空間?；貓蠛瘮等缦拢?/p>

Q初始值設為0。

MATLAB仿真結果如圖2。

仿真結果表明Q學習算法能夠收斂并成功實現避障達到目標點。

5　結束語

強化學習是一種很有前途的學習方法，已經引起越來越多學者的研究興趣。近年來呈現了大量的研究成果，但是仍然有許多亟待解決的問題，例如算法的收斂速度問題與維度災難問題。盡管強化學習發展道路上充滿困難與挑戰，但是其前景廣闊，是未來的趨勢。

參考文獻：

[1]Leslie Pack Kaelbling, Michael L. Littman, Andrew W. Moore. Reinforcement Learning：A Survey. Journal of Artificial Intelligence Research 4 (1996) 237-285.

[2]Richard S. Sutton , Andrew G. Barto , Reinforcement Learning : An Introduction , MIT Press, MA, 1998.

[3]R. S. Sutton，A. G. Barto．Reinforcement learning: An Introduction[M]．MIT Press，Cambridge， MA，2006，72-77．H

[4]P van Hasselt. Insight in Reinforcement Learning: formalanalysis and empirical evaluation of difference learning algorithms. SIKS dissertation series,2011.

[5]John Holand．Reinforcement learning: A survey[J]．Machine learning，1988，3(1):9-14.

[6]Wang X L，Wang L．Research of distinguish matrix dealing with unconformity problems in rough sets[J]．Microcomputer Development，2008，13(6):119-120．

[7]D. Michie，R. A. Chambers．Box: An experiment in adaptive control[M]．Machine intelligent，2010，137-152．

[8]J. C. Q-learning[J]．Machine Learning，1992，8:279-292．rough sets theory[M]．Kluwer Academic Publishers，Norwell，MA，1992．

[9]Markov．Algorithm for attribute reduction based on reinforcement learning on improved discernibility matrix[J] ．Computer Engineering and Application，1997，43(32):83-85．

[10]Wu C D，Zhang Y ，Li M X ．A rough set GA-based hybrid method for mobile

robot[J]．International Journal of automation and computing 2006，3(1):29-34．

[11]R. Slowinski．Intelligent decision support: handbook of applications and advances of the47

[12]陳鋒,胡社教,陳宗海.未知環境下自主移動機器人的行為學習研究[J].模式識別與人工智能,2006,15(04):498-501．

[13]張汝波,顧國昌,劉照德.Q學習理論、算法及應用[J].控制理論及應用,2007,17(05):637-642．

[14]閻平凡．再勵學習算法及其在智能控制中的應用[J]．信息與控制，2006,25(01):28-34．

[15]張汝波.滾動式窗口算法及應用[M].哈爾濱:哈爾濱工程大學出版社,2006:134-139．

[16]陳學松,楊宜民.強化學習研究綜述[J].計算機應用研究,2010.

DOI :10.16640/j.cnki.37-1222/t.2016.01.234