扫地机器人该如何进行路径规划？需要解决什么问题？

路径规划技术是扫地机器人研究的核心内容之一，机器人定位与环境地图构建就是为路径规划服务的。所谓机器人路径规划技术，就是机器人根据自身传感器对环境的感知，自行规划出一条安全的运行路线，同时高效完成作业任务。

通常，移动机器人路径规划需要解决3个问题：

1）使机器人能从初始位置运动到目标位置;

2）用一定的算法使机器人能绕开障碍物，并且经过某些必须经过的点完成相应的作业任务;

3）在完成以上任务的前提下，尽量优化机器人运行轨迹。

移动机器人的路径规划根据其目的的不同可以分为两种，一种是传统的点到点的路径规划，另一种就是完全遍历路径规划。

点到点的路径规划是一种从起始点到终点的运动策略，它要求寻找一条从始点到终点的最优（如代价最小、路径最短、时间最短）并且合理的路径，使移动机器人能够在工作空间顺利地通行而不碰到任何障碍物。完全遍历路径规划是一种在二维工作空间中特殊的路径规划，指在满足某种性能指标最优或准优的前提下，寻找一条在设定区域内从始点到终点且经过所有可达到点的连续路径。

对于扫地机器人来说，其作业任务是清扫房间，它的路径规划属于完全遍历路径规划，需满足两个指标：遍历性和不重复性。所谓遍历性是指扫地机器人运动轨迹需要最大程度的遍布所有可大空间，它反映的是机器人的工作质量问题。所谓不重复性是指扫地机器人的行走路线应尽量避免重复，反映的是机器人的工作效率问题。

扫地机器人的自主寻路可以分为两种：随机覆盖法和路径规划式。

随机覆盖法，有人也称为随机碰撞式导航，但这并非是指机器人真正与环境中的物体产生碰撞，也非毫无章法的在地板上随机移动，换言之在工程操作中“随机”也是一个难以达到要求，随机覆盖法是指机器人根据一定的移动算法，如三角形、五边形轨迹尝试性的覆盖作业区，如果遇到障碍，则执行对应的转向函数。这种方法是一种以时间换空间的低成本策略，如不计时间可以达到 100%覆盖率。随机覆盖法不用定位、也没有环境地图，也无法对路径进行规划，所以其移动路径基本依赖于内置的算法，算法的优劣也决定了其清扫质量与效率的高低。

美国iRobot公司研发的iRobot Roomba 3-8系列是随机碰撞寻路系统的典型代表。

据称，其采用iAdapt智能化清扫技术的专利技术，这是一种软、硬件相结合的智能化AI清扫系统，硬件由Roomba前方的若干红外探测器、底部灰尘侦测器和落差传感器、毛刷胶刷边刷测速系统等等组成，通过Roomba的硬件传回的信息，iRobot自身的软件可以对回传信息进行分析，根据红外回传信息的强度、范围、高度、转速、电流大小、阻力等参数，计算出前方障碍物大致形状，再经过软件的处理运算，得出的结果就是Roomba下一步清洁方式，Roomba以每秒60次的速度计算周边障碍物的情况，同时根据所处环境作出40余种清扫动作，如围绕、折返、螺旋、贴边、转身等等。

其次iRobot采用面积模糊判定算法，根据房间面积自动设定清扫时长。和路径规划不同的是，Roomba开始收集算法估算所需的两个重要参数：单次行进距离和单位时间碰撞频率。单次行进距离越长则间接代表房间面积越大，走几步就调头则间接代表房间面积较小。每次碰撞Roomba都能收集到相关信息，单位时间内碰撞频率越高代表房间面积越小，碰撞频率低则表示需要清扫的面积较大。

市面上大多数扫地机器人虽都采用随机碰撞寻路方式，然而清洁效率却差异很大，归根到底还是软件算法上的问题，这也是为什么同样大家买的都是随机碰撞寻路方式的扫地机器人，在覆盖率与效率上面却有天壤之别。

规划式导航需要建立起环境地图并进行定位。对路径规划的研究已经持续很多年了，也提出了很多种类的方法。不同的方法有各自的优缺点，适用范围各不相同，没有一种路径规划方法能适用于所有的环境信息。其中的人工势场法、栅格法、模板模型法、人工智能法等是路径规划中很典型的方法，并且受到越来越多的关注。下面将分别介绍上述这些典型的路径规划方法。

1.人工势场法

人工势场法是机器人导航中提出的一种虚拟力法，其基本方法是将机器人在周围环境中的运动设计成在一种势场中的运动，是对机器人运动环境的一种抽象描述，机器人在场中具有一定的抽象势能，势能源有两种：斥力极和引力极。

机器人在不希望进入的区域和障碍物属于斥力极：目标及机器人系统建议通过的区域为引力极。在极的周围产生相应的势，在任何一点的势为该点产生的势之和。该势的负梯度称为势力。势场的建立主要用于动态避障，此时的引力极是局部环境中的中间目标，斥力极则是局部环境中的障碍物。引力和斥力的合力作为机器人的加速力，来控制机器人的运动方向和计算机器人的位置。该方法结构简单，便于低层的实时控制，在实时避障和平滑的轨迹控制方面，得到了广泛的应用。但对存在的局部最优解的问题，容易产生死锁现象，因而可能使机器人在到达目标点之前就停留在局部最优点。

2.栅格法

