1. 引言
随着社会与科技的发展，机器人已经不再是单纯的生产工具，开始逐渐进入到家庭，成为直接服务大众的智能家用电器。室内清扫机器人就是其中典型的代表，它能凭借一定的人工智能，自动在房间内完成地板清理工作。目前，市场上已经出现了各种档次不同品牌的室内清扫机器人，越来越多的家庭购买了这类产品。人们关心的是：扫不扫得干净？扫得快不快？使用复杂不复杂？这三问包含了“用户体验”的主要方面，也是室内清扫机器人研发追求的目标。
与仓库、建筑外墙、室外等其它应用场合的清扫机器人相比，室内清扫机器人在清扫质量、快捷性和操作简易性等方面的要求更高。为了实现更好的用户体验，除了在清洁子系统上改进之外，很重要的就是提升器智能化程度，力求实现更高效的路径规划。清扫机器人的路径规划是指根据自身传感器的对环境感知，找到一条最优路径遍历环境中的每一个点，也就是全覆盖路径规划 [1] 。
现有的室内清扫机器人产品，按照路径规划的能力可以分为两类：一类是随机碰撞式，也可以视为无路径规划。这类产品操作简单、成本相对较低，市场占有率高。但资料表明，该类产品第四遍才能达到98%的区域覆盖率 [2] ，清扫效率不高。另一类路径规划式，机器自身行走具有明确的路线，不做无谓的重复清扫。这类产品技术门槛较高，传感器等硬件成本高，多属于高端机型。
清扫机器人路径规划的方法研究一直是研究的热点。本文着眼于适用普通家庭，研究室内清扫机器人的路径规划方法，力求立足现有中低端传感器能力，通过更好的路径规划提升用户体验。
2. 室内清扫机器人路径规划研究现状
室内清扫机器人的路径规划可以分为两个步骤 [1] ：一是环境感知，即确定需清扫的区域；二是规划路径，即确定清扫的线路，实现区域覆盖。
环境感知的方法又可以分为两种：一种是外界输入，由人或其它系统负责获取环境信息。比如大型仓库，可以采用地面画标识线的方式直接确定清扫区域和路径，清扫机器人采用最简单的巡边运动模式，按照标志线指示清扫即可。对于室内家居环境，地面画线通常是不适宜的，一种可能的方式是由人提供地图。但由于操作复杂，家具摆放变化就需要更新地图，一般很少采用。另一种是自我感知，由清扫机器人自己获取环境信息并确定清扫区域。这就需要用到各类传感器，主要有：碰撞开关、超声测距、红外测距、激光测距、视频、陀螺仪、罗盘、无线导航定位等。机器人通过自己不同地点、不同角度的测量，自主确定清扫区域。
规划路径的方法很多，实质上是一个寻优策略和算法的问题，出现很多运用模糊控制、人工势场法、A*算法、神经网络、遗传算法、树/图遍历等技术的解决方案 [1] [3] - [6] 。规划路径的主要约束条件是环境感知的结果和清扫机器人的运动控制能力。所谓清扫机器人的运动控制能力是指其定位、转向、直行的反应速度和精度等，主要取决于运动控制子系统和传感器的能力 [7] 。通常，用步进电机控制转向、直行都没有大的问题。定位能力是清扫机器人的弱项，依靠机器人按照自身运动轨迹进行推算，误差的积累增长很快。利用周边环境信息提高定位精度成为常用的方法。因此，环境感知与规划路径两个步骤并不是截然分开的，在清扫过程中不断细化获取环境信息，修订规划的路径，能够带来更好的适应性。
3. 室内清扫机器人路径规划需求分析
用户需求是产品设计的根本牵引。将用户需求梳理转化为技术需求是实施技术方法研究的基础。
在清扫效果方面，用户希望不留死角、无残留垃圾。为此，室内清扫机器人的路径规划要实现区域全覆盖，避免清扫盲区，尤其是室内边脚区域，最易积尘。实际使用中发现：只清扫一遍往往效果不佳，最好清扫两遍，同时配合灰尘检测，对垃圾多的地方实施重点清扫(很多中低端产品都已有重点清扫功能)。这也是有时感到随机碰撞式清扫机器人效果更好的原因。用路径规划一遍区域全覆盖的时间与随机碰撞式的总清扫时间相比较实际上是不合理的。
在清扫效率方面，用户希望在保证质量的前提下，越快越好，或者一次充电清扫的面积越大越好。为此，路径规划应减少清扫路线的重复，同时避免机器进入某狭小区域后无法脱困。
在操作便捷方面，用户希望尽量减少人的事先准备和清扫过程中的干预。为此，路径规划要尽量采用全自动的方式，避免复杂的用户操作培训。外界输入的环境感知方式是不适宜的。
作为一种消费类的电子产品，用户对其价格是非常敏感的。好的导航类清扫机器人如果价格过高，很多消费者可能宁愿选择价格便宜的随机碰撞式产品。
按照目前的成本水品，精准度最高的激光雷达等传感器不宜采用。扫地机器人鼻祖，美国的iRobot，也放弃使用激光雷达 [8] 。有些方案利用视频信号，通过对家具的图像识别进行定位；有些方案采用若干个支持ZigBee协议的无线终端设备作为锚节点 [9] ，对清扫机器人进行交叉定位，等等。这些方案，要么成本不够低，要么技术不成熟，要么精度不够高。作为定位当前可用传感器的主流是碰撞检测，或者短距离(几十厘米)、粗精度(几厘米)的红外/超声测距等。
4. 基于碰撞检测的纵横弓式路径规划
4.1. 路径规划主要思想
某些路径规划算法，比如“回”字螺旋式 [3] [10] 、回溯式 [11] ，隐含的假设是清扫机器人具有很高的定位能力，因而可以精确地按照规划的路径运动。事实上，这在实际场景中是不现实的，特别是一旦遇到障碍物，规划路径的接续将很困难。
“弓”字往返式是常用的路径规划基本线路构成方式。但是仔细分析现有的路径规划方法，往往能够举出特定场景作为反例，说明其中存在着清扫盲区，换言之场景适应性不高，有些场景区域覆盖率不高。而且没有考虑到机器长期运动后带来的定位误差积累，即使多次清扫也未必能有效减少清扫盲区。
本文以最常用的碰撞检测作为主要的感知手段，以步进电机计数作为主要测距方法，研究满足低成本室内清扫机器人路径规划需求的技术途径。
主要思想是：
1) 自动充电桩定位
很多清扫机器人已近具有自动寻桩定位功能。可利用充电桩作为初始定位和重新定位的起点，各个步骤的转换都以自动充电桩作为标识重新定位，消除定位积累误差。充电桩靠墙边安放，沿墙边即可找到。
2) 区域边界感知
环境感知分为两个阶段。第一阶段只是确定清扫区域的边界，采用清扫机器人从充电桩出发，延墙边(包括靠墙的家具)探测一周，以回到充电桩作为终止。第二阶段在清扫过程中进行，采用扫描式方法，在墙、家具之间走“弓”字形，根据碰撞检测的结果逐步细化室内中部清扫障碍物的边界。
3) 纵横弓式路径规划
采用一遍纵向“弓”字形清扫+一遍横向“弓字形”清扫的路径规划策略。目的是提高清扫质量、减少清扫死角。
4) 障碍区域复检补扫
按照清扫过程中的环境感知记录，对可能遗漏的清扫区域进行复检补扫，最大限度地减少清扫死角。
为说明此路径规划方法，构建典型场景如图1所示。
4.2. 区域边界感知
清扫机器人从充电桩出发，按照一个方面(如逆时针)沿墙边运行一周，得到区域的边界信息，如图2(a)，虚线表示运行的路线，箭头表示运行的方向。边界的长度由运行过程中步进电机的步进步数测量得到，精度要求不高。之后将区域转变为栅格地图的表示，如图2(b)，白色单元表示可清扫，阴影单元表示区域边界。
常用的清扫区域表示方法为栅格地图、几何特征地图和拓扑地图三种 [4] 。相对而言，栅格地图表示方法更便于计算机编程处理。栅格单元的大小依据清扫机器人的单次清扫范围而定，通常可设定为单次清扫宽度的一半。
4.3. 纵横弓式路径规划策略
区域边界感知后，即开始先纵后横的两遍弓式清扫。在清扫过程中细化感知不靠墙的清扫障碍物边界。
首先，仍以充电桩作为起点，从其倚靠的墙的一端墙角开始垂直向(纵向)的弓形清扫，以碰撞检测作为掉头的触发信号，无需高的定位精度要求。图3(a)显示了第一次清扫的路线。兼顾清扫质量和效率，两条相邻平行清扫线路的距离一般设计为略小于机器人单次清扫宽度(或直径)。清扫过程中，将已清扫的格子打上“纵向已清扫”标记，如图3(b)用浅色阴影表示了第一次纵向清扫后已被清扫的区域。
其次，机器以充电桩为起点，沿墙边移动到为某个包含墙边的且未被清扫的区域边界，继续采用纵向弓式路线进行清扫。重复这一过程，直至没有包含墙边的且未被清扫的区域，即完成了全部纵向弓式清扫。图3(c)显示了全部纵向清扫后的区域覆盖情况。
按照上述方法，仍以充电桩为起点，进行横向弓式清扫。图3(d)既是横向清扫的区域覆盖图，也是
(a) 沿边区域感知路线示意图 (b) 栅格地图表示
Figure 2. Regional boundary perception and grid map representation
图2. 区域边界感知及栅格地图表示
(a) 第一次纵向清扫线路 (b) 第一次纵向清扫栅格地图
(c) 纵向清扫后栅格地图 (d) 纵横双向清扫后栅格地图
Figure 3. Demonstration of the vertical & horizontal “bow” cleaning
图3. 纵横弓式清扫过程示意图
纵横双向清扫后的总区域覆盖图。图中虚线方框指示的区域在纵向清扫中遗漏了，原因是从纵向角度，该区域没有无障碍直达墙边的路线。但是从横向角度，可以清扫到。可见，纵横弓式路径规划策略不仅保证了大部分区域实现两遍清扫，而且可以减少清扫死角。对于这类单向死角区域，完全可以再次清扫
(a) 清扫死角示意图 (b) 复检区域判别示意图
Figure 4. Re-check for obstacle area
图4. 障碍区域复检示意图
(a) mBot机器人
(b) mBlock编程开发环境
Figure 5. The mBot Robot and mBlock programming environment
图5. mBot机器人及其mBlock编程开发环境
以提高清扫质量。
4.4. 障碍区域复检补扫
对比图1和图3(d)，可以发现，图4(a)中虚线框指示的区域形成了清扫死角。原因在于按照纵横弓式清扫路线规划方法，该区域在上方可进入的方向上，机器人没有无障碍直达墙边的路线。因此需要进行障碍区域复检补扫。
障碍区域复检的判别准则是：如果存在未垂直碰撞检测边，则该区域需要复检。
复检的方式是：对未垂直碰撞检测的横向边进行纵向检测，对未垂直碰撞检测的纵向边进行横向检测。检测方法可采用碰撞检测或短距离测距检测。
图4(b)显示了两个障碍区域都需要复检，因为分别存在一条未垂直碰撞检测的横向边H1、H2。复检方式是机器对H1、H2分别进行纵向的检测。显然，H1所在区域无需补扫，而H2所在区域存在清扫死角，需补扫。
5. 结论
为验证基于碰撞检测的纵横弓式路径规划的可行性，本文利用mBot机器人和基于Scratch的mBlock图形化编程环境(如图5所示)，实现了一个室内清扫机器人路线规划试验装置，验证了本文提出的基于碰撞检测的纵横弓式路径规划方法的可行性和有效性。
本文提出的方法，充分考虑了在成本可控的约束条件下，现有传感器能力水平，较好地兼顾了质量和效率；减少了清扫死角，区域覆盖率高；路径规划算法简单有效，环境适应性强。