強(qiáng)化學(xué)習(xí)模型及其在避障中的應(yīng)用

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

?

強(qiáng)化學(xué)習(xí)模型及其在避障中的應(yīng)用

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

摘 要：強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)的一個(gè)重要分支，其優(yōu)點(diǎn)是不需要先驗(yàn)知識(shí)，通過與環(huán)境的交互進(jìn)行試錯(cuò)學(xué)習(xí)。與有導(dǎo)師學(xué)習(xí)不同，強(qiáng)化學(xué)習(xí)沒有得到確定的目標(biāo)值而是一個(gè)獎(jiǎng)賞值。本文介紹了強(qiáng)化學(xué)習(xí)的模型和一些常用算法，并將強(qiáng)化學(xué)習(xí)的方法應(yīng)用在避障問題上。

關(guān)鍵詞：強(qiáng)化學(xué)習(xí)；馬爾科夫決策；避障

1　概述

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

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

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

2　強(qiáng)化學(xué)習(xí)模型和馬爾科夫決策過程（Markov decision process, MDPs）

2.1強(qiáng)化學(xué)習(xí)模型

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

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

強(qiáng)化學(xué)習(xí)具有以下特征：

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

Agent在行動(dòng)-評(píng)價(jià)的環(huán)境中獲得知識(shí)，改進(jìn)行動(dòng)方案以適應(yīng)環(huán)境，達(dá)到預(yù)期目的。

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

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

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

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

2.3累積獎(jiǎng)賞模型（3種）

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

有限階段總回報(bào)目標(biāo)為

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

無限折扣總回報(bào)目標(biāo)為

平均回報(bào)目標(biāo)為

3　強(qiáng)化學(xué)習(xí)基本算法

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

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

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

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

3.2蒙特卡羅法

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

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

3.3時(shí)序差分法

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

3.4Q-學(xué)習(xí)

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

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

4　基于Q學(xué)習(xí)的避障應(yīng)用

良好的學(xué)習(xí)性能使得強(qiáng)化學(xué)習(xí)在實(shí)際中獲得越來越廣泛的應(yīng)用，應(yīng)用領(lǐng)域有各種任務(wù)調(diào)度、機(jī)器人控制和游戲等等。本文簡(jiǎn)單介紹基于Q學(xué)習(xí)的避障應(yīng)用。

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

Q初始值設(shè)為0。

MATLAB仿真結(jié)果如圖2。

仿真結(jié)果表明Q學(xué)習(xí)算法能夠收斂并成功實(shí)現(xiàn)避障達(dá)到目標(biāo)點(diǎn)。

5　結(jié)束語

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

參考文獻(xià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)境下自主移動(dòng)機(jī)器人的行為學(xué)習(xí)研究[J].模式識(shí)別與人工智能,2006,15(04):498-501．

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

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

[15]張汝波.滾動(dòng)式窗口算法及應(yīng)用[M].哈爾濱:哈爾濱工程大學(xué)出版社,2006:134-139．

[16]陳學(xué)松,楊宜民.強(qiáng)化學(xué)習(xí)研究綜述[J].計(jì)算機(jī)應(yīng)用研究,2010.

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