简介：基于蒙特卡洛树搜索算法实现的多机器人区域覆盖路径规划项目，采用Python语言编写，整个资源压缩包共六个文件，包含四个py脚本、一份license许可声明和一份markdown说明文档，压缩后大小仅约十九KB，非常轻量，适合快速下载学习。目前已有1102人浏览学习，热度可观。项目利用蒙特卡洛随机模拟与树状搜索机制，在多机器人协同场景中逐步构建状态空间，迭代求解安全高效的覆盖路径，并通过可视化库绘制机器人运动轨迹、覆盖区域以及搜索树的扩展过程，使每一步决策逻辑都清晰可见。代码按功能拆分为路径规划主模块、地图构建模块、结果绘图模块与多机器人调度模块，结构明了，便于二次开发。对于希望学习蒙特卡洛树搜索原理、多机器人协作规划或区域覆盖可视化的人来说，这套资源提供了可直接运行的完整示例与清晰注释，能够帮助快速理解从算法设计到仿真验证的完整流程。

1. 从“扫一遍”到“规划一遍”：蒙特卡洛树搜索如何让多机器人覆盖路径规划真正落地

做过多机器人区域覆盖路径规划的人都知道，一旦地图里出现几堵墙、几个狭长通道，普通“扫一遍”的贪心算法立刻露怯：覆盖率上不去，机器人原地打转，重复区域叠得发烫。蒙特卡洛树搜索算法（MCTS）的价值在于，它把每一步“该派哪个机器人往哪走”变成一棵决策树，用大量随机模拟去估算哪个动作组合的覆盖收益更高，最后把结果可视化出来，让你一眼看到路径、覆盖热力和重复区域。这套 Python 方案不依赖商业求解器，依赖的是 numpy、matplotlib 和一套能讲清楚的状态设计。这篇文章面向已经会写 Python、想从单机覆盖转向多机器人协同规划的开发者，也适合被贪心算法折腾到想换思路的落地工程师。

2. 覆盖规划为什么要选 MCTS：状态树、四步循环与多机器人合流

2.1 先分清问题类型：这是面覆盖，不是 TSP

很多新手拿到“区域覆盖路径规划”第一反应是把它当成 TSP 做：把栅格地图里所有可通行格子当成城市点，然后用 A* 或遗传算法求一条经过所有点一次的最短路径。这个思路看起来顺，实际上在工程里翻车率很高。

TSP 的优化目标是边距离总和，而覆盖规划的优化目标是遍历集合的完整度与重复率。TSP 只需要管一条轨迹上的点顺序，而多机器人覆盖规划同时要管“几个机器人各自走哪片区域”“它们的路径在时间上会不会互相阻塞”“最终是不是所有格子都被覆盖到”。把问题简化成 TSP 的结果通常是：地图分辨率一高，路径开始绕远路；机器人一多，任务分配和路径规划被强行拆开，谁先扫哪片反而成了玄学。

覆盖规划更适合被建模成“状态搜索”问题：状态是当前所有机器人的位置加上共享覆盖矩阵的进度，动作是某一台机器人往相邻栅格移动一步。MCTS 不做一次性求完美解，它通过大量模拟去逐步逼近“哪个动作分支覆盖收益最大”。这个特性和覆盖问题天然匹配，尤其是栅格化地图里边角和障碍很多的时候，MCTS 的随机分支探索比贪心策略更少被局部凹形区卡住。

2.2 MCTS 四步循环在栅格地图上的映射

MCTS 的循环看起来只有四步：选择、扩展、模拟、回溯，但每一步落到覆盖路径规划上都对应着具体的算法决策。

选择阶段做的事情是从根节点出发，沿着已经访问过的子节点一路往下，直到找到一个还没有完全展开的叶子节点。根节点代表“所有机器人都在起点、覆盖矩阵全零”的初始状态。选择时用的 UCT 公式会平衡“这个分支已经表现出来的覆盖收益”和“这个分支我们还没探索够”，具体计算是avg_value + C * sqrt(log(parent_visits) / child_visits)。

扩展阶段是从当前叶子节点生成一个合法子节点。在这个问题上，动作空间是(robot_id, dx, dy)的笛卡尔积，也就是“哪台机器人往哪个方向移动一步”。这一步要过滤掉撞墙、越界、和别的机器人撞到同一格的动作，剩下的动作才会真正挂到树上成为子节点。

