基于強化學習的城市交通路徑規(guī)劃

劉思嘉，童向榮

（煙臺大學計算機與控制工程學院，山東煙臺 264005）

0 引言

路徑規(guī)劃問題是人工智能領(lǐng)域熱點問題，該問題涉及許多領(lǐng)域，包括：移動機器人導航、飛行器航跡規(guī)劃、游戲自動導航以及車輛交通導航等。如今，城市交通路徑規(guī)劃在提升交通系統(tǒng)運行效率方面正發(fā)揮著越來越重要的作用。結(jié)合城市交通特點，可以總結(jié)出城市交通路徑規(guī)劃問題的規(guī)范化定義：將指定某一車輛作為智能體，目的是讓智能體從規(guī)定范圍內(nèi)的狀態(tài)找到一條從起始狀態(tài)到目標狀態(tài)的一條無障礙路徑。其中如何提高路徑規(guī)劃算法的效率成為亟待解決的問題，路徑規(guī)劃算法使用高效的規(guī)劃算法來為智能體車輛選擇合理的導航路徑，從而減少車輛在城市道路上運行的時間，提升城市道路的運行通暢度。

目前，路徑規(guī)劃問題已經(jīng)得到許多學者的關(guān)注，有一些成功的研究成果，具體可以分為全局規(guī)劃和局部規(guī)劃。全局規(guī)劃的算法包括A*算法［1］以及它的各種改進版本等，這些算法已經(jīng)在離線靜態(tài)環(huán)境中表現(xiàn)出優(yōu)異的效果。對于動態(tài)環(huán)境，Yu 等［2］提出了一種在動態(tài)圖中識別K-最短路徑的分布式算法（KShortest Path in Dynamic Graph，KSP-DG），能夠在動態(tài)道路網(wǎng)環(huán)境找到多條最短路徑。但是這些算法過于依賴環(huán)境數(shù)據(jù)，需要在大量數(shù)據(jù)支持下才能完成路徑規(guī)劃，而且在未知環(huán)境下的效果較差，無法應(yīng)用在環(huán)境變化的情況下。局部規(guī)劃包括神經(jīng)網(wǎng)絡(luò)法［3］、遺傳算法［4］以及強化學習算法等。其中強化學習算法由于無需環(huán)境的先驗知識，已經(jīng)得到了廣泛的應(yīng)用。

通過將強化學習算法應(yīng)用到路徑規(guī)劃算法中，能夠有效幫助車輛的行駛路徑規(guī)劃，同時對道路未來通行狀態(tài)的變化加以考慮，從而能夠進一步提高選路算法的合理性，對于緩解城市交通擁堵有著重要的現(xiàn)實意義。因此提出了一種在道路交通網(wǎng)環(huán)境下基于強化學習的車輛路徑規(guī)劃算法，采用將基于模型的算法和模型無關(guān)的算法相結(jié)合的Dyna 框架［5］可以提高規(guī)劃的速度，同時較為經(jīng)典的Sarsa 算法［5］作為選路策略可以提高算法的安全性。

與現(xiàn)有其他算法相比，基于強化學習的路徑規(guī)劃算法有如下特點：1）大部分的路徑規(guī)劃環(huán)境是未知的，需要算法建立到模型上再進行路徑搜索，而模型無關(guān)算法可以在未知環(huán)境工作，算法具有自適應(yīng)能力；2）一些路徑規(guī)劃算法能夠找到最優(yōu)路線，但是可能會經(jīng)過較多的時間，這可能造成資源浪費，強化學習算法能夠找到一條相對較快且較優(yōu)的路線，同時提高路徑規(guī)劃的安全性；3）強化學習是一個不斷嘗試的過程，通過不斷與環(huán)境交互來找到最優(yōu)策略，這樣產(chǎn)生的策略對于智能車來說一定是可以完成的，不會因為路徑太復雜導致無法執(zhí)行。仿真實驗表明：相對于經(jīng)典的路徑規(guī)劃算法，基于強化學習的路徑規(guī)劃算法能夠真實地模擬智能車輛的實際行駛狀態(tài)，有效減少環(huán)境中車輛行駛時間開銷，提高城市交通運行效率。

