多机器人覆盖路径规划：蒙特卡洛树搜索实战指南

简介本资源面向计算机、人工智能、自动化等专业的在校学生与研究人员提供一套基于蒙特卡洛树搜索算法实现多机器人区域覆盖路径规划的完整项目源码可用于课程设计、毕业设计或算法学习进阶。压缩包共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 的选择阶段就是反复套 UCB1UCB 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, parentNone, actionNone): 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, c1.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, c1.414): return max(self.children, keylambda 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, depth20): 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_rewarddepth20是我在 50×50 地图上的经验值地图小可以降到 10地图大或障碍密集可以升到 30。apply_action需要自己实现负责边界检查、障碍判断、机器人碰撞检测返回新位置、即时奖励和是否终止。注意 rollout 里用的是随机策略不是贪心这是为了保证 MCTS 的探索多样性如果你改成贪心前期收敛快但容易陷入局部最优。3. 从零搭一个可运行的多机器人覆盖 MCTS3.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(height50, width50, obstacle_ratio0.1, seed42): rng np.random.default_rng(seed) grid np.zeros((height, width), dtypenp.int8) num_obstacles int(height * width * obstacle_ratio) coords rng.choice(height * width, sizenum_obstacles, replaceFalse) for c in coords: grid[c // width, c % width] 1 return grid def init_robots(grid, num_robots3, seed42): rng np.random.default_rng(seed) free np.argwhere(grid 0) chosen free[rng.choice(len(free), sizenum_robots, replaceFalse)] return chosen.astype(np.int32)obstacle_ratio0.1是中等密度想测试算法鲁棒性可以调到 0.2但超过 0.25 后自由格可能不连通覆盖率永远到不了 95%这时候要么降低阈值要么换地图。seed固定是为了实验可复现写论文或做对比实验时务必固定。机器人数量建议从 2 到 5 之间试超过 5 台在 50×50 地图上碰撞惩罚会频繁触发需要调大等待动作的权重。3.3 MCTS 主循环选择、扩展、模拟、回溯主循环对每台机器人轮流执行一次完整 MCTS每次限定迭代次数返回访问次数最多的动作。def mcts_search(root_state, robot_id, iterations500, c1.414, rollout_depth20): 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, parentnode, actionaction) node.children.append(child) node child # 3. 模拟 reward rollout(node.state, robot_id, depthrollout_depth) # 4. 回溯 while node is not None: node.visits 1 node.value reward node node.parent return max(root.children, keylambda n: n.visits).actioniterations500是单步决策的搜索预算三台机器人跑 200 步就是 30 万次迭代在普通笔记本上大约两三分钟。想更快可以降到 200代价是路径质量下降。apply_action返回的new_state必须是深拷贝否则所有节点共享同一个 mask 引用回溯时数据全乱——这是我第一次写的时候踩的最大的坑调试了两小时才发现。3.4 覆盖结果可视化热力图加路径叠加跑完一轮后把覆盖次数矩阵画成热力图再叠加每台机器人的路径折线一眼就能看出哪片区域被反复扫、哪片是盲区。import matplotlib.pyplot as plt def visualize(grid, coverage_count, paths, save_pathcoverage_result.png): fig, ax plt.subplots(figsize(8, 8)) display coverage_count.copy().astype(float) display[grid 1] np.nan # 障碍格置空 im ax.imshow(display, cmapYlOrRd, interpolationnearest) colors [cyan, lime, magenta, white, orange] for i, path in enumerate(paths): path np.array(path) ax.plot(path[:, 1], path[:, 0], colorcolors[i % len(colors)], linewidth1.5, labelfRobot {i}) ax.legend(locupper right) ax.set_title(Multi-Robot Coverage Heatmap) fig.colorbar(im, axax, labelVisit Count) plt.tight_layout() plt.savefig(save_path, dpi150) plt.show()coverage_count是 H×W 整数矩阵每访问一次加一。障碍格设为nan后 imshow 会自动留白比手动画矩形干净。interpolationnearest保证每个格子边界清晰别用默认的 bilinear否则热力图糊成一片看不出细节。路径颜色循环用五种超过五台机器人就自己加。保存 dpi 设 150 够用要放论文里可以提到 300。4. 参数调优与多机器人协调的避坑清单4.1 探索常数 c 调大调小分别会发生什么现象c 设 0.5 时机器人前 50 步表现很好之后反复在已覆盖区打转覆盖率卡在 70% 上不去。原因探索项权重太低UCB 几乎只选历史收益最高的动作而历史高收益动作集中在开局未覆盖区后期这些动作收益归零但访问次数分母大Q 值下降慢形成惯性。解决把 c 提到 1.4 以上或者引入衰减机制前期 c1.8 鼓励探索后期 c0.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] FalseWindows 下 SimHei 一般都有Linux 可以换 WenQuanYi。图例位置改成loclower right或bbox_to_anchor(1.02, 1)挪到图外别让它压住数据。5. 让结果更可信对比实验设计与收敛曲线跑通单次实验只是起点要让人信服你的 MCTS 方案确实有用得做对比。我一般设三组基线随机游走、贪心最近未覆盖、以及经典牛耕法分区。评价指标四个覆盖率、总步数、重复访问率、决策耗时。每组跑 10 个不同随机种子取平均画带误差棒的柱状图。收敛可视化是另一个加分项。记录每次迭代后根节点最佳动作的 Q 值画一条 Q 值随迭代变化的曲线能直观展示 MCTS 多久进入稳定状态。def plot_convergence(q_history, save_pathconvergence.png): plt.figure(figsize(7, 4)) plt.plot(q_history, colorsteelblue, linewidth1.2) plt.xlabel(Iteration) plt.ylabel(Best Action Q Value) plt.title(MCTS Convergence on Coverage Task) plt.grid(alpha0.3) plt.tight_layout() plt.savefig(save_path, dpi150) plt.show()q_history在每个迭代结束后追加root.best_child().value / root.best_child().visits。如果曲线在 200 次迭代内就平了说明迭代预算可以砍如果一直震荡要么 c 太大要么奖励函数噪声太高需要检查碰撞惩罚是否频繁触发。一个具体技巧把多机器人 MCTS 的决策过程录成帧序列用 matplotlib 的FuncAnimation导出 gif展示机器人如何逐步铺满地图。这个可视化在答辩或汇报时比静态图有说服力得多。我自己的习惯是每次改完奖励函数先跑 3 个种子看覆盖率方差方差大于 5% 就说明参数不稳不急着调迭代次数先回去检查动作空间和碰撞逻辑。希望帮到你。本文还有配套的精品资源点击获取