模拟阶段是整个 MCTS 最粗糙但最重要的部分。从刚扩展出来的节点开始，不让它继续走真正树搜索，而是用轻量级策略快速走若干步，去估计“如果从这个状态往下走，大概能覆盖多少新格子”。这里的策略不能太重，否则每次模拟都会消耗大量时间；但又不能完全随机，因为纯随机会让收益估计方差非常大。

回溯阶段就是把这次模拟得到的收益值，从当前节点一路累加到根节点上，更新每一层节点的访问次数和累计收益。访问次数越多，UCT 公式里的“探索项”就越小，搜索会逐渐收敛到高收益分支。

2.3 为什么不直接用贪心或遗传算法

贪心算法不需要展开多深的树，每次选一个“当前看起来收益最大”的动作，速度快，调试也方便。问题在于贪心是近视眼，尤其当机器人走进一个 U 形障碍区时，每个局部动作看起来都合理，但整体轨迹会被困在里面反复绕。

遗传算法在覆盖规划里也能用，但需要一个人为设计的编码方式把“多机器人轨迹”表示成染色体。栅格地图一精细，染色体长度暴涨，交叉和变异算子设计起来很痛苦。更关键的是，遗传算法迭代多少代算收敛没有明确信号，而 MCTS 的模拟次数增加时，收益曲线的收敛趋势可以直接画出来看。

多机器人场景下还有一类做法是市场机制或拍卖算法，把每个机器人当成独立智能体去投标抢区域。这套思路在小规模地图上效果不错，但它的问题在于环境变了之后重新竞拍的收敛速度跟不上，而且没有全局覆盖矩阵的显式建模，容易出现两个机器人抢同一片区域、另一片区域没人管的情况。

MCTS 站在另一个极端：它用一棵全局状态树把“所有机器人位置 + 共享覆盖矩阵”同时建模，决策和解耦都不需要额外设计，代价只是计算量。只要你的地图能栅格化、动作能离散化、覆盖收益能被模拟函数估算，MCTS 的应用前提就成立。满足不了这三个条件的场景，硬套 MCTS 只会得到一锅乱炖。

3. 用 Python 落地 MCTS 覆盖路径规划：状态定义、动作生成与主循环

3.1 环境准备与地图数据结构

先说明一下运行环境：Python 3.8 以上就够，不需要装重型仿真框架，numpy 负责矩阵运算，matplotlib 负责可视化。如果你还在配环境阶段，用 vscode 或 pycharm 把解释器选好，pip install numpy matplotlib装完就能往下走。社区里流传的“免费 python 源码大全”可以当作参考，但覆盖规划这个方向代码量不大，自己亲手把状态设计和奖励函数写清楚，后面改起来远比看源码有效。

地图我用二维数组表示，0 代表可通行，1 代表障碍。覆盖矩阵用另一张同等尺寸的整数矩阵记录每个格子被覆盖的次数，这张矩阵既服务于搜索的奖励计算，也是最后可视化的核心输入。

import math import random import zlib from dataclasses import dataclass, field import numpy as np import matplotlib.pyplot as plt # 0 = 可通行, 1 = 障碍 MAP = np.array([ [0, 0, 0, 0, 1, 0, 0], [0, 1, 0, 0, 0, 0, 1], [0, 1, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 1, 0], [0, 0, 1, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0], ]) # 两台机器人的起点 starts = [(0, 0), (5, 6)] # 覆盖计数矩阵：0=未覆盖，>0=被覆盖次数 covered_count = np.zeros_like(MAP, dtype=int) def is_free(pos): x, y = pos return ( 0 <= x < MAP.shape[0] and 0 <= y < MAP.shape[1] and MAP[x, y] == 0 )

这段代码定义了整个方案的地图基础。covered_count使用 int 而不是 bool，关键原因是最终可视化要展示“哪些格子被重复覆盖”，如果只用 bool 就只能看到覆盖和未覆盖两种状态，重复覆盖问题和任务分配失衡问题都会被掩盖。is_free是唯一的地图边界判断函数，后面所有动作生成都会过这一关，不要在多个地方各写一套边界判断，否则狭窄通道里很容易因为边界条件不一致产生死锁。