1 相關(guān)工作

在解決路徑規(guī)劃問題的強化學習算法中，Q 學習（QLearning）算法［6］是較為常用的一種算法。喬俊飛等［7］把BP神經(jīng)網(wǎng)絡(luò)引入Q-學習算法中應(yīng)用在移動機器人中，能夠?qū)崿F(xiàn)對未知環(huán)境的路徑規(guī)劃。Wang等［8］將Q-learning算法與Sarsa算法結(jié)合，提出了一種反向的Q-學習算法。Gosavi［9］提出了一種基于Q 學習和神經(jīng)網(wǎng)絡(luò)規(guī)劃器的路徑規(guī)劃方法，實驗證明了該方法在全局信息已知環(huán)境中的有效性。Sarsa 算法［5］是在Q-學習算法的基礎(chǔ)上提出的一種模型無關(guān)的強化學習方法，基于Sarsa 的路徑規(guī)劃算法也得到了一定的研究。王軍紅等［11］提出了一種基于信用分配的Sarsa算法，引入信用分配的概念分配強化信號并修改動作選擇策略，實驗表明該算法可以解決動態(tài)環(huán)境下的路徑規(guī)劃問題。Sarsa 算法與其他方法結(jié)合也取得了一定的研究成果，例如k均值聚類算法（kmeans clustering algorithm，k-means）［12］、圖搜索算法［13］及神經(jīng)網(wǎng)絡(luò)算法［14］等。這些文獻中的算法能夠完成路徑規(guī)劃的基本要求，但是收斂速度較慢，需要耗費大量的時間。

在1991 年，強化學習的先驅(qū)Sutton 等［5］提出了Dyna 框架，這個框架通過加入與模擬環(huán)境交互得到的經(jīng)驗，能夠有效提升算法的收斂速度。Dyna 框架通常與Q-學習算法結(jié)合使用。朱美強［15］通過將流形學習中拉普拉斯特征映射方法與Dyna-Q 算法結(jié)合起來用于解決路徑規(guī)劃的問題，實驗證明取得較好的結(jié)果。史豪斌等［16］提出一種基于Dyna-Q 的旋翼無人機視覺伺服智能控制方法調(diào)節(jié)伺服增益以提高其自適應(yīng)性。但是，Q-學習算法存在一個問題是過于追求獎勵最大化導致智能體在有障礙的地圖中陷入危險次數(shù)過多。

2 理論基礎(chǔ)

算法理論涉及經(jīng)典的馬爾可夫決策過程（Markov Decision Process，MDP），由四元組來描述，其中：

S代表著狀態(tài)集合，指的是城市中的位置；

A代表智能體能夠采取的動作集合，智能體汽車在柵格內(nèi)可執(zhí)行4個動作，分別為上、下、左、右；

P代表著狀態(tài)轉(zhuǎn)移概率矩陣，表示智能體汽車選擇上下左右的概率；

R代表著獎勵函數(shù)，智能體在模擬地圖中移動時，未碰撞障礙物時獎勵值為0，碰撞到障礙物時獎勵值為-1，移動到目標點時獎勵值為2。

馬爾可夫決策過程為強化學習問題提供了基本的理論框架，現(xiàn)存環(huán)境中幾乎所有的強化學習問題都可以使用MDP 去建模。

2.1 模型無關(guān)的強化學習算法

Sarsa 算法是一種使用時序差分求解強化學習控制問題的方法，與Q-學習算法相同，它采用Q-表的方式儲存動作值函數(shù)，決策部分采用貪婪策略（epsilon-greedy）選擇動作。Sarsa 算法屬于在線學習算法，它會先執(zhí)行動作再更新，其基本更新規(guī)則如式（1）所示：

