MeshA*: Efficient Path Planning with Motion Primitives
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (43) · 36785-36792
DOI: 10.1609/aaai.v40i43.41004 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Marat Agranovskiy und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref).
Abstract (Originalsprache)
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.
Zitieren
APA
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
Vancouver
Agranovskiy M, Yakovlev K. MeshA*: Efficient Path Planning with Motion Primitives. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(43):36785-36792. doi:10.1609/aaai.v40i43.41004
BibTeX
@article{Agranovskiy2026,
author = {Agranovskiy, Marat and Yakovlev, Konstantin},
title = {MeshA*: Efficient Path Planning with Motion Primitives},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {43},
pages = {36785--36792},
doi = {10.1609/aaai.v40i43.41004}
}
EUVIMED