3.2 节点定义与状态去重

MCTS 的节点是这个方案的骨架。节点里不能只存“某台机器人的位置”，因为这是一棵描述全局态势的树，节点必须同时体现所有机器人的位置以及当前覆盖进度。

一个很容易踩的坑是：直接把整个覆盖矩阵covered_count复制一份存进每个节点。这在 7x7 的小地图上没感觉，换到 50x50 甚至 100x100 的地图，几百个节点就会吃掉几百 MB 内存。正确做法是节点只存覆盖矩阵的哈希值和位置元组，对局部的覆盖矩阵不进树结构，只在每次迭代时临时维护一份。

@dataclass class MCTSNode: positions: tuple # ((x1,y1), (x2,y2), ...) covered_hash: int # 覆盖矩阵的 CRC32 哈希 parent: "MCTSNode" = None action: tuple = None # (robot_id, dx, dy) children: dict = field(default_factory=dict) visit_count: int = 0 total_value: float = 0.0 @staticmethod def make_key(positions, covered): """用位置元组和覆盖矩阵哈希合并成节点去重键""" cov_hash = zlib.crc32(covered.tobytes()) return (positions, cov_hash)

positions之所以用 tuple 而不是 list，是因为 list 不可哈希，没法直接作为make_key的一部分。covered_hash用 CRC32 是工程上的折中：计算快、占用小，极小概率碰撞在规划实验里可以接受；如果要做严格验证，把zlib.crc32换成hashlib.md5(covered.tobytes()).hexdigest()即可，代价是稍微慢一点。

节点不保存覆盖矩阵副本之后，同一片地图的覆盖状态可以通过哈希快速碰撞检测，避免在“覆盖进度相同但动作序列不同”的分支上重复展开树，这一条能省下三分之一左右的内存和搜索时间。

3.3 动作生成与 UCT 选择

动作生成决定了树的分支宽度。栅格地图上，每个机器人每一步可以做五种动作：上、下、左、右、原地等待。这里很多人会漏掉“原地等待”这个动作，但它非常重要——当机器人已经停在走廊尽头或者当前格子周边全部覆盖完成时，等待比乱走更容易让其他机器人补位。

DIRS = [(0, 0), (-1, 0), (1, 0), (0, -1), (0, 1)] # 原地等待 + 四方向 def generate_actions(positions, occupied): actions = [] for robot_id, pos in enumerate(positions): for dx, dy in DIRS: nxt = (pos[0] + dx, pos[1] + dy) if not is_free(nxt): continue if nxt in occupied: continue actions.append((robot_id, dx, dy)) return actions

occupied是当前所有机器人位置组成的集合，用集合去重判断“目标格是否被其他机器人占用”。默认禁止两台机器人同格，这个约束会加剧路径规划难度，但更接近真实多机器人系统的防碰撞要求。如果你在实验阶段想放宽约束，把if nxt in occupied删掉就行，但模拟阶段的奖励函数里仍然会因为重复覆盖而受到惩罚。

UCT 选择是 MCTS 搜索平衡“探索”和“利用”的核心公式，代码写起来不长，但逻辑需要说透：

def best_child(node, c=1.4): def score(child): if child.visit_count == 0: return float("inf") # 未访问过的节点优先探索 avg = child.total_value / child.visit_count explore = c * math.sqrt(math.log(node.visit_count) / child.visit_count) return avg + explore return max(node.children.values(), key=score)

这里有个新手非常容易搞错的地方：未访问子节点给float("inf")而不是给 0。如果给 0，该子节点只有在同一层所有其他节点都被访问过之后才有机会被选中，这会让探索节奏慢一整拍。MCTS 的标准惯例是“每个叶子至少摸一次底”，所以未访问节点永远是最高优先级。

c是探索常数，默认 1.4 在小地图和中等地图上表现都不错。c越大，搜索越倾向于探索访问次数少的分支；c越小，搜索越倾向于待在收益高的分支。这个参数的调法后面第四章会专门讲。

3.4 主循环与轻量模拟

主循环是把上面所有零件组装起来的发动机。每次迭代从根节点出发，维护一份临时的covered矩阵，沿着树往下走时不断应用节点上的动作，走到叶子后扩展新分支，再快速模拟若干步得到收益，最后逐层回溯更新访问次数和收益值。

