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

Buy & download fulltext article:

OR

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 PR 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: http://dx.doi.org/10.1163/156855307779293698

Publication date: 2007-01-01

Related content

Tools

Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content

Text size:

A | A | A | A
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages. print icon Print this page