Multi-UAV Cooperative Trajectory for Servicing Dynamic Demands and Charging Battery
Kai Wang, Xiao Zhang, Lingjie Duan, Jun Tie
Abstract
Unmanned Aerial Vehicle (UAV) technology is a promising solution for providing high-quality mobile services (e.g., edge computing and local caching) to ground users. How to dynamically determine a UAV swarm's cooperative path planning to best meet many users' spatio-temporally distributed demands is an important question but unaddressed in the literature. Regarding a single UAV's path planning design, we manage to substantially simplify the traditional dynamic program and propose an optimal algorithm of low computation complexity. After coordinating a large number K of UAVs, this simplified dynamic optimization problem becomes intractable and we alternatively present a fast iterative cooperation algorithm with provable approximation ratio <formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex>$1-(1-\frac{1}{K})^{K}$</tex></formula> in the worst case. To relax UAVs' battery capacity limit for sustainable service provisioning, we further allow UAVs to travel to charging stations in the mean time and thus jointly design UAVs' path planning over users' locations and charging stations. We successfully transform the problem to an integer linear program by creating novel directed acyclic graph of the UAV-state transition diagram, and propose an iterative algorithm with constant approximation ratio.