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)

Buy & download fulltext article:

Price: $35.00 plus tax (Refund Policy)

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 C_i of covering a part using UAV_i 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: http://dx.doi.org/10.1163/156855307779293698

Publication date: 2007-01-01