Multi-Agent Coverage Path Planning using a Swarm of Unmanned Aerial Vehicles

In recent years, rapid technological advancements in unmanned aerial vehicles (UAVs) have propelled their applications to a wide range of areas such as agriculture, mapping & surveying, surveillance, and many more. A swarm of UAVs can efficiently accomplish the goals rather than a single UAV due to its ability to cover a larger area. Multi-agent coverage path planning (CPP) is the process of determining efficient coverage paths for the swarm of UAVs to completely cover an area of interest. A cellular grid is formed using hexagonal decomposition to ensure complete coverage, with the centroid of each cell acting as a waypoint. The k-means clustering algorithm is implemented to divide the set of waypoints such that the workload is uniformly distributed among the UAVs. Multi-agent CPP is transformed into multiple single-agent CPP, thereby alleviating the exploratory complexity of multi-agent CPP. A mixed-integer linear programming based vehicle routing problem is formed to optimize the path of each UAV considering various constraints.