设定移动机器人实际几何形状可用方形区域表示。规划过程中将机器人缩为一个点，而环境中的障碍物边界做相应的扩展及模糊化处理。采用网格表示工作空间，即把工作空间划分为一个个大小相同的方格，方格大小与机器人几何外形相同。

用栅格法表示环境：使用大小相同的栅格划分机器人的工作空间，并用栅格数组来表示环境，每个栅格是两种状态之一，或者在自由空间中，或者在障碍物空间中。这种方法的特点是简单，易于实现，从而为路径规划的实现带来了很多方便，具有表示不规则障碍物的能力;其缺点是表示效率不高，存在着时空开销与精度之间的矛盾，栅格的大小直接影响着环境信息存储量的大小和规划时间的长短。栅格划分大了，环境信息存储量就小了，规划时间短，分辨率下降，在密集环境下发现路径的能力减弱;栅格划分小了，环境分辨率高，在密集环境下发现路径的能力强，但环境的存储量大。所以栅格的大小直接影响着控制算法的性能。

3.模板模型法

另外一种常用的方法是模板模型。DeCaravalh提出了一种依靠二维清洁环境的地图并且是基于完全遍历路径规划的模板。为了完成完全遍历路径规划，DeCaravalh定义了五种模板，分别是：前进模型（Towards Model），沿边转向模型（Side Shift）、回逆跟踪（Backtracker），U转弯模型，U转弯交替模型。模板模型法是基于先验知识和先前的环境地图遍历机器人让得到的环境信息来匹配事先定义的模板。因此，整个路径就是一系列的模板组成的。在这个方法中，为了简化路径规划过程，环境事先扩大，这样这种小巧灵活的机器人就可以考虑成一个质点。基于模板的模型完全遍历路径规划，它要求事先定义环境模型和模板的记忆，因此对于变化着的环境就不好处理了，比如在遍历机器人的工作过程中突然出现一个障碍等。

4.人工智能法

近年来有许多学者利用模糊逻辑、人工神经网络、遗传算法等现代计算智能技术来解决机器人的路径规划问题，并取得了一些可喜的成果。

1）模糊控制算法

模糊控制方法应用与路径规划，是一种很有特色的方法，是在线规划中通常采用的一种规划方法，包括建模和全局规划。它用若干个传感器探测前方道路和障碍物的状况，依据驾驶员的驾车经验制定模糊控制规则，用于处理传感器信息，并输出速度、加速度、转角等控制量，指导小车的前进。该方法最大的优点是参与人的驾驶经验，计算量不大，能够实现实时规划，可以做到克服势场法易产生的局部极点问题，效果比较理想。

模糊控制的路径规划方法特别适用于局部避碰规划，具有设计简单、直观、速度快、效果好等特点。

2）神经网络路径规划

神经网络已经被应用到很多的工程领域，机器人领域当然也不例外。神经网络在路径规划中的应用也很多。Tse为清扫移动机器人从一个地方到另外一个地方的运输，提出了BP神经网络，这个模型通过自学习能进行自主导航的路径规划。避障的完全遍历路径规划能够通过离线学习达到，并且有运动行为，路线规划和全局路径规划三个步骤。在运动行为阶段机器人通过各种传感器采集3d环境信息，然后把这些信息输入到BP神经网络中，机器人可以清扫周边的区域直到周边没有未清扫区域。在路线规划阶段，清洁机器人要决定一条最短的路径通向工作空间中其他未清扫区域，在全局路径规划中，产生一个全局环境地图，然后机器人从起始点开始，清扫整个工作空间。

3）遗传算法

遗传算法是由JohnH oland在70年代早期发展起来的一种自然选择和群体遗传机理的搜索算法。它模拟了自然选择和自然遗传过程中发生的繁殖，交配和突变现象。它将每个可能的解看作是群体（所有可能解）中的一个个体，并将每个个体编码成字符串的形式，根据预定的目标函数对每个个体进行评价，给出一个适合值。开始时总是随机地产生一些个体（即候选解），根据这些个体的适合度利用遗传算法（选择、交叉、变异）对这些个体进行交叉组合，得到一个新的个体。这一群新的个体由于继承了上一代的一些优良性质，因而明显优于上一代，这样逐步朝着更优解的方向进化。遗传算法对于复杂的优化问题无需建模和进行复杂的运算，只要用遗传算法的三种算子就能找到优化解，因而在各种领域中得到了广泛的应用。在机器人相关领域研究中，遗传算法已被应用于机械手的轨迹生成、多机器人的路径规划、冗余机械手的障碍避碰。

另一方面，当遗传算法与模糊逻辑，人工神经网络等技术相结合，组合成一个智能学习和进化系统时，便显示了它的强大威力。有很多学者综合运用上述智能方法作了路径规划的尝试。如Toshio Fukuda等人提出了一个具有“结构化智能”的机器人导航系统。它以模糊控制器为核心。路径规划的一种分层决策机构，并且根据反馈得到的奖赏，惩罚信息进行学习和进化。其优点是系统自学习能力，这也是其研究的侧重点，然而他们把系统做的比较复杂，效率较低。

移动机器人的路径规划技术已经取得了丰硕成果，但各种方法各有优缺点，也没有一种方法能适用于任何场合，如模版匹配方法过于依赖机器人过去的经验; 人工势场路径规划方法通常存在局部极小点和计算量过大的问题。不过随着科技不断发展，这些问题都会出现新的解决或者替代方法，同时机器人应用领域还将不断扩大，机器人工作环境会更复杂，移动机器人路径规划这一课题领域还将不断深入。