Leveraging Fixed-Parameter Tractability for Robot Inspection Planning
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912032858570752 |
|---|---|
| author | Mizutani, Yosuke Salomao, Daniel Coimbra Crane, Alex Bentert, Matthias Drange, Pål Grønås Reidl, Felix Kuntz, Alan Sullivan, Blair D. |
| author_facet | Mizutani, Yosuke Salomao, Daniel Coimbra Crane, Alex Bentert, Matthias Drange, Pål Grønås Reidl, Felix Kuntz, Alan Sullivan, Blair D. |
| contents | Autonomous robotic inspection, where a robot moves through its environment and inspects points of interest, has applications in industrial settings, structural health monitoring, and medicine. Planning the paths for a robot to safely and efficiently perform such an inspection is an extremely difficult algorithmic challenge. In this work we consider an abstraction of the inspection planning problem which we term Graph Inspection. We give two exact algorithms for this problem, using dynamic programming and integer linear programming. We analyze the performance of these methods, and present multiple approaches to achieve scalability. We demonstrate significant improvement both in path weight and inspection coverage over a state-of-the-art approach on two robotics tasks in simulation, a bridge inspection task by a UAV and a surgical inspection task using a medical robot. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_00251 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Leveraging Fixed-Parameter Tractability for Robot Inspection Planning Mizutani, Yosuke Salomao, Daniel Coimbra Crane, Alex Bentert, Matthias Drange, Pål Grønås Reidl, Felix Kuntz, Alan Sullivan, Blair D. Robotics Data Structures and Algorithms Autonomous robotic inspection, where a robot moves through its environment and inspects points of interest, has applications in industrial settings, structural health monitoring, and medicine. Planning the paths for a robot to safely and efficiently perform such an inspection is an extremely difficult algorithmic challenge. In this work we consider an abstraction of the inspection planning problem which we term Graph Inspection. We give two exact algorithms for this problem, using dynamic programming and integer linear programming. We analyze the performance of these methods, and present multiple approaches to achieve scalability. We demonstrate significant improvement both in path weight and inspection coverage over a state-of-the-art approach on two robotics tasks in simulation, a bridge inspection task by a UAV and a surgical inspection task using a medical robot. |
| title | Leveraging Fixed-Parameter Tractability for Robot Inspection Planning |
| topic | Robotics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.00251 |