Heuristic algorithms for co-scheduling of edge analytics and routes for UAV fleet missions

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 waypoints and accomplish activities as part of their mission. 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 Mission Scheduling Problem (MSP) 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 utility from the activities while meeting activity deadlines as well as energy and computing constraints. We first prove that MSP is NP-hard and then optimally solve it by formulating a mixed integer linear programming (MILP) problem. Next, we design two efficient heuristic algorithms, jsc and vrc, that provide fast sub-optimal solutions. Evaluation of these three schedulers using real drone traces demonstrate utility-runtime trade-offs under diverse workloads.

Meeting Name

IEEE Annual Joint Conference: INFOCOM, IEEE Computer and Communications Societies (2021: May 10-13, Virtual)

Department(s)

Computer Science

Research Center/Lab(s)

Intelligent Systems Center

Comments

This work is supported by AWS Research Grant, Intelligent Systems Center at Missouri S&T, and NSF grants CCF-1725755 and SCC-1952045.

Keywords and Phrases

Drone; Edge Computing; Energy Constrained; Job Scheduling; Path Planning; UAV; Vehicle Routing; Video Analytics

International Standard Book Number (ISBN)

978-073811281-7

International Standard Serial Number (ISSN)

0743-166X

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2021 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

13 May 2021

Link to Full Text

Share

 
COinS