基于启发式搜索算法的扫地机器人路径规划
发布时间：2021-07-24 20:33
扫地机器人逐渐进入到越来越多的普通家庭,这对扫地机器人的路径规划和定位水平提出了更严格的要求。文章在目前已成熟的栅格法、子区域划分法、模板模型法基础上,提出了一种新的扫地机器人基本路径规划方案,并基于启发式搜索算法对该方案加以实现。该方案通过建立一个二维栅格地图并结合适当的子区域划分方法,将全局清扫问题转化为子区域清扫问题以使清扫更高效、便捷;再通过构造合理的评价函数及利用传感器设立沿边清扫机制对基本方案进行优化。基本路径规划方案与启发式搜索算法、沿边机制结合后,解决了机器人在各子区域之间转移带来的高重复率、复杂路径的寻路低效率、不规则障碍物周围清扫低覆盖率等问题。该方案使扫地机器人在整体清扫工作上覆盖率能达到99%,重复率能控制在10%～18%。
【文章来源】：西华大学学报(自然科学版). 2019,38(04)
【文章页数】：8 页
【部分图文】：
区域间节点图利用深度优先算法很容易对节点图进行遍历并
鞣矫娓咝У睦硐肽勘?［22］。本文利用深度优先搜索算法保证了扫地机器人在障碍物较多的环境下能快速、精准地达到高覆盖率，但同时产生的重复率较高的问题很难完全解决。通过设置合理的评价函数以控制多种情况下的深度优先行为，能在一定程度上减少重复率［1］。评价函数有以下特点:当目标太低时，可以得到最短路径，但是速度会慢;当目标太高时，可以放弃最短路径，但是确保路径搜索算法运行得更快［22］。在这一点上，必须在运行效率和路径选取之间进行权衡［23］。如图7，将区域8内零散分布的障碍物复原，形成了障碍物较多的一个区域。3幅图分别是不同H(n)值的路径规划情况，图7(a)选取了较小的一个H(n)的结果，规划出了路径最优解，但运行最慢［20］;图7(b)选取较大的一个H(n)的结果，规划出了路径次优解，但比图7(a)运行快;图7(c)选取的H(n)最大，规划出了路径最差的解，但比前面两者运行得都快［24］。从这个例子不难看出，将H(n)取一个较为中间的值最为妥当。深度优先算法的内部内容是在每个节点上计算。当H(n)与G(n)完全匹配时，F(n)的值不会沿该路径变化。不在正确路径上的所有节点的F(n)值均大于正确路径上的F(n)值。一般情况下，能够保证路径长度和运行时间可以达到较为均衡的状态，并且解不会偏离最短路径［25］。2．2．2不规则障碍物区域的路径规划方法在区域衔接时若遇到不规则障碍物区域，应该对膨胀处理后的不规则的障碍物边缘进行规划清理。针对不规则障碍物，在分区衔接的路径规划中，
图8对不规则障碍物的沿边清扫示意图3测试如图9所示的全遍历路径规划图，深蓝色的圆为整个清扫过程的起点，深蓝色的勾为整个清扫过程的终点。该图一共有16×12个栅格，黑色的障碍物区域约占50个栅格，自由栅格一共142个。其中，重复遍历的栅格为45个，重复率约31%，覆盖率近100%。本文所设的地图较小、栅格数量较少，且障碍物较为紧凑，便于示意。在实际中，栅格的数量会大大增加，覆盖率也会随之减少。如图10所示，将地图倍增后，重复率降为18%。总的来说，该算法可将重复率控制在10%～18%的范围内。传统算法与改进算法路径规划的覆盖率和重复率对比如表1所示。图9全遍历路径规划图图10全遍历路径重复率示意图表1传统算法与改进算法路径规划对比遍历方式覆盖率/%重复率/%传统规划算法90～94＞20改进规划算法＞9910～18另外，在实际工作中，扫地机器人的转向也会影响清扫效率。在该算法中，由于增加了对角度的约束，减少了转向角度和，在一定程度上提高了整体的清扫效率［2］。综上，改进后的算法在整体的清扫覆盖率、重复率和效率上都有不同程度的提高。4结束语经过对扫地机器人路径规划的探讨，发现不管是使用哪一种规划路径的方法，都会出现一定的重复，只能通过不断优化整体方案来逐渐降低重复率。本文提出的方案在覆盖率和重复率上表现较为突出，且总体时耗、能耗也相应略有降低。在面对不规则障碍物时，由于机器人本身的直径大小会使其在清扫不规则障碍物周身时出现一定的盲区，导致该部分区域无法清洁。接下来可以从以下几方面来考虑改进:改进地图分区方式;改进复杂环境下?
【参考文献】：
期刊论文
[1]基于改进A*算法的移动机器人路径规划[J]. 赵晓,王铮,黄程侃,赵燕伟. 机器人. 2018(06)
[2]扫地机器人路径优化问题的建模及分析[J]. 张行健. 中国新通信. 2018(03)
[3]一种室内扫地机器人全遍历路径规划方法研究[J]. 简毅,高斌,张月. 传感器与微系统. 2018(01)
[4]基于BP神经网络的扫地机器人寻路算法[J]. 杨忠,刘华春. 电脑知识与技术. 2017(10)
[5]一种扫地机器人路径规划的改进算法[J]. 徐胜华,宋树祥,佘果. 测控技术. 2017(02)
[6]智能扫地机器人系统设计[J]. 程丽霞. 机械工业标准化与质量. 2016(09)
[7]智能家庭扫地机器人设计原理研究与分析[J]. 薛慧心. 信息技术. 2014(11)
[8]基于粒子群免疫优化算法的足球机器人路径规划[J]. 王宏亮,王进戈,李军民. 西华大学学报(自然科学版). 2013(06)
[9]深度优先搜索算法和A*算法在迷宫搜索中的仿真研究[J]. 刘翔,龚道雄. 制造业自动化. 2011(11)
[10]基于改进A*算法的仿生机器鱼全局路径规划[J]. 郭强. 西华大学学报(自然科学版). 2011(03)
硕士论文
[1]己知环境下智能清洁机器人路径规划研究[D]. 张堂凯.南京邮电大学 2017
[2]移动机器人路径规划的仿真与实现[D]. 胡楠.安徽工程大学 2017
[3]扫地机器人自主定位算法的研究与应用[D]. 王子发.东华大学 2017
[4]改进生成树算法的多机器人在线地图覆盖[D]. 陈泽涛.齐齐哈尔大学 2016
[5]清洁机器人避障控制及路径规划[D]. 张建龙.武汉科技大学 2015
本文编号：3301380
【文章来源】：西华大学学报(自然科学版). 2019,38(04)
【文章页数】：8 页
【部分图文】：
区域间节点图利用深度优先算法很容易对节点图进行遍历并
鞣矫娓咝У睦硐肽勘?［22］。本文利用深度优先搜索算法保证了扫地机器人在障碍物较多的环境下能快速、精准地达到高覆盖率，但同时产生的重复率较高的问题很难完全解决。通过设置合理的评价函数以控制多种情况下的深度优先行为，能在一定程度上减少重复率［1］。评价函数有以下特点:当目标太低时，可以得到最短路径，但是速度会慢;当目标太高时，可以放弃最短路径，但是确保路径搜索算法运行得更快［22］。在这一点上，必须在运行效率和路径选取之间进行权衡［23］。如图7，将区域8内零散分布的障碍物复原，形成了障碍物较多的一个区域。3幅图分别是不同H(n)值的路径规划情况，图7(a)选取了较小的一个H(n)的结果，规划出了路径最优解，但运行最慢［20］;图7(b)选取较大的一个H(n)的结果，规划出了路径次优解，但比图7(a)运行快;图7(c)选取的H(n)最大，规划出了路径最差的解，但比前面两者运行得都快［24］。从这个例子不难看出，将H(n)取一个较为中间的值最为妥当。深度优先算法的内部内容是在每个节点上计算。当H(n)与G(n)完全匹配时，F(n)的值不会沿该路径变化。不在正确路径上的所有节点的F(n)值均大于正确路径上的F(n)值。一般情况下，能够保证路径长度和运行时间可以达到较为均衡的状态，并且解不会偏离最短路径［25］。2．2．2不规则障碍物区域的路径规划方法在区域衔接时若遇到不规则障碍物区域，应该对膨胀处理后的不规则的障碍物边缘进行规划清理。针对不规则障碍物，在分区衔接的路径规划中，
图8对不规则障碍物的沿边清扫示意图3测试如图9所示的全遍历路径规划图，深蓝色的圆为整个清扫过程的起点，深蓝色的勾为整个清扫过程的终点。该图一共有16×12个栅格，黑色的障碍物区域约占50个栅格，自由栅格一共142个。其中，重复遍历的栅格为45个，重复率约31%，覆盖率近100%。本文所设的地图较小、栅格数量较少，且障碍物较为紧凑，便于示意。在实际中，栅格的数量会大大增加，覆盖率也会随之减少。如图10所示，将地图倍增后，重复率降为18%。总的来说，该算法可将重复率控制在10%～18%的范围内。传统算法与改进算法路径规划的覆盖率和重复率对比如表1所示。图9全遍历路径规划图图10全遍历路径重复率示意图表1传统算法与改进算法路径规划对比遍历方式覆盖率/%重复率/%传统规划算法90～94＞20改进规划算法＞9910～18另外，在实际工作中，扫地机器人的转向也会影响清扫效率。在该算法中，由于增加了对角度的约束，减少了转向角度和，在一定程度上提高了整体的清扫效率［2］。综上，改进后的算法在整体的清扫覆盖率、重复率和效率上都有不同程度的提高。4结束语经过对扫地机器人路径规划的探讨，发现不管是使用哪一种规划路径的方法，都会出现一定的重复，只能通过不断优化整体方案来逐渐降低重复率。本文提出的方案在覆盖率和重复率上表现较为突出，且总体时耗、能耗也相应略有降低。在面对不规则障碍物时，由于机器人本身的直径大小会使其在清扫不规则障碍物周身时出现一定的盲区，导致该部分区域无法清洁。接下来可以从以下几方面来考虑改进:改进地图分区方式;改进复杂环境下?
【参考文献】：
期刊论文
[1]基于改进A*算法的移动机器人路径规划[J]. 赵晓,王铮,黄程侃,赵燕伟. 机器人. 2018(06)
[2]扫地机器人路径优化问题的建模及分析[J]. 张行健. 中国新通信. 2018(03)
[3]一种室内扫地机器人全遍历路径规划方法研究[J]. 简毅,高斌,张月. 传感器与微系统. 2018(01)
[4]基于BP神经网络的扫地机器人寻路算法[J]. 杨忠,刘华春. 电脑知识与技术. 2017(10)
[5]一种扫地机器人路径规划的改进算法[J]. 徐胜华,宋树祥,佘果. 测控技术. 2017(02)
[6]智能扫地机器人系统设计[J]. 程丽霞. 机械工业标准化与质量. 2016(09)
[7]智能家庭扫地机器人设计原理研究与分析[J]. 薛慧心. 信息技术. 2014(11)
[8]基于粒子群免疫优化算法的足球机器人路径规划[J]. 王宏亮,王进戈,李军民. 西华大学学报(自然科学版). 2013(06)
[9]深度优先搜索算法和A*算法在迷宫搜索中的仿真研究[J]. 刘翔,龚道雄. 制造业自动化. 2011(11)
[10]基于改进A*算法的仿生机器鱼全局路径规划[J]. 郭强. 西华大学学报(自然科学版). 2011(03)
硕士论文
[1]己知环境下智能清洁机器人路径规划研究[D]. 张堂凯.南京邮电大学 2017
[2]移动机器人路径规划的仿真与实现[D]. 胡楠.安徽工程大学 2017
[3]扫地机器人自主定位算法的研究与应用[D]. 王子发.东华大学 2017
[4]改进生成树算法的多机器人在线地图覆盖[D]. 陈泽涛.齐齐哈尔大学 2016
[5]清洁机器人避障控制及路径规划[D]. 张建龙.武汉科技大学 2015
本文编号：3301380
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3301380.html
