基于滾動 Q 學(xué)習(xí)的機(jī)器人路徑規(guī)劃算法

張婷宇　鄭寶娟

摘 要 采用滾動Q學(xué)習(xí)的方法解決大規(guī)模環(huán)境下機(jī)器人視野域范圍有限，同時有效改善因 Q 學(xué)習(xí)的狀態(tài)空間增大而產(chǎn)生的維數(shù)災(zāi)難等問題。仿真實(shí)驗結(jié)果表明，應(yīng)用該算法機(jī)器人可在復(fù)雜的未知環(huán)境中快速地規(guī)劃出一條從起點(diǎn)到終點(diǎn)的優(yōu)化避障路徑， 效果令人滿意。

關(guān)鍵詞 路徑規(guī)劃 滾動學(xué)習(xí) Q學(xué)習(xí) 智能算法

中圖分類號：TP242文獻(xiàn)標(biāo)識碼：A

0引言

目前，大多數(shù)自主移動機(jī)器人均是在高度結(jié)構(gòu)化的環(huán)境中執(zhí)行預(yù)先規(guī)定的動作序列，但在新的環(huán)境下或遇到意外情況時，卻不能很好地完成指定任務(wù)，其主要原因是當(dāng)機(jī)器人面對非結(jié)構(gòu)化且存在不確定性的實(shí)際環(huán)境時沒有主動學(xué)習(xí)和自適應(yīng)的能力。自適應(yīng)路徑規(guī)劃可以部分解決這一問題，即機(jī)器人在與環(huán)境的不斷交互過程中，規(guī)劃出一條從指定的起始點(diǎn)到目標(biāo)點(diǎn)，并且滿足一定優(yōu)化標(biāo)準(zhǔn)的、安全避障的路徑。該算法是機(jī)器人應(yīng)用研究的一個重要方面，屬于NP-hard問題。針對上述研究現(xiàn)狀及不足，本文提出了滾動Q學(xué)習(xí)機(jī)器人路徑規(guī)劃算法，以滾動學(xué)習(xí)算法來解決Q學(xué)習(xí)可能發(fā)生的維數(shù)災(zāi)難問題。

1基于滾動的 Q 學(xué)習(xí)算法

算法的基本思想是充分利用機(jī)器人實(shí)時探測到的局部環(huán)境信息，以滾動方式分別在各個規(guī)模較小的視野域內(nèi)進(jìn)行 Q 學(xué)習(xí)，并得到一條該視野域內(nèi)的局部最優(yōu)路徑。機(jī)器人沿該路徑前進(jìn)一段距離后 （該距離長度記為 ），在新的視野域內(nèi)重新獲取動作-狀態(tài)對進(jìn)行 Q 學(xué)習(xí)， 并規(guī)劃當(dāng)前路徑。這樣，在一條條局部最優(yōu)路徑的導(dǎo)航下，機(jī)器人最終沿著一條全局優(yōu)化的避碰路徑到達(dá)終點(diǎn)。

在視野域內(nèi)障礙物較少時，機(jī)器人走1/3長的局部路徑后才在新的視野域內(nèi)繼續(xù)規(guī)劃新路徑;在障礙較多時，每走2步再重新規(guī)劃新路徑;只有在障礙物很多時，機(jī)器人走1步后即重新規(guī)劃。 的取值很難有一個嚴(yán)格的最優(yōu)界定，它只能是根據(jù)實(shí)驗結(jié)果抽象出比較保守的值，其取值原則是必須能保證各個局部路徑疊加后仍能使全局路徑最優(yōu)或近似最優(yōu)。此外，算法得到的路徑是否近似最優(yōu)，會受到視野域尺寸大小的影響。若將視野域半徑設(shè)置過小，則機(jī)器人獲得的環(huán)境信息將過于局部化，規(guī)劃過程容易陷入局部最小;若將視野域半徑設(shè)置過大，則又使?fàn)顟B(tài)-動作對大增，降低算法的收斂速度。因此本實(shí)驗中對于算法中的視野域半徑參數(shù)是根據(jù)大量實(shí)驗的經(jīng)驗來設(shè)定的。大量的實(shí)驗結(jié)果表明，一般視野域半徑范圍取整個工作環(huán)境半徑的 1/10 左右為適。

