张堂凯，罗 杰，李龙俊

(南京邮电大学 自动化学院，江苏 南京 210023)



基于K-Means与SVM结合的栅格分区路径规划方法*

张堂凯，罗 杰，李龙俊

(南京邮电大学 自动化学院，江苏 南京 210023)

智能清洁机器人全局路径规划中，利用栅格法对清洁机器人的工作环境进行建模。分别介绍了K-Means聚类算法和支持向量机(SVM)算法，使用K-Means聚类算法与支持向量机(SVM)相结合的方法，以不同的约束条件进行聚类，在含有复杂障碍物的栅格地图时能有效减少分区，利用蚁群算法对分区后的栅格地图路径规划仿真，有效地提高了蚁群算法在栅格地图路径规划中的整体效率。

栅格地图；K-Means聚类；支持向量机(SVM)；蚁群算法

0 引言

目前市场上的智能清洁机器人在路径规划上大多数采用随机遍历的策略，清扫的全遍历差，耗时长。路径规划是智能清洁机器人的基础问题，对于规划路径的优化主要在于提高清扫覆盖率，降低重复率。

蚁群算法是智能理论研究领域的一种主要算法，可以用于大部分需要优化的应用领域，其中潜力比较大的领域主要有：模式识别、信号处理、电力控制以及移动机器人路径规划等。曾碧[1]等人将蚁群算法与一种概率路线图相结合来规划机器人路径，该方法可以减少蚁群算法在进行大规模路径规划的时间。张赤斌[2]等人将Boustrophedon单元分解法与蚁群算法相结合，采用局部区域遍历与全局运动相结合的完全遍历路径规划方法，在降低算法复杂性的同时又加快了算法的收敛速度。……