GRACE: A Unified 2D Multi-Robot Path Planning Simulator & Benchmark for Grid, Roadmap, And Continuous Environments

本文介绍了 GRACE，这是一个统一的二维多机器人路径规划模拟器与基准测试平台，它通过在网格、路线图和连续环境等多个抽象层级上实例化相同任务，实现了不同建模选择间的透明、可复现比较，从而推动了多机器人规划研究向实际应用的转化。

要点

这篇论文介绍了一个名为 GRACE 的新工具。你可以把它想象成多机器人领域的"万能翻译官"和"公平竞技场"。

为了让你更容易理解，我们可以把多机器人路径规划（让一群机器人互不碰撞地到达目的地）比作指挥一场大型交通演习。

1. 以前的困境：三个不同的“语言”

在 GRACE 出现之前，研究机器人路径规划的科学家们面临着“巴别塔”式的混乱：

• 网格派（Grid）：就像下国际象棋。世界被切分成一个个小方格，机器人只能像棋子一样，一步一格地走。
  • 优点：算得飞快，能指挥成千上万个棋子。
  • 缺点：太死板，不像真实世界。真实机器人是圆滚滚的，可以斜着走，不能像棋子那样“瞬移”。
• 路线图派（Roadmap）：就像看地铁线路图。机器人只能沿着画好的线走，但可以在任何位置停下。
  • 优点：比网格灵活一点。
  • 缺点：还是不够真实，忽略了机器人的大小和转弯半径。
• 连续派（Continuous/MRMP）：就像真实的赛车比赛。机器人可以在任何地方、以任何角度、以任意速度移动，还要考虑刹车和加速。
  • 优点：最真实，最接近现实。
  • 缺点：计算量巨大，稍微多几个机器人，电脑就卡死了。

问题在于：以前，如果你想比较“下棋派”和“赛车派”谁更好，你没法直接比。因为规则不同、地图不同、甚至机器人的大小定义都不同。这就像拿“象棋冠军”和“F1 赛车手”比谁跑得快，根本不公平。

2. GRACE 的解决方案：一个“万能转换器”

GRACE 就像是一个超级翻译器和统一裁判。它的核心功能是：同一个任务，三种画法，公平比赛。

• 同一个场景，三种视角：
  想象你在指挥一群机器人穿过一个仓库。

  • 在 GRACE 里，你可以把仓库变成网格图（像像素画），让机器人按格子走。
  • 也可以把它变成路线图（像地铁图），让机器人沿线走。
  • 还可以把它变成真实世界（像高清游戏），让机器人自由穿梭。
  • 关键点：GRACE 确保这三种画法背后的“任务”是完全一样的（起点、终点、障碍物位置都没变）。

• 公平的裁判：
  以前，不同算法用的计时器和评分标准都不一样。GRACE 制定了一套统一的评分规则。

  • 它问：谁跑得最快？（完成时间）
  • 谁走的弯路最少？（总路程）
  • 谁算得最快？（规划时间）
    不管你是用“下棋法”还是“赛车法”，GRACE 都用同一把尺子量，让你能直接看出谁在什么情况下更厉害。

3. 实验发现了什么？（有趣的发现）

作者用 GRACE 做了一场大实验，发现了一些非常有意思的规律，就像发现了不同交通工具的适用场景：

• 路线图（Roadmap）是“黄金平衡点”：
  如果你想要既快又准，路线图是最佳选择。它比真实的赛车（连续派）算得快得多（快几十倍），但走的路只比真实赛车多一点点（大约多 10%）。

  • 比喻：就像你平时开车，看导航地图（路线图）比拿着指南针在荒野里乱撞（连续计算）要高效得多，而且不会迷路太多。

