摘要：本文提出一种融合细胞自动机与改进蚁群算法的分层路径规划方法，以解决扫地机器人在复杂环境下的全覆盖问题。该方案通过模拟二维栅格地图，使用细胞自动机对栅格图划分，将利用自由度划分 不同子区域，通过构造合理的代价函数对遍历方案进行优化，结合旅行商问题、蚁群算法以串联起所有子区域。与Boustrophedon 算法对比，该方案使扫地机器人在保证覆盖率的情况下，合理划分区域同时减少 重复率。实验表明，该方法在室内场景中全覆盖，路径重复率较传统降低 10% ，且根据等效时间效率显著低于传统智能算法，为扫地机器人提供了高效、可靠的路径规划解决方案。关键词：扫地机器人;路径规划;蚁群算法;细胞自动机;旅行商问题;2-Opt 算法

中图分类号：TP242.6 文献标识码：A

0 引言

随着扫地机器人的不断推广，现在对扫地机器人的路径规划能力已成为衡量其智能化水平的关键指标[1-3]。覆盖路径规划要求机器人在已知环境中以最短路径实现无遗漏、低重复的清扫任务，其核心难点在于如何在存在多个障碍物的非结构化空间中，合理划分子区域并确定最优遍历顺序。对于依赖于人工预设区域或几何划分方法，而面对复杂的实际环境，简单的预设区域无法完美实现；而基于群智能优化的方法虽能提升路径质量，但往往面临计算效率与实时性之间的突出矛盾，使得需要一种高效的方案。

针对上述问题，本文提出了一种结合细胞自动机与蚁群算法的分层路径规划架构[5-7]。本研究最重要的在于设计了一种基于冯诺依曼邻域状态演化的细胞自动机规则，能够自主、高效地完成对环境空间的凹性区域划分，避免了传统划分方法对先验知识的依赖。在此基础上，将子区域间的访问顺序转化为旅行商问题[8]，利用信息素动态更新机制优化蚁群算法的搜索效率[9]，最终生成全局近似最优的覆盖路径。

该方法显著降低了复杂环境下路径规划的计算复杂度，在保证全覆盖性的同时有效减少了路径重复率，为扫地机器人等移动设备在资源受限条件下的实时路径决策提供了可靠解决方案，具有较高的工程应用价值。

1 扫地机器人的运动学分析

1.1 全向轮

全向轮是一种常见的轮式移动机器人轮子形式，其可以在任意方向上移动，其具有较高的灵活性和适应性。全向轮一般由轮毂和两个方向轮组成，轮毂可以绕自身轴线旋转，同时万向轮可以绕轮毂轴线旋转，从而使我们的机器人在任意方向上移动。在运动学分析中，全向轮的核心特性可概括为两点：一是主运动无滑性，即轮毂绕自身轴线转动时，与地面接触点在主运动方向无相对滑动，满足纯滚动条件；二是侧向低阻性，辊子的被动转动将侧向滑动摩擦转化为滚动摩擦，大幅降低侧向运动阻力，可近似认为侧向无附加力矩干扰[1]。

1.1.1 全向轮运动分析

以全向轮小车的几何原点建立 CENTER 坐标系，x 轴方向为小车的向前运动方向（红色箭头），与之垂直向左为y 轴正方向（绿色箭头），z 轴垂直于纸面向外。图表三为三轮全向轮移动小车的坐标系示意图，其中A，B，C 为全向轮与地面的接触点。

1.1.2 全向轮小车运动模式的分析

向前直线运动：M1 电机静止，M2 轮逆时针转动，M3 轮顺时针转动，且 M2 和 M3 轮运动速度大小相同，M2 和M3 的速度方向也是其静摩擦力方向，摩擦力大小相等，方向关于坐标系的 x 轴对称。反之M2，M3 轮反向转动则可则可驱动小车向后运动。

左向直线运动：从图5 可知，M1 轮正转，M2，M3 轮反转。对应这M2 轮和 M3 轮速度X 轴上的投影分量大小相等，方向相反。而在 y 轴上的投影分量大小相等，方向相同，则相互叠加，且叠加后的方向与M1 的速度方向一致。

