简介这是一份基于 Python 与蒙特卡洛树搜索MCTS的多机器人区域覆盖路径规划实现包含核心算法与可视化展示适合学习机器人路径规划、多机器人协作或 MCTS 算法的开发者及研究人员参考。资源压缩包共 6 个文件以 4 个 Python 脚本为主辅以 LICENSE 与 README 说明整体大小仅 19KB结构简洁便于快速阅读和运行实验。目前已有 1102 人学习/下载具备一定参考价值。代码中体现了 MCTS 通过随机采样逐步优化路径在多机器人场景下规划安全高效的覆盖路线并考虑机器人之间的任务协调与避碰同时提供地图绘制与结果可视化功能帮助直观理解搜索过程和最终覆盖效果。对于想快速上手 MCTS 路径规划或需要课程设计/项目雏形的读者这份资源能提供较完整的 Python 示例和算法流程参考。1. 蒙特卡洛树搜索算法与多机器人区域覆盖路径规划为什么这个组合能治我的巡检漏扫病多机器人区域覆盖路径规划CPP在仓储盘点、智能扫地、农业巡检里是个出了名的“听着简单、落地想哭”的问题给你一张栅格地图、几台机器人怎么让它们在规定时间内把地图全部扫完、重复率最低、机器人之间还互不打架我最早尝试用羊群算法和遗传算法做离线求解直到在一次巡检项目里把蒙特卡洛树搜索算法MCTS搬进在线规划模块才发现这套组合拳比我想象中可靠得多。这篇文章我会用可复现的 Python 代码把 MCTS 拆开揉碎落到多机器人区域覆盖场景里并把结果可视化出来。同时把跑通它最常遇到的几个坑也一并交代清楚希望能帮你少走两天弯路。2. 多机器人区域覆盖为什么需要蒙特卡洛树搜索状态建模与选型对比2.1 先从栅格地图说起状态空间和动作空间怎样定义才能让 MCTS 跑起来MCTS 本质上是个黑盒优化器它不关心你的机器人底盘是差速还是麦轮只关心你的状态转移函数是否确定或带概率。标准做法是先把工作空间栅格化0 表示自由区域1 表示障碍物2 表示已被机器人访问过的区域。那么一个状态就是所有栅格子区域覆盖情况的集合你可以直接用 NumPy 的二维数组来维护后续做可视化和碰撞检测都会很高效。动作空间则定义为每台机器人的决策方向。因为机器人之间存在物理约束多智能体动作空间通常用联合动作描述也就是每个机器人各自决策一个方向组合成一个 N 维向量。这里有个细节多机器人系统的状态空间比单机器人复杂得多因为机器人之间互相影响一台机器人移动后另一台机器人的路径就会被压缩。因此我们在定义状态的时候必须把“所有机器人当前各自的坐标”和“全局访问图”一并保存否则模拟阶段的回报函数会失真。import numpy as np import math import random from collections import deque class GridMap: def __init__(self, width, height): self.width width self.height height # 0空闲, 1障碍, 2已访问 self.grid np.zeros((height, width), dtypenp.int8) def set_obstacle(self, x, y): self.grid[y, x] 1 def in_bounds(self, x, y): return 0 x self.width and 0 y self.height def is_free(self, x, y): return self.in_bounds(x, y) and self.grid[y, x] 0 def mark_visited(self, x, y): if self.in_bounds(x, y) and self.grid[y, x] 0: self.grid[y, x] 2逻辑说明GridMap类里的is_free方法排除了边界和障碍物这是整个模拟阶段的命门。如果 MCTS 选择了四个方向上都无路可走的动作我们要返回一个“完成度低”的奖励而不是让代码直接抛异常。另外mark_visited只允许把空闲区域标记为已访问防止机器人把障碍物也“访问”了一遍。参数说明地图的宽和高直接影响搜索空间。常见做法是先用十厘米分辨率栅格化真实环境比如 20 米乘以 20 米的空间栅格化成 200x200 的地图。但 MCTS 在这种规模下跑起来极慢所以工程上一般会先压缩分辨率或者用占据栅格地图的稀疏表示来加速。这个后面也会提到。2.2 MCTS 与遗传算法、强化学习的关键差异为什么在线规划适合覆盖任务传统上大家一听到多机器人覆盖率优化就会想到遗传算法GA。但遗传算法很难塞进实时的调度系统因为它每一轮都要重新计算整个群体的适应度且对环境变化响应很慢。强化学习则需要大量训练数据并且地图一旦变化泛化能力往往要打折扣。蒙特卡洛树搜索MCTS则是一种在线规划方案它不需要预训练只需要一个模拟器和一个评分函数就能够随着环境状态的变化实时规划出下一步动作。它天然适合“单一 episode 内快速响应”的任务也适合我们说的动态区域覆盖。具体到多机器人的区域覆盖路径规划MCTS 的随机模拟过程能快速探索到人类直觉容易忽略的宏观调动策略。比如当两台机器人距离过近时MCTS 会通过模拟期的稀疏性奖励让其中一台主动绕远路去补充覆盖空白区域。这种“绕路”决策在固定策略或者人工设定优先级时很难设定好但 MCTS 可以通过大量蒙特卡罗模拟来评估长线收益。2.3 为什么不用栅格地图上的 A* 或贪心算法直接扫这个问题几乎每次分享都会被问。A* 路径规划是点对点的最短路径算法它不会去考虑整体覆盖规划而贪心算法虽然快但容易陷入局部最优比如被 U 型障碍物困住然后在一小块区域里反复扫。MCTS 的优势在于它通过树搜索和回溯机制能够在模拟阶段看到“被困住”的坏结果从而在前期就避开这种动作。换句话说MCTS 比贪心多了一个“眼光”它看得到几步甚至几十步之后的回报变化。3. 用 Python 实现多机器人蒙特卡洛树搜索可复现的核心代码与参数说明3.1 最小工程骨架节点定义和地图边界条件我们先定义一个 MCTS 节点类保存状态快照、父节点指针、子节点列表以及累计访问次数与累计回报。注意这里我说的“状态”是一个广义概念它包含了地图快照和各机器人位置。但是如果你直接从根节点深拷贝整个地图到每个子节点内存很快就会爆炸。所以常见做法是节点里只保存“动作序列”和“当前评估值”回溯时再去更新全局地图而不是把地图整个存在每个节点里。我给的例子为了让你更容易理解先用轻量级状态来表示。class MCTSNode: def __init__(self, state, parentNone): self.state state self.parent parent self.children [] self.visits 0 self.value 0.0 class MultiRobotMCTS: def __init__(self, grid: GridMap, robot_positions, c_p1.414, simulate_steps100): self.grid grid self.robots robot_positions self.c_p c_p self.simulate_steps simulate_steps self.directions [(0, 1), (0, -1), (1, 0), (-1, 0), (0, 0)] def _ucb(self, node): if node.visits 0: return float(inf) # UCB1 公式平衡利用与探索 exploit node.value / node.visits explore self.c_p * math.sqrt(math.log(node.parent.visits) / node.visits) return exploit explore def select(self, node): while len(node.children) 0: node max(node.children, keyself._ucb) return node def expand(self, node): # 对每个机器人尝试 5 个动作并剪掉非法动作 free_actions [] for robot_id, pos in enumerate(self.robots): for dx, dy in self.directions: nx, ny pos[0] dx, pos[1] dy if self.grid.is_free(nx, ny) or self.grid.in_bounds(nx, ny): free_actions.append((robot_id, dx, dy)) if not free_actions: return node # 每次扩展只增加一个新动作控制分支因子 action random.choice(free_actions) child MCTSNode(node.state, parentnode) node.children.append(child) return child def simulate(self, node): # 随机模拟但偏向未访问的邻近区域 total_visited np.sum(self.grid.grid 2) for _ in range(self.simulate_steps): moved False for robot_id, pos in enumerate(self.robots): random.shuffle(self.directions) for dx, dy in self.directions: nx, ny pos[0] dx, pos[1] dy if self.grid.is_free(nx, ny): self.robots[robot_id] (nx, ny) self.grid.mark_visited(nx, ny) moved True break if not moved: break covered np.sum(self.grid.grid 2) / (np.sum(self.grid.grid 0) - np.sum(self.grid.grid 1)) return covered def backpropagate(self, node, reward): while node is not None: node.visits 1 node.value reward node node.parent逻辑说明这里面simulate函数是最关键的部分。我并没有把每个机器人遍历到彻底而是在每个模拟步里对机器人列表做一次随机动作选择直到所有机器人周围都是障碍物才终止。这种模拟方式能让覆盖率稳定爬升。covered是当前地图里“已访问格子数”除以“空闲格子数”得到的连续值作为这一轮模拟的回报。回溯阶段把回报逐层向上累加后续的select就能依据出一棵“哪条分支更可能得到高覆盖率”的搜索树。参数说明c_p我这边经验是 1.414 在黑白棋里很稳但在多机器人覆盖上建议放大到 10 到 50。因为覆盖回报非常稀疏如果探索因子太小树搜索会一直沿着一条已知路径反复利用导致机器人卡在某个局部区域。simulate_steps是模拟步数100 步只是起步值遇到 100x100 大地图时请调大到 1000 以上。3.2 多机协作的冲突处理与死锁避免为什么不能直接共享全局网格我见过很多新手直接把 MCTS 用在全局网格上共享状态结果就是几台机器人在同一棵树上打架因为模拟阶段移动 A 机器人的同时B 机器人的起始位置已经在上一轮被改变了但树节点的状态没有同步更新。这里我推荐的工程做法是每台机器人单独维护一棵 MCTS模拟阶段在一个私有的“模拟环境副本”上并行跑。每次决策期间机器人之间通过共享内存、Redis 或 socket 同步一次“全局已覆盖图”。这样两个机器人看到的地图是同一个但它们各自对未来的推演互不干扰。如果你用 Python 实现并行最简单的方法是多线程配合 GIL 其实是绕不过去更好的办法是用 多进程multiprocessing 并给每个子进程传入一份地图副本。覆盖结果通过 Redis 客户端写回主进程这样会比线程安全得多也更容易做分布式扩展。在做真机部署时这个模式可以直接套到 ROS 节点通信上每个机器人节点跑一个独立的 MCTS 求解器。3.3 收敛判定与覆盖率统计什么样的覆盖率才算扫完在描述“覆盖完成”之前我们先确定“覆盖率”的量化方法。一般用已覆盖格子数 / 空闲格子总数作为核心指标但不同的任务权重并不一样巡检任务会把漏扫率看得比重复覆盖率更重农业测绘则更关心重叠是否过高。你可以把统计信息封装在CoverageTracker里让它实时计算总体覆盖率和重复扫描比例。class CoverageTracker: def __init__(self, grid: GridMap): self.total_free int(np.sum(grid.grid 0)) self.revisit_count 0 def update(self, grid: GridMap): currently_visited int(np.sum(grid.grid 2)) coverage_ratio currently_visited / self.total_free return coverage_ratio def compute_revisit_ratio(self, grid: GridMap, visited_once_mask: np.ndarray): revisit_mask (grid.grid 2) visited_once_mask return int(np.sum(revisit_mask)) / self.total_free if self.total_free 0 else 0这里的逻辑说明update就是算一个简单的比例而compute_revisit_ratio则需要你额外传入一张visited_once_mask表示每个格子是否只被访问过一次。如果重复覆盖率太高说明 MCTS 的奖励设计偏向“原地徘徊”了需要调大路径不重复的惩罚项。4. 把覆盖结果可视化出来Matplotlib 热力图、路径轨迹与动态刷新4.1 生成静态覆盖热力图把二维数组变成一眼能看懂的颜色拿到 grid 里 0、1、2 的二维数组后我用 Matplotlib 的imshow和cmap做一步转换。具体做法是把 grid 涂成一幅 RGB 彩色图障碍物用黑灰色未访问区域用浅蓝色已访问区域用绿色。这样可以非常直观地看到覆盖效果有没有漏扫、有没有过度重复扫一目了然。import matplotlib.pyplot as plt import matplotlib.patches as mpatches def draw_coverage(grid: GridMap, robots): fig, ax plt.subplots(figsize(10, 10)) # 将整数网格映射为 RGB 颜色 display np.zeros((grid.height, grid.width, 3)) for y in range(grid.height): for x in range(grid.width): if grid.grid[y, x] 1: display[y, x] [0.1, 0.1, 0.1] # 障碍 elif grid.grid[y, x] 2: display[y, x] [0.2, 0.6, 0.2] # 已覆盖 else: display[y, x] [0.2, 0.6, 0.9] # 空闲 ax.imshow(display, originlower) # 画机器人当前位置 for i, (x, y) in enumerate(robots): ax.plot(x, y, r*, markersize15) # 绘制图例 legend_patches [ mpatches.Patch(color#1a1a1a, labelObstacle), mpatches.Patch(color#33aa33, labelVisited), mpatches.Patch(color#3399e6, labelFree), mpatches.Patch(colorred, labelRobot) ] ax.legend(handleslegend_patches, locupper right) ax.set_title(Multi-Robot Coverage Path Planning with MCTS) return fig, ax逻辑说明这段代码本质是数据可视化里的“伪彩色映射”只不过我手动为每个格子指定了 RGB 颜色。这样做的好处是你可以任意定义颜色的含义比如把“重复覆盖率超过 3 次的格子”标记为黄色从而快速暴露过度重复覆盖的区域。originlower指的是让地图的 y 轴从下往上增长更符合笛卡尔坐标系直觉。参数说明markersize控制机器人星标大小一般在巡检图上用 15 到 20 就足够醒目。如果你要出论文图可以用fig.savefig(coverage.png, dpi300)保存高分辨率图。4.2 动态过程可视化与 GIF 导出一张图看清 MCTS 搜索路径推进过程只看最终覆盖热力图你很难判断 MCTS 在中间步骤是否走进了死胡同。因此我一般保留每轮模拟后的地图状态每隔 10 个迭代步保存一帧图像最后用 Pillow 合成为 GIF或者直接在笔记本里用FuncAnimation播放。from PIL import Image import io def export_progress_gif(grid: GridMap, robots, frames): images [] for frame in frames: fig, ax draw_coverage(frame[grid], frame[robots]) buf io.BytesIO() fig.savefig(buf, formatpng) buf.seek(0) images.append(Image.open(buf).copy()) plt.close(fig) images[0].save(mcts_coverage_progress.gif, save_allTrue, append_imagesimages[1:], duration200, loop0)逻辑说明动态可视化对调试帮助很大因为一旦发现某个阶段所有机器人都挤在一个角落里你马上就能知道是模拟策略设置出了问题。duration200表示每帧显示 200 毫秒播放效果柔和。如果某些帧出现空白多半是画布或者缓冲没有正确关闭记得在保存完图像后调用plt.close(fig)释放内存。5. 多机器人区域覆盖里蒙特卡洛树搜索的 5 个常见翻车点现象、原因与解决5.1 现象模拟几十轮覆盖率就是上不去机器人总在障碍物边缘打转原因模拟策略太随机完全没有考虑未访问区域的分布。MCTS 的模拟阶段如果只是纯随机游走那它把大量采样时间浪费在已经覆盖过的区域和障碍物墙上。解决把模拟阶段的纯随机采样改为“偏向未访问邻居”的加权采样。具体可以统计机器人当前位置上下左右四个邻格里有多少个未访问格然后给这些方向更高的被选中概率。我刚才代码里的random.shuffle是最低成本的实现进阶可以改成按权重采样。def weighted_choice(self, pos): candidates [] weights [] for dx, dy in self.directions: nx, ny pos[0] dx, pos[1] dy if self.grid.is_free(nx, ny): candidates.append((dx, dy)) # 简单启发式未访问过 相对开放区域加分 weight 1.0 if (nx, ny) not in self.visited_points: weight 5.0 weights.append(weight) if not candidates: return (0, 0) return random.choices(candidates, weightsweights)[0]5.2 现象多机器人相互拥挤、团队串行化明明可以并行覆盖却变成排队扫原因这几乎都是因为模拟阶段没有做机器人之间的空间约束惩罚。如果两台机器人靠得太近它们的下一步动作空间会严重重叠导致总体覆盖率上升变慢。解决在simulate的每一步回报里加入稀疏性奖励。计算两两机器人之间的欧氏距离如果小于设定阈值比如 5 个格子就在回报上扣 0.2 分。这样做会让 MCTS 主动学习保持间距。5.3 现象UCB 公式中的平衡参数非常难调不是太小就是太大原因math.log和visits之间的量纲导致惩罚项和奖励项不在一个数量级。奖励如果是覆盖率也就是 0 到 1 之间那么 UCB 的探讨项经常会占到 0.2 以上能够被搜索发现但如果奖励是“绝对覆盖格子数”exploit 是几千explore 如果还用 1 开头搜索就纯粹走向了利用。解决把所有回报都归一化到 0 到 1 的连续区间并把c_p初始按sqrt(2) * 最大回报估算最大回报是 1那么c_p先设 1.414然后观察覆盖率曲线若长时间不变则调大到 10。5.4 现象地图里存在较长走廊或凹型障碍时MCTS 规划路线不完整有漏扫原因MCTS 本身并不理解区域单元分解它看不到“这个长走廊必须从一头走到另一头才能不漏”。在没有强先验的情况下树搜索很容易在走廊出口附近反复徘徊无法下定决心冲出去。解决在地图预处理阶段先把栅格地图做连通域分解。每个连通区域单独跑一遍 MCTS区域之间的转移顺序再用一个简单的旅行商问题模型来规划。这样能大幅减少搜索空间也顺带解决了漏扫问题。5.5 现象内存爆炸Python 进程跑一会儿就被 OOM kill 掉原因有些方案把每个状态都完整深拷贝到节点里。假如你的地图是 200x200一棵树存 5 万个节点就要存 20 亿个格子不炸才怪。解决节点只保存增量动作和父节点引用回溯时再重建状态。或者直接按时序滚动更新每迭代 100 次就释放掉数据结构里不再使用的深分支节点可以有效控制内存增长。6. 参数调优与工程化落地从验证算法到技术改造的最后一公里如果你想让这套方案跑在真机系统里我的建议是先把 MCTS 的回报函数拆成三层覆盖率、平均移动距离、重叠率。覆盖率解决“是否扫全”平均移动距离解决“是否高效”重叠率解决“是否做了无用功”。只有权重分配合理树搜索才能规划出既省时又不漏扫的路线。另外一个容易忽略的坑是覆盖率指标不能只看最终结果要看覆盖率收敛曲线。我踩过最大的坑就是为了让最终覆盖率达到 98%把simulate_steps拉到几千结果每次模拟都要两秒钟MCTS 的迭代次数反而变少整体规划时间反而更长。后来我改用早停机制当覆盖率在 50 轮迭代内提升不超过 0.5% 时就强制结束搜索接受当前的覆盖率结果。这样可以有效避免后期无用搜索耗能。在真机部署时你不需要真的在每个机器人上跑 Python 脚本常见的做法是把这个算法跑在 IPC 工控机里通过 ROS 的move_base接口把 MCTS 给出来的路径点发送给底盘。如果追求更实时也可以把地图分辨率降低到 0.5 米每格这样单次规划时间能压到 200 毫秒以内。我自己的习惯是先跑一个小地图快速观察覆盖率曲线的上升斜率斜率变平就调大c_p或者更换模拟策略的权重。这套逻辑我用了很长时间稳定度相当不错。希望帮到你。本文还有配套的精品资源点击获取
简介这是一份基于 Python 与蒙特卡洛树搜索MCTS的多机器人区域覆盖路径规划实现包含核心算法与可视化展示适合学习机器人路径规划、多机器人协作或 MCTS 算法的开发者及研究人员参考。资源压缩包共 6 个文件以 4 个 Python 脚本为主辅以 LICENSE 与 README 说明整体大小仅 19KB结构简洁便于快速阅读和运行实验。目前已有 1102 人学习/下载具备一定参考价值。代码中体现了 MCTS 通过随机采样逐步优化路径在多机器人场景下规划安全高效的覆盖路线并考虑机器人之间的任务协调与避碰同时提供地图绘制与结果可视化功能帮助直观理解搜索过程和最终覆盖效果。对于想快速上手 MCTS 路径规划或需要课程设计/项目雏形的读者这份资源能提供较完整的 Python 示例和算法流程参考。1. 蒙特卡洛树搜索算法与多机器人区域覆盖路径规划为什么这个组合能治我的巡检漏扫病多机器人区域覆盖路径规划CPP在仓储盘点、智能扫地、农业巡检里是个出了名的“听着简单、落地想哭”的问题给你一张栅格地图、几台机器人怎么让它们在规定时间内把地图全部扫完、重复率最低、机器人之间还互不打架我最早尝试用羊群算法和遗传算法做离线求解直到在一次巡检项目里把蒙特卡洛树搜索算法MCTS搬进在线规划模块才发现这套组合拳比我想象中可靠得多。这篇文章我会用可复现的 Python 代码把 MCTS 拆开揉碎落到多机器人区域覆盖场景里并把结果可视化出来。同时把跑通它最常遇到的几个坑也一并交代清楚希望能帮你少走两天弯路。2. 多机器人区域覆盖为什么需要蒙特卡洛树搜索状态建模与选型对比2.1 先从栅格地图说起状态空间和动作空间怎样定义才能让 MCTS 跑起来MCTS 本质上是个黑盒优化器它不关心你的机器人底盘是差速还是麦轮只关心你的状态转移函数是否确定或带概率。标准做法是先把工作空间栅格化0 表示自由区域1 表示障碍物2 表示已被机器人访问过的区域。那么一个状态就是所有栅格子区域覆盖情况的集合你可以直接用 NumPy 的二维数组来维护后续做可视化和碰撞检测都会很高效。动作空间则定义为每台机器人的决策方向。因为机器人之间存在物理约束多智能体动作空间通常用联合动作描述也就是每个机器人各自决策一个方向组合成一个 N 维向量。这里有个细节多机器人系统的状态空间比单机器人复杂得多因为机器人之间互相影响一台机器人移动后另一台机器人的路径就会被压缩。因此我们在定义状态的时候必须把“所有机器人当前各自的坐标”和“全局访问图”一并保存否则模拟阶段的回报函数会失真。import numpy as np import math import random from collections import deque class GridMap: def __init__(self, width, height): self.width width self.height height # 0空闲, 1障碍, 2已访问 self.grid np.zeros((height, width), dtypenp.int8) def set_obstacle(self, x, y): self.grid[y, x] 1 def in_bounds(self, x, y): return 0 x self.width and 0 y self.height def is_free(self, x, y): return self.in_bounds(x, y) and self.grid[y, x] 0 def mark_visited(self, x, y): if self.in_bounds(x, y) and self.grid[y, x] 0: self.grid[y, x] 2逻辑说明GridMap类里的is_free方法排除了边界和障碍物这是整个模拟阶段的命门。如果 MCTS 选择了四个方向上都无路可走的动作我们要返回一个“完成度低”的奖励而不是让代码直接抛异常。另外mark_visited只允许把空闲区域标记为已访问防止机器人把障碍物也“访问”了一遍。参数说明地图的宽和高直接影响搜索空间。常见做法是先用十厘米分辨率栅格化真实环境比如 20 米乘以 20 米的空间栅格化成 200x200 的地图。但 MCTS 在这种规模下跑起来极慢所以工程上一般会先压缩分辨率或者用占据栅格地图的稀疏表示来加速。这个后面也会提到。2.2 MCTS 与遗传算法、强化学习的关键差异为什么在线规划适合覆盖任务传统上大家一听到多机器人覆盖率优化就会想到遗传算法GA。但遗传算法很难塞进实时的调度系统因为它每一轮都要重新计算整个群体的适应度且对环境变化响应很慢。强化学习则需要大量训练数据并且地图一旦变化泛化能力往往要打折扣。蒙特卡洛树搜索MCTS则是一种在线规划方案它不需要预训练只需要一个模拟器和一个评分函数就能够随着环境状态的变化实时规划出下一步动作。它天然适合“单一 episode 内快速响应”的任务也适合我们说的动态区域覆盖。具体到多机器人的区域覆盖路径规划MCTS 的随机模拟过程能快速探索到人类直觉容易忽略的宏观调动策略。比如当两台机器人距离过近时MCTS 会通过模拟期的稀疏性奖励让其中一台主动绕远路去补充覆盖空白区域。这种“绕路”决策在固定策略或者人工设定优先级时很难设定好但 MCTS 可以通过大量蒙特卡罗模拟来评估长线收益。2.3 为什么不用栅格地图上的 A* 或贪心算法直接扫这个问题几乎每次分享都会被问。A* 路径规划是点对点的最短路径算法它不会去考虑整体覆盖规划而贪心算法虽然快但容易陷入局部最优比如被 U 型障碍物困住然后在一小块区域里反复扫。MCTS 的优势在于它通过树搜索和回溯机制能够在模拟阶段看到“被困住”的坏结果从而在前期就避开这种动作。换句话说MCTS 比贪心多了一个“眼光”它看得到几步甚至几十步之后的回报变化。3. 用 Python 实现多机器人蒙特卡洛树搜索可复现的核心代码与参数说明3.1 最小工程骨架节点定义和地图边界条件我们先定义一个 MCTS 节点类保存状态快照、父节点指针、子节点列表以及累计访问次数与累计回报。注意这里我说的“状态”是一个广义概念它包含了地图快照和各机器人位置。但是如果你直接从根节点深拷贝整个地图到每个子节点内存很快就会爆炸。所以常见做法是节点里只保存“动作序列”和“当前评估值”回溯时再去更新全局地图而不是把地图整个存在每个节点里。我给的例子为了让你更容易理解先用轻量级状态来表示。class MCTSNode: def __init__(self, state, parentNone): self.state state self.parent parent self.children [] self.visits 0 self.value 0.0 class MultiRobotMCTS: def __init__(self, grid: GridMap, robot_positions, c_p1.414, simulate_steps100): self.grid grid self.robots robot_positions self.c_p c_p self.simulate_steps simulate_steps self.directions [(0, 1), (0, -1), (1, 0), (-1, 0), (0, 0)] def _ucb(self, node): if node.visits 0: return float(inf) # UCB1 公式平衡利用与探索 exploit node.value / node.visits explore self.c_p * math.sqrt(math.log(node.parent.visits) / node.visits) return exploit explore def select(self, node): while len(node.children) 0: node max(node.children, keyself._ucb) return node def expand(self, node): # 对每个机器人尝试 5 个动作并剪掉非法动作 free_actions [] for robot_id, pos in enumerate(self.robots): for dx, dy in self.directions: nx, ny pos[0] dx, pos[1] dy if self.grid.is_free(nx, ny) or self.grid.in_bounds(nx, ny): free_actions.append((robot_id, dx, dy)) if not free_actions: return node # 每次扩展只增加一个新动作控制分支因子 action random.choice(free_actions) child MCTSNode(node.state, parentnode) node.children.append(child) return child def simulate(self, node): # 随机模拟但偏向未访问的邻近区域 total_visited np.sum(self.grid.grid 2) for _ in range(self.simulate_steps): moved False for robot_id, pos in enumerate(self.robots): random.shuffle(self.directions) for dx, dy in self.directions: nx, ny pos[0] dx, pos[1] dy if self.grid.is_free(nx, ny): self.robots[robot_id] (nx, ny) self.grid.mark_visited(nx, ny) moved True break if not moved: break covered np.sum(self.grid.grid 2) / (np.sum(self.grid.grid 0) - np.sum(self.grid.grid 1)) return covered def backpropagate(self, node, reward): while node is not None: node.visits 1 node.value reward node node.parent逻辑说明这里面simulate函数是最关键的部分。我并没有把每个机器人遍历到彻底而是在每个模拟步里对机器人列表做一次随机动作选择直到所有机器人周围都是障碍物才终止。这种模拟方式能让覆盖率稳定爬升。covered是当前地图里“已访问格子数”除以“空闲格子数”得到的连续值作为这一轮模拟的回报。回溯阶段把回报逐层向上累加后续的select就能依据出一棵“哪条分支更可能得到高覆盖率”的搜索树。参数说明c_p我这边经验是 1.414 在黑白棋里很稳但在多机器人覆盖上建议放大到 10 到 50。因为覆盖回报非常稀疏如果探索因子太小树搜索会一直沿着一条已知路径反复利用导致机器人卡在某个局部区域。simulate_steps是模拟步数100 步只是起步值遇到 100x100 大地图时请调大到 1000 以上。3.2 多机协作的冲突处理与死锁避免为什么不能直接共享全局网格我见过很多新手直接把 MCTS 用在全局网格上共享状态结果就是几台机器人在同一棵树上打架因为模拟阶段移动 A 机器人的同时B 机器人的起始位置已经在上一轮被改变了但树节点的状态没有同步更新。这里我推荐的工程做法是每台机器人单独维护一棵 MCTS模拟阶段在一个私有的“模拟环境副本”上并行跑。每次决策期间机器人之间通过共享内存、Redis 或 socket 同步一次“全局已覆盖图”。这样两个机器人看到的地图是同一个但它们各自对未来的推演互不干扰。如果你用 Python 实现并行最简单的方法是多线程配合 GIL 其实是绕不过去更好的办法是用 多进程multiprocessing 并给每个子进程传入一份地图副本。覆盖结果通过 Redis 客户端写回主进程这样会比线程安全得多也更容易做分布式扩展。在做真机部署时这个模式可以直接套到 ROS 节点通信上每个机器人节点跑一个独立的 MCTS 求解器。3.3 收敛判定与覆盖率统计什么样的覆盖率才算扫完在描述“覆盖完成”之前我们先确定“覆盖率”的量化方法。一般用已覆盖格子数 / 空闲格子总数作为核心指标但不同的任务权重并不一样巡检任务会把漏扫率看得比重复覆盖率更重农业测绘则更关心重叠是否过高。你可以把统计信息封装在CoverageTracker里让它实时计算总体覆盖率和重复扫描比例。class CoverageTracker: def __init__(self, grid: GridMap): self.total_free int(np.sum(grid.grid 0)) self.revisit_count 0 def update(self, grid: GridMap): currently_visited int(np.sum(grid.grid 2)) coverage_ratio currently_visited / self.total_free return coverage_ratio def compute_revisit_ratio(self, grid: GridMap, visited_once_mask: np.ndarray): revisit_mask (grid.grid 2) visited_once_mask return int(np.sum(revisit_mask)) / self.total_free if self.total_free 0 else 0这里的逻辑说明update就是算一个简单的比例而compute_revisit_ratio则需要你额外传入一张visited_once_mask表示每个格子是否只被访问过一次。如果重复覆盖率太高说明 MCTS 的奖励设计偏向“原地徘徊”了需要调大路径不重复的惩罚项。4. 把覆盖结果可视化出来Matplotlib 热力图、路径轨迹与动态刷新4.1 生成静态覆盖热力图把二维数组变成一眼能看懂的颜色拿到 grid 里 0、1、2 的二维数组后我用 Matplotlib 的imshow和cmap做一步转换。具体做法是把 grid 涂成一幅 RGB 彩色图障碍物用黑灰色未访问区域用浅蓝色已访问区域用绿色。这样可以非常直观地看到覆盖效果有没有漏扫、有没有过度重复扫一目了然。import matplotlib.pyplot as plt import matplotlib.patches as mpatches def draw_coverage(grid: GridMap, robots): fig, ax plt.subplots(figsize(10, 10)) # 将整数网格映射为 RGB 颜色 display np.zeros((grid.height, grid.width, 3)) for y in range(grid.height): for x in range(grid.width): if grid.grid[y, x] 1: display[y, x] [0.1, 0.1, 0.1] # 障碍 elif grid.grid[y, x] 2: display[y, x] [0.2, 0.6, 0.2] # 已覆盖 else: display[y, x] [0.2, 0.6, 0.9] # 空闲 ax.imshow(display, originlower) # 画机器人当前位置 for i, (x, y) in enumerate(robots): ax.plot(x, y, r*, markersize15) # 绘制图例 legend_patches [ mpatches.Patch(color#1a1a1a, labelObstacle), mpatches.Patch(color#33aa33, labelVisited), mpatches.Patch(color#3399e6, labelFree), mpatches.Patch(colorred, labelRobot) ] ax.legend(handleslegend_patches, locupper right) ax.set_title(Multi-Robot Coverage Path Planning with MCTS) return fig, ax逻辑说明这段代码本质是数据可视化里的“伪彩色映射”只不过我手动为每个格子指定了 RGB 颜色。这样做的好处是你可以任意定义颜色的含义比如把“重复覆盖率超过 3 次的格子”标记为黄色从而快速暴露过度重复覆盖的区域。originlower指的是让地图的 y 轴从下往上增长更符合笛卡尔坐标系直觉。参数说明markersize控制机器人星标大小一般在巡检图上用 15 到 20 就足够醒目。如果你要出论文图可以用fig.savefig(coverage.png, dpi300)保存高分辨率图。4.2 动态过程可视化与 GIF 导出一张图看清 MCTS 搜索路径推进过程只看最终覆盖热力图你很难判断 MCTS 在中间步骤是否走进了死胡同。因此我一般保留每轮模拟后的地图状态每隔 10 个迭代步保存一帧图像最后用 Pillow 合成为 GIF或者直接在笔记本里用FuncAnimation播放。from PIL import Image import io def export_progress_gif(grid: GridMap, robots, frames): images [] for frame in frames: fig, ax draw_coverage(frame[grid], frame[robots]) buf io.BytesIO() fig.savefig(buf, formatpng) buf.seek(0) images.append(Image.open(buf).copy()) plt.close(fig) images[0].save(mcts_coverage_progress.gif, save_allTrue, append_imagesimages[1:], duration200, loop0)逻辑说明动态可视化对调试帮助很大因为一旦发现某个阶段所有机器人都挤在一个角落里你马上就能知道是模拟策略设置出了问题。duration200表示每帧显示 200 毫秒播放效果柔和。如果某些帧出现空白多半是画布或者缓冲没有正确关闭记得在保存完图像后调用plt.close(fig)释放内存。5. 多机器人区域覆盖里蒙特卡洛树搜索的 5 个常见翻车点现象、原因与解决5.1 现象模拟几十轮覆盖率就是上不去机器人总在障碍物边缘打转原因模拟策略太随机完全没有考虑未访问区域的分布。MCTS 的模拟阶段如果只是纯随机游走那它把大量采样时间浪费在已经覆盖过的区域和障碍物墙上。解决把模拟阶段的纯随机采样改为“偏向未访问邻居”的加权采样。具体可以统计机器人当前位置上下左右四个邻格里有多少个未访问格然后给这些方向更高的被选中概率。我刚才代码里的random.shuffle是最低成本的实现进阶可以改成按权重采样。def weighted_choice(self, pos): candidates [] weights [] for dx, dy in self.directions: nx, ny pos[0] dx, pos[1] dy if self.grid.is_free(nx, ny): candidates.append((dx, dy)) # 简单启发式未访问过 相对开放区域加分 weight 1.0 if (nx, ny) not in self.visited_points: weight 5.0 weights.append(weight) if not candidates: return (0, 0) return random.choices(candidates, weightsweights)[0]5.2 现象多机器人相互拥挤、团队串行化明明可以并行覆盖却变成排队扫原因这几乎都是因为模拟阶段没有做机器人之间的空间约束惩罚。如果两台机器人靠得太近它们的下一步动作空间会严重重叠导致总体覆盖率上升变慢。解决在simulate的每一步回报里加入稀疏性奖励。计算两两机器人之间的欧氏距离如果小于设定阈值比如 5 个格子就在回报上扣 0.2 分。这样做会让 MCTS 主动学习保持间距。5.3 现象UCB 公式中的平衡参数非常难调不是太小就是太大原因math.log和visits之间的量纲导致惩罚项和奖励项不在一个数量级。奖励如果是覆盖率也就是 0 到 1 之间那么 UCB 的探讨项经常会占到 0.2 以上能够被搜索发现但如果奖励是“绝对覆盖格子数”exploit 是几千explore 如果还用 1 开头搜索就纯粹走向了利用。解决把所有回报都归一化到 0 到 1 的连续区间并把c_p初始按sqrt(2) * 最大回报估算最大回报是 1那么c_p先设 1.414然后观察覆盖率曲线若长时间不变则调大到 10。5.4 现象地图里存在较长走廊或凹型障碍时MCTS 规划路线不完整有漏扫原因MCTS 本身并不理解区域单元分解它看不到“这个长走廊必须从一头走到另一头才能不漏”。在没有强先验的情况下树搜索很容易在走廊出口附近反复徘徊无法下定决心冲出去。解决在地图预处理阶段先把栅格地图做连通域分解。每个连通区域单独跑一遍 MCTS区域之间的转移顺序再用一个简单的旅行商问题模型来规划。这样能大幅减少搜索空间也顺带解决了漏扫问题。5.5 现象内存爆炸Python 进程跑一会儿就被 OOM kill 掉原因有些方案把每个状态都完整深拷贝到节点里。假如你的地图是 200x200一棵树存 5 万个节点就要存 20 亿个格子不炸才怪。解决节点只保存增量动作和父节点引用回溯时再重建状态。或者直接按时序滚动更新每迭代 100 次就释放掉数据结构里不再使用的深分支节点可以有效控制内存增长。6. 参数调优与工程化落地从验证算法到技术改造的最后一公里如果你想让这套方案跑在真机系统里我的建议是先把 MCTS 的回报函数拆成三层覆盖率、平均移动距离、重叠率。覆盖率解决“是否扫全”平均移动距离解决“是否高效”重叠率解决“是否做了无用功”。只有权重分配合理树搜索才能规划出既省时又不漏扫的路线。另外一个容易忽略的坑是覆盖率指标不能只看最终结果要看覆盖率收敛曲线。我踩过最大的坑就是为了让最终覆盖率达到 98%把simulate_steps拉到几千结果每次模拟都要两秒钟MCTS 的迭代次数反而变少整体规划时间反而更长。后来我改用早停机制当覆盖率在 50 轮迭代内提升不超过 0.5% 时就强制结束搜索接受当前的覆盖率结果。这样可以有效避免后期无用搜索耗能。在真机部署时你不需要真的在每个机器人上跑 Python 脚本常见的做法是把这个算法跑在 IPC 工控机里通过 ROS 的move_base接口把 MCTS 给出来的路径点发送给底盘。如果追求更实时也可以把地图分辨率降低到 0.5 米每格这样单次规划时间能压到 200 毫秒以内。我自己的习惯是先跑一个小地图快速观察覆盖率曲线的上升斜率斜率变平就调大c_p或者更换模拟策略的权重。这套逻辑我用了很长时间稳定度相当不错。希望帮到你。本文还有配套的精品资源点击获取