• 网格（Grid）是“速度狂魔”：
  如果你需要指挥成千上万个机器人（比如几千个扫地机器人），网格法是唯一的选择。它算得极快，虽然走的路稍微远一点，但在大规模场景下，它是唯一能跑起来的方案。

  • 比喻：就像指挥蚁群，你不能跟每只蚂蚁商量怎么转弯，只能给它们定下简单的“上下左右”规则，这样效率最高。

• 真实世界（Continuous）是“精密手术”：
  只有当机器人动作非常复杂、空间非常狭窄，或者对安全性要求极高时，才需要用到最复杂的“赛车模式”。

4. 为什么这很重要？

GRACE 的出现，让机器人研究从“关起门来各自为战”变成了“公开透明的竞技场”。

• 以前：A 团队说我的算法好，因为它在网格上跑得快；B 团队说我的好，因为我在真实模拟里没撞车。大家没法比。
• 现在：有了 GRACE，我们可以把 A 和 B 放在同一个任务里，用三种不同的视角去测试。我们能清楚地看到：在什么情况下，简单的规则就够了？在什么情况下，必须用复杂的模型？

总结

GRACE 就是一个多机器人路径规划的“通用实验室”。它把复杂的数学模型变成了大家都能看懂的“翻译”，帮助科学家们搞清楚：什么时候该用“傻瓜式”的简单规则，什么时候该用“高智商”的复杂计算。

这不仅让学术研究更透明、更公平，也让未来的机器人（比如仓库里的物流车、马路上的自动驾驶车队）能更聪明、更高效地工作。

技术摘要

1. 研究背景与问题 (Problem)

核心挑战：
多智能体路径规划（MAPF）和多机器人运动规划（MRMP）的研究领域目前存在严重的碎片化问题。

• 离散化方法（如网格 MAPF）： 擅长大规模扩展和算法基准测试，但通常假设同质智能体、离散时间和忽略动力学约束，导致难以直接应用于真实机器人。
• 连续化方法（如 MRMP）： 能够处理连续时空、运动学/动力学约束及异质机器人，提供高保真度，但计算成本高，且难以在不同抽象层级之间进行公平、可复现的比较。

现有工具的局限性：
现有的模拟器要么在简化假设下可扩展性很好（如网格），要么保真度高但缺乏跨表示（Cross-representation）的可比性。研究者难以回答以下关键问题：

• 何时使用路图（Roadmap）抽象就足够了？
• 路图或连续模型在什么情况下会实质性改变结论？
• 如何在相同任务和指标下，公平地比较 MAPF 和 MRMP？

2. 方法论 (Methodology)

为了解决上述问题，作者提出了 GRACE，一个统一的 2D 仿真与基准测试平台。

A. 统一的问题建模

GRACE 定义了一个基础世界模型，并通过显式的、可复现的抽象算子将其映射到三种不同的表示层级：

1. 连续空间 (Continuous, $\rho_{cont}$)： 保持原始环境（多边形障碍物）和智能体（任意凸多边形足迹、异质运动模型，如双积分器）。
2. 路图 (Roadmap, $\rho_{road}$)： 从自由空间提取有向图。智能体被抽象为具有停止 - 启动特性的单积分器（Single-integrator），具有统一的有效半径。
3. 网格 (Grid, $\rho_{grid}$)： 将环境离散化为 $M$-连接的占用网格。智能体被抽象为同质圆盘，动作定义为离散时间步的移动。

关键机制：

• 双向转换： 平台支持从连续到路图/网格，以及从路图/网格回连续空间的转换，确保任务实例在不同层级间的一致性。
• 统一评估协议： 无论使用何种表示，都使用相同的指标（成功率、总成本 SoC、最大完工时间 Makespan、规划时间）进行评估。
• 确定性仿真核心： 基于 Box2D (C++20) 构建，支持 60Hz 的确定性连续时间仿真，确保在相同种子和参数下，状态轨迹是位级（bitwise）一致的。

B. 架构设计