def simulate(positions, covered, depth_limit=30, lam=0.5): """轻量模拟：快速走 depth_limit 步，估计新增覆盖收益""" sim_covered = covered.copy() sim_pos = list(positions) value = 0.0 for _ in range(depth_limit): occupied = set(sim_pos) actions = generate_actions(sim_pos, occupied) if not actions: break # 优先选择能把“未覆盖”变成“已覆盖”的动作 new_cover_actions = [] for robot_id, dx, dy in actions: nx, ny = sim_pos[robot_id][0] + dx, sim_pos[robot_id][1] + dy if sim_covered[nx, ny] == 0: new_cover_actions.append((robot_id, dx, dy)) if new_cover_actions: robot_id, dx, dy = random.choice(new_cover_actions) else: robot_id, dx, dy = random.choice(actions) nx, ny = sim_pos[robot_id][0] + dx, sim_pos[robot_id][1] + dy if sim_covered[nx, ny] == 0: value += 1.0 else: value -= lam # 重复覆盖惩罚 sim_covered[nx, ny] += 1 sim_pos[robot_id] = (nx, ny) return value

模拟策略的设计原则是“够用但不贪心”。这里优先选新增覆盖动作，判断条件是目标格当前覆盖次数为 0，这比完全随机模拟收敛速度快得多，但又不会像纯启发式那样反复掉进同一个局部陷阱。lam是重复覆盖惩罚系数，默认 0.5，意思是“重复覆盖一个格子，抵消掉半个新增覆盖的收益”。这个值直接影响机器人是倾向于绕路去扫新区，还是就地多踩两遍。

模拟深度depth_limit需要根据机器人数量调整。一台机器人跑 30 步足够探索一片小区域，三台机器人最好把步数扩到 60 到 90，否则模拟还没走完地图就被截断了，收益估计会偏差很大。

主循环和回溯逻辑如下：

def mcts_search(root, init_covered, n_iter=3000, c=1.4, depth_limit=30, lam=0.5): for _ in range(n_iter): node = root covered = init_covered.copy() # 选择：沿已访问子树深入 while node.children and all(ch.visit_count > 0 for ch in node.children.values()): node = best_child(node, c) robot_id, dx, dy = node.action px, py = node.positions[robot_id] covered[px + dx, py + dy] += 1 # 扩展：给叶子补一个未访问子节点 child = expand(node, covered) if child is not None: node = child robot_id, dx, dy = child.action px, py = child.positions[robot_id] covered[px + dx, py + dy] += 1 # 模拟 reward = simulate(node.positions, covered, depth_limit, lam) # 回溯 while node is not None: node.visit_count += 1 node.total_value += reward node = node.parent return best_child(root, c=0.0) # c=0：只取当前收益最高的分支

请注意expand函数的职责：它根据covered找合法动作，创建一个子节点并挂到当前节点上，返回 None 表示已经没有可以扩展的动作了。实现时直接复用generate_actions，过滤出还没有被创建为子节点的动作即可。

best_child(root, c=0.0)是搜索结束后的决策方式：不再管探索项，只取累计平均收益最高的分支，这样选出来的动作分支对应的是当前搜索认为覆盖效率最高的方向。

4. 覆盖结果可视化与三个必调参数：把热力图和轨迹一次看清

4.1 可视化到底画什么：热力覆盖图、轨迹线与重复覆盖标记

覆盖规划的可视化不是追求做一个可视化大屏，而是要让“覆盖次数分布”成为第一眼信息。matplotlib 三张图叠起来就够：第一层是障碍底图，第二层是覆盖热力图，第三层是每台机器人的轨迹线。额外值得做的是在重复覆盖次数超过 1 的格子上打一个标记，这样“哪里扫多了、哪里没扫到”直接从图上读出来。

def draw_result(covered_count, routes, obstacles): fig, axes = plt.subplots(1, 2, figsize=(12, 5)) # 左图：覆盖热力图，颜色越亮代表覆盖次数越多 im = axes[0].imshow(covered_count, cmap="hot", vmin=0, vmax=max(1, int(covered_count.max()))) axes[0].set_title("Coverage Heatmap") fig.colorbar(im, ax=axes[0]) # 右图：障碍底图 + 机器人轨迹 axes[1].imshow(obstacles, cmap="gray_r", vmin=0, vmax=1) for robot_id, path in routes.items(): ys = [p[1] for p in path] xs = [p[0] for p in path] axes[1].plot(ys, xs, label=f"robot {robot_id}") axes[1].legend() plt.tight_layout() plt.savefig("coverage_result.png", dpi=150)

