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

?

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

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

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

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

1　概述

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

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

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

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

2.1強化學習模型

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

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

強化學習具有以下特征：

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

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

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

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

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

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

2.3累積獎賞模型（3種）

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

有限階段總回報目標為

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

無限折扣總回報目標為

平均回報目標為

3　強化學習基本算法

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

3.1動態(tài)規(guī)劃法

動態(tài)規(guī)劃法是一種基于模型的策略尋優(yōu)方法。這種方法將動態(tài)系統(tǒng)的狀態(tài)和值函數(shù)的概念用于定義函數(shù)方程(現(xiàn)在通常稱為Bellman方程)。這類通過求解Bellman方程來解決最優(yōu)控制問題的方法被稱為動態(tài)規(guī)劃。

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

3.2蒙特卡羅法

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

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

3.3時序差分法

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

3.4Q-學習

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

Q函數(shù)定義及Q值的調(diào)整方法如下：

4　基于Q學習的避障應用

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

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

Q初始值設為0。

MATLAB仿真結果如圖2。

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

5　結束語

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

參考文獻：

[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]陳鋒,胡社教,陳宗海.未知環(huán)境下自主移動機器人的行為學習研究[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