基于最小二乘支持向量機的移動機器人導航

侯艷麗

（商丘師范學院計算機與信息技術(shù)學院，河南商丘476000）

移動機器人要在未知環(huán)境中安全地完成指定任務(wù)，導航系統(tǒng)應(yīng)具有靈活性和適應(yīng)性，使其能適應(yīng)工作環(huán)境，提高工作效率[1]。要達到這一目的，學習是一個不可缺少的重要環(huán)節(jié)。強化學習以其自學習和自適應(yīng)的特點成為求解不完全、離散的馬爾可夫決策問題的有效方法，已經(jīng)廣泛應(yīng)用在機器人研究領(lǐng)域[2-7]。在國內(nèi)外大量的強化學習研究中，大都把系統(tǒng)的狀態(tài)看作有限的集合。但是在實際機器人導航中，系統(tǒng)的狀態(tài)空間往往是連續(xù)的，并存在狀態(tài)變量的空間復(fù)雜性問題[8]。為了解決強化學習中的泛化問題，常用神經(jīng)網(wǎng)絡(luò)值函數(shù)做最優(yōu)策略逼近[2-7]。盡管這些方法可以提高強化學習的效率，但在理論上是非凸的，容易陷入局部極小。文獻[9]提出利用LS-SVM實現(xiàn)由系統(tǒng)狀態(tài)-動作對到Q值函數(shù)的映射，同時為了提高學習速度，引入滾動時間窗。該方法與神經(jīng)網(wǎng)絡(luò)相比，泛化能力明顯提高，簽于此，筆者將其用于CASIA-I的導航控制中。

1 移動機器人模型

安裝有觸覺紅外、近紅外和超聲等多傳感器的CASIA-I利用它們感知障礙物。它們的有效作用距離分別為dch=20 cm，dnear=45 cm和45～350 cm。將這些傳感器分成3組：1）由觸覺紅外ch1～ch3、近紅外nh1～nh3和超聲ul1～ul3構(gòu)成；2）由觸覺紅外ch4～ch8、近紅外nh4～nh8和超聲ul4～ul8構(gòu)成；3）由觸覺紅外ch9～ch11，近紅外nh9～nh11和超聲ul9～ul11構(gòu)成。

假設(shè)CASIA-I的動作有直行、右轉(zhuǎn)15°，左轉(zhuǎn)15°。直行的最大速度為每步dmax。不管是觸覺紅外還是近紅外，當探測到障礙物時，輸出為1，否則，輸出為0。取

di為障礙物到超聲的距離，ds為事先確定的安全區(qū)域的半徑，將CASIA-I工作環(huán)境分成：

1）自由空間FS

2）安全空間SS

3）非安全空間NSS

其他情況都歸并到該空間，在該空間中，至少存在一個障礙物。因此必須采取措施，避免相碰。

在上述空間劃分的基礎(chǔ)上，CASIA-I從當前狀態(tài)，執(zhí)行某一動作，達到其后續(xù)狀態(tài)，回報函數(shù)為：

2 基于LS-SVM的Q學習

Q學習的實現(xiàn)過程為：在每個時間步t，觀察當前狀態(tài)st，選擇和執(zhí)行動作at，再觀察后續(xù)狀態(tài)st+1并接受立即回報rt，然后用式（3）來調(diào)整Qt。

η控制學習速度，0≤γ≤1表示學習系統(tǒng)的遠視程度。

為了構(gòu)造LS-SVM，提高估計速度，樣本是窗式移動的[10]。即在將新數(shù)據(jù)加入樣本集之前要進行KKT[11]判斷，若滿足KKT條件，不更新訓練集，時間窗保持不變，若違反，滾動時間窗，重新訓練得到的LS-SVM。設(shè)t時刻訓練樣本集由過去L組數(shù)據(jù)構(gòu)成。

為了解決學習中探索與利用的兩難問題，LS-SVM的輸出被送入隨機動作選擇器。采用BoltzmanGibbs分布作為選擇策略[10]，則動作ak從動作集A={a1，a2，…am}中被選擇的概率為：

式中，T＞0為溫度參數(shù)，控制動作選擇的隨機程度。

3 LS-SVM的學習及導航算法

對L區(qū)間的數(shù)據(jù)進行建模，把回歸問題表示為約束優(yōu)化問題：

其中，γi反映區(qū)間內(nèi)樣本的重要程度，文中定義為：

建立Lagrange函數(shù)，并根據(jù)KKT條件，得到回歸模型為：

根據(jù)上述分析，CASIA-I導航算法描述如下：

第一步：初始化Q學習控制器及回歸模型的參數(shù)；

第二步：根據(jù)各傳感器提供的信息確定機器人的當前狀態(tài)st，如果st?FS，則執(zhí)行第三步。否則執(zhí)行：

