Compact Workspace Decomposition Based on a Bottom-Up Approach
In this paper, we present an algorithm that addresses the challenge of dividing a workspace among multiple UAVs. The workspace can be any convex or non-convex polygon and may contain holes of various shapes that represent no-fly zones. The UAVs can be heterogeneous, with different levels of autonomy...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10824800/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841550792082849792 |
|---|---|
| author | Georgy Skorobogatov Toni Calvo Cristina Barrado Esther Salami |
| author_facet | Georgy Skorobogatov Toni Calvo Cristina Barrado Esther Salami |
| author_sort | Georgy Skorobogatov |
| collection | DOAJ |
| description | In this paper, we present an algorithm that addresses the challenge of dividing a workspace among multiple UAVs. The workspace can be any convex or non-convex polygon and may contain holes of various shapes that represent no-fly zones. The UAVs can be heterogeneous, with different levels of autonomy, speed, and range. The goal of the workspace division is to obtain areas whose sizes are best matched to the capabilities of the UAVs while maximizing compactness. The algorithm decomposes the polygon representing the workspace into a triangular grid, followed by an iterative process of accumulating adjacent triangles while maximizing the compactness of the resulting regions. The performance of the algorithm and the quality of the partitions generated by the algorithm are compared to existing methods. Results show that this approach outperforms others in several metrics, achieving a 5% to 10% improvement in compactness, while maintaining reasonable performance, with a time overhead of up to approximately two seconds when splitting a polygon into ten parts. |
| format | Article |
| id | doaj-art-b017e7882b8244e38508ef7d3dbd311d |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-b017e7882b8244e38508ef7d3dbd311d2025-01-10T00:01:12ZengIEEEIEEE Access2169-35362025-01-01133917392810.1109/ACCESS.2025.352580010824800Compact Workspace Decomposition Based on a Bottom-Up ApproachGeorgy Skorobogatov0https://orcid.org/0000-0003-2536-1470Toni Calvo1https://orcid.org/0009-0003-1396-2831Cristina Barrado2https://orcid.org/0000-0003-0100-724XEsther Salami3https://orcid.org/0000-0002-4635-2963Computer Architecture Department, Technical University of Catalonia, Castelldefels, SpainComputer Architecture Department, Technical University of Catalonia, Castelldefels, SpainComputer Architecture Department, Technical University of Catalonia, Castelldefels, SpainComputer Architecture Department, Technical University of Catalonia, Castelldefels, SpainIn this paper, we present an algorithm that addresses the challenge of dividing a workspace among multiple UAVs. The workspace can be any convex or non-convex polygon and may contain holes of various shapes that represent no-fly zones. The UAVs can be heterogeneous, with different levels of autonomy, speed, and range. The goal of the workspace division is to obtain areas whose sizes are best matched to the capabilities of the UAVs while maximizing compactness. The algorithm decomposes the polygon representing the workspace into a triangular grid, followed by an iterative process of accumulating adjacent triangles while maximizing the compactness of the resulting regions. The performance of the algorithm and the quality of the partitions generated by the algorithm are compared to existing methods. Results show that this approach outperforms others in several metrics, achieving a 5% to 10% improvement in compactness, while maintaining reasonable performance, with a time overhead of up to approximately two seconds when splitting a polygon into ten parts.https://ieeexplore.ieee.org/document/10824800/UAVmulti-robot systemsworkspace divisionpolygon partition |
| spellingShingle | Georgy Skorobogatov Toni Calvo Cristina Barrado Esther Salami Compact Workspace Decomposition Based on a Bottom-Up Approach IEEE Access UAV multi-robot systems workspace division polygon partition |
| title | Compact Workspace Decomposition Based on a Bottom-Up Approach |
| title_full | Compact Workspace Decomposition Based on a Bottom-Up Approach |
| title_fullStr | Compact Workspace Decomposition Based on a Bottom-Up Approach |
| title_full_unstemmed | Compact Workspace Decomposition Based on a Bottom-Up Approach |
| title_short | Compact Workspace Decomposition Based on a Bottom-Up Approach |
| title_sort | compact workspace decomposition based on a bottom up approach |
| topic | UAV multi-robot systems workspace division polygon partition |
| url | https://ieeexplore.ieee.org/document/10824800/ |
| work_keys_str_mv | AT georgyskorobogatov compactworkspacedecompositionbasedonabottomupapproach AT tonicalvo compactworkspacedecompositionbasedonabottomupapproach AT cristinabarrado compactworkspacedecompositionbasedonabottomupapproach AT esthersalami compactworkspacedecompositionbasedonabottomupapproach |