馬朋委 潘地林 汪立冬

摘要：為解決隨機(jī)環(huán)境下的智能體的路徑規(guī)劃問(wèn)題，借助強(qiáng)化學(xué)習(xí)算法的自學(xué)習(xí)和和自適應(yīng)的特點(diǎn)，引入Q學(xué)習(xí)算法處理隨機(jī)環(huán)境下的路徑規(guī)劃問(wèn)題。實(shí)驗(yàn)結(jié)果表明，該算法在解決隨機(jī)環(huán)境中路徑規(guī)劃的有效性。

關(guān)鍵詞：強(qiáng)化學(xué)習(xí)；Q_learning；路徑規(guī)劃；隨機(jī)環(huán)境

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）31-0148-02

Reinforcement Learning based Agent Path Planning in Random Environment

MA Peng-wei， PAN Di-lin， WANG Li-dong

（Anhui University of Science and Technology， Computer Science and Engineering， Huainan 232001，China）

Abstract： In order to solve the problem of path planning on agent in random environment， with the help of reinforcement learning algorithm of self learning and adaptive characteristics of the introduction of Q_learning algorithm to deal with the path planning problem of random environment. The experimental results show that the algorithm in solving path planning in random environment is effective.

Key words：reinforcement learning； Q_learning； path planning； random environment

1 概述

路徑規(guī)劃[1]是一個(gè)重要的研究課題，在機(jī)器人導(dǎo)航和游戲智能體中都有著很大的研究?jī)r(jià)值。在確定環(huán)境下（比如只有靜止障礙物的尋路過(guò)程）可以很有效地解決此類問(wèn)題。但在隨機(jī)環(huán)境下，這種隨機(jī)性就破壞了A*算法的要求。隨機(jī)環(huán)境相對(duì)于確定環(huán)境（固定順序的一系列操作一定會(huì)得到相同的結(jié)果）而言的，因?yàn)槊恳徊降牟僮鞯慕Y(jié)果都是隨機(jī)的，即使相同的操作序列也會(huì)得到不同的結(jié)果。此時(shí)如果強(qiáng)行應(yīng)用的話，最好的情形也需要做很多修改工作，最差的情形是A*會(huì)給出錯(cuò)誤的答案。在此我們引入一個(gè)解決隨機(jī)條件下的多步?jīng)Q策問(wèn)題，強(qiáng)化學(xué)習(xí)（Reforcement Learning）。

強(qiáng)化學(xué)習(xí)是一種在線的、無(wú)導(dǎo)師的機(jī)器學(xué)習(xí)方法，主要表現(xiàn)在由環(huán)境提供的強(qiáng)化信號(hào)對(duì)智能體所產(chǎn)生動(dòng)作的好壞作一種評(píng)價(jià)，而不是告訴智能體如何產(chǎn)生正確的動(dòng)作，智能體依靠自身與環(huán)境的交互進(jìn)行學(xué)習(xí)，在行動(dòng)和評(píng)價(jià)的環(huán)境中獲得知識(shí)，對(duì)行動(dòng)方案進(jìn)行改進(jìn)適應(yīng)環(huán)境，已達(dá)到獲得最優(yōu)動(dòng)作。20世紀(jì)90年代，強(qiáng)化學(xué)習(xí)通過(guò)與運(yùn)籌學(xué)、控制理論的交叉結(jié)合，在理論和算法方面取得了突破性的研究成果，奠定了強(qiáng)化學(xué)習(xí)的理論基礎(chǔ)，并在機(jī)器人控制領(lǐng)域、優(yōu)化調(diào)度等序貫決策中取得了成功的應(yīng)用[2]。

2 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)是一個(gè)能夠感知環(huán)境的自治智能體如何通過(guò)學(xué)習(xí)選擇能夠達(dá)到目標(biāo)的最優(yōu)動(dòng)作，即強(qiáng)化學(xué)習(xí)的任務(wù)就是學(xué)習(xí)從環(huán)境到動(dòng)作的映射[3]。強(qiáng)化學(xué)習(xí)的學(xué)習(xí)過(guò)程類似于人，從來(lái)不是靜止被動(dòng)地等待，而是主動(dòng)地對(duì)環(huán)境試探交互，從環(huán)境給予的反饋信號(hào)來(lái)學(xué)習(xí)知識(shí)，改進(jìn)行動(dòng)方案，已達(dá)到預(yù)期的目的，這也符合強(qiáng)化學(xué)習(xí)的特征[4]。強(qiáng)化學(xué)習(xí)大部分都是以馬爾科夫決策過(guò)程（Markov Decision Process）為基礎(chǔ)。馬爾科夫決策過(guò)程借助四元組來(lái)描述。S為環(huán)境狀態(tài)空間，[A]為動(dòng)作空間，[P]為狀態(tài)轉(zhuǎn)移概率，[r]為立即回報(bào)函數(shù)。強(qiáng)化學(xué)習(xí)的模型如圖1：