1）構(gòu)造t時刻LS-SVM的學習訓練樣本集D；

2）根據(jù)貪心策略選擇最大Q值對應(yīng)的動作αt；

3）執(zhí)行動作αt，獲取下一時刻狀態(tài)St+1及立即回報rt；

4）按照式（3）更新Q值，得到目標值Qt；

5）判斷新數(shù)據(jù)（xt，Qt）是否違反KKT條件，若不違反，則保持時間窗不變，若違反，則將該數(shù)據(jù)加入訓練集并滾動時間窗；

第三步：根據(jù)傳感器提供的數(shù)據(jù)，調(diào)整移動機器人的運動方向，然后以每步dmax的最大速度向目標運動一步；

第四步：若不滿足學習結(jié)束條件，t←t+1，轉(zhuǎn)第二步。

4 仿真研究

對文中所提方法進行30次的獨立仿真運行，取η=0.16，γ=0.94，T=0.009，C=100，ε=0.006，σ=0.5，L=33。表1給出了系統(tǒng)學習性能比較，由表1可知，與文獻[5]提出的基于BP神經(jīng)網(wǎng)絡(luò)的Q學習系統(tǒng)相比，基于SVM的Q學習在每次仿真中均能以較少的學習次數(shù)獲得最優(yōu)策略，而基于LS-SVM則以更少的次數(shù)獲得最優(yōu)策略。

5 結(jié)束語

強化學習已經(jīng)應(yīng)用在移動機器人導航中，為了解決強化學習中的泛化問題，提出用基于時間窗的LS-SVM實現(xiàn)由系統(tǒng)狀態(tài)-動作對到的Q值函數(shù)的映射。實驗結(jié)果表明所提方法能夠使機器人在較少的學習次數(shù)內(nèi)無碰撞的到達目的地。

[1] 蔡自興，賀漢根，陳虹.未知環(huán)境中移動機器人導航控制研究的若干問題[J].控制與決策，2002，4（17）:385-391.CAI Zi-xing，HE Han-gen，CHEN Hong.Some issues for mobile robots navigation under unknown environments[J]Control and Decision，2002，4（17）:385-391.

[2] Cicirelli G，D’Orazio T，Distante A.Neural Q-learning control architectures for wall-following behavior[C]//Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems，2003.

[3] Carreras M，Ridao P，EI-Fakdi A.Semi-online neural Q-learning for real-time robot learning[C]//Proceedings of theIEEE/RSJ International Conference on Intelligent Robots and Systems，Las Vegas Nevada，2003：662-667.

表1 具體系統(tǒng)性能比較Tab.1 The comparison of system performance

[4] Kondo T，Ito K.A reinforcement learning with evolutionary state recruitment strategy for autonomous mobile robots control[J].Robotics ans Autonomous Systems，2004，46（2）:121-124.

[5] Yang G S，Chen K A，Cheng W.Mobile robot navigation using neural Q-Learning[C]//IEEE Proceedings of International Conference on Machine Learning and Cybernetics，Shanghai，China，2004：48-52.

[6] Yang G S，Hou Z G，Liang Z Z.Distributed visual navigation based on neural Q-learning for a mobile robot[C]//International Journal of Vehicle Autonomous Systems，Britain，2006：225-235.

[7] 秦政，丁福光，邊信黔.強化學習在移動機器人自主導航中的應(yīng)用[J].計算機工程與應(yīng)用，2007，43（18）:215-217.QIN Zheng，DING Fu-guang，BIAN Xin-qian.Application of reinforcement learning in autonomous navigation for mobile robot[J].Computer Engineering and Applications，2007，43（18）:215-217.

[8] Preu P，Delepoulies S，Raqcheville J C.A generic architecture for adaptive agents based on reinforcement learning[J].Information Sciences，2004，（161）:37-55.

[9] 王雪松，田西蘭，程玉虎.最小二乘支持向量機在強化學習系統(tǒng)中的應(yīng)用[J].系統(tǒng)仿真學報，2008，14（20）:3702-3706.WANG Xue-song，TIAN Xi-lan，CHEN Yu-hu.Application of least squares support vector machine to reinforcement learning system[J].Journal of System Simulatioin，2008，14（20）:3702-3706.

[10] BO C M，WANG Z Q，LU A J.Study and application on dynamic modeling method based on SVMand sliding time window techniques[C]//Proceedings of the 6th World Congress on Intelligent Control and Automation.Piscataway:Institute of Electrical and Electronics Engineerings Inc.Press，2006:4714-4718.

[11] Suykens J A K，Vandewale J.Least squares support vector machine classifiers[J].Neural Processing Letters，1999，9（3）:293-300.