Publication

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.