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. The authors consider the problem of maximally parallelizing the coverage of a contiguous rectilinear region represented by p is an element of R by dividing p amongst eta 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 eta parts such that the cost Ci of covering a part using UAV, is proportional to the relative rate at which the UAV can coverage. This problem, however, is NP-hard and they instead give a polynomial time algorithm for solving a closely related problem: divide p into eta 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. The authors prove that the algorithm runs in O(N log N + etaN) time. To the best of their knowledge, this is the first time that an algorithm for solving the constrained partitioning problem has been reported.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Rectilinear workspace partitioning for parallel coverage using multiple unmanned aerial vehicles


    Contributors:

    Published in:

    Advanced Robotics ; 21 , 1/2 ; 105-120


    Publication date :

    2007


    Size :

    16 Seiten, 9 Bilder, 18 Quellen




    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    English




    Barrier Coverage Using Unmanned Aerial Vehicles

    Kumar, Amit / Ghose, Debasish | TIBKAT | 2023


    Barrier Coverage using Unmanned Aerial Vehicles

    Kumar, Amit / Ghose, Debasish | AIAA | 2023


    Swarming of Unmanned Aerial Vehicles by Sharing Distributed Observations of Workspace

    Krizek, Martin / Horyna, Jiri / Saska, Martin | IEEE | 2022



    Imaging using multiple unmanned aerial vehicles

    MISHRA LALAN JEE / CORLETO MENA JOSE G | European Patent Office | 2018

    Free access