简介：本资源面向计算机、人工智能、自动化等专业的在校学生与研究人员，提供一套基于蒙特卡洛树搜索算法实现多机器人区域覆盖路径规划的完整项目源码，可用于课程设计、毕业设计或算法学习进阶。压缩包共6个文件，包含4个Python脚本、1个Markdown说明文档和1个LICENSE授权文件，整体约22KB，其中Python脚本分别负责单机与多机场景下的MCTS规划逻辑及覆盖结果可视化绘制，README则给出项目结构说明与运行指引。目前已有78人学习关注。读者可借此理解蒙特卡洛树搜索在多机器人协同覆盖中的建模方式、搜索流程与路径生成策略，并直接运行代码观察覆盖效果图，也可在现有框架上修改扩展，实现自定义环境或算法对比实验，适合作为算法入门与项目原型搭建的参考素材。
1. 多机器人覆盖路径规划：为什么蒙特卡洛树搜索值得你花一个周末跑通
一片 50×50 的栅格区域，三台机器人从不同角落出发，要求每格至少被访问一次、总步数尽量短、彼此不撞车——这是区域覆盖路径规划最朴素的描述。传统做法是分区后各跑 A* 或 Boustrophedon 牛耕法，规则清晰但一旦地图有障碍、机器人数量变化，分区边界就得重算，扩展性差。蒙特卡洛树搜索（MCTS）把这个问题转成序贯决策：每台机器人每一步选哪个方向，由 UCB 公式在「探索未走区域」和「利用已知高收益路径」之间权衡，四阶段（选择、扩展、模拟、回溯）天然支持多智能体轮流决策。Python 生态里 numpy 做栅格运算、matplotlib 做覆盖结果可视化，一套代码两三百行就能跑出可复现的对比实验。这篇面向已经会 Python 基础语法、想找一个能写进简历或课程设计的完整项目的读者，从环境配置一路讲到参数调优和可视化出图。
2. 把覆盖问题翻译成 MCTS 能吃的四元组
2.1 状态、动作、奖励、终止条件怎么定义
MCTS 本身是通用搜索框架，能不能用好，全看你怎么把区域覆盖映射成它认识的四个要素。我一般这样定义：
- 状态 s：一个三元组
(coverage_mask, robot_positions, step_count)。coverage_mask是 H×W 的布尔矩阵，True 表示该格已被任一机器人访问过；robot_positions是 N×2 的整数数组，记录每台机器人当前坐标；step_count是全局步数，用来触发终止。 - 动作 a：对当前轮到的机器人，动作空间是上下左右加原地等待共 5 个离散动作。原地等待在多机器人场景里很关键，它让某台机器人可以「让路」，避免两机同时挤进同一格。
- 奖励 r：每走一步，如果新位置是未覆盖格，奖励 +1；如果是已覆盖格，奖励 -0.1；如果撞到障碍或越界，奖励 -1 并原地不动；如果与其他机器人位置冲突，奖励 -1。终止时若覆盖率达标，额外给 +50 的完成奖励。
- 终止条件：覆盖率达到设定阈值（比如 95%）或步数超过上限（比如 3×H×W）。
这套定义的好处是奖励信号密集，MCTS 的模拟阶段不需要走到底就能区分好坏动作。代价是参数多，后面避坑章节会讲怎么调。
2.2 用 UCB 在多机器人轮流决策中做选择
单智能体 MCTS 的选择阶段就是反复套 UCB1：
UCB = Q(s,a)/N(s,a) + c * sqrt(ln(N(s)) / N(s,a))多机器人场景下，每个机器人维护自己的一棵子树，但共享同一个全局状态。轮到机器人 i 决策时，从它的根节点开始，按 UCB 选子节点，直到遇到未完全扩展的节点。这里有个容易翻车的点：如果所有机器人共用一棵树，节点爆炸；如果完全独立建树，机器人之间就失去了协调。常见做法是共享状态、独立建树，但在模拟阶段把所有机器人的动作串起来推演。
import numpy as np import math class MCTSNode: def __init__(self, state, parent=None, action=None): self.state = state # (coverage_mask, positions, step) self.parent = parent self.action = action # 到达本节点的动作 self.children = [] self.visits = 0 self.value = 0.0 self.untried_actions = list(range(5)) # 5 个离散动作 def ucb_score(self, c=1.414): if self.visits == 0: return float('inf') exploit = self.value / self.visits explore = c * math.sqrt(math.log(self.parent.visits) / self.visits) return exploit + explore def best_child(self, c=1.414): return max(self.children, key=lambda n: n.ucb_score(c)) def is_fully_expanded(self): return len(self.untried_actions) == 0ucb_score里的c是探索常数，理论值 √2≈1.414，实际覆盖任务里我通常从 1.0 开始试，地图越大越偏向调高到 1.8 左右，让机器人多去探未覆盖区。best_child只在已扩展的子节点里选，所以调用前必须确认is_fully_expanded()为真，否则要先走扩展逻辑。
2.3 模拟阶段怎么快速估算一条路径的覆盖收益
模拟（rollout）是 MCTS 最耗时的环节。如果每次模拟都随机走到终止，50×50 地图上单次决策可能要几秒。我的做法是限制模拟深度，比如只推演 20 步，用这 20 步内新增的覆盖格数作为收益估计。这叫截断模拟，牺牲一点精度换十倍速度。
def rollout(state, robot_id, depth=20): mask, positions, step = state mask = mask.copy() positions = positions.copy() total_reward = 0.0 for _ in range(depth): action = np.random.randint(0, 5) new_pos, reward, done = apply_action(mask, positions, robot_id, action) positions[robot_id] = new_pos if reward > 0: mask[new_pos[0], new_pos[1]] = True total_reward += reward if done: break return total_rewarddepth=20是我在 50×50 地图上的经验值，地图小可以降到 10，地图大或障碍密集可以升到 30。apply_action需要自己实现，负责边界检查、障碍判断、机器人碰撞检测，返回新位置、即时奖励和是否终止。注意 rollout 里用的是随机策略，不是贪心，这是为了保证 MCTS 的探索多样性，如果你改成贪心，前期收敛快但容易陷入局部最优。
3. 从零搭一个可运行的多机器人覆盖 MCTS
3.1 环境准备与依赖安装
Python 版本建议 3.9 以上，3.8 也能跑但类型提示写法受限。依赖只有三个核心库，不需要 GPU。
python -m venv venv source venv/bin/activate # Windows 用 venv\Scripts\activate pip install numpy matplotlib tqdmnumpy负责栅格矩阵和向量化运算，matplotlib出覆盖热力图和路径图，tqdm给 MCTS 迭代加进度条——别小看这个，MCTS 跑几千次迭代没进度条你会以为程序卡死。如果你用 VSCode，配置好 Python 解释器指向 venv 里的 python，再装个 Pylance，类型提示能帮你少写不少 bug。
3.2 栅格地图与机器人状态初始化
地图用一个二维 numpy 数组表示，0 是自由格，1 是障碍。机器人初始位置手动指定或随机撒在自由格上，但要保证彼此不重叠。
def create_map(height=50, width=50, obstacle_ratio=0.1, seed=42): rng = np.random.default_rng(seed) grid = np.zeros((height, width), dtype=np.int8) num_obstacles = int(height * width * obstacle_ratio) coords = rng.choice(height * width, size=num_obstacles, replace=False) for c in coords: grid[c // width, c % width] = 1 return grid def init_robots(grid, num_robots=3, seed=42): rng = np.random.default_rng(seed) free = np.argwhere(grid == 0) chosen = free[rng.choice(len(free), size=num_robots, replace=False)] return chosen.astype(np.int32)obstacle_ratio=0.1是中等密度，想测试算法鲁棒性可以调到 0.2，但超过 0.25 后自由格可能不连通，覆盖率永远到不了 95%，这时候要么降低阈值要么换地图。seed固定是为了实验可复现，写论文或做对比实验时务必固定。机器人数量建议从 2 到 5 之间试，超过 5 台在 50×50 地图上碰撞惩罚会频繁触发，需要调大等待动作的权重。
3.3 MCTS 主循环：选择、扩展、模拟、回溯
主循环对每台机器人轮流执行一次完整 MCTS，每次限定迭代次数，返回访问次数最多的动作。
def mcts_search(root_state, robot_id, iterations=500, c=1.414, rollout_depth=20): root = MCTSNode(root_state) for _ in range(iterations): node = root # 1. 选择 while node.is_fully_expanded() and node.children: node = node.best_child(c) # 2. 扩展 if node.untried_actions: action = node.untried_actions.pop() new_state, _, _ = apply_action(*node.state, robot_id, action) child = MCTSNode(new_state, parent=node, action=action) node.children.append(child) node = child # 3. 模拟 reward = rollout(node.state, robot_id, depth=rollout_depth) # 4. 回溯 while node is not None: node.visits += 1 node.value += reward node = node.parent return max(root.children, key=lambda n: n.visits).actioniterations=500是单步决策的搜索预算，三台机器人跑 200 步就是 30 万次迭代，在普通笔记本上大约两三分钟。想更快可以降到 200，代价是路径质量下降。apply_action返回的new_state必须是深拷贝，否则所有节点共享同一个 mask 引用，回溯时数据全乱——这是我第一次写的时候踩的最大的坑，调试了两小时才发现。
3.4 覆盖结果可视化：热力图加路径叠加
跑完一轮后，把覆盖次数矩阵画成热力图，再叠加每台机器人的路径折线，一眼就能看出哪片区域被反复扫、哪片是盲区。
import matplotlib.pyplot as plt def visualize(grid, coverage_count, paths, save_path="coverage_result.png"): fig, ax = plt.subplots(figsize=(8, 8)) display = coverage_count.copy().astype(float) display[grid == 1] = np.nan # 障碍格置空 im = ax.imshow(display, cmap="YlOrRd", interpolation="nearest") colors = ["cyan", "lime", "magenta", "white", "orange"] for i, path in enumerate(paths): path = np.array(path) ax.plot(path[:, 1], path[:, 0], color=colors[i % len(colors)], linewidth=1.5, label=f"Robot {i}") ax.legend(loc="upper right") ax.set_title("Multi-Robot Coverage Heatmap") fig.colorbar(im, ax=ax, label="Visit Count") plt.tight_layout() plt.savefig(save_path, dpi=150) plt.show()coverage_count是 H×W 整数矩阵，每访问一次加一。障碍格设为nan后 imshow 会自动留白，比手动画矩形干净。interpolation="nearest"保证每个格子边界清晰，别用默认的 bilinear，否则热力图糊成一片看不出细节。路径颜色循环用五种，超过五台机器人就自己加。保存 dpi 设 150 够用，要放论文里可以提到 300。
4. 参数调优与多机器人协调的避坑清单
4.1 探索常数 c 调大调小分别会发生什么
现象：c 设 0.5 时，机器人前 50 步表现很好，之后反复在已覆盖区打转，覆盖率卡在 70% 上不去。原因：探索项权重太低，UCB 几乎只选历史收益最高的动作，而历史高收益动作集中在开局未覆盖区，后期这些动作收益归零但访问次数分母大，Q 值下降慢，形成惯性。解决：把 c 提到 1.4 以上，或者引入衰减机制，前期 c=1.8 鼓励探索，后期 c=0.8 鼓励利用。我一般直接用固定 1.414，简单省事，效果够用。
4.2 机器人互相堵路导致覆盖率骤降
现象：三台机器人跑到一个窄通道口，两台互相等待，第三台绕远路，总步数比两台机器人还多。原因：碰撞惩罚 -1 和未覆盖奖励 +1 量级接近，MCTS 在模拟时随机策略经常撞车，导致碰撞路径的估值被低估，但真实执行时又不得不撞。解决：把碰撞惩罚调到 -3，同时在动作空间里给「等待」动作一个小的正奖励 +0.05，让让路变成有吸引力的选择。另一个办法是加一个简单的优先级规则，机器人编号小的优先走，编号大的遇到冲突必须等待，这属于工程上的兜底，不优雅但有效。
4.3 模拟深度和迭代次数的性价比拐点
现象：迭代从 200 加到 2000，覆盖率只从 88% 涨到 91%，但耗时翻了十倍。原因：MCTS 的收敛曲线在覆盖任务里通常呈对数形，前 300 次迭代收益最大，之后边际递减。解决：迭代次数设 300 到 500 之间，把省下的时间用来增加 rollout 深度或跑多次取平均。我做过一组对比，500 次迭代加深度 20，和 2000 次迭代加深度 10，覆盖率差不多，但前者快 3 倍。具体拐点跟地图大小有关，建议自己画一条「迭代次数 vs 覆盖率」曲线找。
4.4 覆盖率统计口径不一致导致结果虚高
现象：程序报告覆盖率 98%，但热力图上一片区域明显没去过。原因：统计时把障碍格也算进了分母，或者把机器人初始位置所在格直接标记为已覆盖但没计入访问次数。解决：覆盖率分母只算自由格总数，初始位置格要显式标记 mask 为 True 并计入 coverage_count。另外注意边界情况，机器人原地等待时不应该增加覆盖计数，否则等待动作会刷覆盖率。
4.5 可视化中文乱码与图例遮挡
现象：标题里的中文变成方框，图例盖住了右上角的覆盖热区。原因：matplotlib 默认字体不含中文，图例位置固定。解决：设置plt.rcParams["font.sans-serif"] = ["SimHei"]和plt.rcParams["axes.unicode_minus"] = False，Windows 下 SimHei 一般都有，Linux 可以换 WenQuanYi。图例位置改成loc="lower right"或bbox_to_anchor=(1.02, 1)挪到图外，别让它压住数据。
5. 让结果更可信：对比实验设计与收敛曲线
跑通单次实验只是起点，要让人信服你的 MCTS 方案确实有用，得做对比。我一般设三组基线：随机游走、贪心最近未覆盖、以及经典牛耕法分区。评价指标四个：覆盖率、总步数、重复访问率、决策耗时。每组跑 10 个不同随机种子取平均，画带误差棒的柱状图。
收敛可视化是另一个加分项。记录每次迭代后根节点最佳动作的 Q 值，画一条 Q 值随迭代变化的曲线，能直观展示 MCTS 多久进入稳定状态。
def plot_convergence(q_history, save_path="convergence.png"): plt.figure(figsize=(7, 4)) plt.plot(q_history, color="steelblue", linewidth=1.2) plt.xlabel("Iteration") plt.ylabel("Best Action Q Value") plt.title("MCTS Convergence on Coverage Task") plt.grid(alpha=0.3) plt.tight_layout() plt.savefig(save_path, dpi=150) plt.show()q_history在每个迭代结束后追加root.best_child().value / root.best_child().visits。如果曲线在 200 次迭代内就平了，说明迭代预算可以砍；如果一直震荡，要么 c 太大，要么奖励函数噪声太高，需要检查碰撞惩罚是否频繁触发。
一个具体技巧：把多机器人 MCTS 的决策过程录成帧序列，用 matplotlib 的FuncAnimation导出 gif，展示机器人如何逐步铺满地图。这个可视化在答辩或汇报时比静态图有说服力得多。我自己的习惯是每次改完奖励函数先跑 3 个种子看覆盖率方差，方差大于 5% 就说明参数不稳，不急着调迭代次数，先回去检查动作空间和碰撞逻辑。希望帮到你。
本文还有配套的精品资源，点击获取