Step 1：設(shè)置起點(diǎn)gstart和終點(diǎn)gend，并初始化工作環(huán)境WS，機(jī)器人的視野半徑r，以及保守閾值n1和n2;

Step 2：若機(jī)器人在當(dāng)前視野域內(nèi)探測到gend，則用新算法規(guī)劃出一條從機(jī)器人當(dāng)前位置到gend的優(yōu)化路徑，規(guī)劃算法終止;

Step 3：產(chǎn)生gsub，機(jī)器人以PR為出發(fā)點(diǎn)，gsub為終點(diǎn)，用滾動Q學(xué)習(xí)算法規(guī)劃出一條局部優(yōu)化路徑，并記錄下該路徑長度local_pathlen;

Step 4：計算Pobstacle、 ，機(jī)器人沿局部規(guī)劃路徑行進(jìn);

Step 5：根據(jù)機(jī)器人當(dāng)前位置PR和視野半徑r更新視野域，并對視野域內(nèi)環(huán)境作柵格化處理，轉(zhuǎn)至Step 2。

2仿真實(shí)驗

通過仿真實(shí)驗來驗證本文提出算法的有效性和先進(jìn)性。實(shí)驗環(huán)境為 Windows XP， Intel（R） Core（TM）2Duo CPU T6400 2.00 GHz， 2G 內(nèi)存，編譯工具為VC++6.0。

為了驗證在較大規(guī)模環(huán)境下全局滾動 Q 學(xué)習(xí)算法的效果，在 50 ？50 的未知環(huán)境下做了大量的實(shí)驗，效果令人滿意。以半徑為r = 5的機(jī)器人為例，即 實(shí)時地進(jìn)行動態(tài)調(diào)整。根據(jù)大量實(shí)驗總結(jié)的經(jīng)驗，設(shè)置 n1= 0.3，n2= 0.7。在第1個視野域內(nèi)，機(jī)器人用滾動算法規(guī)劃出一條局部路徑記為 l1，并計算出 Pobstacle= 0.25 < n1，所以機(jī)器人將 設(shè)為l1長度的1 /3 （即 = 3）;然后沿l1前進(jìn)3步后，再根據(jù)新的 視野域重新映射子目標(biāo)并規(guī)劃路徑，重新計算 ;重復(fù)上述過程;直到探測到 gend并規(guī)劃完最后一段路徑為止。

3結(jié)論

在未知環(huán)境下采用標(biāo)準(zhǔn)的Q學(xué)習(xí)算法進(jìn)行機(jī)器人路徑規(guī)劃時，由于缺乏對環(huán)境的先驗知識，使得算法速度緩慢，特別是隨著環(huán)境規(guī)模增大，學(xué)習(xí)狀態(tài)空間增大，甚至?xí)l(fā)生維數(shù)災(zāi)難。為此，本文提出了滾動Q學(xué)習(xí)算法，該算法在未知較大規(guī)模環(huán)境下進(jìn)行滾動學(xué)習(xí)，采取這些措施后，大幅提高了算法的收斂速度和環(huán)境適應(yīng)能力。仿真實(shí)驗結(jié)果表明該算法的效果令人滿意，具有算法簡單、速度快、環(huán)境適應(yīng)性強(qiáng)等特點(diǎn)。特別是當(dāng)機(jī)器人對復(fù)雜環(huán)境中障礙物信息一無所知以及環(huán)境規(guī)模較大時，更能體現(xiàn)該算法的優(yōu)越性。該算法具有自學(xué)習(xí)和自適應(yīng)能力，是一種很有發(fā)展前景的算法。

參考文獻(xiàn)

[1] Ahuh，D，J&J.H.Park.Path planning and navigationfor autonomous mobile robot[C].IEEE 28th the AnnualConf of the Industrial Electronics Society. Seville： IEEEPress，2002：1538-1542.

[2] Vladimiro Miranda， Nuno Fonseca. EPSO-evolutionaryparticle swarm optimization， a new algorithm withapplication in power systems[C]. Transmission andDistributionConf and Exhibition.Yokohama，2002：745-750.

[3] 宋清昆，胡子嬰.基于經(jīng)驗知識的 Q-學(xué)習(xí)算法[J].自動化技術(shù)與應(yīng)用，2006，25（11）：10-12.