Towards real time scheduling for persistent UAV service: A rolling horizon MILP approach, RHTA and the STAH heuristic

摘要

The automation of logistics tasks for fleets of UAVs is a key element of persistent operation. Such automation includes the provision of robotic service stations to replace consumables and orchestration algorithms enabling the UAVs to simultaneously pursue their objectives and manage the logistics process. Here we consider a system of UAVs and service stations distributed across a field of operations whose purpose is to provide continuous escort/surveillance to customers traversing known time-space trajectories. Our goal is to develop centralized real-time large scale-system orchestration methods for such a service. This goal is pursued in three directions. 1)We extend an existing mixed integer linear program (MILP) formulation to allow for arbitrary UAV initial locations and fuel levels. The MILP uses a more general service station recharge model. The new MILP is incorporated into a rolling horizon optimization for real time use. 2) We extend an RHTA heuristic to allow for arbitrary fuel levels and UAV locations. 3) Based on insight from the problem formulation, the STAH heuristic is developed. Numerical studies assess the effectiveness and numerical character of the proposed approaches. STAH was at least 30 times faster than RHTA with similar values. Both are much faster than the MILP solved via CPLEX. A real time scheduling example is considered.