提出MeshA*算法，提升基于运动基元的路径规划效率
MeshA*: Efficient Path Planning With Motion Primitives
- 在网格上搜索同时匹配运动基元序列，降低搜索复杂度
- 相比传统方法运行时间缩短1.5至2倍，保持最优与完备性
- 适合需要高效路径规划的机器人导航场景
我们研究一种路径规划问题，其中可能的移动动作以一组与环境网格对齐的运动基元表示。每个基元对应代理的一段短时运动，表示为网格中扫过的单元序列。通常采用启发式搜索（如A*）在由这些基元生成的格网结构上进行路径搜索（基于格网的规划）。然而，由于分支因子大，实际应用中搜索效率较低。为此，我们提出一种新方法：在网格单元上进行搜索（如原始A*），同时将可能的运动基元序列拟合到这些单元中。由此产生的算法——MeshA*，在保证完整性和最优性的同时，显著优于传统的基于格网的规划方法，在运行时间上减少1.5至2倍。
原文摘要 · Abstract (English)
We study a path planning problem where the possible move actions are represented as a finite set of motion primitives aligned with the grid representation of the environment. That is, each primitive corresponds to a short kinodynamically-feasible motion of an agent and is represented as a sequence of the swept cells of a grid. Typically, heuristic search, i.e. A*, is conducted over the lattice induced by these primitives (lattice-based planning) to find a path. However, due to the large branching factor, such search may be inefficient in practice. To this end, we suggest a novel technique rooted in the idea of searching over the grid cells (as in vanilla A*) simultaneously fitting the possible sequences of the motion primitives into these cells. The resultant algorithm, MeshA*, provably preserves the guarantees on completeness and optimality, on the one hand, and is shown to notably outperform conventional lattice-based planning (x1.5-x2 decrease in the runtime), on the other hand.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。