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.
DOI: 10.1609/aaai.v40i43.41004
Download the article (PDF) from the AAAI website: https://ojs.aaai.org/index.php/AAAI/article/view/41004
Download the article preprint (PDF) at arXiv.org: https://arxiv.org/abs/2412.10320
eLibrary: https://elibrary.ru/item.asp?id=91288197
ResearchGate: https://www.researchgate.net/publication/402663846_MeshA_Efficient_Path_Planning_with_Motion_Primitives
Agranovskiy M., Yakovlev K. (2026) MeshA*: Efficient Path Planning with Motion Primitives // Proceedings of the AAAI Conference on Artificial Intelligence, 40(43), 36785–36792. https://doi.org/10.1609/aaai.v40i43.41004