MeshA*: Efficient Path Planing With Motion Primitives

Авторы

Яковлев К. С.

Аннотация

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

Скачать статью (PDF) на сайте AAAI (англ.): https://ojs.aaai.org/index.php/AAAI/article/view/41004

Скачать препринт статьи (PDF) на arXiv.org (англ.): https://arxiv.org/abs/2412.10320

РИНЦ: 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