其中：S為當前狀態(tài)，A為當前狀態(tài)選擇的動作，S′為下一個狀態(tài)，A′為下一個狀態(tài)選擇的動作，R為獎勵值，γ為折扣因子，α為學習因子，Q為q值的集合。在仿真實驗中，學習率α=0.01，折扣因子γ=0.9。

從更新函數(shù)可以看出，相較于Q-學習算法，Sarsa 算法是一種更為保守的算法，它更在乎每一步的決策，它對錯誤和陷阱更加敏感。在城市交通路徑規(guī)劃中，智能車對碰撞更加敏感，那么系統(tǒng)需要一個更加安全的算法來指導智能車的移動。Sarsa 算法是一個兼顧安全與速度的無模型強化學習算法，它更加符合城市交通環(huán)境，所以選擇使用Sarsa算法作為基礎(chǔ)算法指導智能體的路徑規(guī)劃。

2.2 基于Dyna框架的強化學習算法

在模型無關(guān)的強化學習算法中，智能體能使用從環(huán)境中產(chǎn)生的經(jīng)驗中直接學習到策略；而在基于模型的強化學習中，智能體使用模擬產(chǎn)生的模擬經(jīng)驗規(guī)劃出新的策略；在Dyna框架中，智能體利用與環(huán)境交互產(chǎn)生的直接經(jīng)驗來學習一個模型，同時利用模型生成模擬經(jīng)驗，使用真實經(jīng)驗和模擬經(jīng)驗同時作用于智能體，幫助智能體去學習和規(guī)劃出合適的策略。

Dyna框架如圖1所示。

圖1 Dyna框架Fig.1 Dyna framework

從圖1 可以看出，Dyna 框架表示一個規(guī)劃的過程。在智能體每次尋找路徑過程中，Dyna 框架都會通過獲得的模擬經(jīng)驗和完善模型來指導智能體的選擇，這樣可以使智能體在運行過程中不斷地思考，更快地選擇最優(yōu)路徑。相比其他算法，收斂速度有一定的優(yōu)勢。在城市交通路徑規(guī)劃中，將車輛作為智能體，車輛能夠移動的位置作為狀態(tài)空間，車輛選擇的每個動作作為動作空間。在車輛選擇到達目標位置的路徑的過程中，車輛首先在狀態(tài)空間中根據(jù)獎勵函數(shù)的值選擇下一個狀態(tài)，同時在系統(tǒng)中構(gòu)建關(guān)于環(huán)境的地圖。車輛繼續(xù)與真實環(huán)境交互獲得直接經(jīng)驗，車輛也與構(gòu)建的模型交互獲得模擬經(jīng)驗幫助智能車提前規(guī)劃路徑。在兩者共同作用下，車輛能夠避免選擇較差的路徑，提升車輛路徑規(guī)劃的速度。

3 基于Dyna框架的Sarsa算法

Dyna 學習框架下可以與多種強化學習算法相結(jié)合。結(jié)合方式為使用基礎(chǔ)算法與未知環(huán)境進行交互獲取真實樣本，再使用Dyna 框架對交互中建立的地圖模型進行多次規(guī)劃獲取虛擬樣本，最終使用真實樣本與虛擬樣本共同指導智能體的路徑規(guī)劃過程?；A(chǔ)算法選擇的是Sarsa 算法。首先Sarsa算法是一種在線學習的算法，它會在狀態(tài)轉(zhuǎn)換的過程中學習，并且整個學習和行動過程只使用一個策略，同時使用兩次?-貪婪的方式選擇出Q（S，A）和Q（S′，A′）。相對于其他算法，Sarsa 算法更加謹慎，與Dyna 學習框架的規(guī)劃過程相結(jié)合，既保證了算法的安全性，又能提升算法的運行速度。

Dyna-Sa（Dyna-Sarsa）在城市交通環(huán)境的流程如圖2所示。

圖2 Dyna-Sa框架流程Fig.2 Flowchart of Dyna-Sa framework

3.1 Dyna-Sa算法