圖1 強(qiáng)化學(xué)習(xí)框架

在馬爾科夫決策過(guò)程中，Agent是通過(guò)一個(gè)決策函數(shù)（即策略）來(lái)選擇動(dòng)作的，常用π表示策略。在定義了策略后對(duì)應(yīng)狀態(tài)-動(dòng)作值函數(shù)為[Qπ（s，a）]，[Qπ（s，a）]表示在狀態(tài)s下根據(jù)策略π執(zhí)行動(dòng)作a的期望值如式（1）：

[Qπ（s，a）=Eπt=0∞γtrt+1|st=s，at=a] （1）

最優(yōu)動(dòng)作值函數(shù)的定義為式（2）：

[Qπ（s，a）=maxπQπ（s，a）=s'∈SP（s，a，s'）r+γmaxa'∈AQ*（s'，a'）] （2）

最優(yōu)策略是使得Agent在每一個(gè)狀態(tài)下均能獲得最大值的策略如式（3）：

[π*（s）=arg maxaQ*（s，a）] （3）

其中[arg maxaQ*（s，a）]是狀態(tài)[S]的一個(gè)函數(shù)，其值為使[Q*（s，a）]最大的動(dòng)作[a]。一些強(qiáng)化學(xué)習(xí)算法已經(jīng)在理論和應(yīng)用方面取得了重大的成功[Q]_learning[5]，TD（λ）[6]， SARSA[7]。本文選取[Q]_learning算法，[Q]_learning是一種有效的模型無(wú)關(guān)強(qiáng)化學(xué)習(xí)算法。

3 [Q]_learning算法

[Q]_learning算法是Watkins最早于1989提出來(lái)的[8]，又稱離策略TD學(xué)習(xí)。它采用[Q（s，a）]狀態(tài)動(dòng)作對(duì)的值做估計(jì)函數(shù)。在[Q]學(xué)習(xí)中智能體維護(hù)一個(gè)查找表[Q（s，a）]，其中[Q]和[S]分別是狀態(tài)和行為的集合智能體借助時(shí)間差分的思想來(lái)更新查找表。智能體在每一次學(xué)習(xí)迭代時(shí)都需要考察每一個(gè)行為，如果每個(gè)狀態(tài)-動(dòng)作對(duì)被無(wú)限頻繁的訪問(wèn)，且學(xué)習(xí)率合適，算發(fā)最終會(huì)收斂，其收斂性已得到證明。常見(jiàn)的動(dòng)作選擇策略有[ε-greedy]和Boltzmann分布，本文采用的是[ε-greedy]算法，指的是多數(shù)情況下選擇具有最大Q值的動(dòng)作，但以概率[ε]選擇其它動(dòng)作。[Q]_learning的迭代公式如（4）：

[Q（st，at）←Q（st，at）+α[rt+γmaxaQ（st+1，a）-Q（st，at）]] （4）

其中[α]為學(xué)習(xí)率（步長(zhǎng)），[α∈（0，1]]，[γ]為折扣因子，[γ∈（0，1]]

其學(xué)習(xí)過(guò)程如下：

Step 1：初始化：[Qs，a]為任意值（為方便計(jì)算，通常初始化為0），設(shè)置步長(zhǎng)[α]，折扣因子[γ]。

Step 2：Repeat 給定起始狀態(tài)[S2]

Repeat（對(duì)于一幕的每一步）

根據(jù)[ε-greedy]的策略選擇動(dòng)作[at]，得到立即回報(bào)[rt]和下一個(gè)狀態(tài)[st+1]

更新[Q（st，at）←Q（st，at）+α[rt+γmaxaQ（st+1，a）-Q（st，at）]]

[st←st+1]

直到[st]是終止?fàn)顟B(tài)

直到所有的[Q（s，a）]收斂

