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

傅思程++陈中柘++向羽

摘 要 路径规划是清扫机器人的关键技术，通常采用栅格法进行全覆盖路径规划，但在遇到死角和凹型地形时，会存在着容易被死角困住或重复率过高等问题。本文在栅格法的田埂式路径规划的基础上进行了改进：加入优先级的行走规则，融入回溯法，最后在单元格加入特征标记。提出的改进方法使新型田埂式的路径规划即能做到全覆盖，又能从死角中走出，且降低了路径的重复率，具有更高的工作效率。

【关键词】清扫机器人 路径规划 新型田埂式

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，处于半活跃状态，清扫小车继续运行，当到达第二个特征栅格时，将活性参数+1，即此时活性参数变为2，处于活跃状态，此时清扫小车将不再执行田埂式运行方法，而是执行凹形区域运行算法，当进入凹形区域后将活性参数复位，重新置0，等待再度遇到凹形特征栅格后激活。特征栅格的位置要根据周围环境中障碍物栅格与非障碍物栅格的相对位置来判断。当清扫小车所处栅格的左上或右上为障碍栅格，正上为非障碍栅格，或者左下或右下为障碍栅格，正下为非障碍栅格，则清扫小车当前位置的栅格即为特征栅格，特征栅格如图6所示，其中A1，A2，A3即为特征栅格，当清扫机器人通过A1，A2，或者A3，A2时就会通过A2栅格进入凹形区域。通过新田埂式运行方法，清扫小车就可以免去横纵结合的田埂式全覆盖算法，还可以方便地从凹形区域即死角中出来继续执行清扫任务，极大地提高了效率，节省了清扫时间。

综上所述，这种结合优先级法，回溯法，凹形区域特征标记法而产生新方法，本论文称之为新田埂式法。

5 结论

本文基于传统的田埂式路径规划方法，进行了三个方面的改进：加入优先级的行走规则，融入回溯法和在单元格加入特征标记。本文提出的新型田埂式路径规划的路径能够做到全覆盖，且遇到凹形区域死角时能够执行另一套回溯算法以快速地脱离凹形区域死角继续完成清扫工作，通过加入标记法一定程度上降低了由于优先级法和回溯法所带来的重复率。总之，改进的新型田埂式的路径规划方案即能做到全覆盖，又能从死角中走出，且降低了路径的重复率，具有更高的工作效率。

（通信作者：陈中柘）

参考文献

[1]王显.智能清扫机器人路径规划及自动充电系统研究[D].河南：郑州大学，2014.

[2]王俭，赵鹤鸣，陈卫东.移动机器人全覆盖路径规划研究[J].微计算机信息，2006，3（02）：194-197.

[3]高丽宏.移动机器人的路径规划和避障控制[D].辽宁：大连理工大学，2002.

[4]任亚楠，贾瑞清，何金田.基于超声波传感器的移动机器人避障系统研究[J].中国测试，2012（03）：76-79.

[5]Ping-Min Hsu，Chun-Liang Lin，Meng-Yao Yang.On the Complete Coverage Path Planning for Mobile Robots[J].Intell Robot Syst，2014（74）：945-963.

作者简介

傅思程，男，四川省成都市人。

陈中柘（1968-），女，四川省成都市人。现为电子科技大学副教授、博士，主要研究方向为机械电子及机器人。

作者单位

1.四川省成都市石室中学 四川省成都市 610050

2. 电子科技大学 四川省成都市 610000