This repository contains the official implementation of MeshA*, a kinodynamic path planning algorithm presented at the AAAI Conference on Artificial Intelligence (2026).
MeshA* solves path planning problems with differential constraints using a finite set of motion primitives. Unlike conventional Lattice-Based A* (LBA*), which searches directly over the state lattice, MeshA* operates on Extended Cells. This abstraction allows the algorithm to perform early pruning of unpromising trajectory bundles while guaranteeing both completeness and solution optimality. Empirically, MeshA* reduces runtime by 1.5–2x compared to state-of-the-art baselines in cluttered environments.
The following animations demonstrate the qualitative difference in state-space exploration between the baseline and the proposed method.
- LBA* (Left): Exhibits a high branching factor, generating full bundles of primitives at every expanded state.
- MeshA* (Right): Propagates as a wavefront across grid cells. Primitive bundles are only generated at specific "Pivot" states (Initial Extended Cells), allowing for significant pruning of the search space.
| Lattice-Based A* (Baseline) | MeshA* (Proposed) |
 |
 |
|
Visualization of the search frontier on a cluttered map. (Animations generated using the visualization tools provided in this repository). |
|
...
If you use this code or ideas in your research, please cite our AAAI paper:
@misc{agranovskiy2025meshaefficientpathplanning,
title={MeshA*: Efficient Path Planning With Motion Primitives},
author={Marat Agranovskiy and Konstantin Yakovlev},
year={2025},
eprint={2412.10320},
archivePrefix={arXiv},
primaryClass={cs.RO},
url={https://arxiv.org/abs/2412.10320},
}