[發(fā)明專利]一種改進(jìn)的Dyna-Q學(xué)習(xí)路徑規(guī)劃算法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110278598.0
• 申請(qǐng)日: 2021-03-16
• 公開(kāi)（公告）號(hào): CN112964272A
• 公開(kāi)（公告）日: 2021-06-15
• 發(fā)明（設(shè)計(jì)）人: 石振;王保華;王科銀;張建輝
• 申請(qǐng)（專利權(quán)）人: 湖北汽車工業(yè)學(xué)院
• 主分類號(hào): G01C21/34
• 分類號(hào): G01C21/34
• 代理公司: 濟(jì)南泉城專利商標(biāo)事務(wù)所 37218
• 代理人: 張貴賓

本發(fā)明將基于模型的算法和模型無(wú)關(guān)的算法相結(jié)合的Dyna框架結(jié)合Q?learning算法應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃，同時(shí)為了加快算法的收斂，在Q值初始化時(shí)引入人工勢(shì)場(chǎng)法初始化Q值，仿真實(shí)驗(yàn)表明，加入規(guī)劃后的算法收斂前的運(yùn)行幕數(shù)會(huì)大大減少，并且規(guī)劃步數(shù)越大算法收斂前運(yùn)行幕數(shù)越少，但是加入規(guī)劃會(huì)增加算法的時(shí)間復(fù)雜度；改進(jìn)的Dyna?Q學(xué)習(xí)算法加快了算法的收斂速度，能夠高效的完成移動(dòng)機(jī)器人在未知環(huán)境中的路徑規(guī)劃問(wèn)題。

技術(shù)領(lǐng)域

本發(fā)明涉及機(jī)器人路徑規(guī)劃技術(shù)領(lǐng)域，具體涉及一種改進(jìn)的Dyna-Q學(xué)習(xí)路徑規(guī)劃算法。

背景技術(shù)

路徑規(guī)劃技術(shù)可以引導(dǎo)移動(dòng)機(jī)器人從起始位置避開(kāi)障礙物到達(dá)目標(biāo)位置，是實(shí)現(xiàn)移動(dòng)機(jī)器人自主導(dǎo)航的關(guān)鍵。根據(jù)對(duì)環(huán)境信息的掌握程度不同，路徑規(guī)劃分為全局路徑規(guī)劃和局部路徑規(guī)劃。全局路徑規(guī)劃是在已知的環(huán)境中規(guī)劃出移動(dòng)機(jī)器人的運(yùn)動(dòng)路徑，常用的全局路徑規(guī)劃算法有可視圖、格柵法、拓?fù)浞ǖ龋欢植柯窂揭?guī)劃的環(huán)境信息未知或者是部分已知，比較廣泛應(yīng)用的算法有神經(jīng)網(wǎng)絡(luò)法、人工勢(shì)場(chǎng)法、強(qiáng)化學(xué)習(xí)算法等。在眾多的路徑規(guī)劃算法中，強(qiáng)化學(xué)習(xí)算法因其無(wú)需對(duì)環(huán)境進(jìn)行建模而得到廣泛的應(yīng)用。

強(qiáng)化學(xué)習(xí)算法主要通過(guò)智能體不斷與環(huán)境交互獲得外部環(huán)境信息實(shí)現(xiàn)多步?jīng)Q策問(wèn)題的優(yōu)化求解。根據(jù)是否已知環(huán)境模型強(qiáng)化學(xué)習(xí)可分為有模型強(qiáng)化學(xué)習(xí)和無(wú)模型強(qiáng)化學(xué)習(xí)。

Q-learning是一種典型的無(wú)模型強(qiáng)化學(xué)習(xí)算法。Q-learning算法通過(guò)構(gòu)建Q表存儲(chǔ)狀態(tài)動(dòng)作值，智能體在與環(huán)境交互的過(guò)程中獲得獎(jiǎng)勵(lì)從而更新Q值。

基于模型的強(qiáng)化學(xué)習(xí)算法通過(guò)智能體與環(huán)境交互來(lái)優(yōu)化模型，而直接的強(qiáng)化學(xué)習(xí)算法通過(guò)智能體與環(huán)境交互來(lái)優(yōu)化策略。Dyna學(xué)習(xí)框架結(jié)合基于模型的學(xué)習(xí)和直接學(xué)習(xí)，智能體一方面利用與環(huán)境交互的經(jīng)驗(yàn)來(lái)優(yōu)化策略，另一方面利用經(jīng)驗(yàn)來(lái)學(xué)習(xí)模型，學(xué)習(xí)到的模型同樣用來(lái)指導(dǎo)智能體選擇動(dòng)作。

人工勢(shì)場(chǎng)模型是Khatib提出的一種虛擬力法。該方法假設(shè)移動(dòng)機(jī)器人在一種虛擬力場(chǎng)下運(yùn)動(dòng)。目標(biāo)點(diǎn)對(duì)機(jī)器人產(chǎn)生引力，引導(dǎo)機(jī)器人朝其運(yùn)動(dòng)，障礙物對(duì)機(jī)器人產(chǎn)生斥力，避免機(jī)器人與其產(chǎn)生碰撞，機(jī)器人在運(yùn)動(dòng)路徑上的每一點(diǎn)所受的合力等于這一點(diǎn)的引力和斥力之和。

Dyna學(xué)習(xí)框架可以和其他的無(wú)模型強(qiáng)化學(xué)習(xí)算法結(jié)合。本文選擇Dyna框架和Q-learning算法相結(jié)合的Dyna-Q學(xué)習(xí)應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃中。雖然，Dyna-Q學(xué)習(xí)相較于Q-learning算法增加了規(guī)劃過(guò)程，可以在一定程度上提升算法的性能，但其無(wú)法改變Q-learning算法由于把Q值初始化為0或者是隨機(jī)數(shù)而導(dǎo)致的算法初期搜索的盲目性，從而導(dǎo)致算法初期產(chǎn)生大量的無(wú)效迭代。為了解決Q-learning算法的上述不足，引入人工勢(shì)場(chǎng)法對(duì)算法進(jìn)行改進(jìn)。

發(fā)明內(nèi)容

針對(duì)現(xiàn)有技術(shù)中關(guān)于Dyna框架和Q-learning算法相結(jié)合中存在的不足，本發(fā)明特提供一種改進(jìn)的Dyna-Q學(xué)習(xí)路徑規(guī)劃算法。

一種改進(jìn)的Dyna-Q學(xué)習(xí)路徑規(guī)劃算法，包括以下步驟：

1. 輸入環(huán)境信息：起始位置和目標(biāo)位置；

2. 設(shè)置參數(shù)ɑ、γ、ε、ζ，初始化模型M(s，a)；

3. 初始化Q表；

4. 循環(huán)；

5. 初始化狀態(tài)S；

6. 采用ε-貪婪策略選擇動(dòng)作A；

7. 執(zhí)行所選動(dòng)作到達(dá)下一狀態(tài)S’并獲得相應(yīng)獎(jiǎng)勵(lì)R；

8. 更新Q值；

9. 用R和S’更新模型M(s，a)；

10.n次模擬；

11. 每次模擬都隨機(jī)選擇一個(gè)之前出現(xiàn)過(guò)的狀態(tài)S以及該狀態(tài)下的動(dòng)作A；

12. 基于模型M(S，A)得到獎(jiǎng)勵(lì)R和下一狀態(tài)S’；

13.再次更新Q值；

14. 達(dá)到一定步數(shù)或一定收斂條件，終止；