摘要： 本文提出了一种基于 A* 算法的清洁机器人完全覆盖路径规划算法，该算法将 A* 算法作为 U 形搜索算法的启发式搜索方法。该算法的思路是，清洁机器人从起点出发，使用 U 形算法清洁清洁区域，当机器人进入死节点时，使用 A* 算法规划从清洁机器人到未清洁区域的最近路径，然后清洁机器人沿着这条路径使用 U 形搜索算法清洁到未清洁区域，直到这个环境区域全部覆盖。仿真结果表明，本文提出的算法具有高覆盖率、低重复率的特点。
关键词： 清洁机器人，A* 算法，U 形搜索算法，完全覆盖路径规划。
1. 引言
        随着人工智能技术和移动机器人技术的快速发展，智能机器人路径规划技术越来越受到研究人员的关注。智能机器人路径规划研究分为两个方面：一个是点到点的优化路径规划，另一个是完全覆盖优化路径规划。目前，点到点的优化规划被国内外专家研究得更多，而完全覆盖路径规划的研究相对较少。完全覆盖路径规划是指在不包含障碍物的环境区域中尽可能短的时间内遍历整个区域，并尽可能降低路径重复率。完全覆盖路径规划具有广泛的应用背景，在清洁机器人、收割机器人、播种机器人和搜救机器人等领域具有重要意义。
        根据不同的移动策略，完全覆盖路径规划可以分为随机运动策略和非随机运动策略。随机运动策略是指清洁机器人在遇到障碍物时随机旋转一定角度，这种方式清洁机器人的工作效率不高，需要长时间才能完成工作区域的完全覆盖，并且位置和环境建模也需要进一步探索。非随机运动策略是指使用一种性能评估函数来控制清洁机器人的运动路径，而性能评估函数是清洁效率的关键。根据不同的环境信息，完全覆盖路径规划方法可以分为已知环境路径规划和未知环境路径规划。在已知环境中，清洁机器人根据已知环境信息进行建模和生成图，然后使用图遍历方法进行路径规划；在未知环境中，清洁机器人使用其自身的传感器系统来探索和识别环境，并根据环境识别信息进行建模和生成图，然后使用相应的方法进行路径规划。
2. 基本概念和相关工作
2.1 基本概念
本文将 A* 算法应用于 U 形搜索算法的完全覆盖路径规划，以提高完全覆盖路径规划的效率。具体定义如下：

•  完全覆盖路径规划： 给定一个环境区域 S，F 表示环境中的障碍物，机器人 A 绕过障碍物遍历环境区域 S 的路径 L 是完全覆盖路径规划。
• A *算法： A* 算法是一种启发式搜索算法，用于点到点的最短路径规划。在基于 A* 算法的路径规划中，需要选择评估函数，评估函数用于节省大量的无意义搜索并提高搜索效率。评估函数对评估位置很重要，使用不同的评估函数会有不同的效果。
• U 形搜索： 清洁机器人的 U 形搜索模式是从边缘点开始沿直线行走，遇到边界后向同一方向旋转 180 度，然后沿反方向直线行走。转弯直径与机器人直径一致。当遇到障碍物时，机器人采用隔离方法躲避障碍物。如此反复，直到整个区域被覆盖，如图 1 所示。
• 内螺旋搜索 (ISS)： 内螺旋算法的基本思想是机器人沿着某个方向遍历环境区域。当前面的网格没有被覆盖时，机器人向前移动。如果前面的网格已经被覆盖或存在障碍物，则机器人向右旋转 90 度，如图 2 所示。

2.2 相关工作
        目前，主要的完全覆盖路径规划方法包括随机覆盖法、模板模型法、波斯特洛芬覆盖法、STC 覆盖法和 ISC 覆盖法等。这些方法存在一些缺点，例如随机覆盖法由于障碍物的随机转向和电池功率有限，不能保证环境的完全覆盖。同时，该算法的智能化程度很低，重复清洁率很高。模板模型法使用不同的地图和模板根据不同的环境进行完全覆盖，但环境不匹配时无法实现完全覆盖。波斯特洛芬覆盖法由于障碍物较多，会导致覆盖不完整。STC 覆盖法由于其网格标准，无法覆盖较小的区域。ISC 覆盖法经常导致障碍物附近区域无法完全覆盖。考虑到清洁机器人清洁未清洁区域时尽可能走最短路径，本文使用网格法对环境信息进行建模，并提出了一种新的完全覆盖路径规划算法，该算法结合了 U 形路径规划算法和 A* 算法，并与内部螺旋法进行了比较，并使用 MATLAB 进行了仿真实验。