將Sarsa 算法與Dyna 框架結(jié)合，目的是將Dyna-Sa 算法應(yīng)用到城市路徑規(guī)劃，具體如下：

研究的問題是單智能體路徑規(guī)劃，智能體為控制的車輛。在實現(xiàn)路徑規(guī)劃的過程中，智能體需要按照一些特定的規(guī)則尋找路徑，這些特定的規(guī)則就是算法，Dyna-Sa 算法作為新規(guī)則應(yīng)用到城市路徑規(guī)劃問題中。在城市路徑規(guī)劃中，隨著車輛的運行，其所處的環(huán)境也在不斷變化，這對于路徑規(guī)劃是很大挑戰(zhàn)。Dyna 框架可以很好地解決這個問題，智能體既從模型中獲得模擬經(jīng)驗，也從直接交互的環(huán)境中獲得經(jīng)驗，兩種經(jīng)驗?zāi)軌驗橹悄荏w選路提供指導，智能體可以快速找到一條安全的路徑。

下面給出Dyna-Sa算法步驟：

1）初始化嘗試要理解得到的模型Model（s，a）；

2）對于每一輪迭代，先根據(jù)當前狀態(tài)和Q（S，A）用?-貪婪的方式得到新狀態(tài)S′和獎勵R；

3）然后用Sarsa更新價值函數(shù)Q（S，A）；

4）用R，S′更新模型Model（s，a）（與真實環(huán)境交互完畢后，進行n次模擬）；

5）每次模擬都隨機選擇一個之前出現(xiàn)過的狀態(tài)S，并在此基礎(chǔ)上隨機選擇一個動作A；

6）基于模型Model（S，A）得到S′和R；

7）再使用Sarsa更新價值函數(shù)：

Q(S，A)=Q(S，A) +α(R+γQ(S′，A′) -Q(S，A))

Dyna-Sa算法基本流程中，外部循環(huán)過程直接利用數(shù)據(jù)經(jīng)驗去構(gòu)建環(huán)境模型，從而更新值函數(shù)，內(nèi)部循環(huán)過程使用構(gòu)建模型去生成新的模擬經(jīng)驗，用來更新值函數(shù)，對較于簡單的規(guī)劃過程或者強化學習算法，Dyna-Sa算法呈現(xiàn)出更高的效率。

Dyna-Sa 是保證安全性的一種算法。它的安全性取決于基礎(chǔ)算法和框架的配合。基礎(chǔ)算法Sarsa 使用了廣義策略迭代的思想，會使用下一步的狀態(tài)S′和根據(jù)狀態(tài)給出的動作A′的Q值來對目標值進行估計。這就會對目標值的選擇更加敏感，對于獎勵值低的狀態(tài)，智能體就會選擇遠離。同時使用Dyna 框架進行不斷地模擬運行，在運行過程中能夠記錄下有風險的行為，智能體能夠避免這些路徑而選擇安全性更高的路徑。

在速度方面，Dyna-Sa 使用了Dyna 框架，直接對環(huán)境進行建模，算法同時獲得模擬經(jīng)驗和直接交互的經(jīng)驗，等同于智能體在未知環(huán)境中使用較少的時間嘗試了更多的路徑。相對于其他算法，能夠幫助更快的智能體選擇最優(yōu)路徑，最終有效提高了整個算法的收斂速度。

3.2 算法分析

目前，Dyna-Q 算法已經(jīng)成功應(yīng)用到一些模擬環(huán)境中，這些場景與城市交通環(huán)境有一些差異。首先討論Sarsa 算法和Q-學習算法的不同點，以及選擇Sarsa 算法應(yīng)用到Dyna 框架中的原因。

這兩種算法的差異主要體現(xiàn)在更新函數(shù)的不同，Sarsa 使用的是利用下次狀態(tài)所采取的動作對應(yīng)的Q值來更新Q值，Q-學習使用下次狀態(tài)的最大Q值來更新。通過分析這兩種更新方式，可以得到兩種算法的特性：Sarsa 算法會探索更多的可能性，而Q-學習算法則會更傾向于選擇最大可能性的選擇。在學習效果方面，Q-學習算法具備學習到全局最優(yōu)的能力，Sarsa 則相對差一些。收斂速度方面，Sarsa 與Q-學習算法有相似的效果。