图 4

图 5

由图可知全向轮外围的辊子是与地面接触的，当全向轮绕轮毂转动时辊子会与地面产生摩擦力，辊子受到的合力为 F ，可沿着辊子坐标系的坐标轴分解为纵向 F 平行和横向 F 垂直，其中纵向分力 F 平行是由于电机驱动轮毂转动，轮毂会带动辊子整体绕轮毂轴线转动，辊子与地面接触产生静摩擦从而驱使全向轮向前运动[2]。

下面对全向轮小车进行运动学分析，建立运动学模型。为了更加简便，我们做出以下三点假设

1：小车是刚体。

2：小车的运动局限于平面上，忽略地面的凹凸不平及其带来的影响。

3：车轮与地面不打滑。

2 扫地机器人路径规划分析

2.1 路径规划的衡量指标

在扫地机器人的路径规划中，需要贴近实际生活，即能够合理划分出房屋中房间，使扫地机器人提高工作效率。同时，扫地机器人的实际使用意义需要其100%的覆盖率，因此使用全遍历路径规划实现全区域覆盖且无碰撞，但其在重复路径使用方面效果不好。实用性是衡量路径能否在现实中安全、高效执行的重要指标。使机器人完成从理论到实际使用的转变，保证了规划出的路径不仅理论最优，更能实际部署并稳定运行。

本文中，以划分合理性，重复覆盖率和实用性指标这三方面作为衡量指标。

2.1.1 划分合理性

划分合理性是指在扫地机器人的路径规划中根据房屋的实际布局和功能区域进行合理划分，以提高清扫效率和覆盖全面性。主要评判标准为：各子区域应保持良好连通性，避免形成孤立区域导致无法覆盖。其次各子区域应尽量均匀，避免出现过大或过小的子区域，将过小的区域合并可以显著提升清洁效率。最后划分的子区域中应不含障碍物。

2.1.2 重复覆盖率[4]

重复覆盖率R 指机器人重复经过的区域面积占总面积的比例，重复覆盖率可用来描述路径效率。最优情况下，每条路径只覆盖未清扫区域一次，无重复路径，此时重复覆盖率趋近于 0，重复清扫则表明路径效率降低。SR 表示完成清扫时重复清扫面积，S 表示任务总区域面积，重复覆盖率可以表示为：

（10）

2.1.3 实用性指标

扫地机器人路径规划的实用性指标通常包括路径的可行性、稳定性、路径成本等，首要的是可行性与安全性，这保证了机器人可以正常完成路径。稳定性指机器人在复杂区域下的可靠性，通常会进行大量测试，记录成功概率。综合成本是指机器人在运行时的各种消耗，包含机器人使用成本，通行路径成本等。这些指标共同作用，确保路径规划结果在实际情况中能够准确执行。

2.2 基本路径规划

本文采用的路径规划方案为：使用栅格地图，先建立一个二维的栅格地图，再将整个栅格地图划分为数个子区域，机器人分别对各个子区域进行清扫，以此完成清扫的目标。基本路径规划如下图所示：

图6 基本路径规划示意图

3 静态地图扫地机器人的路径规划方案

3.1 栅格地图的建立

3.1.1 环境建模

在ROS 中栅格地图（Grid Map）的构建是机器人导航和环境建模中的重要步骤。将环境划分成各个独立的小单格，每个格子存储对应区域的占用状态，栅格地图的信息用一个一维数组表示，数组每个元素表示每个栅格的占据状态。本文使用的栅格地图其中0 表示空闲区域（即图1 中白色区域），1表示完全占据区域（即图1 中黑色区域）-1 表示未知区域。

栅格地图的栅格粒度（Grid granularity）决定了地图的精度，较小的网格可以表示更细节的环境，尺寸较大时栅格的数量减少。本文中的网格尺寸为小车直径。下图为本文使用的栅格地图。

细胞按接下来的规则进行变化，同时使用同步更新策略，确保所有细胞同时根据当前全局状态计算下一状态。

