扫地机器人是怎样规划路径的？

所谓机器人路径规划技术，就是机器人根据自身传感器对环境的感知，自行规划出一条安全的运行路线，同时高效完成作业任务。用一定的算法使机器人能绕开障碍物，并且经过某些必须经过的点完成相应的作业任务；

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

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

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

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

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

1.人工势场法

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

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

2.栅格法

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

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

3.模板模型法

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