城市道路復雜，車流量較大，當從車輛出發(fā)點到目標點進行路徑規(guī)劃時，需要考慮很多因素。其中一個重要因素是避開車輛擁堵路段，那么對于城市交通環(huán)境下的路徑規(guī)劃，最短的路徑并不一定是最優(yōu)的路徑。Sarsa 算法和Q-學習算法都能在訓練中選擇遠離擁堵路段的路徑。同時需要考慮在車輛運行過程中，在規(guī)劃路線中發(fā)生擁堵的情況。Sarsa 算法能夠探索更多可能性，在規(guī)劃路線路況發(fā)生變化時，能夠做出較快改變，選擇其他暢通路線。

強化學習算法需要在與環(huán)境的交互中通過學習策略來獲得最大化回報或?qū)崿F(xiàn)特定目標，與其他路徑規(guī)劃應(yīng)用場景不同，城市交通路徑規(guī)劃的成本較高，在智能體汽車訓練過程中，難免與障礙物發(fā)生碰撞。需要選擇較為安全的路徑規(guī)劃算法。Sarsa 算法會選擇更加保守的策略，在更新Q值的時候已經(jīng)為未來規(guī)劃好了動作，能夠有效避免碰撞。在算法與框架結(jié)合過程中，存在算法不收斂和計算時間過長的情況。對于算法不收斂的情況，需要考慮到基礎(chǔ)算法自身特點，與Q-學習算法相比，Sarsa 算法對低獎勵值的狀態(tài)更加敏感，在選擇下一步動作時會規(guī)避風險，這是一個較為安全的行動策略，但在障礙物較為密集的情況下，智能體較低概率通過獎勵值低的狀態(tài)，導致在局部區(qū)域產(chǎn)生死循環(huán)，Dyna-Sa 算法無法收斂。通過調(diào)整系統(tǒng)參數(shù)來避免該情況，提高系統(tǒng)貪婪值使得智能體探索更多未知狀態(tài)，降低盲目選擇高獎勵的概率，最終減少算法不收斂的情況。具體參數(shù)選擇在仿真實驗部分詳細說明。

計算時間過長原因是規(guī)劃次數(shù)選擇不當。增加規(guī)劃次數(shù)有利于增加虛擬經(jīng)驗，更好地幫助智能體選擇路徑。但過多規(guī)劃會占用大量系統(tǒng)內(nèi)存，路徑規(guī)劃目的是更快地選擇一條安全的路徑到達目標狀態(tài)。規(guī)劃次數(shù)過多影響系統(tǒng)整體運行速度，這與期望目標產(chǎn)生沖突。在經(jīng)過多次仿真實驗后得出：當規(guī)劃次數(shù)為30 時，算法表現(xiàn)較優(yōu)。在仿真實驗中，由于建立的地圖模型規(guī)模較小，所以規(guī)劃次數(shù)選擇較少的數(shù)值。隨著模型復雜化，規(guī)劃次數(shù)應(yīng)當相應(yīng)增加。

3.3 算法復雜度分析

強化學習算法復雜度與狀態(tài)空間大小n和智能體訓練次數(shù)m相關(guān)，在Dyna 框架模擬運行的次數(shù)可以認為在每次訓練次數(shù)中，所以Dyna-Sa算法的時間復雜度為O（m（n-1））。

4 仿真實驗

實驗部分是將提出的算法和城市交通路徑規(guī)劃問題結(jié)合起來進行仿真實驗，通過與其他幾種經(jīng)典的強化學習路徑規(guī)劃算法的實驗結(jié)果進行對比，來驗證該算法的性能。首先做出如下假設(shè)：不考慮智能車與障礙物邊界碰撞問題以及交通信號燈等外在因素，僅將道路邊界與擁堵車流作為障礙物。在本章中使用兩個實驗來證明提出算法的有效性。

