Improved Algorithms for Co-Scheduling of Edge Analytics and Routes for UAV Fleet Missions
Aakash Khochare, Francesco Betti Sorbelli, Yogesh Simmhan, Sajal K. Das
Abstract
Unmanned Aerial Vehicles (UAVs) or drones are increasingly used for urban applications like traffic monitoring and construction surveys. Autonomous navigation allows drones to visit <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">waypoints</i> and accomplish <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">activities</i> as part of their <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">mission</i> . A common activity is to hover and observe a location using on-board cameras. Advances in Deep Neural Networks (DNNs) allow such videos to be analyzed for automated decision making. UAVs also host edge computing capability for on-board inferencing by such DNNs. To this end, for a fleet of drones, we propose a novel <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Mission Scheduling Problem ()</i> that co-schedules the flight routes to visit and record video at waypoints, and their subsequent on-board edge analytics. The proposed schedule maximizes the data capture and computing utilities from the activities while meeting the activity deadlines, and the energy and computing constraints. We first prove that is NP-hard and then optimally solve it by formulating a mixed integer linear programming (MILP) problem. Next, we design five time-efficient heuristic algorithms that provide sub-optimal but fast solutions that are empirically competitive with the optimal solution. Evaluation of these five schedulers using real drone traces demonstrate utility–runtime trade-offs under diverse workloads.