想象一下你是一群小型电池驱动机器人集群的大脑。你的任务是派遣它们去一个充满障碍物的巨大仓库中寻找隐藏的宝藏。你必须为每台机器人决定三件事：抓取哪些宝藏、以什么顺序访问它们，以及如何绕过箱子而不发生碰撞。这是一个巨大的谜题，被称为“组合优化”。这就像是在解一个数独游戏，但数字一直在移动，网格也在不断变化。
通常，机器人使用标准的计算机大脑来解决这些谜题。但标准大脑非常“贪婪”；它们大量消耗电力，这对于依靠小型电池运行的机器人来说是个问题。最近，科学家们制造了一种新型的、超高效的微型计算机芯片，称为“伊辛机”（Ising machine）。不要把它想成是一个按部就班进行计算的计算器，而要把它看作一个物理系统，它会趋向于进入低能态，就像一个小球滚下山坡寻找最深的谷底一样。这些芯片速度极快，几乎不耗电，但它们也非常小，且对能容纳的谜题规模有严格的限制。现在的关键问题是：我们能否将这些复杂的机器人规划问题压缩进这些微小且挑剔的芯片中以节省能源，还是说它们实在太受限了？
这篇论文正是对此问题进行了探索。研究人员尝试使用一块真实的、紧凑的 CMOS 伊辛芯片（一个拥有 45 个微型开关的物理设备）来帮助规划多台机器人的路径。他们并没有试图将整个巨大的谜题一次性强加给芯片，因为那样芯片会因承受不住压力而“爆炸”。相反，他们发明了一种聪明的“流水线”方法，将大问题分解成能够适配芯片的小块碎片，在芯片上解决这些碎片，然后再将答案缝合在一起。
以下是他们的发现：
- 芯片是专家而非总经理： 该芯片非常擅长为问题的微小部分生成“候选方案”（可能的解），但它无法自行修复错误的解。主机器人计算机（“宿主”）仍然需要承担繁重的任务，即检查答案是否合理并将其整合在一起。
- 三个层面，三个不同的问题： 规划过程分为三个层面，每一层都遇到了芯片的不同瓶颈：
- 路径规划（寻找路径）： 如果每次只观察机器人周围一个 5x5 的微小区域，芯片可以很好地解决这个问题。通过向前滑动这个窗口，机器人就可以在整个地图中导航。这种方法比标准计算机方法节省了 37 倍的能量。
- 目标分配（谁获得什么）： 芯片非常擅长在机器人之间分配一组目标。这种方法是一个巨大的胜利，其能耗比标准方法低了 8,000 倍。
- 巡回构建（访问顺序）： 这是最棘手的部分。芯片内部的规则（其“系数范围”）过于微弱，无法处理确保机器人恰好访问每个目标一次且不重复所需的严苛数学逻辑。研究人员不得不使用计算机模拟该芯片来进行这一部分，虽然模拟结果显示出巨大的潜力，但目前还无法直接在物理硬件上运行。
- “多重映射”技巧： 由于芯片非常挑剔，研究人员并没有只尝试一种映射方式。他们同时尝试了四种不同的映射方式（就像尝试通过挤压、拉伸或旋转，把方榫头塞进圆孔里一样）。他们发现，没有哪一种单一的方式是始终最优的；使用混合方法使系统变得更加可靠。
最终，整个系统（“伊辛流水线”）生成的路径仅比最佳标准计算机方法差了 9%，但它实现的能耗降低了 130 倍。论文得出结论：虽然这些微型芯片目前还不能取代主机器人大脑，但它们非常适合作为特定小任务的“低功耗加速器”。如果你希望你的机器人电池寿命更长，你不需要一个更大的大脑，你只需要让一个微小且高效的辅助芯片来处理这个谜题中那些细小而棘手的环节。
技术摘要：用于多机器人多目标规划的伊辛加速技术
问题陈述
自主机器人系统（如仓库车队和搜救队）在面临复杂的组合规划挑战时，必须在严格的能量预算下运行。多机器人多目标（MRMT）规划问题涉及三个交织的任务：将目标分配给机器人（目标共享）、确定每个机器人的访问序列（路径构建）以及寻找避障路径（路径规划）。
虽然这些问题的经典求解器已经非常成熟，但它们依赖于通用处理器，这对于电池驱动的平台来说可能过于耗能。伊辛机（Ising machines）通过硬件动力学近似最小化二次二元目标，为低功耗替代方案提供了可能。然而，目前的紧凑型 CMOS 伊辛芯片面临显著约束：有限的自旋数（例如 45 个自旋）、狭窄的整数系数范围以及固定的硬件接口。目前尚不清楚这些约束是否会阻碍现实机器人工作负载的直接映射，或者一种硬件感知的分解策略是否能实现有效的加速。
方法论
本文提出了一种硬件感知伊辛映射流水线，该流水线不将伊辛芯片视为独立的规划器，而是将其视为经典规划循环中的低功耗候选生成加速器。主机处理器负责处理分解、验证、评分和全局拼接，而伊辛芯片则解决小型且分解后的子问题。
1. 工作负载特征分析
作者分析了 MRMT 的三个层级，以识别特定的硬件瓶颈：
- 路径规划： 直接表述（基于单元、基于边或基于时间扩展）即使对于中等规模的网格（例如 10×10 网格需要 100 多个变量）也会超过 45 个自旋的预算。
- 路径构建： 标准旅行商问题（TSP）表述需要 N2 个变量和强大的“独热”（one-hot）惩罚约束。虽然对于较小的 N，自旋数量可能符合要求，但所需的惩罚系数往往会超出 CMOS 芯片狭窄的整数范围，导致无效的排列。
- 目标共享： 多旅行商问题（mTSP）的表述规模为 O(RN2)，远超自旋预算。
2. 多映射流水线
为了克服硬件限制，该流水线采用了**组合策略（portfolio approach）**而非单一的确定性映射。它生成多个硬件兼容的逻辑问题变体，并根据原始目标函数选择最佳的有效候选方案。关键技术包括：
- 分解： 将全局问题分解为芯片大小的子问题（例如，用于路径规划的空间补丁、用于路径构建的集群、用于目标共享的递归拆分）。
- 自旋合并： 将过载的逻辑自旋复制到额外的物理自旋上，以重新分配巨大的耦合并降低系数幅度。
- 系数量化： 应用不同的规则（线性、截断、基于秩或平方根）将实值系数映射到芯片有限的整数范围内。
- 自旋预算分支： 通过冻结一部分变量，来枚举略大于自旋预算的子问题。
3. 特定层级的伊辛方法
- 补丁滑动路径规划： 将地图划分为小的 5×5 空间补丁。在补丁上使用自旋合并技术求解基于单元的 QUBO，以处理连通性惩罚。主机对局部目标进行排序，并将有效的局部路径拼接成全局路径。
- 集群路径构建： 将目标根据距离进行递归拆分为集群。对集群进行排序，并将每个集群作为局部开路径 TSP 进行求解。由于系数范围限制无法直接在芯片上执行，该层级使用逻辑伊辛求解器（Tabu 采样）进行评估，并采用相同的 45 个自旋约束来投影芯片性能。
- 递归目标共享： 使用距离加权图割（graph cuts）对机器人和目标进行递归划分。对拆分后的目标应用系数量化。主机固定锚点节点以引导拆分，并将“无机器人”包分配给边际成本增加最小的机器人。
核心贡献
- 硬件感知特征分析： 本文指出不同的规划层级对硬件限制的压力不同：路径规划和目标共享主要受限于自旋数，而路径构建由于排列约束主要受限于系数范围。
- 多映射流水线： 一种新颖的框架，通过分解问题为芯片规模的子问题，并评估多种映射组合（通过自旋合并、量化和分支），从而从有限的硬件中恢复有用的候选方案。
- 三种基于伊辛的规划方法：
- 带有自旋合并的补丁滑动路径规划。
- 带有自旋预算分支（通过逻辑评估）的集群路径构建。
- 带有系数量化和批处理的递归目标共享。
- 端到端评估： 在真实的 45 自旋全连接 CMOS 伊兴芯片上进行的实验性评估，证明了该流水线可以产生具有竞争力的路径，并显著降低能耗。
实验结果
实验在具有 20% 障碍物密度的 10×10 网格世界中进行，使用了 45 自旋 CMOS 伊辛芯片（8 个并行核心）和经典主机（Intel i7-12700）。
- 路径规划： 伊辛流水线解决了 996/1000 个实例，中值路径长度与经典基准（BFS、A*、GBFS）相匹配。它实现了 37 倍的能量降低（14 µJ vs. 523 µJ 对于 A*），代价是更高的延迟（1.6 ms vs. 35 µs）。
- 路径构建： 使用逻辑伊辛后端投影芯片性能，该方法实现了 0.0% 的中值最优性差距（匹配精确暴力法）和 1.63% 的平均差距，优于最近邻算法和 2-opt 算法。投影能量比 3-opt 低 770 倍。
- 目标共享： 递归伊辛方法实现了 29.0 的中值总路径成本，而最强的经典基准（顺序单项拍卖，SSA）为 28.0。它实现了 8,000 倍的能量降低（9 µJ vs. 73 mJ）。
- 端到端流水线： 完整的伊辛流水线生成的路径处于强经典基准（SSA + 3-opt + A）的 9% 范围内，同时消耗的能量*减少了 130 倍。主要的瓶颈是由于补丁滑动方法的顺序特性导致的路径规划延迟。
- 多映射有效性： 研究证实，没有任何单一的映射规则（自旋合并风格或量化方法）占据主导地位；评估多种映射组合显著提高了成功率和鲁棒性。
意义与主张
本文声称，只要围绕硬件约束设计系统，紧凑型 CMOS 伊辛机可以成为特定机器人规划栈的高效加速器。作者强调：
- 直接全局映射是不够的： 现实的规划问题超出了当前的自旋和系数限制。
- 候选生成 vs. 全局求解： 近期伊辛硬件最有效的角色是为局部组合子问题生成候选方案，而经典逻辑负责处理分解、验证和全局一致性。
- 硬件感知设计至关重要： 自旋数、系数范围和解码有效性不仅仅是实现细节，更是决定哪些规划层级可以卸载到硬件上的基本决定因素。
- 能量效率： 提出的流水线表明，可以实现显著的节能（在特定层级高达 8,000 倍），这使得伊辛加速对于能量受限的机器人平台极具吸引力，即使延迟仍然是一个权衡因素。
研究结论认为，随着 CMOS 伊辛芯片在自旋数和精度方面的规模扩大，所提出的流水线可以扩展到更大的补丁和更集成的规划系统，但目前的实用性依赖于一种混合的、硬件感知的架构。
每周获取最佳 computer science 论文。
受到斯坦福、剑桥和法国科学院研究人员的信赖。
请查收邮箱确认订阅。
出了点问题，再试一次？
无垃圾邮件，随时退订。