1）自由度为 3 的细胞，如果如果恰好有3 个邻域自由度为4 ，自身状态变为4。同时自由度为4的细胞如果至少有3 个邻域自由度为3，自身状态变为3。

2）自由度为3 的细胞，如果至少有2 个邻域自由度为4，自身状态变为 4。自由度为 2 的细胞，如果至少有 1 个邻域自由度为4，自身状态变为 4。

3）自由度为2 的细胞，如果存在邻域自由度为3，自身状态变为3。

图7 栅格地图

3.1.2 扫地机器人运动规则

基于最后的自由度矩阵，使用洪水填充算法进行填充。洪水填充算法是一种在二维平面上填充连通区域的算法，使用该算法将相邻的同自由度单元格划分为同一区域。

图8 机器人运动方向

本文中设置扫地机器人可以在四个方向运动，移动规则如图8 所示。

3.2 子区域的划分

建立栅格地图后，需要根据划分合理性的评判标准对栅格地图进行划分，即划分栅格地图时必须确保完整覆盖整个地图，确保完整的覆盖率。各个子区域之间需要保证连通性，子区域内的所有栅格需要保持联通，避免出现无法覆盖的栅格。基此，本文使用细胞自动机进行子区域的划分。

细胞自动机是定义在一个具有离散、有限状态的细胞组成的细胞空间上，并按照一定演化规则，在离散的时间上演化的动力学系统[5]。包含三个特点：

1）细胞状态[6]。细胞自动机中的每个细胞都拥有一个有限的、离散的状态集合。本文中细胞指栅格地图中的单元格。

2）细胞邻域关系[7]。这是指细胞周围的细胞集合，每个细胞的状态更新都受到周围细胞的影响，本文中依据二维栅格地图使用冯诺易曼型邻域。冯诺易曼型邻域指的是与中心细胞的边相邻接的细胞集合（4 个相邻细胞 ）

3）细胞状态转换规则[7]。指在细胞邻域的限定下细胞状态随时间变化的函数。该规则是细胞自动机动态演化的核心驱动力。

图12 划分结果

图中表示最终划分子区域结果，共划分出 6 个子区域。每个子区域都符合划分合理性的评判标准，通过该方法，可以有效提高扫地机器人清扫的效率和准确性，更贴合实际使用情况。

3.3 全局路径规划方案

3.3.1 子区域内遍历方法

扫地机器人在子区域中的路径规划要求能够访问该区域内的所有可通行单元格，同时需要保证子区域内 100% 的覆盖率前提下，最小化转弯次数和冗余度。在子区域已通过自由度分析确保连通性的前提下，选择Z 字形扫描作为覆盖策略，该方法通过双向交替的扫描方式实现子区域内遍历。

图9 冯诺易曼型邻域

图中黑色部分表示自身，灰色部分表示细胞邻域。

细胞的状态按照自由度 i 进行区分，自由度 i 为每个可通行单元格4 邻域中可通行单元格数量，状态为0-4。

图 10 初始自由度地图

图中表示各子区域内遍历路径。可以看出该覆盖策略产出的路径不能适配所有子区域，原因在于不灵活的扫描轴只能根据行进行交替扫描。

图11 最终自由度地图

基于Z 字形扫描进行优化，其核心两点在于扫描轴选择和方向切换，其中扫描轴选择决定路径沿行方向或列方向行动，方向切换是在遇到子区域边界上，机器人的移动方向必须反转，以避免长距离的回溯。为了评估和选择最优的遍历策略，即选择行扫描还是列扫描，我们引入了路径成本模型，优化目标为最小化总路径成本 。

C=ωt×T+ωr×R

其中 T 是转弯次数指路径中方向变化的次数。在遍历中，主要发生在遇到区域边界处。R 是冗余度指路径重复访问的单元格数量，即路径长度与区域面积之差。其中，ωt 和ωr 分别是转弯次数和冗余度的权重。

