Rectilinear workspace partitioning for parallel coverage using multiple unmanned aerial vehicles
Authors: Agarwal, Amit; Hiot, Lim Meng; Joo, Er Meng; Nghia, Nguyen Trung
Source: Advanced Robotics, Volume 21, Numbers 1-2, 2007 , pp. 105-120(16)
Publisher: VSP, an imprint of Brill
Key:
- Free Content
- New Content
- Subscribed Content
- Free Trial Content
- Free Content
- New Content
- Subscribed Content
- Free Trial Content
Abstract:
Given a planar workpiece R, the objective of region coverage is to find an ordered list of waypoints and the geometry of paths between consecutive waypoints along which the centroid of a sensor footprint can be moved to efficiently trace a minimal superset of R. We consider the problem of maximally parallelizing the coverage of a contiguous rectilinear region represented by P ∈ R by dividing P amongst η unmanned aerial vehicles (UAVs). The rates at which the UAVs can perform region coverage may differ. The optimum solution to this problem comprises a decomposition of P into η parts such that the cost Ci of covering a part using UAVi is proportional to the relative rate at which the UAV can coverage. This problem, however, is NP-hard and we instead give a polynomial time algorithm for solving a closely related problem: divide P into η parts that are each rectilinear, contiguous and whose areas are in the ratio of relative capabilities of the UAVs. Following the division of P, each part is covered by the corresponding UAV. We prove that our algorithm runs in O(N log N + ηN) time. To the best of our knowledge, this is the first time that an algorithm for solving our constrained partitioning problem has been reported.Keywords: POLYGON PARTITIONING; URBAN AND AIRBASE RECONNAISSANCE; AERIAL ROBOTICS
Document Type: Research article
DOI: 10.1163/156855307779293698
Key:
- Free Content
- New Content
- Subscribed Content
- Free Trial Content
- Free Content
- New Content
- Subscribed Content
- Free Trial Content
Click here for Page Help