skip to main content

Title: Heuristic Algorithms for Co-scheduling of Edge Analytics and Routes for UAV Fleet Missions
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.  more » « less
Award ID(s):
Author(s) / Creator(s):
Date Published:
Journal Name:
IEEE International Conference on Computer Communications (INFOCOM)
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. The use of unmanned aerial vehicles (UAVs) or drones, has significantly increased over the past few years. There is a growing demand in the drone industry, creating new workforce opportunities such as package delivery, search and rescue, real estate, transportation, agriculture, infrastructure inspection, and many others, signifying the importance of effective and efficient control techniques. We propose a scheme for controlling a drone through gaze extracted from eye-trackers, enabling an operator to navigate through a series of waypoints. Then we demonstrate and test the utility of our approach through a pilot study against traditional controls. Our results indicate gaze as a promising control technique for navigating drones revealing novel research avenues. 
    more » « less
  2. null (Ed.)
    The use of semi-autonomous Unmanned Aerial Vehicles (UAVs or drones) to support emergency response scenarios, such as fire surveillance and search-and-rescue, has the potential for huge societal benefits. Onboard sensors and artificial intelligence (AI) allow these UAVs to operate autonomously in the environment. However, human intelligence and domain expertise are crucial in planning and guiding UAVs to accomplish the mission. Therefore, humans and multiple UAVs need to collaborate as a team to conduct a time-critical mission successfully. We propose a meta-model to describe interactions among the human operators and the autonomous swarm of UAVs. The meta-model also provides a language to describe the roles of UAVs and humans and the autonomous decisions. We complement the meta-model with a template of requirements elicitation questions to derive models for specific missions. We also identify common scenarios where humans should collaborate with UAVs to augment the autonomy of the UAVs. We introduce the meta-model and the requirements elicitation process with examples drawn from a search-and-rescue mission in which multiple UAVs collaborate with humans to respond to the emergency. We then apply it to a second scenario in which UAVs support first responders in fighting a structural fire. Our results show that the meta-model and the template of questions support the modeling of the human-on-the-loop human interactions for these complex missions, suggesting that it is a useful tool for modeling the human-on-the-loop interactions for multi-UAVs missions. 
    more » « less
  3. Deep neural networks (DNNs) are being applied to various areas such as computer vision, autonomous vehicles, and healthcare, etc. However, DNNs are notorious for their high computational complexity and cannot be executed efficiently on resource constrained Internet of Things (IoT) devices. Various solutions have been proposed to handle the high computational complexity of DNNs. Offloading computing tasks of DNNs from IoT devices to cloud/edge servers is one of the most popular and promising solutions. While such remote DNN services provided by servers largely reduce computing tasks on IoT devices, it is challenging for IoT devices to inspect whether the quality of the service meets their service level objectives (SLO) or not. In this paper, we address this problem and propose a novel approach named QIS (quality inspection sampling) that can efficiently inspect the quality of the remote DNN services for IoT devices. To realize QIS, we design a new ID-generation method to generate data (IDs) that can identify the serving DNN models on edge servers. QIS inserts the IDs into the input data stream and implements sampling inspection on SLO violations. The experiment results show that the QIS approach can reliably inspect, with a nearly 100% success rate, the service qualtiy of remote DNN services when the SLA level is 99.9% or lower at the cost of only up to 0.5% overhead. 
    more » « less
  4. This paper presents a novel mission-oriented path planning algorithm for a team of Unmanned Aerial Vehicles (UAVs). In the proposed algorithm, each UAV takes autonomous decisions to find its flight path towards a designated mission area while avoiding collisions to stationary and mobile obstacles. The main distinction with similar algorithms is that the target destination for each UAV is not apriori fixed and the UAVs locate themselves such that they collectively cover a potentially time-varying mission area. One potential application for this algorithm is deploying a team of autonomous drones to collectively cover an evolving forest wildfire and provide virtual reality for firefighters. We formulated the algorithm based on Reinforcement Learning (RL) with a new method to accommodate continuous state space for adjacent locations. To consider a more realistic scenario, we assess the impact of localization errors on the performance of the proposed algorithm. Simulation results show that the success probability for this algorithm is about 80% when the observation error variance is as high as 100 (SNR:-6dB). 
    more » « less
  5. Autonomous systems, such as Unmanned Aerial Vehicles (UAVs), are expected to run complex reinforcement learning (RL) models to execute fully autonomous positionnavigation-time tasks within stringent onboard weight and power constraints. We observe that reducing onboard operating voltage can benefit the energy efficiency of both the computation and flight mission, however, it can also result in on-chip bit failures that are detrimental to mission safety and performance. To this end, we propose BERRY, a robust learning framework to improve bit error robustness and energy efficiency for RL-enabled autonomous systems. BERRY supports robust learning, both offline and on-board the UAV, and for the first time, demonstrates the practicality of robust low-voltage operation on UAVs that leads to high energy savings in both compute-level operation and systemlevel quality-of-flight. We perform extensive experiments on 72 autonomous navigation scenarios and demonstrate that BERRY generalizes well across environments, UAVs, autonomy policies, operating voltages and fault patterns, and consistently improves robustness, efficiency and mission performance, achieving up to 15.62% reduction in flight energy, 18.51% increase in the number of successful missions, and 3.43× processing energy reduction. 
    more » « less