Scaling Motion Planning Infeasibility Proofs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917687488151552 |
|---|---|
| author | Li, Sihui Dantam, Neil T. |
| author_facet | Li, Sihui Dantam, Neil T. |
| contents | Achieving completeness in the motion planning problem demands substantial computation power, especially in high dimensions. Recent developments in parallel computing have rendered this more achievable. We introduce an embarrassingly parallel algorithm for constructing infeasibility proofs. Specifically, we design and implement a manifold triangulation algorithm on GPUs based on manifold tracing with Coxeter triangulation. To address the challenge of extensive memory usage within limited GPU memory resources during triangulation, we introduce batch triangulation as part of our design. The algorithm provides two orders of magnitude speed-up compared to the previous method for constructing infeasibility proofs. The resulting asymptotically complete motion planning algorithm effectively leverages the computational capabilities of both CPU and GPU architectures and maintains minimum data transfer between the two parts. We perform experiments on 5-DoF and 6-Dof manipulator scenes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_04795 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Scaling Motion Planning Infeasibility Proofs Li, Sihui Dantam, Neil T. Robotics Achieving completeness in the motion planning problem demands substantial computation power, especially in high dimensions. Recent developments in parallel computing have rendered this more achievable. We introduce an embarrassingly parallel algorithm for constructing infeasibility proofs. Specifically, we design and implement a manifold triangulation algorithm on GPUs based on manifold tracing with Coxeter triangulation. To address the challenge of extensive memory usage within limited GPU memory resources during triangulation, we introduce batch triangulation as part of our design. The algorithm provides two orders of magnitude speed-up compared to the previous method for constructing infeasibility proofs. The resulting asymptotically complete motion planning algorithm effectively leverages the computational capabilities of both CPU and GPU architectures and maintains minimum data transfer between the two parts. We perform experiments on 5-DoF and 6-Dof manipulator scenes. |
| title | Scaling Motion Planning Infeasibility Proofs |
| topic | Robotics |
| url | https://arxiv.org/abs/2406.04795 |