基于聚类分区和改进蚁群算法的清洁机器人路径规划研究

《基于聚类分区和改进蚁群算法的清洁机器人路径规划研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、■单位代码１０２９３密级：：塘鄭Ｊ今凌ｉｔ據专业学位硕ｚｂ论文乃东Ｉｋｉｌｌ＇＇：派？？■？？．．－Ｖ－—．＇，令，．．？■．？．．？－ｅ．．’＇‘：论文题目；基于聚类分区和改进蚁群算法的清洁机器人路径规划硏究１２１３０５３２２９学号李龙俊姓名—＇罗杰ｖｖ’导师＇工程硕±＞专业学位类别全曰帝ｉＪ类型控制王—糧专业（领域），？１．一＇二零六年Ｈ月＇＞夺．＿论文提交日期今巧；皆方拉二，．若片．‘：．‘叮！！，

2、１矿：捧鷄鄭ＩＶ贫＞娜－轉類誦－ｈ．的畔；浅去遍譜冻谦漫ResearchonpathplanningofcleaningrobotbasedonclusterpartitionandimprovedantcolonyalgorithmThesisSubmittedtoNanjingUniversityofPostsandTelecommunicationsfortheDegreeofMasterofEngineeringByLongJunLiSupervisor:Prof.JieLuoMarch2016南京邮电大学学位论文原创性声明本人声明所呈交的学位论文是我个人

3、在导师指导下进行的研究．Ｘ作及取得的研究成果。尽我所知，除了文中特别加Ｗ标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成巧，也不包含为获得南京邮电大学或其它教巧机构的学位或证书而使用过的材料。一与我同Ｘ作的同志对本研究所做的任何贡献均曰在论文中作了明确的说明并表示了谢窓。一本人学位论丈及涉及相关资料若有不尖，愿意承担切相关的法律贵任。＾硏究生签名：寺名攸円期：南京邮电大学学位论文使用授权声明本人授权南京邮电大学可Ｗ保留并向国家有关部口或机构送交论文的复印件和电子文档；允许论文被查阅和借阅；可Ｗ将学位论文的全部或部分内容编入有关数据库进行

4、检索；可Ｗ采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质论文一的内容相致。论文的公布。（包括刊登）授权南京邮电大学研究生院办理涉密学位论文在解密后适用本授权书。研究生签名：走先唯导师签名：日期：作摘要智能清洁机器人融合了多项人工智能技术，广泛地应用于家庭、公共场所、写字楼等环境的半自动或自动清洁。全局路径规划是智能清洁机器人中最重要的技术之一，在一定程度上标志着智能清洁机器人智能化水平。全局路径规划要求清洁机器人在已知环境信息的情况下，以最小的代价（如路径最短、时间最少、能耗最低等）规划一条覆盖全局且不与障碍物发生碰撞的最优或较优路径

5、。蚁群算法作为一种常用的路径优化算法，具有原理简单且实现容易等优点，已经有许多研究者将其用于解决智能清洁机器人路径规划问题。使用蚁群算法来解决清洁机器人路径规划问题时，蚁群算法具有容易收敛到局部最优解和解决大规模问题时效率低下的缺点。本文基于聚类分区和改进蚁群算法进行了清洁机器人路径规划研究，主要工作如下：首先利用栅格法对清洁机器人工作的环境进行建模，然后考虑到路径优化算法在面对凹形障碍物容易陷入局部最优解的缺点，对已知的栅格地图上的障碍物使用数字图像处理里面的腐蚀（Erosion）、膨胀（Dilation）进行预处理，使得凹形障碍物变成矩形障碍物，从而避免蚁群算法陷入局部最小解。其次

6、，针对优化算法在解决大规模路径优化问题时效率低下的问题，提出了将栅格地图分区，然后分布地对栅格区域使用蚁群算法进行路径规划的方法。本文使用K-Means聚类算法和支持向量机（svm）相结合的方法，以不同的约束条件进行聚类，使得栅格地图被纵向地分割成几个区域，然后再利用蚁群算法对分割完成的栅格区域进行路径寻优，使得蚁群算法总的效率大幅提高。最后，针对蚁群算法本身求解全局路径规划问题时，具有易于收敛到局部最优解和解决大规划对称环境问题时效率低下的缺点，提出了一种改进的蚁群算法。该算法在采用伪随机比例规则选择路径的基础上，采用了局部信息素更新和全局信息素更新相结合的更新策略；在局部搜索方式上

7、采用4opt（4-optimization）方法进行局部搜索；使得算法的全局搜索能力和效率都得到了提高。针对使用本文方法解决路径规划问题时，出现的路径穿过障碍物的现象，采用LB（Liang-Barsky）裁剪算法得到与障碍物栅格相交的路径，再对路径进行修正得到最终的清洁机器人全局最优路径。综合仿真实验结果表明，本文提出的方法能够高效地实现清洁机器人全局路径规划。关键词:清洁机器人，路径规划，蚁群算法，腐蚀膨胀，K-Means聚类，支持向量机I