ScaleMPA: Rethinking Scalable RRT* Acceleration With a Grid-Native Representation

📄 arXiv: 2609.24497v1 📥 PDF

作者: Zilong Wang, Yuzhou Chen, Xinyue He, Chen Zhang, Guanghui He

分类: cs.RO, cs.AR

发布日期: 2026-09-21

💡 一句话要点

提出ScaleMPA以解决高维环境中的实时运动规划问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 运动规划 RRT* 高维环境 并行计算 网格表示 实时系统 机器人导航 自动驾驶

📋 核心要点

  1. 核心问题：现有的RRT*加速方法在高维环境中存在超线性复杂性和结构依赖，限制了并行性。
  2. 方法要点：ScaleMPA通过网格原生表示和直接网格访问，优化了运动规划过程，提升了并行性。
  3. 实验或效果：ScaleMPA在28nm CMOS上实现，规划延迟达到毫秒级，速度提升4.7到44.4倍。

📝 摘要（中文）

实时运动规划在大规模和高维环境中仍然面临挑战。现有的RRT加速方法采用树中心的状态组织，虽然降低了每次查询的成本，但仍保留了超线性的端到端复杂性，并通过结构依赖限制了并行性。本文提出ScaleMPA，一种通过网格原生表示重新思考RRT的运动规划加速器。通过用直接的网格访问替代层次遍历，ScaleMPA减少了规划器的关键路径，并暴露了细粒度的并行性。为了在稀疏高维规划下使这一重构方案更具实用性，ScaleMPA进一步提出了多分辨率网格搜索引擎和哈希网格内存系统。该系统在28nm CMOS上实现，达到了毫秒级的规划延迟，并在速度上比现有的运动规划加速器提升了4.7到44.4倍。

🔬 方法详解

问题定义：本文旨在解决在大规模和高维环境中实时运动规划的效率问题。现有的RRT*加速方法由于树中心的状态组织，导致了超线性的复杂性和结构依赖，限制了并行处理能力。

核心思路：ScaleMPA的核心思路是采用网格原生表示，替代传统的层次遍历方法，通过直接的网格访问来减少规划器的关键路径，从而提高并行性和效率。

技术框架：ScaleMPA的整体架构包括多分辨率网格搜索引擎和哈希网格内存系统。多分辨率网格搜索引擎用于处理稀疏高维空间，而哈希网格内存系统则用于高效存储和访问规划数据。

关键创新：ScaleMPA的主要创新在于其网格原生表示和直接网格访问的设计，这与现有方法的树中心结构形成了本质区别，显著提高了并行性和计算效率。

关键设计：在设计中，ScaleMPA采用了多分辨率策略来适应不同的规划需求，并通过哈希表实现快速数据存取，确保了在高维空间中的高效性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

ScaleMPA在28nm CMOS实现了毫秒级的规划延迟，并在速度上相较于现有的运动规划加速器实现了4.7到44.4倍的提升，展示了其在高维环境中出色的性能和实用性。

🎯 应用场景

ScaleMPA的研究成果在机器人导航、自动驾驶、虚拟现实等领域具有广泛的应用潜力。其高效的运动规划能力能够支持复杂环境下的实时决策，提升系统的智能化水平和响应速度，具有重要的实际价值和未来影响。

📄 摘要（原文）

Real-time motion planning remains challenging in large and high-dimensional environments. Prior acceleration of RRT follows tree-centric state organization, which reduces per-query cost but preserves superlinear end-to-end complexity and limits parallelism through structural dependencies. This paper presents ScaleMPA, a motion-planning accelerator that rethinks RRT with a grid-native representation. By replacing hierarchical traversal with direct grid-based access, ScaleMPA reduces the planner critical path and exposes fine-grained parallelism. To make this reformulation practical under sparse high-dimensional planning, ScaleMPA further proposes a multi-resolution grid search engine and a hash-grid memory system. Implemented in 28 nm CMOS, ScaleMPA achieves millisecond-level planning latency and delivers 4.7$\times$--44.4$\times$ speedup over state-of-the-art motion-planning accelerators.