Asymptotically-Optimal Multi-Query Path Planning for a Polygonal Robot
<|reference_start|>Asymptotically-Optimal Multi-Query Path Planning for a Polygonal Robot: Shortest-path roadmaps, also known as reduced visibility graphs, provides a highly efficient multi-query method for computing optimal paths in two-dimensional environments. Combined with Minkowski sum computations, shortest-path roadmaps can compute optimal paths for a translating robot in 2D. In this study, we explore the intuitive idea of stacking up a set of reduced visibility graphs at different orientations for a polygonal holonomic robot to support the fast computation of near-optimal paths, allowing simultaneous 2D translation and rotation. The resulting algorithm, rotation-stacked visibility graph (RVG), is shown to be resolution-complete and asymptotically optimal. Extensive computational experiments show RVG significantly outperforms state-of-the-art single- and multi-query sampling-based methods on both computation time and solution optimality fronts.<|reference_end|>
@article{zhang2024asymptotically-optimal,
    title={Asymptotically-Optimal Multi-Query Path Planning for a Polygonal Robot},
    author={Duo Zhang, Zihe Ye, Jingjin Yu},
    journal={arXiv preprint arXiv:2409.03920},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.03920},
    primaryClass={cs.RO}
}