4.1 仿真環(huán)境

本文代碼的運行基于Intel Core i7-7700HQ CPU@2.80 GHz 的處理器、NVIDIA GeForce GTX1060 的顯卡以及8 GB 內(nèi)存的硬件環(huán)境，使用Windows 10 操作系統(tǒng)搭建軟件環(huán)境，實驗平臺是PyCharm，編程語言是Python。

本實驗驗證算法的地圖由柵格法建立。需要選擇合適的柵格尺寸，為保證規(guī)劃精度，同時確保智能體汽車的安全，將柵格尺寸設(shè)定為恰好與模擬智能車的外輪廓邊長相同。地圖中的障礙物固定生成，智能體汽車在柵格內(nèi)可執(zhí)行4 個動作，分別為上、下、左、右。

4.2 不同規(guī)劃步數(shù)收斂速度對比

首先使用柵格建立一個的無障礙地圖，智能體從初始狀態(tài)到達目標狀態(tài)。引入Dyna 框架的目的是將基于模型的強化學習和模型無關(guān)的強化學習結(jié)合起來。通過實驗做出規(guī)劃步數(shù)分別為0、5、50的步數(shù)變化曲線，如圖3。其中圖3中的N表示規(guī)劃步數(shù)，橫軸表示智能體的迭代次數(shù)，縱軸表示每次迭代智能體從初始狀態(tài)到目標狀態(tài)所需步數(shù)。

圖3 不同規(guī)劃步數(shù)收斂速度對比Fig.3 Convergence speed comparison of different planning steps

從實驗結(jié)果可以看出：隨著迭代次數(shù)的增加，圓形表示的規(guī)劃步數(shù)為50 的情況收斂速度最快，矩形代表的規(guī)劃步數(shù)為5 的情況次之，星形表示的無規(guī)劃的情況最慢。最終可以得出結(jié)論：智能體使用模型產(chǎn)生的模擬經(jīng)驗越多，狀態(tài)值函數(shù)的更新次數(shù)越多，那么它的步數(shù)收斂的速度越快。

4.3 模擬地圖下的仿真

本章使用柵格構(gòu)建一個模擬地圖，地圖尺寸為6×6，如圖4～5 所示。其中左上角五角星表示智能車初始狀態(tài)，右下角圓形表示目標狀態(tài)，地圖中間黑色矩形表示障礙物，白色區(qū)域為可移動區(qū)域。任務(wù)是找到一條路徑將智能車從初始狀態(tài)移動到目標狀態(tài)。

圖4 無障礙地圖模型Fig.4 Map model without obstacle

圖5 有障礙地圖模型Fig.5 Map model with obstacles

4.4 仿真參數(shù)選擇

使用Q-學習算法、Sarsa 算法和Dyna-Q 算法作為對比實驗，與新算法進行比較。所有實驗的相關(guān)參數(shù)如下：算法最大嘗試回合設(shè)置為100，學習率α，折扣因子γ，貪婪值。其中的學習率、折扣因子和貪婪值需要通過運行實驗調(diào)整參數(shù)獲得，實驗如下。

首先調(diào)整的是強化學習算法的學習率。學習率可以理解為算法的學習效率。當學習率較大時，算法的學習速度快，但是容易導致易損失值爆炸；當學習率較小時，算法的學習速度慢，同時會出現(xiàn)過擬合問題，算法的收斂速度變慢。由于仿真環(huán)境較為簡單，所以不需要設(shè)置動態(tài)變化的學習率便可使算法實現(xiàn)最優(yōu)效果。通過實驗可以得到：當學習率小于0.01時，算法收斂速度過慢，影響算法性能；當學習率大于0.01時，梯度可能會在最小值附近來回震蕩，甚至導致無法收斂；當學習率等于0.01 時，收斂速度最優(yōu)，同時無其他副作用。算法的學習率設(shè)置為0.01。