• 核心层： 负责物理仿真、碰撞检测（基于 AABB 树和接触流形）和轨迹执行。
• 规划器接口： 统一的接口连接各类规划器（经典搜索、学习-based、混合方法），支持共享库或子进程运行。
• 用户界面： 提供交互式编辑（环境、智能体、规划器参数）和可视化（热力图、时间线、占用层）。

3. 主要贡献 (Key Contributions)

1. 统一的仿真与基准平台 (GRACE)：
   • 首次在一个 API 和评估协议下，系统性地支持网格、路图和连续环境模型。
   • 定义了明确的抽象算子和跨表示转换机制，消除了手动重新编写任务的需求，确保了实验的可复现性。
2. 实证研究与权衡分析：
   • 利用 GRACE 在共享实例集上比较了不同表示层级。
   • 在网格上对主流规划器家族进行了基准测试。
   • 量化了表示 - 保真度权衡（Representation-Fidelity Trade-offs）：MRMP 提供高保真但速度慢；网格/路图规划器扩展性更强但精度较低。
3. 大规模可扩展性验证：
   • 展示了在 modest 硬件上支持约 2000 个智能体的仿真能力，并提供了详细的资源消耗数据（CPU、内存）。

4. 实验结果 (Results)

A. 跨环境模型基准测试 (Cross-Environment Benchmarking)

• 路图 (Roadmap) 的表现： 在大多数任务中，路图抽象是“足够好”的。其总成本（SoC）仅比连续 MRMP 高约 8-18%，但最大完工时间（Makespan）缩短了约 40-50%，规划时间更是减少了 98% 以上（相比连续方法）。
• 网格 (Grid) 的表现： 网格规划速度极快（规划时间仅为连续方法的 2.4% 左右），但代价是 SoC 显著增加（约 123%）。
• 密度影响： 路图的密度是一个可控的“速度 - 质量”旋钮。超密集路图可以进一步逼近连续空间的结果，同时保持规划速度。

B. 网格规划器基准测试 (Cross-MAPF-Planner Benchmarking)

• 在标准网格地图上测试了 6 种规划器（包括 CBSH2-RTC, EECBS, LaCAM, 学习-based 方法等）。
• LaCAM 在所有测试地图和智能体数量下均达到了 100% 的成功率，表现出极强的鲁棒性。
• EECBS 在低中规模下表现优异，但在高密度下性能下降较快。
• 学习/混合方法 在特定地图上表现良好，但跨地图方差较大。
• 结果验证了 GRACE 作为可复现的网格基准测试平台的兼容性。

C. 可扩展性与资源使用

• 实时性 (RTF)： 在仓库地图（540m x 140m）上，使用 LaCAM 规划，GRACE 在 2500 个智能体 时仍能维持实时仿真（RTF $\ge$ 1）。
• 内存效率： 峰值内存随智能体数量线性增长，斜率约为 0.179 MB/智能体，表明其具有极低的单智能体开销。
• 确定性： 仿真结果在相同设置下完全可复现，便于调试和对比。

5. 意义与影响 (Significance)

• 弥合理论与现实的鸿沟： GRACE 提供了一个桥梁，使研究者能够在一个框架内评估从高度抽象（网格）到高保真（连续动力学）的不同规划策略，帮助判断何时简化是合理的，何时必须考虑动力学。
• 促进公平比较： 通过统一的实例定义、预算限制和评估指标，消除了以往研究中因环境设置不同而导致的不可比性。
• 推动多机器人系统落地： 通过量化不同抽象层级的性能边界，为实际部署中的算法选择提供了数据支持（例如：在需要快速响应的场景下，路图可能是最佳平衡点）。
• 开源与社区贡献： 代码已开源，支持多种主流规划器，为未来的多机器人规划研究提供了标准化的测试床。

局限性：
目前仅限于 2D 静态环境、固定凸几何形状，且路图/网格层面对智能体进行了抽象。未来的工作将探索不确定性、动态变化环境、终身规划以及与 ROS 2 和车队管理系统的集成。