这段代码里最需要注意的是imshow和plot的坐标顺序。imshow显示二维数组时第一个维度是行，也就是 x，第二个维度是列也就是 y。所以画轨迹时plot(ys, xs)而不是plot(xs, ys)，否则轨迹会和热力图错位。这是 Python 数据可视化里最常见的坐标系翻车点，比算法本身的概率高多了。

生成轨迹线数据时，要从最终选中的最佳节点开始，不断回溯到根节点，反序收集每个节点上的action，按机器人编号分别组装成路径。这一步不需要额外算法，就是把树的回溯路径展开成坐标数组。

4.2 三个必调参数：模拟次数、探索常数 C、重复惩罚 λ

参数调优是这个方案里最接近“玄学”的部分，但也是决定搜索结果质量的关键。我按调参顺序列一张参数表，新手照着这个顺序调，基本不会一头扎进死角。

调参顺序我一般固定为：先调c。把c从 1.4 开始，单次跑完看轨迹是否在狭窄区域高频抖动。如果抖动明显，说明探索过重，降低c到 0.8 左右再跑。然后调λ，看热力图上重复覆盖的点是否集中出现在某个角落。最后调n_iter，把搜索过程中的根节点收益曲线画出来，如果曲线还在明显上升就继续加迭代次数，如果已经走平就没有必要再加。

画收益曲线的代码很简单：在mcts_search主循环里每隔 200 次迭代把根节点的total_value / visit_count记录一次，最后plt.plot(values)。如果这条曲线在 5000 次之后仍然每 200 次上升超过 0.5%，可以考虑继续加到 8000 或 10000 次。

4.3 地图变大之后：状态数膨胀的边界

MCTS 最怕的不是算法不收敛，而是状态节点数增长太快。7x7 的小地图随便跑，20x20 的地图节点数能达到几万，50x50 的地图如果动作筛选不严，内存和耗时都会直线上升。

我的经验是三条限制缺一不可：第一，depth_limit不要贪长，覆盖规划模拟只需要评估“接下来一小段谁会更有价值”，30 到 50 步足够，太长反而拖慢每轮迭代。第二，节点去重哈希必须启用，否则同一个覆盖状态会通过不同动作序列被反复创建，节点数量爆炸到无法收拾。第三，可以对长期无人访问的分支做剪枝：每次迭代结束后，如果某个子节点的visit_count不到父节点访问次数的 5%，可以安全释放掉，因为它在 UCT 公式里的探索项已经非常小，大概率不会再被选中。

如果地图真的达到 100x100 以上，单机跑 MCTS 就明显吃力，常见做法是把地图切块，每块先单独跑覆盖规划，再用边界栅格做衔接。这个方案比全局强行搜一棵大树稳定得多。

5. 从死锁到离散化失真：覆盖路径规划最容易踩的 5 个坑

5.1 坑一：机器人在窄走廊里来回震荡

现象：路径图上机器人在一条宽度只有两个格子的走廊里来回折返，覆盖热力图显示两端被反复踩，中间区域却还没扫完。

原因：选择阶段评估的是单个动作的即时收益，窄走廊里向前和向后两个方向都可能接近未覆盖格，UCT 的探索项会不断鼓励尝试另一方向，导致策略在两三个点之间反复横跳。

解决：在奖励函数里加动作连续性奖励。具体做法是：如果当前节点的动作方向和父节点一致，在回溯收益里额外加一个 0.05 的小值。这个量级不至于扭曲整体策略，但足以打破“左右横跳”的平衡点。

5.2 坑二：树越展越宽，内存先爆掉了

现象：程序跑到一半报 MemoryError，或者节点数到了十几万之后明显卡顿。

原因：这是最常见的“把覆盖矩阵全量复制进节点”导致的内存泄漏式增长。每个节点保存一个 50x50 的矩阵副本，一万个节点就是 2500 万个 int，内存消耗接近 100MB。