然后調(diào)整折扣因子尋找最優(yōu)性能。折扣率能夠避免產(chǎn)生狀態(tài)的無限循環(huán)，當折扣率較小時，智能體更加在意短期回報；當折扣率較大時，長期回報變得更重要。通過實驗得出當折扣因子為0.9 時能夠確保收斂的速度較快，同時不會導致不收斂的方差，更加適合仿真實驗地圖環(huán)境。

由于使用Sarsa算法作為基礎(chǔ)算法，其采樣的策略和指導的策略都是采用的貪婪策略，這就涉及貪婪值的選取問題。為此，最優(yōu)貪婪值需要設(shè)計實驗來獲取，保證算法性能，其他參數(shù)在貪婪值變化的過程中保持不變。在實驗過程中，貪婪度在（0，1）區(qū)間取值，一些經(jīng)典文獻將貪婪值劃分成3 個區(qū)間，分別是（0，0.1］、（0.1，0.2］、（0.2，1）。將3 種不同貪婪度的Dyna-Sa 算法應(yīng)用到有障礙地圖中，進行100 次迭代訓練，同時使用收斂速度和碰撞次數(shù)作為評價標準。最終可以得到如表1的結(jié)果。

從表1 中可以看出貪婪度處于（0.1，0.2］區(qū)間時，算法能夠表現(xiàn)出最優(yōu)性能。在貪婪度處于（0，0.1］區(qū)間時，算法會選擇獎勵值最大的狀態(tài)，所以收斂速度較慢，同時碰撞次數(shù)較多，安全性較差。貪婪度處于（0.2，1）區(qū)間時，算法表現(xiàn)過于保守，智能體會在某個安全區(qū)域內(nèi)停滯，導致算法無法收斂，同時碰撞次數(shù)較多。

最終將學習率設(shè)置為0.01，折扣因子設(shè)置為0.9，貪婪度值在仿真實驗的有障礙地圖設(shè)置為0.2，在無障礙地圖中設(shè)置為0.1。

獎勵R的設(shè)置如式（2）所示：

表1 不同貪婪度下的算法性能Tab.1 Algorithm performance under different greedinesses

仿真地圖環(huán)境較簡單，獎勵R的取值對實驗結(jié)果影響有限，所以選擇簡單的值便可實現(xiàn)算法功能。智能體在模擬地圖中移動時，未碰撞障礙物時獎勵值為0，碰撞到障礙物時獎勵值為-1，移動到目標點時獎勵值為2。

4.5 仿真實驗結(jié)果及分析

按照前面的參數(shù)設(shè)置，將4 種算法分別引入地圖中進行實驗。每個算法進行100 次迭代訓練，其中使用Dyna 框架的規(guī)劃次數(shù)為30，就是將智能體與模擬環(huán)境進行30次交互來獲得虛擬經(jīng)驗。每個算法實驗重復10 次，然后取平均值作為實驗輸出數(shù)據(jù)。算法性能的評價標準為算法平均運行時間、平均碰撞障礙物次數(shù)、達到收斂所需回合和達到收斂所需時間。

無障礙地圖和有障礙地圖實驗結(jié)果如表2～3所示。從表2～3中的數(shù)據(jù)可以看出，使用Dyna框架的算法的各項數(shù)據(jù)都要優(yōu)于未使用框架的算法，這就體現(xiàn)了規(guī)劃的高效性。在無障礙地圖的實驗中，Dyna-Q算法和Dyna-Sa算法性能相似。在有障礙地圖的實驗中，平均碰撞數(shù)、達到收斂回合和達到收斂時間方面，Dyna-Sa算法均要優(yōu)于Dyna-Q算法，但在平均運行總時間方面，Dyna-Sa表現(xiàn)稍差。原因是Dyna-Sa算法是一種風險敏感算法，在學習初期，Dyna-Sa算法因躲避障礙物而放棄較近路徑，保證安全性，但會導致時間浪費，Sarsa算法同理。在多次學習后，Dyna-Sa算法得到的經(jīng)驗會指導智能體選擇最優(yōu)路徑，所需時間會逐漸縮短。綜合表中數(shù)據(jù)可以得出：Dyna-Sa算法從總體看較優(yōu)于其他三種算法，在保證安全性的同時，能夠在較短時間內(nèi)找到一條較優(yōu)路徑，滿足城市交通路徑規(guī)劃這種特殊環(huán)境的要求。

