Cooperative Path Planning of a UAV Swarm to Meet Temporal-Spatial User Demands

摘要

Unmanned Aerial Vehicle (UAV) technology is a promising solution for providing high-quality mobile services (e.g., edge computing, fast Internet connection, and local caching) to ground users, where a UAV with limited service coverage travels among multiple geographical user locations (e.g., hotspots) for servicing demands locally. It is necessary for different UAVs to cooperate with each other for servicing many users, and how to determine their cooperative path planning to best meet many users' spatio-temporally distributed demands is an important question. This paper is the first to design and analyze cooperative path-planning algorithms of a UAV swarm for optimally servicing many spatial locations with dynamic user arrivals and waiting deadlines in the time horizon. For each UAV, it needs to decide whether to wait at the current location or chase a newly released demand in another location, under upper coordination with the other UAVs in the swarm. For each UAV's routing problem even without coordinating with the rest UAVs, it follows dynamic programming structure and is difficult to solve directly given many user demands. We manage to simplify and propose an optimal algorithm of fast computation time (only polynomial with respect to both the numbers of user locations and user demands) for returning the UAV's optimal path-planning. When a large number $ert Kert$ of UAVs are coordinating, the dynamic programming simplification becomes intractable. Alternatively, we present an iterative cooperation algorithm with approximation ratio $1-(1-rac{1}{ert Kert })^{ert Kert }$ in the worst case, which is proved to obviously outperform the traditional idea of partitioning UAVs to serve different user/location clusters separately. Finally, we conduct simulation experiments to show that our algorithm's average performance is close to the optimum.