改进的清洁机器人全覆盖路径规划算法

摘 要：本文研究了基于已知环境地图栅格化描述的清洁机器人全覆盖路径规划算法，对未清扫区域和障碍区域分别进行标记，记录区域清扫次数，利用不同的优先准则，即顺时针优先准则、逆时针优先准则和最优区域随机选择准则，搜索清扫区域，从而得到清洁机器人的全覆盖路径规划的改进随机算法。利用MATLAB语言编程进行仿真实验，实验结果表明，改进的搜索算法能保证清洁机器人完成清扫区域全覆盖的前提下，使得平均重复覆盖率比一般随机算法低。

【关键词】清洁机器人 路径规划 全覆盖 优先准则 最优区域随机优先搜索

1 引言

源于将吸尘器和移动机器人相结合，从而实现自动清扫的想法，有人提出了清洁机器人的概念。具体来说，一个扫地机器人的实现需要对传感器、控制系统、路径规划、吸尘技术和电源等系统进行很好的设计和组合，在这其中，传感器和吸尘技术对于清扫质量固然重要，但对机器人自主移动路径的设计和控制才更是真正体现机器人智能水平高低的重要关键技术。

一般的移动机器人路径规划是指根据机器人所感知的环境，按照某种优化指标，从起始点到目标点规划出一条与场景中障碍物不发生碰撞的最短路径。与上述路径规划不同，清洁机器人的路径规划是在尽量短的时间内完成对全部清扫区域的遍历。所以这里所述的路径规划并非指从起始点到终点的路径进行规划，而是需要实现清洁机器人对清扫区域的全覆盖路径规划，同时在满足全覆盖的前提下使得重复覆盖率尽量低。在全覆盖路径规划方面，无障碍物区域内的覆盖问题已经得到了令人比较满意的解决，已知环境的区域分割和未知环境的地图生成两个方面也分别开展了一些研究并取得了一定成果。

而目前市面上的清洁机器人多采用随机的路径规划算法，利用传感器信息让机器人在碰到障碍物或走到区域边界时，随机旋转一定角度以选择下一步移动方向。这种方法在时间足够长的情况下，理论上可以达到全覆盖。但由于电池提供的动力有限和问题的实际性，随机路径规划算法具有不可忽略的局限性，同时这种算法所体现的机器智能性也很低，常常出现已清扫区域不断地重复清扫，未清扫区域一直不清扫。考虑到让机器人尽量选择未清扫区域先进行清扫，本文将随机算法进行改进，考虑了顺时针优先、逆时针优先和最优区域随机选择三种不同的优先准则，并利用MATLAB进行了仿真实验。

2 基于栅格地图的已知环境描述

首先，我们对一般室内环境进行观察，可以看出，无论房间边界形状还是室内物体形状，大部分都为矩形，或近似矩形。因此本文采用矩阵以存储整个已知的环境地图，并把有障碍物区域用100标记，其他未清扫区域用0标记，已清扫过 遍的区域用 标记。这样，室内环境地图就用一个矩阵map来表示了。

具体来说，第一步是将已知的区域环境地图进行栅格化描述，如图1所示。

然后给每个栅格进行标记，对未遍历的栅格标记为0，遍历过1遍的栅格标记为1，遍历过2遍的栅格标记为2，……，遍历过 遍的栅格标记为 ，障碍物所在栅格标记为100（一般情况下总有

3 改进的全覆盖算法

一般的随机算法随机选择机器人下一步清扫区域容易造成已清扫区域过渡清扫，未清扫区域迟迟不能得到清扫。本文考虑了三种不同优先准则以改进完全随机的算法。第一种，考虑机器人按照顺时针方向检查下一步可行区域，并按照顺时针优先的方向选择清扫次数最少的区域进行清扫；第二种刚好与第一种相反，考虑机器人按照逆时针方向检查下一步可行区域，并按照逆时针优先的方向选择清扫次数最少的区域进行清扫；第三种，将已清扫区域的次数进行统计，让机器人在下一步可清扫区域中识别已清扫次数最少的区域，再从中随机选择一个区域进行清扫。按照三种优先准则可以设计不同的程序算法。

3.1 最优区域随机选择的随机搜索算法

设定map为清扫区域地图，障碍物位置标记为100，未清扫区域标记为0。机器人每清扫一个位置，就将该位置map值加1.机器人获取下一步可行方向的清扫次数，在清扫次数最少的可行方向随机选择一个方向作为下一步行进方向，称这种算法为最优区域随机选择搜索算法，其流程图如图3所示。

3.2 顺（逆）时针优先的搜索算法

考虑到让机器人尽量沿着上一次行进方向前行，将最优区域随机选择算法改进为顺时针和逆时针方向优先的搜索算法，在每一次选择时按固定方向优先选择下具有最少清扫次数的可行方向，算法流程图如图4所示。

面对不同的环境区域，可能清扫效率不同，在没有障碍物的区域中，这两种准则都能很好的遍历整个区域，但在有障碍物的情况下，就可能造成重复，并且障碍物越多，可能造成重复覆盖越严重。

4 仿真实验

利用MATLAB软件，本文进行了仿真实验。假设环境为图2所示，栅格化后得到140个方形栅格，并有3个障碍物占据20个栅格。清洁机器人初始位置是左上角位置，清洁机器人当前位置为黄色光标位置，清洁机器人已清扫位置标记为蓝色。

分别按照具有顺时针优先准则和逆时针优先准则以及最优区域随机选择算法执行程序，遍历过程分别如图5、图6和图7所示。统计在不同优先准则下清洁机器人重复清扫的次数，统计结果如表1.

从表1可以看出，在顺时针和逆时针优先准则下，最大重复次数达到5次，而最优区域随机选择算法最大重复次数为4次，优于前两种准则；三种准则下，采用最优区域随机选择算法只清扫1次的比例最大，但顺时针优先选择算法重复覆盖1次即清扫2次的比例最大。

将重复次数加权平均计算重复度 ，其中 表示权重，分别取为0、0.1、0.21、0.29、0.4， 表示重复次数，分别取为1、2、3、4、5.这样计算可得重复度分别为0.126632、0.184416、0.158173。

实验结果表明，顺时针优先准则的改进算法重复度最低，其次是最优区域随机选择算法，最差是逆时针优先准则。分析原因，这应该和清扫区域的障碍物所在位置和机器人初始位置有一定关系，综合来说，最优区域随机选择算法具有平均清扫重复度最低的优势，而对于个别特别区域，可能采用其他两种固定优先方向的准则会更好。

5 结论

本文主要研究清洁机器人在已获取环境地图的情况下如何规划其全覆盖的清扫路径问题。首先将环境地图栅格化表示，将障碍物区域标记为100，未清扫区域标记为0，为了达到在尽量短的时间内将整个房间清扫干净，也就是在尽量短时间内清洁机器人走遍房间的每一个位置的目的，本文算法的终止条件设置为栅格化环境地图的每个栅格标记都不为0，从而保证了清扫覆盖率为100%，然后统计重复覆盖率，以评价算法的好坏。顺时针优先和逆时针优先这两种准则针对具体障碍物所在不同区域，清扫效率会有不同，如何根据区域特征采用不同准则或联合应用不同准则还需要进一步研究。

作者简介

王新武（1990-），男，西南石油大学理学院信息与计算科学专业学生，研究方向：人工智能与机器人学。

作者单位

西南石油大学 理学院 四川省成都市 610500