表2 無障礙地圖實驗結(jié)果Tab.2 Experimental results on map without obstacle

表3 有障礙地圖實驗結(jié)果Tab.3 Experimental results on map with obstacles

圖6 和圖7 分別表示無障礙物和有障礙物環(huán)境下算法收斂情況，橫軸表示迭代次數(shù)，縱軸表示算法每次迭代結(jié)束時經(jīng)過的步數(shù)。

圖6 無障礙物環(huán)境下算法收斂情況Fig.6 Convergence of algorithm in obstacle-free environment

圖7 有障礙物環(huán)境下算法收斂情況Fig.7 Convergence of algorithm in environment with obstacles

為了更好地展示算法性能，方便讀者閱讀，將整個迭代過程進行分割。在無障礙環(huán)境中，圖6（a）部分表示前25回合算法收斂情況，可以得出：所有算法在17 回合后都已經(jīng)收斂；Dyna-Sa 算法和Dyna-Q 算法收斂速度相似，遠優(yōu)于不使用Dyna 框架的算法。圖6（b）部分表示26 回合到100 回合的算法收斂情況，可以得出：所有算法都收斂，沒有異常情況出現(xiàn)。圖7（a）、（b）、（c）分別表示前30 回合、31～70 回合、71～100 回合有障礙環(huán)境算法收斂情況，所有算法都呈現(xiàn)同一趨勢：首先步數(shù)較少，然后突然升高，最終趨于平穩(wěn)。原因是在有障礙物的環(huán)境中，智能體首先嘗試碰撞障礙物獲取環(huán)境狀態(tài)，步數(shù)較少，然后在躲避障礙物的過程，產(chǎn)生大量的步數(shù)，最終產(chǎn)生一條通往目標狀態(tài)的完整路徑，達到收斂狀態(tài)。Sarsa 算法在整個過程無法收斂；Q-Learning 算法在37回合后能夠達到收斂；Dyna-Q 算法和Dyna-Sa 算法分別在24 回合和18 回合達到收斂。Dyna-Sa 是一種風險敏感算法，所以迭代產(chǎn)生平均步數(shù)較多。

5 結(jié)語

針對城市交通路徑規(guī)劃問題，新算法Dyna-Sa 主要是以Dyna 為框架，使用Sarsa 的更新函數(shù)和決策方式，將模型無關(guān)和基于模型的算法結(jié)合的Dyna 框架向無模型的強化學習算法引入模型，使用學習到的經(jīng)驗來訓練模型，同時利用模型來產(chǎn)生模擬的經(jīng)驗，最后與從環(huán)境中直接學習的經(jīng)驗兩者共同作用于值函數(shù)的更新。本文分析了城市交通路徑規(guī)劃的特殊性，比較了Sarsa 算法和經(jīng)典強化學習算法Q-學習的特點，選擇了更為保守并且適合的Sarsa算法與Dyna框架結(jié)合。

仿真實驗表明智能體規(guī)劃次數(shù)越多，學習到的模擬經(jīng)驗就越多，算法的收斂速度越快。第二個實驗將提出的算法與其他3種算法在仿真地圖上對比，結(jié)果顯示Dyna-Sa算法能夠有效避免障礙物，提高了路徑規(guī)劃的安全性，同時能夠保證快速找到一條符合要求的路徑，更加適合應(yīng)用在城市交通環(huán)境中。

未來工作主要是研究算法在動態(tài)交通環(huán)境中表現(xiàn)，以及在獎勵值的設(shè)置中增加變量函數(shù)來提升算法整體的收斂速度，同時提高車輛路徑規(guī)劃過程中的安全性。