Asymptotically-Optimal Multi-Query Path Planning for a Polygonal Robot
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910894144880640 |
|---|---|
| author | Zhang, Duo Ye, Zihe Yu, Jingjin |
| author_facet | Zhang, Duo Ye, Zihe Yu, Jingjin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03920 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Asymptotically-Optimal Multi-Query Path Planning for a Polygonal Robot Zhang, Duo Ye, Zihe Yu, Jingjin Robotics 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. |
| title | Asymptotically-Optimal Multi-Query Path Planning for a Polygonal Robot |
| topic | Robotics |
| url | https://arxiv.org/abs/2409.03920 |