1 前言

覆盖全路径规划（Complete Coverage Path Planning，简称CCPP）的核心任务在于：为机器人规划一条路径，使其能够遍历目标区域内的每一个角落，同时巧妙避开所有障碍物。听起来简单，实际实现却颇具挑战。

Choset根据环境地图是否预先已知，将CCPP算法划分为“在线式”与“离线式”两大类。离线式算法依赖静态环境信息，假设地图已提前绘制完成——然而在现实场景中，许多情况下我们无法获得完整地图。因此，在线式算法应运而生：它不需要预先知晓环境全貌，而是依靠传感器实时扫描，边行走边构建地图，这类方法也被称为基于传感器的覆盖算法。

若按算法工作原理进行划分，又可细分为随机碰撞法、单元分解法、生物激励法、模板法、智能算法等多种流派。无论采用哪种方法，都必须满足几个基本要求：机器人需覆盖目标区域内除障碍物外的所有点；过程中应尽量避免重复路径；运动轨迹最好简单易控（如直线或圆弧）；在条件允许时，还需找出“最优”路径——要么总路程最短，要么能耗最低。

2 随机碰撞法

随机碰撞法本质上是一种“以时间换空间”的策略。其思路非常直接：机器人随机选择一个方向前进，沿途覆盖该直线扫过的面积；一旦碰撞到障碍物，便顺时针旋转一定角度，然后继续重复上述过程。这种方法的覆盖面积完全依赖运气，理论上只要时间足够长，确实能覆盖较大范围——但效率极低。

不过，它也有自身优势：不需要复杂的定位传感器，通常仅需安装几个红外传感器即可，计算量也极小。缺点则十分明显：在局部范围内会反复走重复路径，且对环境适应性较差。尤其是在包含多个子区域、仅由一条狭窄走廊连接的环境中，随机碰撞法可能长时间在走廊内“撞墙”，难以抵达另一个区域。

在实际应用中，扫地机器人常因动态障碍物而被卡住，此时调用随机路径覆盖作为“挣脱困境”的应急手段，是一种常见的处理方式。

3 单元分解法

单元分解法的思路是将整个自由空间分割成若干个简单、互不重叠的子区域（每个子区域称为一个“细胞”），这些细胞的并集恰好填满整个自由空间。随后，机器人在每个子区域内采用简单的覆盖方式（如来回往复运动或螺旋运动）逐一清扫，完成所有子区域的覆盖即实现全局任务。

以梯形分解法为例，它是最经典的精确细胞分解方法。首先让机器人沿着空间边界走一圈，构建完整地图；然后使用一条竖直切割线从左到右扫描整个区域，每当切割线碰到多边形障碍物的顶点时，便切出一个子区域。最终得到的每个子区域均为梯形。机器人在每个梯形内进行往复运动完成覆盖，效果如下图所示。

其他代表性方法还包括牛耕单元分解法[1,2]、莫尔斯分解法[3,4]、线扫分割法等，此处不再展开，感兴趣的读者可查阅参考文献。

4 生物激励法

Yang和Luo将生物激励的神经网络模型应用于清洁机器人的全覆盖路径规划。他们采用栅格地图表示环境，每个栅格对应一个神经元细胞，并提出一个分流方程来计算周围神经元对当前神经元的激励或抑制程度。方程如下：

[公式略，原文中无具体公式文本，只有描述]

其中x_i表示第i个神经元的状态；A为非负常数，代表神经元活性的衰减速率；B、D为神经元状态的上下限；I_i为外部输入，ω_ij是第i个神经元与第j个神经元的连接权值，通常由两个神经元之间的距离计算得出。第i个神经元的活性值连接关系如下图所示。

当机器人位于某个栅格时，会计算周围所有神经元的活性值，然后选择活性值最大的那个栅格作为下一步的落脚点。生物激励法的优点是适用性好，避障和实时性表现不错；缺点是路径重复率可能偏高。

5 模板法

模板法由Neumann de Carvalho R等人提出，它依赖二维环境地图的先验知识，同时也能处理地图上未标注的意外障碍。该方法将机器人的运动行为预先设定为七种固定模板（如下图所示），这些模板基本覆盖了机器人在环境中可能遇到的所有情况。机器人根据当前情况匹配相应模板进行运动，最终完成全覆盖。

模板法的优势在于原理简单、计算开销小，且能应对动态障碍物；缺点是必须事先知道地图，适用性较窄，智能程度也不高。

6 智能算法

Wang[5]将遗传算法与牛耕单元分解法相结合：首先使用分割线将自由空间切分为子区域，然后通过遗传算法对这些子区域进行编码，建立子区域之间的基点信息，再搜索出最优的覆盖顺序。在每个子区域内仍采用往复运动进行覆盖——这样一来，CCPP问题便被转化为经典的旅行商问题（TSP）。

Zhang[6]则将蚁群算法引入单元分解法：根据两个子区域之间的连通性信息定义距离矩阵，再用蚁群算法优化覆盖顺序。实验结果表明，这种结合既能保证全覆盖，又能使规划出的路径更短、重叠率更低、效率更高。不过对于复杂环境，依然难以完全避开障碍物附近的恢复区域。