清扫机器人的新型田埂式路径规划方法.docVIP

清扫机器人的新型田埂式路径规划方法 　　摘 要 路径规划是清扫机器人的关键技术，通常采用栅格法进行全覆盖路径规划，但在遇到死角和凹型地形时，会存在着容易被死角困住或重复率过高等问题。本文在栅格法的田埂式路径规划的基础上进行了改进：加入优先级的行走规则，融入回溯法，最后在单元格加入特征标记。提出的改进方法使新型田埂式的路径规划即能做到全覆盖，又能从死角中走出，且降低了路径的重复率，具有更高的工作效率。 　　【关键词】清扫机器人 路径规划 新型田埂式 　　1 引言 　　路径规划和避障是移动机器人的关键技术之一，比如家庭服务机器人，包括清扫机器人、修剪机器人等，在工作的时候都必须进行路径规划和避障。路径规划和避障是移动机器人是否能高效率工作的关键，因此，具有很高的工程应用价值和理论研究价值。 　　依据机器人的任务可以把路径规划法分成环境区域内全覆盖路径规划算法以及特定点到特定点之间的路径规划算法即两点间的路径规划算法。全覆盖路径规划是指在机器人从起始点到终点的行进过程中，必须全覆盖整个环境区域中除障碍物以外的其他所有区域，并且做到重复率低、无碰撞并且安全。 　　常用的路径规划方法主要有人工势场法、栅格法、神经网络法、混沌遗传算法等。清扫机器人常使用栅格法，栅格法的行走路线有内外螺旋方式运行，田埂式运行等，但都存在着路径重复率过高或者对于死角遗漏，需要重新启动再次清扫的问题。因此本文对传统栅格法进行了多方面的改进，提出了一种新型田埂式运行方法，此种方法在算法上并不复杂，并且路径重复率大大降低，做到全覆盖，下面介绍这种运行方法。 　　2 田埂式路径规划的基本运行方式 　　田埂式路径规划的核心原理是使清扫机器人沿着直线一个栅格一个栅格的向前运行，遇到障碍物则以90度为单位进行转向，进入相邻的栅格中，然后再次同方向转动90度，继续直线方式行走，按照此规律反复运行，一直到覆盖整个清扫区域为止。但是在清扫机器人遇到障碍物的情况下，就不能做到全覆盖，如图1，会使得一部分的区域被遗漏，尽管使用横纵复合的方式运行可以解决，即当第一次的运行方向为横向运行，那么第二次的运行方向就为纵向运行，但是这样的话，清扫率重复率过高，效率极低，且只能在障碍物较少并且不密集的情况取得较好的效果，因此，本文将田埂法做出了以下改进。 　　3 田埂式运行方法的改进 　　3.1 加入优先级的新型田埂式运行方法 　　首先，第一个改进是在田埂式基本的运行方式上加上优先级的概念，即在清扫机器人的栅格之间的运动加上了一种规则，比如左方，上方，右方，下方，这样的话，清扫机器人就不再是遇到障碍物就进行90度的转向，继而进行同向90度的转向，而是在栅格地图中按照绝对方向优先向左方移动，如左方有障碍物或者已经清扫过，则向右方移动，按照优先级顺序以此类推地进行运动。这样的话就能避免田埂式基本运行方式所带来的遗漏问题，如图2所示。 　　3.2 加入回溯法的新型田埂式运行方法 　　当加入优先级算法之后，在面对凹形障碍物时，某些凹形的死角可能会困住清扫机器人，如图3所示。第二层的改进是加入回溯法解决凹形区域的死角问题。所谓回溯法，就是当清扫机器人不能前进，或进入死胡同时，应往回移动至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地有哪些信誉好的足球投注网站，直至找到所要求的解或解空间中已没有活结点时为止。回溯法可以使陷入死角的机器人按进入的路径退回，避免长时间陷在死角中，可以大大提高运行效率。 　　当清扫机器人陷入凹形陷阱时，如图4所示，清扫机器人进入到A栅格时，然后进入到B栅格，可以看到A栅格除了与B栅格连接之外，不与任何其他待清扫栅格连接，清扫机器人就进入了死角，此时清扫机器人将进行回溯操作：即机器人先回到死角栅格B点的上一个栅格A，并且在B栅格上做上特定的标记，回到A点时再度使用回溯法直至走出凹形区域。因此，回溯法就是当清扫机器人陷入一些复杂的障碍物区域时，清扫机器人通过返回前一个状态来继续判断可走区域，直至最终走出这种区域。 　　3.3 加入特征标记的新田埂式运行方法 　　如果采用了加入了固定的优先级的田埂式运行方式，虽然使用回溯法可以走出凹形区域，即通常所说的死角，但是由于优先级规则所带来的影响，使得出现下述情况的凹形区域时，清扫机器人在第一次经过凹形区域时会从凹形区域的上方或下方直接通过，如图5所示，而不会进入凹形区域，造成此区域的遗漏。所以为了解决该问题，本文对凹形区域加入特征标记的方法。 　　凹形区域特征标记法就是当清扫机器人处于凹形区域的特征栅格时会在当前的位置做一个标记，本文是设置了一个活性参数，在未处于任何特征栅格时，活性参数为0，当到达第一个特征栅格时，将活性参数+1，即此时活性参数变为1，处于半活跃状态，清扫小车继续运行，当到达