最优遍历路径生成后，序列中的第一个单元格定义为起点，最后一个单元格定义为终点。这些确定的起终点将作为全局路径规划中，连接不同子区域的接口节点，确保全局覆盖路径的连贯性和可执行性。

图13 基本Z 字形扫描路径图

在上文基础上，由于本地图所使用的模拟为在低分辨率情况下划分出子区域，实际情况地图将更为复杂，且栅格的实际边长更加大。使用图15 中，将分辨率调整至 2 倍以贴合实际情况，得到最终结果重复率为 24.80% ，总自由单元格数是276，总路径长度是367。

对比优化前后可见，在区域1 中重复率大幅下降，在此阶段中根据重复率公式重复率从 6% 下降到 3% 。对于其他区域，尤其是区域 2，起始点和终点相对里外侧更加近，这使得后续对子区域遍历顺序所需要的路径将大大减少，可优化重复覆盖率。

3.3.2 子区域遍历顺序

在全局路径规划中，子区域的遍历顺序极大影响了整体路径的效率。该问题可看为旅行商问题，旅行商问题是一个经典的组合优化问题：一名推销员希望走遍多个城市来销售他的商品，他只会访问每个城市一次，并最终返回他出发的第一个城镇，任意两个城市之间的距离是已知的。推销员总的路径长度是根据城镇的访问顺序决定的，目标是找出给出最短路径长度的访问顺序。

2opt 算法是一种启发式搜索方法，其原理为先求得一个原始解，然后交换所得解的两条边。将所得新解与原解进行比较，保留好的解。继续循环直到找到最优解。但在处理大规模或结构复杂的优化问题时。2opt 算法有可能陷入局部最优解，针对该问题，本文加入蚁群算法优化遍历顺序[8]。

3.3.3 蚁群算法数学模型[10]

蚁群算法原理为，在蚂蚁觅食的过程中，蚂蚁会在走过的路径中释放一种叫做“信息素”的物质，用来标记自己走过的路径。基本思想就是根据概率选择信息素浓度大的路径走，信息素浓度越高，蚂蚁选择该路径的概率也越大。碰到还没走过的路，就随机挑选一条路走。

3.3.4 蚁群算法流程

（1）初始化蚁群算法的各个参数。

（2）将蚂蚁放置在子区域终点，目的地为下个子区域起点。

（3）每只蚂蚁按机器人运动方式和路径选择概率公式选择下一个节点直到找到目的地。

（4）计算各蚂蚁路径长度，得出最优路径。

（5）更新信息素。

（6）令 t=t+1。

（7）如果 tmax ，则在步骤（2）重复，否则输出最优路径结束循环。

3.4 路径优化结果

根据前文划分的子区域结果，经过2opt 算法和蚁群算法的共同作用，得到子区域间遍历顺序：2-3-4-6-1-5

图 14 优化后子区域遍历路径

图15 子区域间连接路径

图16 传统牛耕算法

以传统牛耕算法为例，其采用通常固定扫描方向（如水平扫描）。当遇到狭窄的垂直通道或死胡同时，水平扫描会导致路径质量极差，甚至在死胡同里必须原路退回。

从图16 可看出在类似 U 形连通器结构的区域传统牛耕算法难以识别，会导致错误或是反复的来回于两个子区域，导致大量的重复路径。在优化方案中在每个划分的子区域内，细胞自动机模型会动态选择垂直或水平方向，保证扫描轴线与子区域的最长边对齐。

在使用相同地图的情况下，传统牛耕算法的重复率为 35.05% 。结果表明在覆盖率一致的情况下，优化算法有效降低了重复率。

4 结论

本研究通过构建融合细胞自动机与改进蚁群算法的规划架构，提供了复杂环境下扫地机器人的全覆盖路径规划问题新的解决方法。实验结果表明，基于局部邻居状态演化的细胞自动机规则能够有效实现环境空间的自主区域划分，生成具有高度凹凸性倾向的子区域模块。改进的蚁群算法通过结合2-Opt 算法，显著提升了区域间遍历顺序的求解效率与质量。该方法的普遍性在于其不依赖于环境先验模型，在二维栅格地图即可启动，因而适用于静态地图的室内场景。

