Efficient Planning for Scalable and Load-Balanced Area Coverage by Multiple Unmanned Aerial Vehicles

Multi-robot systems offer a promising solution to efficient coverage of areas for search and rescue, environmental monitoring, material-spraying and exploration. This paper presents a scalable coverage partition-and-path planning (SCoPP) method that provides time-efficient coverage with workload balanced plans for each robot in the team. Non-convex coverage areas and no-fly zones within are also taken into consideration. SCoPP partitions the specified area into as many regions as the number of robots in the team, via area-discretization into cells, clustering of cells into partitions and load-balanced auctioning of cells that lie on the inter-partition boundaries. Subsequently it generates an ordered list of waypoints for each robot to visit using a nearest-neighbor path planning primitive. Two additional sub-routines modify this last step to allow user-prioritized locations to be visited earlier than other locations or prior to a specified deadline. Using multiple unmanned aerial vehicles (UAVs) to perform post-flood survey is considered as the example application to evaluate performance over different sized areas. SCoPP demonstrates superior performance compared to one baseline, and competitive trade-offs among mission completion efficiency, workload balancing and computing time, compared to another recent baseline. SCoPP and its prioritized sub-routines provide promising scalability with team size of up to 150 UAVs, while keeping computing times to within a few minutes. An outdoor experimental validation of SCoPP with a small team of three UAVs is also provided to demonstrate the deployment potential of SCoPP.