# MeshA*: Efficient Path Planning With Motion Primitives

arXiv: https://arxiv.org/abs/2412.10320 · HTML: https://mlsanity.com/paper/2412.10320/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 17 references that are in the map.
- First posted on arXiv 13 Dec 2024.

## Builds on (most cited first, 3 of 3)

- [Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic](https://mlsanity.com/paper/1404.2334/) (2014)
- [Sampling-based optimal kinodynamic planning with motion primitives](https://mlsanity.com/paper/1809.02399/) (2018)
- [Learning a Lattice Planner Control Set for Autonomous Vehicles](https://mlsanity.com/paper/1903.02044/) (2019)

## Abstract (arXiv)

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.