輸出最終策略。

[Q]學(xué)習(xí)算法在強(qiáng)化學(xué)習(xí)算法中最為基本，實(shí)際應(yīng)用也很廣泛。只要在任意的狀態(tài)智能體嘗試一個(gè)行為的次數(shù)不受限制（即智能體在一個(gè)狀態(tài)不會(huì)總是執(zhí)行相同的行動(dòng)子集），則不管智能體真正依據(jù)的策略是哪個(gè)，[Q]學(xué)習(xí)都學(xué)習(xí)一個(gè)最優(yōu)的策略。

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證算法的有效性，本文選取一個(gè)15X10的迷宮如圖2，S為迷宮的開(kāi)始節(jié)點(diǎn)，G為終點(diǎn)，棕色塊相當(dāng)于墻壁或障礙物，灰色塊為可行區(qū)域，紅色塊代表陷阱，綠色塊為算法的最終的規(guī)劃路徑。

圖2

本文選取[ε]為0.2，，折扣率[γ]為0.9，步長(zhǎng)[α]為0.1，回報(bào)函數(shù)r定義如式（5）：

[r=5 終點(diǎn)，隨機(jī)選取一個(gè)點(diǎn)開(kāi)始-5陷阱-1撞到墻壁或障礙物，待在原地0其他情況] （5）

智能體剛開(kāi)始從[S]位置出發(fā)，目標(biāo)是終點(diǎn)[G]的位置。執(zhí)行動(dòng)作[a]時(shí)有一定的概率會(huì)向兩側(cè)移動(dòng)（假如0.8概率向右移動(dòng)時(shí)，會(huì)有0.1的概率向上移動(dòng)，0.1的概率向下移動(dòng)）強(qiáng)化學(xué)習(xí)憑借自身自學(xué)習(xí)的特性，不斷的與環(huán)境交互，獲得反饋信號(hào)（獎(jiǎng)賞值），更新該位置的[Q]查找表，直到程序迭代結(jié)束，強(qiáng)化學(xué)習(xí)能夠很好的從環(huán)境中獲得該知識(shí)，得到一個(gè)最優(yōu)策略。圖2的運(yùn)行結(jié)果表明算法有很好的效果，表明強(qiáng)化學(xué)習(xí)的在線學(xué)習(xí)特點(diǎn)在隨機(jī)環(huán)境中的優(yōu)勢(shì)，驗(yàn)證了算法的可行性。

5 結(jié)束語(yǔ)

雖然強(qiáng)化學(xué)習(xí)在隨機(jī)環(huán)境地圖規(guī)劃中能夠較好的應(yīng)用，但它也存在著學(xué)習(xí)知識(shí)較慢，算法需要多次迭代才能收斂，在執(zhí)行選取動(dòng)作的策略時(shí)也存在著探索與利用的平衡問(wèn)題。如何加快算法的收斂速度，提升在環(huán)境中學(xué)習(xí)知識(shí)的能力，一直是強(qiáng)化學(xué)習(xí)研究的重點(diǎn)。

參考文獻(xiàn)：

[1] 陳衛(wèi)東，李寶霞，朱奇光.模糊控制在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（31）：221-223.

[2] 史忠植.智能科學(xué)[M].北京：清華大學(xué)出版社，2006：30-35.

[3] Mitchell T M.機(jī)器學(xué)習(xí)[M].曾華軍，譯.北京：機(jī)械工業(yè)出版社，2008：21-26.

[4] 譚民，王碩，曹志強(qiáng).多機(jī)器人系統(tǒng)[M].北京：清華大學(xué)出版社，2005：65-72.

[5] L.P. Kael bling， M.L. Littman， and A.W.Moore，reinforcementlearning：Asurvey[R].Arxivpreprintcs/9605103， pp.237-285，1996.

[6] L.Tang B. AnandD.Cheng，An agent reinforcement learning model based on neural networks[C].Bio-Inspired Computational Intelligence and Applications，pp.117-127，2007.

[7] Jinsong，Leng， LakhmiJain，Colin Fyfe.Convergence Analysis on Approximate Reinforcement Learning[C]，Z.Zhang andSiekmann （Eds）：KSEM 2007，LNAI 4798，pp.85-91.

[8] SUTTON R S， BARTO A G.Reinforcement learning：an introduction [M]. Cambridge： MIT， 1998：150-185.