研究过程中发现，当环境中存在大量细小且分布密集的障碍物时，细胞自动机规则可能产生过度分割现象，导致区域数量增多，虽不影响全覆盖性，但一定程度上增加了蚁群算法求解TSP 问题的复杂度。当前模型针对动态出现的障碍物尚未建立实时重规划机制。

与先前研究[4]相比，其使用的方案基于栅格法的特性以及矩形子区域有便于用坐标标识、方便实现等优势，将各区域划分为矩形，本文认为需要兼顾实际使用，引入划分合理性作为评判根据。本文在传统群智能优化框架内引入了细胞自动机以解决自主划分问题，在保证算法透明性与可解释性的同时，兼具了良好的环境适应性。

本研究验证了通过简单局部规则涌现出全局空间划分模式的可行性，为复杂系统的自组织研究提供了跨学科案例。在实用层面，所提方法以软件为主计算高效、不依赖高精度传感器与强大算力支持。但是依旧具有局限性，比如对高复杂度环境的敏感性，在障碍物极度密集、琐碎（如儿童散落大量玩具）的环境中，CA 算法可能导致过度分割，即产生大量细小区域。虽然保证了全覆盖性，但会急剧增加TSP 问题的复杂度，影响整体规划效率。

后续研究可以增强动态重规划能力，集成轻量级实时障碍物感知模块。当检测到动态障碍物时，可局部触发CA 规则进行小块区域重划分，实现全局规划与局部反应的完美融合。同时引入智能规则优化机制，针对过度分割问题，可探索基于强化学习的CA 参数调优，进一步加强细胞自动机与深度学习模型的结合，让机器自主学习在不同环境复杂度下最优的阈值，使分区策略更具智能化。例如利用卷积神经网络预测最优规则参数，以进一步提升划分效率与质量，还可以尝试将本架构扩展至多机器人协同覆盖场景，研究区域分配与路径规避的综合策略。

参考文献：

[1]吴蕊，李振华，蔡宇鑫.基于 ROS 的视觉导航机器人设计[J].物联网技术，2025，15（12）.

[2]周宝昌，林梓宏，周旭华等.基于ROS 的全向轮智能机器人小车设计[J].装备制造技术，2022（11）：80-83.

[3]轮趣科技 WHEELTEC L150PRO 多功能智能小车资料.

[4]谢坤霖，李宗根，代宇航，等.基于启发式搜索算法的扫地机器人路径规划[J].西华大学学报（自然科学版），2019，38（04）：69-76.

[5]曾志峰.细胞自动机的特点及应用领域研究[J].信息通信，2014，（10）：159.

[6]张奇志，周亚丽.基于人工势场与细胞自动机的移动机器人路径规划算法[J].北京信息科技大学学报（自然科学版），2014，29（05）：8-13+22.DOI：10.16508/j.cnki.11-5866/n.2014.05.014.

[7] 刘 翠 . 基 于 细 胞 自 动 机 的 城 市 空 间 研 究 进 展 [J]. 华 中 建筑，2018，36（04）：16-19.DOI：10.13942/j.cnki.hzjz.2018.04.005.

[8]秦东各，王长坤.一种基于 2-opt 算法的混合型蚁群算法[J].工业控制计算机，2018，31（01）：98-100.

[9] 危 雄 飞 . 一 种 改 进 蚁 群 算 法 在 旅 行 商 问 题 中 的 应 用 研 究 [D]. 景 德 镇 陶 瓷 大学，2024.DOI：10.27191/d.cnki.gjdtc.2024.000086.

[10]Yang H ，Qi J ，Miao Y ， et al.A New Robot Navigation Algorithm Based on a Double-Layer Ant Algorithm and Trajectory Optimization.[J].IEEE Trans. Industrial Electronics，2019，66（11）：8557-8566. 姓名：郭峻宇，

出生年月日：20041212，性别：男，民族：汉，籍贯：山东，本科生，学习单位：，详细地址：上海市松江区龙腾路333 号