解决：节点只保存covered_hash，所有覆盖矩阵通过哈希去重。如果连哈希缓存都扛不住，就改成周期性剪掉低访问量的子树。MCTS 不是精确算法，剪掉一部分低频节点对最终路径的影响微乎其微，但内存可以稳定在可控范围。

5.3 坑三：模拟策略太“聪明”，反而让搜索结果变差

现象：模拟阶段用了很强的启发式，每步都优先覆盖最近的新格子，结果收益曲线收敛很慢，最终路径反常地绕远路。

原因：这和直觉相反——模拟策略越贪心，模拟结果方差越小，整棵树的搜索方向越快被锁定到单一局部最优。覆盖问题是稀奖励环境，模拟阶段需要保留一定的随机性，让不同分支都有机会被评估。

解决：把模拟策略改成“一半概率走启发式，一半概率完全随机”。这样既保留了模拟的收敛速度，又保留了探索多样性。不要觉得随机策略是在倒退，对 MCTS 来说，模拟的目的是估值抽样，不是真的要走出那条路径。

5.4 坑四：多机器人“伪均衡”，两台机器人都挤在一边

现象：两台机器人最终覆盖面积差不多，但热力图显示它们覆盖的区域高度重叠，地图另一边大片未扫。

原因：奖励只看“新增覆盖是否增加”，没有考虑“各台机器人之间是否公平分担”。结果就是两台机器人都在地图左侧来回抢新格子，右侧因为距离远，每次选择时收益都要扣掉移动步数，迟迟轮不到。

解决：在回溯收益中加入均衡项。每个机器人维护一个已覆盖格数数组covered_by_robot，如果一个动作让当前机器人覆盖格数明显超过平均值，收益按比例打折。均衡系数不能太大，否则机器人为了追求公平会互相让路，整体覆盖率反而下降。

5.5 坑五：可视化里路径很完美，实际部署却漏扫

现象：仿真热力图上所有格子都是亮的，部署到实际环境后却发现部分区域没有被真正覆盖。

原因：栅格地图是离散化模型，实际机器人有一个覆盖半径，而规划的计算假设是“机器人经过格子中心就算覆盖”。当格子尺寸比机器人覆盖半径大时，两个格子之间的间隙在实际环境中就成了盲区。

解决：可视化额外叠加一层“实际覆盖置信图”：把每个格子的中心点坐标和机器人轨迹点的距离与覆盖半径做比较，凡是距离大于半径的格子标记为“名义覆盖但实际漏扫”。跑完规划后先看这层置信图再决定是否部署。这个步骤不需要改算法，只是给可视化加一个后处理滤镜，但它是从仿真走到真实环境之间最便宜的一道后悔药。

6. 进阶：把 MCTS 覆盖规划从试验脚本改造成可复用工具

6.1 把收益函数做成可插拔接口

我最早写这个项目时，把奖励逻辑焊死在simulate函数里，后来换地图、换指标要求时，每次都要改函数体，改完还要担心破坏搜索逻辑。建议做一层接口：搜索函数接收一个reward_fn，默认实现是“新增覆盖 +1、重复覆盖 -λ”，实际使用可以根据场景替换成带均衡项、带边界奖励、带覆盖半径权重的自定义函数。这个重构很小，但收益极大，因为算法参数和业务指标被正式拆开了，后续实验全部走配置而不是改代码。

6.2 验证方法：同一张地图至少跑 10 次再看均值

MCTS 是随机算法，跑一次得出的路径不能说明问题。常规做法是在同一张地图、同一组起点、同一组参数下跑 10 次，统计覆盖率的均值、重复率、总耗时，最好再和一个贪心基线做对比。如果 MCTS 的覆盖率均值不低于贪心，且重复率更低，这个方向才有继续投入的价值。指标很多，但覆盖率和重复率是最核心的两个，建议先只盯这两个，其他均衡度指标等都稳定了再上。

我现在的习惯是每改一次参数，先跑三张不同复杂度地图的 10 次统计，再决定要不要上 5000 次以上的大规模搜索。不要在一张地图上调出完美参数就急着部署，换一张地图很可能会现出原形。希望这个方案和坑位记录能帮你在区域覆盖路径规划上少走一段弯路。

本文还有配套的精品资源，点击获取