扫地机器人的路径规划研究

83常熟理工学院学报（自然科学）JournalofChangshuInstituteofTechnology（NaturalSciences）第32卷第2期　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Vol.32No.22018年3月　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Mar.,2018收稿日期：2017-11-01通信作者：毛丽民，高级实验师，硕士，研究方向：机器人目标跟踪，E-mail：[e-mail].王亮宇， 等：扫地机器人的路径规划研究扫地机器人的路径规划研究王亮宇，毛丽民，徐星宇，陈　煜（常熟理工学院电气与自动化工程学院，江苏常熟215500）摘要：扫地机器人的路径规划通常采用将地图转换为栅格的方法，但遇到比较复杂的环境时，会存在漏扫或困在死角的情况.为了解决这个问题，本文在栅格法的基础上加入了田埂式算法，并在田埂法中加入了优先级，同时配合A*算法中特征的标记，提高了到达预定位置的效率.通过实际的测试，证明了该方法的可行性.关键词：机器人；路径规划；田埂式；A*算法中图分类号：TP368　　文献标识码：A　　文章编号：1008-2794（2018）02-0083-05近几年，扫地机器人技术发展迅速，扫地机器人在保证有良好清洁效果的同时，将追求更加智能、高效［1］.扫地机器人的路径规划是一种环境区域内的全覆盖路径规划，路径规划是扫地机器人的关键技术之一［2］.常用的路径规划方法主要有栅格法、Dijkstra算法、启发式搜索算法、神经网络算法、混沌遗传算法等［3］.清扫机器人通常使用栅格法，行走路线有内外螺旋方式运行、田埂式运行等.在实际应用中，由于存在各种约束，单纯使用田埂式运行存在着路径重复率高或有死角存在等问题［4］.本文对传统栅格法进行了改进，提出了一种田埂式运行与A*算法相结合的方法，使扫地机器人路径重复率降低，从而实现全覆盖.1　A*算法原理A*算法是典型的启发式搜索算法，该方法能对空间的每一个区域进行评定，根据评定的系数得到最好的位置，再从这个位置进行搜索直到找到目标.扫地机器人需要在最短的时间到达预定的位置以提高效率，所以路径必须是最短.因此本文加入了限制条件，能更有效地找出当前空间的最短路径.首先以机器人的大小把空间划分为矩形栅格［5］，如图1所示，然后将这个排列有序的栅格简化成一个二维数组，数组的每个元素就是网络中的方块，栅格定义为可通过或者是不可通过.如图2所示，以机器人为中心，前后左右4个方向开始搜索，到距离目标点最近的相邻栅格，连续下去得出到达目的地的路径.A*算法的估价函数表示为：f（n）=g（n）+h（n）.f（n）就是估价函数，g（n）的值就是从机器人当前所在栅格到目标点之间距离的栅格数.h（n）的值是在当前栅格上机器人可通行的可能性.因为在实际运动过程中会有墙、凳子、桌子等作为障碍物.在设计规则的时候，空间信息越多约束条件也就越多，这样排除掉没用的节点也会更多，规则越符合设计的要求，估价函数就越好［6］.图1基本栅格图ᵪಘӪ䳌⺽⢙ⴞⲴൠ84常熟理工学院学报（自然科学）2018年G的值就是从机器人当前所在栅格到目标点之间的栅格数.H的值是在当前栅格上机器人可通行的可能性.方格的F值F=G+H.令当栅格为没有经过时G=1，当栅格为障碍时G=100，当栅格已经来过一次或以上时G=10，避免重扫的情况发生.令移动一个栅格的移动耗费为1，即H=1，F的值是G和H的和［7］.如图3所示是搜索的结果，G和H的值都计算得出后写在4个方向的栅格内.如图4所示，右边一个栅格到达目的地需要机器人移动两个格子，H值是2.其他栅格以此类推.每个格子的F值由G值和H值相加得到.F值最小的，则为下一个运动位置.当机器人碰到障碍物后，G值变为100，此时F值很大，机器人不选择此栅格，选择下面或者上面的栅格，此时出现优先级的问题，是优先向上还是向下，本文将优先级设置为向下，有利于机器人的规则行走.重复这个过程，直到机器人到达目的地停止搜索，如图5所示.机器人只要按之前得出来的节点按顺序行走，直到到达最终目的地，机器人实际的移动位置如图6所示.2　田埂式算法的原理首先对机器人所在位置的直线栅格先走一遍，当遇到障碍时以90°向固定的方向转动，进入到下一列直线中，然后再次同方向转动90°，继续直线方式行走，按照此规律反复运行，一直到覆盖整个清扫区域为止.但扫地机器人在实际的运动中，会遇到各种障碍，该方法不能做到全覆盖，如图7所示，被障碍挡住的部分就没有清扫，虽然可以采用横纵切换的清扫方式，但效率很低［8］.本文将田埂法做了改进，加入优先级.首先，机器人每走完一条直线，设为x轴，也就是遇到障碍时，记录x-1和x+1，机器人没去过的栅格，利用A*计算出距离此时最近的栅格，然后走过去，再按照顺序清扫，以此类推，如图8所示，这样避免了田埂式基本运行方式所带来的遗漏问题.3　路径规划程序的实现本文把A*算法和田埂式算法整合，在机器人执行过程中A*起到规划路径的作用，而田埂式算法起到寻找房间没扫或者漏扫的区域.如图9所示，首先，机器人按照直线行走，当遇到障碍时，启动田埂式算法，找出机器人左边和右边所没有去过的栅格，并且记录在maps数组中.然后启动A*算法，得到在maps中离当前机器人所在位置最近的栅格，并且利用A*算法到达这个位置并且开启新一轮的运行，直到maps数组中没有栅格为止，此时整个房间清扫完毕.3.1　A*算法程序的实现矩阵map［xx］［yy］用来存放地图中每块栅格的G值.再以当前机器人所在中心查询每个方向的G值和距离目标点的H值.然后把两个值进行相加得到最终的F值.最后判断哪个F值等于min值，那么这个方向就是机器人将要移动的最近的方向.最后需要把走过的栅格的G值加上一个权重，以免下次重复移动到这一块.图2机器人移动方向ᵪಘӪ图3路径规划开启ᵪಘӪH=4G=1G=1H=2ⴞⲴൠG=1G=1H=4H=4图4路径规划中遇到墙体ᵪಘӪF=5F=5F=5F=3H=4G=1G=1H=2䳌⺽⢙G=100ⴞⲴൠG=1G=1H=4H=4䳌⺽⢙G=100䳌⺽⢙G=100F=5G=1H=3图5产生路径ᵪಘӪF=5F=5F=5F=3H=4G=1G=1H=2䳌⺽⢙G=100ⴞⲴൠG=1G=1H=4H=4䳌⺽⢙G=100䳌⺽⢙G=100F=4G=1H=3F=5G=1H=4F=4G=1H=3F=5G=1H=1F=3G=1H=2图6实际路径ᵪಘӪF=5F=5F=5H=4G=1G=1H=2䳌⺽⢙G=100ⴞⲴൠG=1G=1H=4H=4䳌⺽⢙G=100䳌⺽⢙G=100G=1H=3G=1H=4G=1H=3G=1H=1G=1H=2F=3F=4F=5F=4F=3F=2图7无田埂式算法效果图8有田埂式算法效果85第2期王亮宇，等：扫地机器人的路径规划研究如图10所示，开始运行时，读取机器人当前栅格的前后左右4个栅格的G值，紧接着计算H值，然后把G和H值相加，得到总的F值，然后比较在4个方向的F值，选取F值最小的路径，并且把当前栅格的G值加10，表明机器人来过，以避免重复清扫.3.2　田埂式算法程序的实现定义x1为当前机器人所在列的起始格，xx为当前机器人所在列的结束格，maps矩阵中存放机器人当前列的之前一列和之后一列，如图11中的x-1和x+1列中相同行所没有去过且除去障碍物的栅格.机器人在x列上运行，起点位置的行值为y1，终点位置的行值为yy，这样机器人所走的格式为6格，然后程序逐行循环6次，搜索出在X-1列和X+1列上机器人所没有去过的栅格，也就是没有扫过的地方.图11中在X-1列上有两格黑色的栅格模拟已扫过的地方，需要过滤掉，然后把其余空的栅格坐标存入到maps数组中.图12所示是执行田埂式算法的流程图，程序开始运行时，判断开始行是否小于或者等于终止行，如果不是就返回开始步，反之把初值为0的i加1，然后判断i是否小于50，如果是，就把数组中没用的数据清除，存入当前y+1轴上没有清扫过的坐标于maps数组中，接着继续将i值加1，直到i＞50的时候，就跳进下一个循环中，进行同样的操作把y-1轴上没有清扫过的坐标存入maps数组中，直到这个i也大于50后整个程序就进入下一个循环，重复以上的操作.4　调试4.1　扫地机器人扫地机器人（图13）以自身的直径旋转，相对于方形来说就没有多余的部分会撞到周围的障碍.机器人可行的结构和合理的传感器，才能使算法达到最佳的效果.如图14所示，机器人的轮子是可伸缩的结构，防止遇到高起的障碍时整个底盘搁浅在障碍物上.如图15所示，机器人边上装有碰撞条，用于判断当前是否碰到障碍物.4.2　Labview仿真调试在机器人实际调试之前，首先采用Labview进行仿真实验，以减少一些不必要的错误，给机器人实际调试做准备.图14机器人轮子图15碰撞条触发图13扫地机器人图10A*算法流程䈫ਆ4њᯩੁG٬ᴰሿ٬䇑㇇H٬ᗇࠪᙫⲴF٬ᖃࡽḵṬG٬࣐10ᔰ࿻NY图11机器人栅格图X-1XX+1图12田埂式算法流程ᔰ࿻㹼=ࡍ٬␵䴦ᮠ㓴ᔰ࿻㹼≤㓸→㹼YNᆈޕᖃࡽy+1䖤඀ḷࡍ٬i=0i++i≤50Yࡍ٬i=0i++i≤50N␵䴦ᮠ㓴Yᆈޕᖃࡽy-1䖤඀ḷN图9机器人整体运行流程图ᔰ࿻䘀㹼䙷ࡠ䳌⺽੟ࣘ⭠ෲ㇇⌅A*㇇ࠪᴰ䘁オ։⛩䈳ᮤᯩੁ࡙⭘A*㿴ࡂ䐟ᖴ86常熟理工学院学报（自然科学）2018年首先，利用Labview实现最简单的A*算法，从一个点到另一个点的测试，如图16所示，起点坐标是（0，0），G=255的格子代表墙，0就是可以到达的区域，3是机器人已经走过的区域，由图17可见，机器人顺利避开了障碍，走出了该区域.然后加上田埂式算法测试整体效果.如图17（a）所示，当模拟运行一小部分时，左上角显示的起点坐标是（0，1），可以看到值为3的格子是模拟的机器人，开始以弓字形方向侵占地图，并且时刻记录田埂算法的数据，存在maps数组中.如图17（b）所示，机器人运行到最下方，发现下方都是墙，利用A*搜寻在maps数组中离当前位置最近的0点清扫，如图17（c）所示.此时又发现墙壁，于是循环之前的步骤，去到最近的0点，持续清扫，如图17（d）所示.继续执行以上循环的步骤，如图17（e）所示.直到最后，如图17（f）所示，把所有的0都填补完成，100%完成清扫［9］.图16A*算法基础模拟4.3　实际运行调试机器人起始位置如图18（a）所示.启动扫地机器人，向左运行，如图18（b）所示.遇到墙面时如图18（c）所示.把墙面的栅格标记，此时利用田埂式算法计算得出机器人周围最近的空栅格，下方是墙体，因此机器人向上方运行，到上方一列中最近的栅格.为保证是弓字形方式清扫，机器人转180°，如图18（d）所示，然后再开始新一列的清扫.机器人需要到障碍的右边清扫，开启A*算法，以最近的路线绕过障碍，如图19（a）所示.向下运行两个栅格，再向右运行两个栅格，如图图18机器人弓字形运行图图17A*算法模拟过程87第2期王亮宇，等：扫地机器人的路径规划研究19（b）和图19（c）所示.绕过障碍，机器人继续向上运行一个栅格，到达目的地，如图19（d）所示，即没清扫的区域.通过对具体数据的对比分析发现（见表1），在简单的场景中田埂式算法相较于A*算法的运行时间少，但在复杂的环境中A*算法相比田埂式算法具有优势，经过改进后，运行时间与清扫效率明显提高.5　总结本文分析了A*算法和田埂式算法，结合各自的特点，提出了一种新的路径规划方法，将A*算法和田埂式算法整合到扫地机器人的路径规划中.在实际的清扫测试中，机器人能沿着规划路径避开障碍物，不重复清扫，证明了该方法的可行性.参考文献：［1］徐国保，尹怡欣，周美娟.智能移动机器人技术现状及展望［J］.机器人技术与应用，2007（2）：29-34.［2］戴博，肖晓明，蔡自兴.移动机器人路径规划技术的研究现状与展望［J］.控制工程，2005，12（3）：198-202.［3］谭宝成，王培.A*路径规划算法的改进及实现