基于最小二乘支持向量机的移动机器人导航

侯艳丽

（商丘师范学院计算机与信息技术学院，河南商丘476000）

移动机器人要在未知环境中安全地完成指定任务，导航系统应具有灵活性和适应性，使其能适应工作环境，提高工作效率[1]。要达到这一目的，学习是一个不可缺少的重要环节。强化学习以其自学习和自适应的特点成为求解不完全、离散的马尔可夫决策问题的有效方法，已经广泛应用在机器人研究领域[2-7]。在国内外大量的强化学习研究中，大都把系统的状态看作有限的集合。但是在实际机器人导航中，系统的状态空间往往是连续的，并存在状态变量的空间复杂性问题[8]。为了解决强化学习中的泛化问题，常用神经网络值函数做最优策略逼近[2-7]。尽管这些方法可以提高强化学习的效率，但在理论上是非凸的，容易陷入局部极小。文献[9]提出利用LS-SVM实现由系统状态-动作对到Q值函数的映射，同时为了提高学习速度，引入滚动时间窗。该方法与神经网络相比，泛化能力明显提高，签于此，笔者将其用于CASIA-I的导航控制中。

1 移动机器人模型

安装有触觉红外、近红外和超声等多传感器的CASIA-I利用它们感知障碍物。它们的有效作用距离分别为dch=20 cm，dnear=45 cm和45～350 cm。将这些传感器分成3组：1）由触觉红外ch1～ch3、近红外nh1～nh3和超声ul1～ul3构成；2）由触觉红外ch4～ch8、近红外nh4～nh8和超声ul4～ul8构成；3）由触觉红外ch9～ch11，近红外nh9～nh11和超声ul9～ul11构成。

假设CASIA-I的动作有直行、右转15°，左转15°。直行的最大速度为每步dmax。不管是触觉红外还是近红外，当探测到障碍物时，输出为1，否则，输出为0。取

di为障碍物到超声的距离，ds为事先确定的安全区域的半径，将CASIA-I工作环境分成：

1）自由空间FS

2）安全空间SS

3）非安全空间NSS

其他情况都归并到该空间，在该空间中，至少存在一个障碍物。因此必须采取措施，避免相碰。

在上述空间划分的基础上，CASIA-I从当前状态，执行某一动作，达到其后续状态，回报函数为：

2 基于LS-SVM的Q学习

Q学习的实现过程为：在每个时间步t，观察当前状态st，选择和执行动作at，再观察后续状态st+1并接受立即回报rt，然后用式（3）来调整Qt。

η控制学习速度，0≤γ≤1表示学习系统的远视程度。

为了构造LS-SVM，提高估计速度，样本是窗式移动的[10]。即在将新数据加入样本集之前要进行KKT[11]判断，若满足KKT条件，不更新训练集，时间窗保持不变，若违反，滚动时间窗，重新训练得到的LS-SVM。设t时刻训练样本集由过去L组数据构成。

为了解决学习中探索与利用的两难问题，LS-SVM的输出被送入随机动作选择器。采用BoltzmanGibbs分布作为选择策略[10]，则动作ak从动作集A={a1，a2，…am}中被选择的概率为：

式中，T＞0为温度参数，控制动作选择的随机程度。

3 LS-SVM的学习及导航算法

对L区间的数据进行建模，把回归问题表示为约束优化问题：

其中，γi反映区间内样本的重要程度，文中定义为：

建立Lagrange函数，并根据KKT条件，得到回归模型为：

根据上述分析，CASIA-I导航算法描述如下：

第一步：初始化Q学习控制器及回归模型的参数；

第二步：根据各传感器提供的信息确定机器人的当前状态st，如果st⊂FS，则执行第三步。否则执行：

1）构造t时刻LS-SVM的学习训练样本集D；

2）根据贪心策略选择最大Q值对应的动作αt；

3）执行动作αt，获取下一时刻状态St+1及立即回报rt；

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

5）判断新数据（xt，Qt）是否违反KKT条件，若不违反，则保持时间窗不变，若违反，则将该数据加入训练集并滚动时间窗；

第三步：根据传感器提供的数据，调整移动机器人的运动方向，然后以每步dmax的最大速度向目标运动一步；

第四步：若不满足学习结束条件，t←t+1，转第二步。

4 仿真研究

对文中所提方法进行30次的独立仿真运行，取η=0.16，γ=0.94，T=0.009，C=100，ε=0.006，σ=0.5，L=33。表1给出了系统学习性能比较，由表1可知，与文献[5]提出的基于BP神经网络的Q学习系统相比，基于SVM的Q学习在每次仿真中均能以较少的学习次数获得最优策略，而基于LS-SVM则以更少的次数获得最优策略。

5 结束语

强化学习已经应用在移动机器人导航中，为了解决强化学习中的泛化问题，提出用基于时间窗的LS-SVM实现由系统状态-动作对到的Q值函数的映射。实验结果表明所提方法能够使机器人在较少的学习次数内无碰撞的到达目的地。

[1] 蔡自兴，贺汉根，陈虹.未知环境中移动机器人导航控制研究的若干问题[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 具体系统性能比较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] 秦政，丁福光，边信黔.强化学习在移动机器人自主导航中的应用[J].计算机工程与应用，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] 王雪松，田西兰，程玉虎.最小二乘支持向量机在强化学习系统中的应用[J].系统仿真学报，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.