3. 基于 A 算法的完全覆盖路径规划算法*
        本文使用网格法对环境信息进行建模，并将带障碍物的网格用 2 标记，将无障碍物的网格用 0 标记。它将 A* 算法应用于 U 形算法，形成新的完全覆盖路径规划算法。它使用 U 形算法搜索网格模型中已经建模的除障碍物以外的区域，同时使用 1 标记已覆盖的区域。然后，它使用 A* 算法找到从清洁机器人到未覆盖区域的最近路径，并沿着这条路径使用 U 形路径规划进行清洁工作，直到整个区域被覆盖。
3.1 环境网格
        网格法作为一种建模方法，研究得比较多，将整个覆盖区域划分为许多小网格并进行标记。本文给出了两种标记分别表示未覆盖区域和障碍物区域。使用网格法建立环境模型将实际的房间地图转换为数字矩阵，并通过实际区域和网格区域的映射实现了房间区域的离散表示。为了实现清洁室内卫生的目的，清洁机器人的目标是花费更少的时间寻找最短路径清洁所有阴影网格。本文将网格分为两种类型，阴影部分是不需要清洁的网格，空白部分是需要清洁的网格，清洁机器人在该网格中寻找路径进行清洁工作。
3.2 基本思想
        清洁机器人根据 U 形算法的思路清洁环境区域。在 U 形路径规划算法中，如果机器人的前一个网格是边界，并且其左侧或右侧网格存在障碍物，则机器人沿着原路径回到左侧或右侧障碍物的末端；如果机器人的左右两侧网格都被清洁了，则表示机器人进入了死状态，此时机器人需要停止等待下一次清洁任务；此时，如果机器人的左右两侧网格没有被覆盖，则该机器人向左或向右旋转 180 度，以相反的方向进行清洁。当机器人使用 U 形算法清洁环境信息并进入死状态时，且机器人的左右两侧都被清洁了，此时，将清洁机器人作为起点，将未清洁区域作为目标点，然后使用 A* 算法找到到达目标点的最优路径。以同样的方法，找到从当前清洁机器人到整个未覆盖区域的最优路径。我们选择最短路径作为清洁机器人清洁的优选路径。依此类推，直到所有未覆盖区域都被清洁。
3.3 评估函数
本文中，每个位置的评估值可以用以下评估函数表示：
f(n)=g(n)+h(n)
其中，f(n) 是从当前位置到目标节点的总成本评估，即计算最优路径。
g(n) 表示从初始节点到任意节点 n 的实际路径成本，
h(n) 表示从节点 n 到目标节点的最优路径估计成本，即根据一种方法计算估计值。从这个评估函数可以看出，搜索的启发式信息体现在 h(n) 中。如果评估值越来越接近实际值，则表明评估函数更好。
本文将 10*10 网格环境中的目标节点设置为数字 g，定义从节点 n 到节点 g 的启发式函数为：

其中，“[ ]”表示整数运算，“%”表示模运算，“| |”表示绝对值运算。
3.4 U 形 A 路径规划算法*
        本文提出了一种新的完全覆盖路径规划算法，称为 U 形 A* 路径规划 (UAPP) 算法。描述如下：

1. 使用网格法模型对平面上的清洁环境区域进行建模，并将环境信息抽象为二维网格。
2. 使用 2 标记有障碍物的网格，使用 0 标记无障碍物的网格。
3. 使用 U 形算法搜索该环境的完全覆盖路径，并使用 1 标记已清洁的网格。
4. 如果机器人的前一个网格已经被覆盖或存在障碍物，则向左（或向右）旋转 180 度，然后沿反方向直线行走。
5. 如果清洁机器人的左侧或右侧网格被覆盖，则执行回滚操作。如果清洁机器人的左右两侧都被清洁了，则转到步骤 6；如果清洁机器人周围存在未清洁的网格，则转到步骤 3。
6. 将当前清洁机器人作为起点，未清洁区域作为目标点，然后使用 A* 算法找到到达未清洁区域的最优路径，此时选择最短路径作为清洁机器人清洁的优选路径，然后清洁机器人沿着这条路径到达未清洁区域，转到步骤 3；如果存在未清洁区域，则表示该区域已经被完全覆盖，转到步骤 7。
7. 算法结束。
8.